Python：如何快速搜索集合中的子字符串？

Question

我有一套大约30万元组

In [26]: sa = set(o.node for o in vrts_l2_5) 
In [27]: len(sa)
Out[27]: 289798
In [31]: random.sample(sa, 1)
Out[31]: [('835644', '4696507')]

现在我想查找基于一个公共子字符串的元素，例如前4个“数字”（实际上元素是字符串）。这是我的方法：

^{pr2}$

有没有一种更有效的，也就是说，更快的方法来解决这个问题？在

Answer 1

我仔细研究并实施了4个建议的解决方案，以比较它们的效率。我用不同的前缀长度运行测试，看看输入如何影响性能。trie和sorted list的性能对输入的长度非常敏感，随着输入的增加，两者都会变得更快（我认为这实际上对输出的大小很敏感，因为输出随着前缀的增加而变小）。然而，排序集解决方案在所有情况下都绝对更快。在

在这些计时测试中，sa中有200000个元组，每个方法运行10次：

for prefix length 1
  lookup_set_startswith    : min=0.072107 avg=0.073878 max=0.077299
  lookup_set_int           : min=0.030447 avg=0.037739 max=0.045255
  lookup_set_trie          : min=0.111548 avg=0.124679 max=0.147859
  lookup_set_sorted        : min=0.012086 avg=0.013643 max=0.016096
for prefix length 2
  lookup_set_startswith    : min=0.066498 avg=0.069850 max=0.081271
  lookup_set_int           : min=0.027356 avg=0.034562 max=0.039137
  lookup_set_trie          : min=0.006949 avg=0.010091 max=0.032491
  lookup_set_sorted        : min=0.000915 avg=0.000944 max=0.001004
for prefix length 3
  lookup_set_startswith    : min=0.065708 avg=0.068467 max=0.079485
  lookup_set_int           : min=0.023907 avg=0.033344 max=0.043196
  lookup_set_trie          : min=0.000774 avg=0.000854 max=0.000929
  lookup_set_sorted        : min=0.000149 avg=0.000155 max=0.000163
for prefix length 4
  lookup_set_startswith    : min=0.065742 avg=0.068987 max=0.077351
  lookup_set_int           : min=0.026766 avg=0.034558 max=0.052269
  lookup_set_trie          : min=0.000147 avg=0.000167 max=0.000189
  lookup_set_sorted        : min=0.000065 avg=0.000068 max=0.000070

代码如下：

^{pr2}$

Answer 2

您可以使用trie data structure。可以用dict对象树（参见How to create a TRIE in Python）构建一个，但是有一个包marisa-trie通过绑定到c++库来实现一个内存高效的版本

我以前没有用过这个库，但是在玩它的时候，我得到了这个功能：

from random import randint
from marisa_trie import RecordTrie

sa = [(str(randint(1000000,9999999)),str(randint(1000000,9999999))) for i in range(100000)]
# make length of string in packed format big enough!
fmt = ">10p10p"
sa_tries = (RecordTrie(fmt, zip((unicode(first) for first, _ in sa), sa)),
            RecordTrie(fmt, zip((unicode(second) for _, second in sa), sa)))

def lookup_set(sa_tries, x_appr, y_appr):
    """lookup prefix in the appropriate trie and intersect the result"""
     return (set(item[1] for item in sa_tries[0].items(unicode(x_appr))) & 
             set(item[1] for item in sa_tries[1].items(unicode(y_appr))))

lookup_set(sa_tries, "2", "4")

Answer 3

你可以在O(log(n) + m)时间内完成，其中n是元组的数目，m是匹配元组的数目，如果你可以保留两个元组的排序副本。 排序本身将花费O(nlog(n))，也就是说，它将是渐进的慢于而不是您的天真方法，但是如果您必须执行一定数量的查询（超过log(n)，这几乎肯定是相当小的），它将得到回报。在

其思想是可以使用对分来找到第一个值和第二个值正确的候选值，然后与这些集相交。在

但是请注意，您需要一种奇怪的比较：您关心以给定参数开头的所有字符串。这仅仅意味着在搜索最正确的匹配项时，应该用9s填充该键

一个完整的工作代码（虽然没有经过很多测试）：

from random import randint
from operator import itemgetter

first = itemgetter(0)
second = itemgetter(1)

