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}$