返回索引的元组/列表列表中的 Python 最快搜索

Question

我有一个列表/元组的元组/列表(我使用哪个无关紧要)，其中内部列表或元组的值具有可变大小。我需要检查变量是否在第一个插槽内部列表或元组中。

Structure looks like this:

[ [[list of x amount of ints],[same number of ints as first slot],[[y number of ints], [z number of ints], .... , [a number of ints]], ... repeated about 20x]

例子:

([1, 21, 54, 55, 93, 99, 284, 393, 964, 1029, 1214, 1216, 1223, 1253, 1258, 1334, 1365, 1394, 1397, 1453, 1471, 1543, 1589, 1824, 1975, 2054, 2090, 2164, 2165, 2166, 2167, 2323, 2547, 2645, 2802, 2809, 2931, 2958, 3031, 3071, 3077, 3078, 3189, 3199, 3202, 3203], [1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 2, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4, 2, 1, 1, 1, 1, 1, 2, 3, 1, 2, 1, 3, 3, 1, 2], [[3], [1], [4], [2], [12], [6], [3], [8], [20, 27], [11], [4, 7], [71], [133], [14, 74], [6], [67], [34], [3, 16], [9, 7, 23, 71], [11, 43], [67], [71], [4], [139], [16], [52], [4], [31], [7, 50], [2, 12], [1, 1, 83, 114], [13, 70], [60], [121], [30], [16], [214], [29, 78], [9, 37, 60], [14], [216, 249], [28], [2, 2, 21], [4, 18, 22], [59], [8, 24]])

This is just the first value of my list of 20k+ elements that is similar.

所以我有一个函数来检查一个数字是否在:

[1, 21, 54, 55, 93, 99, 284, 393, 964, 1029, 1214, 1216, 1223, 1253, 1258, 1334, 1365, 1394, 1397, 1453, 1471, 1543, 1589, 1824, 1975, 2054, 2090, 2164, 2165, 2166, 2167, 2323, 2547, 2645, 2802, 2809, 2931, 2958, 3031, 3071, 3077, 3078, 3189, 3199, 3202, 3203]

它会返回索引。

我的功能:iD 是我要查找的数字，而 posting 只是我嵌套循环中的第一个元素(上面的直接 block 是 posting 的示例)

def searchCurrentPosting(iD,posting):
x = 0

for each in posting[0]:
    if iD == each:
         return x
    x += 1
return False

每次给出一个新词(某个给定数字的 20k 次方)时，我都必须运行此搜索功能。此代码将运行大约一分钟。无论如何要缩短时间？

编辑:如果你想要我的整个程序，它是:

这是我的主要驱动程序:http://pastebin.com/Udjit7PP

它解析的文件是:CACM 集合，这是 IR 测试的标准。

使用词干提取(端口词干提取):http://pastebin.com/AzA0fvdV

是的，我正在创建倒排索引。

Answer 1

由于索引 0 处的列表已排序，因此您可以使用 bisect模块在 O(log N) 时间内找到索引:

In [33]: import bisect

In [34]: lst = [1, 21, 54, 55, 93, 99, 284, 393, 964, 1029, 1214, 1216, 1223, 1253, 1258, 1334, 1365, 1394, 1397, 1453, 1471, 1543, 1589, 1824, 1975, 2054, 2090, 2164, 2165, 2166, 2167, 2323, 2547, 2645, 2802, 2809, 2931, 2958, 3031, 3071, 3077, 3078, 3189, 3199, 3202, 3203]

In [35]: n = 2802

In [36]: ind = bisect.bisect_left(lst, n)

In [37]: if lst[ind] == n:
    ...:     print 'Item found at {}'.format(ind)
    ...:     
Item found at 34

请注意，如果列表未排序，那么最好先对其进行排序并将引用存储在变量中，这样您就不必一次又一次地对其进行排序。

另一种选择是使用字典，将项目作为键，索引作为值(对于重复的项目，只存储它们第一次出现的索引，即类似于 list.index)。创建字典后，您可以在 O(1) 时间内获取项目的索引。

In [38]: dct = {}

In [39]: for i, x in enumerate(lst):
    ...:     if x not in dct:
    ...:         dct[x] = i
    ...:         

In [40]: dct.get(n)
Out[40]: 34

In [41]: dct.get(1000) #return None for non-existent items

时序比较:

In [43]: lst = list(range(10**5))

In [44]: %timeit bisect.bisect_left(lst, 10**5-5)
1000000 loops, best of 3: 444 ns per loop

In [45]: %timeit lst.index(10**5-5)
1000 loops, best of 3: 1.29 ms per loop

In [46]: %timeit dct.get(10**5-5) #dct created using the new list.
10000000 loops, best of 3: 104 ns per loop

---

如果您连续更新索引为 0 的列表并且它没有排序，那么您应该简单地使用 list.index() 而不是使用循环、字典或一分为二。

In [47]: try:
    ...:     ind = lst.index(n)
    ...:     print 'Item found at {}'.format(ind)
    ...: except IndexError:
    ...:     pass
    ...: 
Item found at 34