Найдите значение в диапазоне в справочной таблице
У меня есть самая простая проблема для реализации, но до сих пор я не смог получить голову вокруг решения в Python.
Я создал таблицу, которая выглядит подобной этому:
501 - ASIA
1262 - EUROPE
3389 - LATAM
5409 - US
Я протестирую определенное значение, чтобы видеть, находится ли оно в пределах этих диапазонов, 389 -> ASIA, 1300 -> LATAM, 5400 -> US. Значение, больше, чем 5 409, не должно возвращать справочное значение.
Я обычно имею один к одному соответствию и реализовал бы словарь для поиска.
Но в этом случае я должен рассмотреть эти диапазоны, и я не вижу свой выход из проблемы.
Возможно, не предоставляя целое решение, Вы могли предоставить некоторые комментарии, которые помогли бы мне посмотреть в правильном направлении?
Это очень похоже на a vlookup в электронной таблице.
Я описал бы свое знание Python как где-нибудь промежуточный основной для посредничания.
3 ответа
Вы можете использовать модуль 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')
Сначала создайте отсортированный индекс:
index = sorted(table.iteritems())
Затем используйте биссектрису, чтобы найти свой ключ:
_, value = bisect.bisect_left(index, (key, ''))
Если у вас всего 5409 значений, я бы просто поместил каждое целое число из диапазона в словарь и произвел бы нормальный поиск. Каждая запись занимает 12 байт, всего всего 500 КБ , так что зачем беспокоиться.
Вот отличный код для этого:
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]