快速搜索两个列表中的所有元素

Question

假设我有两个大列表，list_of_A_objects 包含类 A 的对象，list_of_B_objects 包含类 B 的对象。

它们都有字符串成员。

我想要能够搜索两个列表中的所有元素，并且如果 A 对象的字符串成员是 B 对象的字符串成员的子字符串，我想要执行某些操作。

下面的代码对于较小的列表来说是可以的，但是如果列表很大，它可能需要很长时间。

有没有一种方法可以使这个过程更快呢？我一直在考虑以某种方式使用字典，因为它们具有快速查找的功能，但我无法想出具体实现方法。

这是我目前拥有的代码。

class A:
    def __init__(self, x):
        self.string = x

class B:
    def __init__(self,x):
        self.string = x

list_of_A_objects = get_large_list_of_A_objects()

list_of_B_objects = get_large_list_of_B_objects() 


for A_object in list_of_A_objects:
    for B_Object in list_of_B_objects:
        if A_object.string in B_Object.string:
            do_something()

- monty

---

我关心的不是做某事所需的时间。上面的代码是我问题的简化示例。在我的实际问题中，随着一个列表变得越来越大，另一个列表也会变得越来越大，因此当其中一个列表增加大小时，我会遇到n^2时间排序的情况。 - monty

我问这个问题是因为在查找第一个匹配项和查找多个匹配项或执行某些操作之间存在很大的差异，我认为使用集合或字典也无法解决问题，因为你正在查找子字符串。 - Padraic Cunningham

好的，我明白你的意思了。它需要搜索多个匹配项。谢谢。 - monty

字符串上是否有任何约束？如果它们是一般的字符串，那么似乎很难做到比二次复杂度更好，但如果它们是特殊的，可能会有一些技巧。 - jme

Answer 1

您可以做的一件事是从B对象中创建一个单一的字符串。在构建这个字符串的同时，您还可以创建一个索引列表，以便知道较大字符串中每个字符串的索引。请参见下面的代码。

请注意，我不是Python程序员，所以您需要理解我的伪代码。

BStrings = ""
list_of_Indexes = new list of int
for B_object in list_of_B_objects
    list_of_Indexes.Add(length of BStrings)
    BStrings = BStrings + B_Object.string + newline

现在，您可以为每个A_object搜索BStrings字符串。如果找到该字符串，则函数返回在字符串中找到它的索引。然后，您可以对list_of_indexes进行二进制搜索，以确定哪个B_object包含该字符串。

这并没有真正改变操作的复杂性（仍然是MxN，其中M是A列表中对象的数量，N是B列表的长度），但搜索单个字符串的子字符串将比循环B列表更快，因为它避免了设置搜索的开销。

如果即使这样仍然太慢，那么您将需要使用类似于Aho-Corasick字符串匹配算法的东西。可能有一个不错的Python实现。

- Jim Mischel

---

谢谢您抽出时间回答，我会考虑一下的。 - monty

Answer 2

这里是使用字典实现的Python代码。首先将其中一个列表转换为以其对象字符串为索引的形式。

a_map = {}

for A_object in list_of_A_objects:
    a_map[A_object.string] = A_object

然后对于另一个列表中的每个对象，检查该对象的字符串是否存在于字典中（在常数时间内），如果存在则执行某些操作

for B_object in list_of_B_objects:
    if B_object.string in a_map:
        do_something(a_map[B_object.string])

假设每个A_object都有一个独特的字符串。如果不是这种情况，那么您可以将a_map的值变成对象数组，而不是单个对象。

- FuzzyTree