Как ускорить перебор элементов списка?

Question

[Shabunoff]

Есть набор последовательностей из 15 цифр. Эти цифры 1, 2 или 3. Например:
121231321223212

Нужно сравнить каждую из последовательностей с каждой и "запомнить" количество совпадений между ними.

Например последовательности:
111111111111121
111111111111112
Имеют 13 совпадений.

Сейчас это реализовано вот так:

diff=2
matrix = [[0] * len(list) for i in range(len(list))]
for i in range(len(list)):
for j in range(i, len(list)):
dis = distance.hamming(list[i], list[j])
if dis < diff:
matrix[i][j] = 1
matrix[j][i] = 1


Кусок кода сравнивает каждую строку списка list типа '111132123123213' друг с другом, и строит квадратную матрицу,
в пересечении строк и столбцов которой записывается 1 (если строки отличаются меньше чем на заданное количество (diff) отличий), либо 0 (если наоборот).

Задача ускорить данный кусок кода.
При такой реализации при списке из 1340 строк он выполняется на моем ПК за 2,5 секунд, а хотелось бы работать со списками от 20000 до 100000 строк

Comments

[Wataru]

Вопрос в том, что вы дальше с этой матрицей делать будете. Ее построение особо не ускорить. Ну, в несколько раз переписав на c++ и используя векторизацию. Для сотен тысяч строк все равно будет работать минуты.

А вот дальнейшую обработку может и возможно ускорить на порядки, если выкинуть всю матрицу целиком и использовать какие-то хитрые алгоритмы на строках. Или матрицу можно не считать всю целиком.

[Wataru]

Кстати, оберните код в тег code, а то вопрос удалят.

Answer 1

[Wataru]

Можно в несколько раз с оптимизировать, переписав на C++ c векторизацией (SSE там всякие). Тогда сравнение двух строк будет 1-2 инструкции вместо 15. Еще можно распаралеллить вычисления. Но все эти оптимизации все равное не позволят вам быстро считать для 100000 строк. Что уж говорить, сама матрица будет занимать минимум 10 гигабайт, если аккуратно на C писать или типизированный numpy массивы использовать. А так она и все 20 и 40 гигабайт займет запросто.

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

Answer 2

[dmshar]

Т.е. прошло больше года, а вы не сдвинулись ни на шаг?
https://qna.habr.com/q/740387
И скорее всего, даже не прочитали ответы, которые вам там дали.
Это отлично характеризует автора вопроса и подсказывает всем, что смысла отвечать на него нет никакого.

Comments

[Shabunoff]

Читал.
К сожалению те ответы не дают больше скорости.
К задаче вернулся не давно с новой мотивацией.
Но знаний в Python не хватает.
А если вам это что то характеризует и подсказывает то зачем отвечаете?)))

[dmshar]

В "том" ответе как минимум три идеи, которые надо попробовать, я вижу. Вы их уже попробовали? И что? Почему не отписали, почему тут не указали, что они не работают и почему, и надо другие? Или вы этого такого делали?

[longclaps]

Shabunoff, я - один из отвечавших вам год назад. Вы, очевидно, кретин, поэтому я буду объяснять вам предельно ясно.
Для краткости я обойдусь не 15-значным числом, а двузначным, на общность подхода это не повлияет. Допустим, у меня набор из четырёх последовательностей:
11
12
13
23
Построим табличку участия (вероятности) каждого из символов в каждом знакоместе:

|  1   |  2
--+------+---
1 | 0.75 | 0.25 
2 | 0.25 | 0.25
3 | 0.00 | 0.50

Для каждого знакоместа выберем символ с максимальной вероятностью, получится 13. Ура!
Но что, если бы последовательность 13 отсутствовала в исходном наборе (из вашей постановки задачи неясно, важно ли это)? Что ж, смоделируем такую ситуацию:
11
12
23
33

|  1   |  2
--+------+---
1 | 0.50 | 0.25 
2 | 0.25 | 0.25
3 | 0.25 | 0.50

Как и обещал, побеждает 13, но её нет в исходном списке.
Тогда выбираем из исходных последовательностей ту, что даёт максимальную сумму весов своих символов, в нашем случае их две - 11 и 33. Сложность задачи линейная от числа последовательностей. Тут выбор за вами.
Вы за год не сподобились сообразить эту хню. Бросьте, это не ваше.

[Shabunoff]

"hamming distance чем меньше, тем больше совпадений" - самый быстрый вариант из "того ответа"
Ответ Сергей Паньков для меня слишком сложный.

"Почему не отписали, почему тут не указали, что они не работают и почему, и надо другие? Или вы этого такого делали?" - Чет не подумал что это важно. Ссори.

Я пробовал переводить список в numpy и сравнивать каждый элемент последовательности.
Этот алгоритм был реализован на VB несколько лет назад "поэлементным сравнением последовательностей" и работал существенно быстрее.

[Сергей П]

Даже кусок кода свой не потрудился отформатировать.