10

我知道我可以散列奇异值作为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？

如果这样的散列是不可能的，我还能如何改进它的运行时间？我正在处理足够大的数据集，线性运行时间不够快。

编辑：为了回应奇恩的回答，我必须注意不能假设间隔是规则的。事实上，我几乎可以保证他们不是

为了回应评论中的请求，我应该提到我这样做是为了在遗传算法中实现基于适应度的选择。算法本身是做功课的，但具体实现只是为了提高生成实验数据的运行时间。

4

4 回答 4

12

正如其他人所指出的那样，您将获得的最佳算法是 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列表替换为较低阈值的列表，然后就可以了。

于 2012-01-28T06:21:16.133 回答
4

您不一定需要散列整个值范围。例如，在上面给出的比例中，如果给定 0.15，则可以将其四舍五入到 0.2（小数点后的第一个数字），然后散列 0.2。

这必须有多高效？您可以尝试的另一种方法是二进制搜索。将区间值按排序顺序存储在列表中，并对其进行二进制搜索。例如：

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

然后，您只需进行二进制搜索即可找到大于 x 的最小元素。这将产生 O(log(n))。

于 2012-01-28T05:43:41.937 回答
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, ...)
于 2012-01-28T05:34:52.097 回答
3

为了提高运行时间，您可以实现二分搜索。

否则，您可以将间隔阈值放在 trie 上。

编辑：让我提出一个实现：

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 方法涉及更多，我认为它更适合低级语言。

于 2012-01-28T05:48:17.977 回答