如何使用 python 有效地匹配两个大列表之间的字符串？ （510.000.000 次比较）
How to efficiently match strings between two big lists with python? (510.000.000 comparisons)
我遇到了一个很长的 运行 for 循环的问题。
有两个 python 列表（A 和 B）：
A 包含大约 170.000 个长度在 1 到 100 个字符之间的字符串。
B 包含大约 3.000 个长度相同的字符串。
现在我需要从列表 A 中查找包含列表 B 中的一项的项。
考虑到 A 中的每个字符串都需要与 B 中的每个字符串进行比较，因此需要进行 510.000.000 次比较。这似乎计算成本太高了。
有什么方法可以加快速度？
伪代码：
A = [] # length: 170.000 (strings)
B = [] # length: 3.000 (strings)
for item in A:
for element in B:
if element in item:
print("store the item which contains the element to db")
列表中某些元素的示例内容：
A[0] = "This is some random text in which I want to find words"
A[1] = "It is just some random text"
...
B[0] = "text"
B[1] = "some random text"
...
我不想在第一场比赛结束后就停下来，因为可能还有更多比赛。
目标是将所有匹配项存储在一些新的 variable/db.
中
def two_list(a,b):
对于 a 中的项目：
对于 b 中的数字：
如果项目==num：
打印（项目）
打印(two_list(a,b))
您也可以使用 pandas 执行此操作。
adf = (
pandas.DataFrame(A,columns=['text'])
.assign(strlen=lambda x: x['text'].str.len())
) #create a df from the first array
bdf = (
pandas.DataFrame(B,columns=['text'])
.assign(strlen=lambda x: x['text'].str.len())
.sort_values('strlen')
) #create a df from the second array
resultdf = pandas.DataFrame()
for i,row in bdf.itterrows():
if len(row['text']) > adf.text.max():
break
resultdf = resultdf.append(
adf[lambda x: x['text'].str.contains(row['text'])],ignore_index=True)
resultdf
你可以试试这个：
d={}
for i in range(1,101):
d[i]=[]
for x in A:
for y in range(min(101, len(x))-i+1):
d[i].append([x[y:y+i]), A])
result=[]
for item in B:
s=d[len(item)]
for k in s:
if item==s[0]:
result.append(s[1])
解释：我们创建了一个字典，键为 1-100，表示 B 中元素的可能长度。我们在列表 A 中循环。对于 A 中的每个项目，我们从 1 循环到最大值（从项目的长度开始的最小值或 100) 并将 A 的所有部分保存到 d 中的关联键。
完成后，我们只需循环列表 B 一次，并将（B 的）元素与 d 的相应键中的值进行比较。
例如，如果元素的长度是 20，我们将只检查 d[20]。如果元素与某个项目相同，我们保存相应的 A-item
第一个答案：如果你只需要做一次，那就暴力破解吧。 570M 子字符串操作很多，是的，我猜这将花费一个小时左右，但这比您找出、编写和调试更快的解决方案所花费的时间要少。
第二个答案：尝试将 B 中的字符串放入 trie。理论上，这会使它更快，但实际上，它可能不会，除非你找到一个用 C 实现的 python trie 库。否则，遍历一个 trie（或实际上任何其他字符串搜索数据结构） python 会变慢。
您面临的问题是，如果您有一个来自 A 的字符串和一个来自 B 的字符串，那么 b in a 会相对较快，因为在引擎盖下子字符串匹配将 运行在 C 中。但是，如果您在 python 中编写理论上更有效的解决方案，即使“大 O”运行ning 时间更快，实际 运行ning 时间也可能会更慢因为解释 python 比 C.
慢得多
这里有两个解决方案（其中l1是第一个列表，l2是第二个列表）：
方案A，二分查找（时间复杂度O(nlogn)）：
import bisect
def method_bisect(x, b):
index = bisect.bisect_left(b, x)
if x == b[index]:
return x
return None
results = []
l2.sort()
for l in l1:
result = method_bisect(l, l2)
if result:
results.append(result)
二解散列table（时间复杂度O(n)）：
B_d = {key: [] for key in l2}
results = []
for l in l1:
if l in B_d:
results.append(l)
最后我采用了@busfighter 在评论中建议的解决方案：
"You can sort both lists by length of strings and therefore
break your inner loop if length of element is greater than item. It won't make complexity lower but it will decrease number of
operations."
Speedwise 他说：
"sorting has O(nlogn) complexity(which is lower than O(nm) if n and m
are of one order) and finding length of string is cheaper(O(1)) than
checking if string is a substring of another one(O(n*m) where n and m
are lengths of strings))"
我遇到了一个很长的 运行 for 循环的问题。
有两个 python 列表（A 和 B）：
A 包含大约 170.000 个长度在 1 到 100 个字符之间的字符串。 B 包含大约 3.000 个长度相同的字符串。
现在我需要从列表 A 中查找包含列表 B 中的一项的项。
考虑到 A 中的每个字符串都需要与 B 中的每个字符串进行比较，因此需要进行 510.000.000 次比较。这似乎计算成本太高了。
有什么方法可以加快速度？
伪代码：
A = [] # length: 170.000 (strings)
B = [] # length: 3.000 (strings)
for item in A:
for element in B:
if element in item:
print("store the item which contains the element to db")
列表中某些元素的示例内容：
A[0] = "This is some random text in which I want to find words"
A[1] = "It is just some random text"
...
B[0] = "text"
B[1] = "some random text"
...
我不想在第一场比赛结束后就停下来，因为可能还有更多比赛。 目标是将所有匹配项存储在一些新的 variable/db.
中def two_list(a,b): 对于 a 中的项目： 对于 b 中的数字： 如果项目==num： 打印（项目）
打印(two_list(a,b))
您也可以使用 pandas 执行此操作。
adf = (
pandas.DataFrame(A,columns=['text'])
.assign(strlen=lambda x: x['text'].str.len())
) #create a df from the first array
bdf = (
pandas.DataFrame(B,columns=['text'])
.assign(strlen=lambda x: x['text'].str.len())
.sort_values('strlen')
) #create a df from the second array
resultdf = pandas.DataFrame()
for i,row in bdf.itterrows():
if len(row['text']) > adf.text.max():
break
resultdf = resultdf.append(
adf[lambda x: x['text'].str.contains(row['text'])],ignore_index=True)
resultdf
你可以试试这个：
d={}
for i in range(1,101):
d[i]=[]
for x in A:
for y in range(min(101, len(x))-i+1):
d[i].append([x[y:y+i]), A])
result=[]
for item in B:
s=d[len(item)]
for k in s:
if item==s[0]:
result.append(s[1])
解释：我们创建了一个字典，键为 1-100，表示 B 中元素的可能长度。我们在列表 A 中循环。对于 A 中的每个项目，我们从 1 循环到最大值（从项目的长度开始的最小值或 100) 并将 A 的所有部分保存到 d 中的关联键。 完成后，我们只需循环列表 B 一次，并将（B 的）元素与 d 的相应键中的值进行比较。 例如，如果元素的长度是 20，我们将只检查 d[20]。如果元素与某个项目相同，我们保存相应的 A-item
第一个答案：如果你只需要做一次，那就暴力破解吧。 570M 子字符串操作很多，是的，我猜这将花费一个小时左右，但这比您找出、编写和调试更快的解决方案所花费的时间要少。
第二个答案：尝试将 B 中的字符串放入 trie。理论上，这会使它更快，但实际上，它可能不会，除非你找到一个用 C 实现的 python trie 库。否则，遍历一个 trie（或实际上任何其他字符串搜索数据结构） python 会变慢。
您面临的问题是，如果您有一个来自 A 的字符串和一个来自 B 的字符串，那么 b in a 会相对较快，因为在引擎盖下子字符串匹配将 运行在 C 中。但是，如果您在 python 中编写理论上更有效的解决方案，即使“大 O”运行ning 时间更快，实际 运行ning 时间也可能会更慢因为解释 python 比 C.
这里有两个解决方案（其中l1是第一个列表，l2是第二个列表）：
方案A，二分查找（时间复杂度O(nlogn)）：
import bisect
def method_bisect(x, b):
index = bisect.bisect_left(b, x)
if x == b[index]:
return x
return None
results = []
l2.sort()
for l in l1:
result = method_bisect(l, l2)
if result:
results.append(result)
二解散列table（时间复杂度O(n)）：
B_d = {key: [] for key in l2}
results = []
for l in l1:
if l in B_d:
results.append(l)
最后我采用了@busfighter 在评论中建议的解决方案：
"You can sort both lists by length of strings and therefore break your inner loop if length of element is greater than item. It won't make complexity lower but it will decrease number of operations."
Speedwise 他说：
"sorting has O(nlogn) complexity(which is lower than O(nm) if n and m are of one order) and finding length of string is cheaper(O(1)) than checking if string is a substring of another one(O(n*m) where n and m are lengths of strings))"