Каков наилучший способ хранения целых чисел, сопоставленных со строками, чтобы ключи могли быть диапазонами в python?

Question

Как лучше всего хранить (неизменяемые) данные в формате:

doodahs = {
0-256: "FOO",
257: "BAR",
258: "FISH",
279: "MOOSE",
280-65534: "Darth Vader",
65535: "Death to all newbies" }

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

О, и это на Python 2.4, поэтому, пожалуйста, дайте действительно хорошую причину для обновления, если вы хотите, чтобы я использовал более новую версию (и я пойду на 3:)

Answer 1

Я бы разделил диапазон на кортеж, а затем внутри вашего класса оставил бы элементы в упорядоченном списке. Вы можете использовать модуль bisect для создания вставок O (n) и поиска O (logn).

Если вы конвертируете дикт в ваш новый класс, вы можете создать неупорядоченный список и отсортировать его в конце

doodahs = [
    (0, 256, "FOO"),
    (257, 257, "BAR"),
    (258, 258, "FISH"),
    (279, 279, "MOOSE"),
    (280, 65534, "Darth Vader"),
    (65535, 65535, "Death to all newbies")]

Ваш __getitem__ может работать примерно так:

def __getitem__(self, key):
    return self.doodahs[bisect.bisect(self.doodahs, (key,))]

__setitem__ может выглядеть примерно так:

def __setitem__(self,range,value):
    bisect.insort(self.doodahs, range+(value,))

Answer 2

Если ваши целые числа имеют верхнюю границу меньше нескольких миллионов, вы просто расширяете диапазоны до отдельных значений.

class RangedDict( dict ):
    def addRange( self, iterator, value ):
        for k in iterator:
            self[k]= value

d= RangedDict()
d.addRange( xrange(0,257), "FOO" )
d[257]= "BAR"
d[258]= "FISH"
d[279]= "MOOSE"
d.addRange( xrange(280,65535), "Darth Vader" )
d[65535]= "Death to all newbies"

Все ваши поиски работают и мгновенно.

Answer 3

Учитывая, что у вас нет никаких «пробелов» в ваших ключах, почему вы просто не сохраняете начало каждого сегмента, а затем ищите с помощью пополам, как предложено?

doodahs = (
    (0, "FOO"),
    (257, "BAR"),
    (258, "FISH"),
    (279, "MOOSE"),
    (280, "Darth Vader"),
    (65535, "Death to all newbies")
)

Answer 4

class dict2(dict):
    def __init__(self,obj):
            dict.__init__(self,obj)
    def __getitem__(self,key):
            if self.has_key(key):
                    return super(dict2,self).__getitem__(key)
            else:
                    for k in self:
                            if '-' in k:
                                    [x,y] = str(k).split('-')
                                    if key in range(int(x),int(y)+1):
                                            return super(dict2,self).__getitem__(k)
                    return None


d = {"0-10":"HELLO"}
d2 = dict2(d)
print d,d2,d2["0-10"], d2[1]