Быстрый поиск всех элементов в двух списках

Скажем, у меня есть два больших списка: list_of_A_objects, которые содержат объекты класса A, и список _of_B_объектов, которые содержат объекты класса 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() 

Одна вещь, которую вы можете сделать, это создать одну строку из объектов B. Создавая это, вы также создаете список индексов, поэтому вы знаете индекс каждой строки в большей строке. См. Код ниже.

Обратите внимание, что я не программист на питоне, поэтому вам придется интерпретировать мой псевдокод.

 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 

Теперь вы можете искать строку BStrings для каждого объекта A_object. Если строка найдена, функция возвращает индекс, где она была найдена в строке. Затем вы можете выполнить двоичный поиск в list_of_indexes, чтобы определить, какой B_объект содержит эту строку.

Это не меняет сложность операции (это все еще MxN, где M – количество объектов в списке A, а N – длина списка B), но поиск одной строки для подстрок будет быстрее, чем зацикливание над списком B, поскольку оно позволяет избежать накладных расходов на настройку поиска.

Если даже это слишком медленно, тогда вы захотите использовать что-то вроде алгоритма соответствия строк Aho-Corasick . Вероятно, есть достойная реализация Python.

Вот реализация python с использованием словаря. Сначала преобразуйте один из списков в индексированные по его строкам объекта

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

Затем для каждого объекта в другом списке проверьте, существует ли строка слова в словаре (в постоянное время), и если так do_something

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

Это предполагает, что каждый A_объект имеет уникальную строку. Если это не так, вы можете сделать значения a_map массивом объектов вместо одного объекта.