Векторизация вложенная для циклов в понимании списка

Question

У меня есть два списка строк, в которых я вычисляю расстояние Дамерау – Левенштейна, чтобы проверить, какие из них похожи.Вопрос, который у меня есть в этом списке, более 200k +, и с пониманием это занимает довольно много времени.Для вычисления расстояния я использую пакет pyxDamerauLevenshtein, который написан на Cython, поэтому не должно быть узких мест

series = ([damerau_levenshtein_distance(i, j) for i in original_string for j in compare_string])

Вот так выглядит мой код, и мне интересно, можно ли его как-то векторизовать для повышения производительности, илиможет быть, какой-то другой способ ускорить вычисления?

Какой у меня набор данных:

Исходная строка - это pd. Серия уникальных названий улиц

Сравнить строку - это pd.Серии вручную введенных названий улиц, которые я хочу сравнить, чтобы найти сходство

Вывод должен быть таким:

   Original    Compare   Distance
0  Street1     Street1      1
1  Street2     Street1      2
2  Street3     Street1      3
3  Street4     Street3      5
4  Street5     Street3      5
5  Street6     Street6      1

Answer 1

Если вы можете придумать способ использовать функции карты (или imap), а не вложенные циклы, вы можете попробовать использовать multiprocessing для полной загрузки вашего процессора.Например, в этом случае:

pool.map(lambda j: map(lambda i: damerau_levenshtein_distance(i, j),original_string),compare_string) 

, где 'pool.map' - многопроцессорная карта, а вторая 'map' - обычная.

Ниже приведен быстрый, но функциональный примермногопроцессорной обработки, которая может охватывать то, что вы ищете.Я структурировал его немного по-другому, чтобы избежать некоторых проблем с засолкой и заставить его вычисляться в фоновом режиме несколько асинхронно, так как ваши списки длинные ...
(Это, безусловно, можно улучшить, но, надеюсь, должно послужить доказательствомконцепция для вашего примера)

import multiprocessing as mp
import itertools

list1 = range(5)
list2 = range(5)

def doSomething(a,b):
    return a+b #Your damerau_levenshtein_distance function goes here

def mapDoSomething(args):
    i = args[0] #An element of list2
    otherlist = args[1] #A copy of list1
    return [doSomething(i,j) for j in otherlist]

if __name__ == '__main__':
    pool = mp.Pool()
    answer = pool.imap(mapDoSomething,zip(list2,itertools.repeat(list1)))
    print(list(answer)) #imap will compute the results in the background whilst the rest of the code runs. You can therefore ask for individual lists of results, and it won't block unless the result hasn't been computed yet. To do this, you would use answer.next() or iterate over the results somewhere else. However, by converting to a list here, I'm forcing all results to finish before printing. This is only to show you it worked. For larger lists, don't do this.
    pool.close()
    pool.join()

Этот код производит:

[[0, 1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7], [4, 5, 6, 7, 8]]

, каждый из которыхэлемент list1 оперирует (я добавил их) каждым элементом list2, что, я думаю, и есть то, что вы пытались сделать в своем коде со списками строк.

Код устанавливает пул процессов, а затем использует imap для разделения обработки по списку2 между несколькими процессами.Функция zip лениво группирует элемент list2 с полной копией list1, поскольку imap поддерживает функции только с одним аргументом.Затем эта группа разделяется и используется в mapDoSomething, который запускает функцию doSomething для каждого элемента в list1 с каждым элементом list2.

Поскольку я использовал imap, списки печатаются сразу после их вычисления, а не ожидают завершения всего результата.