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

Question

Я знаю, что я могу хэшировать единичные значения в качестве ключей в dict, Например, я могу хэш 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) времени выполнения и в конечном итоге не лучше, чем убить elifs (я должен был бы перебрать ключи и проверить, если key[0] <= x <= key[1]).

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

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

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

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

Answer 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 список с вашим списком нижних порогов, и там вы идете.

Answer 2

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

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

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

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

Answer 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, ...)

Answer 4

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

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

РЕДАКТИРОВАТЬ: позвольте мне предложить реализацию:

class IntervalHash():
    def __init__(self,SortedList):
        #check it's 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)

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