Найти значение в пределах диапазона в таблице поиска

Question

У меня есть простейшая проблема для реализации, но до сих пор я не смог найти решение в Python.

Я построил таблицу, похожую на эту:

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

Я протестирую определенное значение, чтобы увидеть, попадает ли оно в эти диапазоны, 389 -> ASIA, 1300 -> LATAM, 5400 -> US. Значение больше 5409 не должно возвращать искомое значение.

У меня обычно есть совпадение один к одному, и я бы реализовал словарь для поиска.

Но в этом случае я должен рассмотреть эти диапазоны, и я не вижу выхода из проблемы.

Может быть, не предоставив полного решения, не могли бы вы дать некоторые комментарии, которые помогли бы мне смотреть в правильном направлении?

Это очень похоже на vlookup в электронной таблице.

Я бы описал мои знания Python как нечто среднее между базовым и промежуточным.

Answer 1

Вы можете использовать модуль bisect. Вместо линейного поиска будет использоваться бинарный поиск, который, будем надеяться, будет быстрее:

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])

Напечатает:

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

Answer 2

Сначала создайте отсортированный индекс:

index = sorted(table.iteritems())

Затем используйте bisect, чтобы найти свой ключ:

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

Answer 3

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

Вызов getSection

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

дает:

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

Answer 4

Если у вас просто 5409 значений, я бы просто поместил каждое целое число в диапазоне в словаре и сделал обычный поиск. Каждая запись занимает 12 байтов, общая сумма составляет всего 500Kb , так что зачем?

Вот некоторый аккуратный код для этого:

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]