Блог

Я сталкиваюсь с проблемой очень длительного выполнения цикла for.

Существует два списка python (A и B):

A содержит около 170.000 строк длиной от 1 до 100 символов. B содержит около 3000 строк одинаковой длины.

Теперь мне нужно найти элементы из списка 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"
...
  

Я не хочу останавливаться после первого совпадения, так как совпадений может быть больше.
Цель состоит в том, чтобы сохранить все совпадения в некоторой новой переменной / db.

Первый ответ: если вам нужно сделать это только один раз, просто примените грубую силу. 570 миллионов операций с подстроками — это много, да, я предполагаю, что это займет час или около того, но это меньше времени, чем вам потребуется, чтобы найти, написать и отладить более быстрое решение.

Второй ответ: попробуйте поместить строки в B в дерево. Теоретически это ускорит процесс, но на практике, вероятно, этого не произойдет, если вы не найдете библиотеку trie python, которая реализована на C. В противном случае обход trie (или действительно любой другой структуры данных поиска строк) в python будет медленным.

Проблема, с которой вы сталкиваетесь, заключается в том, что если у вас есть одна строка из A и одна строка из B, это b in a будет относительно быстро, потому что под капотом сопоставление подстрок будет выполняться в C. Но если вы создадите более теоретически эффективное решение на python, даже если время выполнения «big O» будет быстрее, фактическое время выполнения, вероятно, будет медленнее, потому что интерпретируемый python намного медленнее, чем C.

Вы можете попробовать это:

 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])
  

Объяснение: Мы создаем dict с ключами 1-100, которые представляют возможные длины элементов в B. Мы зацикливаемся в списке A. Для каждого элемента в A мы выполняем цикл от 1 до max (минимальный столбец из длины элемента или 100) и сохраняем все части A в связанный ключ в d.
Когда это закончится, нам нужно только один раз перебрать список B и сравнить элемент (из B) со значениями в соответствующем ключе d .
Например, если длина элемента равна 20, мы будем проверять только в d[20] . Если элемент является eual с каким-либо элементом, мы сохраняем соответствующий A-элемент

Вот два решения (где 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)
  

Хэш-таблица второго решения (временная сложность O (n)):

 B_d = {key: [] for key in l2}
results = []
for l in l1:
    if l in B_d:
        results.append(l)
  

Вы также можете сделать это с 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
  

В конце концов я выбрал решение, которое @busfighter предложил в комментариях:

«Вы можете отсортировать оба списка по длине строк и, следовательно, прервать свой внутренний цикл, если длина элемента больше, чем item . Это не снизит сложность, но уменьшит количество операций. «

По скорости он говорит:

«сортировка имеет сложность O (nlogn) (которая ниже, чем O (nm), если n и m имеют один порядок), и поиск длины строки дешевле (O (1)), чем проверка, является ли строка подстрокой другого (O (n * m), где n и mэто длины строк))»

определение two_list(a,b): для элемента в a: для num в b: если item==num: print(item)

print(two_list(a, b))