1

我试图找到 2 个字符串之间的所有形式的插入。所以我有一个包含 1400 万个字符串的列表，然后我必须检查每个字符串有哪些可能的插入可以将一个字符串转换为另一个字符串（基本上计算插入频率）。假设 x 是一个字符串，y 是另一个字符串，其中 x 是 y 的子字符串，所以我们必须找出哪些插入将 x 转换为 y。

我正在使用以下代码段。它有效，但需要很多时间。我什至尝试将负载分布在 64 个处理器上，但仍需要 20 天才能完成。

for i in Words:
#trying to distribute load across different processes, so can ignore this part
   h = hashlib.sha256(i)
   n = int(h.hexdigest(),base=16)
   if (n%64!=ix): #ix is a process based id
    continue


   for j in Words:#
    if len(i)>len(j):
        continue
    if( i!=j and i in j):  # i is a substring of j
        ind=j.find(i)
        s1=j[0:ind]
        s2=j[ind+len(i):len(j)]

                    if(len(s1)>0):
            if (not transform.has_key(s1)):
                transform[s1]=1
            else:
                transform[s1]+=1

        if(len(s2)>0):
            if (not transform.has_key(s2)):
                transform[s2]=1
            else:
                transform[s2]+=1
4

1 回答 1

1

不是将每个单词相互比较（二次运行时间），而是取每个单词的每个正确子字符串（线性运行时间，假设单词长度是有界的）并检查它是否在单词集中（查找 a 的元素set是常数时间） .

这在我的笔记本电脑上运行了不到 2 秒（46265 个字（长度 < 10），具有 47015 个独特的转换（总共 799089 个））：

from collections import Counter

# for testing
from random import choice, randrange
from string import ascii_uppercase
big_word = "".join(choice(ascii_uppercase) for i in range(10000))
words = [big_word[randrange(len(big_word)):][:randrange(1, 10)] for i in range(100000)] # words of up to 9 letters; all are substrings of big_word  

# now the real code
def insertions(words):
    for word in words:
        for i in range(1, len(word) - 1):
            ins = word[:i]
            rest = word[i:]
            for j in range(1, len(rest)):
                if rest[:j] in words:
                    yield ins
        for i in range(1, len(word) - 1):
            rest = word[:i]
            ins = word[i:]
            for j in range(len(rest) - 1):
                if rest[j:] in words:
                    yield ins

transforms = Counter(insertions(set(words)))
于 2012-12-20T23:07:17.893 回答