开发者

Find value within a range in lookup table

I have the simplest problem to implement, but so far I have not been able to get my head around a solution in Python.

I have built a table that looks similar to this one:

501 - ASIA
1262 - EUROPE
3389 - LATAM
5409 - US

I will test a certain value to see if it falls within these ranges, 389 -> ASIA, 1300 -> LATAM, 5400 -> US. A value greater than 5409 should not return a lookup value.

I normally have a one to one match, and would implement a dictionary for the lookup.

But in this case I have to consider these ranges, and I am not seeing my way out of the problem.

Maybe 开发者_运维问答without providing the whole solution, could you provide some comments that would help me look in the right direction?

It is very similar to a vlookup in a spreadsheet.

I would describe my Python knowledge as somewhere in between basic to intermediate.


You could use the bisect module. Instead of linear search, that would use binary search, which would hopefully be faster:

import bisect

places = [
    (501, 'ASIA'),
    (1262, 'EUROPE'),
    (3389, 'LATAM'),
    (5409, 'US'),
]
places.sort() # list must be sorted

for to_find in (389, 1300, 5400):
    pos = bisect.bisect_right(places, (to_find,))
    print '%s -> %s' % (to_find, places[pos])

Will print:

389 -> (501, 'ASIA')
1300 -> (3389, 'LATAM')
5400 -> (5409, 'US')


First make a sorted index:

index = sorted(table.iteritems())

Then, use bisect to find your key:

_, value = bisect.bisect_left(index, (key, ''))


places = [(501,"ASIA"),(1262,"EUROPE"),(3389,"LATAM"),(5409,"US")]
places.sort()

def getSection(places,requests):
    PL= len(places)
    LAST=places[-1][0]
    for R in requests:
        for P in range(PL):
            if not (R < 0 or R>LAST):#keep away integers out of range
                if R<=places[P][0]:
                    print R,"->",places[P][1]
                    break
            else:
                break

A call to getSection,

getSection(places,(5000000,389,1300,5400,-1,6000))

gives:

389 -> ASIA
1300 -> LATAM
5400 -> US


If you just have 5409 values I would just put each integer in the range in the dictionary and do normal lookups. Each entry takes 12bytes, the total is just 500Kb, so why bother.

Here is some neat code to do this:

places = [
    (501, 'ASIA'),
    (1262, 'EUROPE'),
    (3389, 'LATAM'),
    (5409, 'US'),
]

def make_zones( borders ):
    last = 0
    for n,v in borders:
        for i in range(last, n+1):
            yield i,v
        last = i+1

zones = dict(make_zones(places))

print zones[501], zones[502]
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