Хеши диапазон значений

Я знаю, что я могу использовать сингулярные значения как ключи в dict. Например, я могу hash 5 как один из ключей в dict.

В настоящее время я сталкиваюсь с проблемой, которая требует от меня хеширования диапазона значений.

В принципе, мне нужен более быстрый способ сделать это:

if 0 <= x <= 0.1:
    # f(A)
elif 0.1 <= x <= 0.2:
    # f(B)
elif 0.2 <= x <= 0.3:
    # f(C)
elif 0.3 <= x <= 0.4:
    # f(D)
elif 0.4 <= x <= 0.5:
    # f(E)
elif 0.5 <= x <= 0.6:
    # f(F)

где x - некоторый параметр float произвольной точности.

Самый быстрый способ, о котором я могу думать, это хеширование, но вот проблема: я могу использовать (0.1, 0.2) как ключ, но это все равно будет стоить мне время O (n) и в конечном итоге не лучше, чем множество elif (мне нужно будет перебирать ключи и проверять, есть ли key[0] <= x <= key[1]).

Есть ли способ хешировать диапазон значений, чтобы я мог проверить хеш-таблицу для 0.15 и все равно получить #execute B?

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

РЕДАКТИРОВАТЬ. В ответ на ответ на скуку я должен отметить, что интервалы нельзя считать регулярными. На самом деле, я могу почти гарантировать, что они не

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

Ответы

Ответ 1

Как отмечали другие, лучшим алгоритмом, который вы собираетесь получить для этого, является то, что O (log N), а не O (1), с чем-то по строкам поиска пополам через отсортированный список.

Самый простой способ сделать это в Python - это стандартный модуль bisect, http://docs.python.org/library/bisect.html. Обратите внимание, в частности, на пример в разделе 8.5.2, при выполнении операций с числовой таблицей - это именно то, что вы делаете:

>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']

Замените строку grades на список функций, список breakpoints с вашим списком нижних порогов, и там вы идете.

Ответ 2

Вам не обязательно хешировать весь диапазон значений. Например, в приведенной выше шкале, если вам дали 0,15, вы можете округлить ее до 0,2 (первая цифра после десятичной точки) и вместо этого вместо хэш 0,2.

Насколько эффективно это должно быть? Альтернативой, которую вы можете попробовать, является двоичный поиск. Сохраняйте значения интервалов в отсортированном порядке в списке и выполняйте на нем двоичный поиск. Например:

sorted_list = [ (0.1, function1), (0.2, function2), ....(0.6, function6) ]

Затем вы просто выполняете двоичный поиск, чтобы найти наименьший элемент, который больше, чем x. Это даст O (log (n)).

Ответ 3

Если ваши интервалы регулярны, вы можете масштабировать, а затем floor ваши операнды до минимума каждого диапазона, а затем передавать этот результат непосредственно в dict, сопоставляя эти нижние границы с соответствующим обработчиком.

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

# Integerize our 0.1 width intervals; scale by x10
handlerDict = {}
handlerDict[0] = lambda x: ... # 0.1
handlerDict[1] = lambda x: ... # 0.2
handlerDict[2] = lambda x: ... # 0.3
...

# Get the right handler, scaling x by x10; handle
handlerDict[int(10*x)](x, ...)

Ответ 4

Чтобы улучшить время выполнения, вы можете реализовать поиск по бисекции.

В противном случае вы можете поместить интервальные пороги в trie.

EDIT: позвольте мне предложить реализацию:

class IntervalHash():
    def __init__(self,SortedList):
        #check it sorted 
        self.MyList = []
        self.MyList.extend(SortedList) 
        self.lenlist = len(self.MyList)
    def get_interval(self,a):
        mylen = self.lenlist 
        mypos = 0
        while mylen > 1:
            mylen = (mylen/2 + mylen % 2)
            if mypos + mylen > self.lenlist - 1:
                if self.MyList[self.lenlist - 1] < a:
                    mypos = self.lenlist - 1
                break
            if self.MyList[mypos + mylen] < a:
                mypos += mylen
        if mypos == 0:
            if self.MyList[0] > a: 
                return ("-infty",self.MyList[0],0)
        if mypos == self.lenlist - 1:
            return (self.MyList[mypos],"infty",0)
        return (self.MyList[mypos],self.MyList[mypos+1],0)

A = [0.32,0.70,1.13]
MyHasher = IntervalHash(A)
print "Intervals are:",A
print 0.9 ," is in ",MyHasher.get_interval(0.9)
print 0.1 ," is in ",MyHasher.get_interval(0.1)
print 1.8 ," is in ",MyHasher.get_interval(1.8)

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