sa = [(str(randint(0, 1000000)), str(randint(0, 1000000))) for _ in range(300000)]
f_sorted = sorted(sa, key=first)
s_sorted = sa
s_sorted.sort(key=second)
max_length = max(len(s) for _,s in sa)

# See: bisect module from stdlib
def bisect_right(seq, element, key):
    lo = 0
    hi = len(seq)
    element = element.ljust(max_length, '9')
    while lo < hi:
        mid = (lo+hi)//2
        if element < key(seq[mid]):
            hi = mid
        else:
            lo = mid + 1
    return lo


def bisect_left(seq, element, key):
    lo = 0
    hi = len(seq)
    while lo < hi:
        mid = (lo+hi)//2
        if key(seq[mid]) < element:
            lo = mid + 1
        else:
            hi = mid
    return lo


def lookup_set(x_appr, y_appr):
    x_left = bisect_left(f_sorted, x_appr, key=first)
    x_right = bisect_right(f_sorted, x_appr, key=first)
    x_candidates = f_sorted[x_left:x_right + 1]
    y_left = bisect_left(s_sorted, y_appr, key=second)
    y_right = bisect_right(s_sorted, y_appr, key=second)
    y_candidates = s_sorted[y_left:y_right + 1]
    return set(x_candidates).intersection(y_candidates)

以及与初始解决方案的比较：

^{pr2}$

如您所见，此解决方案比您的天真方法快240-1400倍（在这些示例中）。在

如果你有一大堆火柴：

In [19]: %timeit lookup_set('1', '2')
10 loops, best of 3: 27.1 ms per loop

In [20]: %timeit lookup_set2('1', '2')
10 loops, best of 3: 152 ms per loop

In [21]: len(lookup_set('1', '2'))
Out[21]: 3587
In [23]: %timeit lookup_set('', '2')
10 loops, best of 3: 182 ms per loop

In [24]: %timeit lookup_set2('', '2')
1 loops, best of 3: 212 ms per loop

In [25]: len(lookup_set2('', '2'))
Out[25]: 33053

如您所见，即使匹配的数量约为总大小的10%，此解决方案也会更快。但是，如果您试图匹配所有数据：

In [26]: %timeit lookup_set('', '')
1 loops, best of 3: 360 ms per loop

In [27]: %timeit lookup_set2('', '')
1 loops, best of 3: 221 ms per loop

它变慢了（不是那么慢），尽管这是一个非常特殊的情况，我怀疑你会经常匹配几乎所有的元素。在

请注意，sort所花的时间非常小：

In [13]: from random import randint
    ...: from operator import itemgetter
    ...: 
    ...: first = itemgetter(0)
    ...: second = itemgetter(1)
    ...: 
    ...: sa2 = [(str(randint(0, 1000000)), str(randint(0, 1000000))) for _ in range(300000)]

In [14]: %%timeit
    ...: f_sorted = sorted(sa2, key=first)
    ...: s_sorted = sorted(sa2, key=second)
    ...: max_length = max(len(s) for _,s in sa2)
    ...: 
1 loops, best of 3: 881 ms per loop

如您所见，完成两个已排序的副本不到一秒钟。实际上，由于上面的代码对第二个副本进行“就地”排序（尽管tim sort可能仍然需要O(n)内存），所以它的速度会稍微快一些。在

这意味着，如果您必须执行超过6-8个查询，此解决方案将更快。在

---

注意：python的标准库提供了一个bisect模块。但是它不允许key参数（尽管我记得读过Guido想要它，所以将来可能会添加它）。因此，如果您想直接使用它，就必须使用“decorate-sort-undecorate”这个成语。在

而不是：

f_sorted = sorted(sa, key=first)

您应该：

f_sorted = sorted((first, (first,second)) for first,second in sa)

也就是说，显式地插入键作为元组的第一个元素。然后，可以使用('123', '')作为元素传递给bisect_*函数，它应该会找到正确的索引。在

我决定避免这个。我复制粘贴了来自模块源代码的代码，并对其稍作修改，为您的用例提供了一个更简单的接口。在

---

最后一点：如果可以将元组元素转换为整数，那么比较会更快。然而，大部分时间仍然需要执行集合的交集，所以我不知道它到底能提高多少性能。在