Shabunoff
@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 строк
  • Вопрос задан
  • 268 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Можно в несколько раз с оптимизировать, переписав на C++ c векторизацией (SSE там всякие). Тогда сравнение двух строк будет 1-2 инструкции вместо 15. Еще можно распаралеллить вычисления. Но все эти оптимизации все равное не позволят вам быстро считать для 100000 строк. Что уж говорить, сама матрица будет занимать минимум 10 гигабайт, если аккуратно на C писать или типизированный numpy массивы использовать. А так она и все 20 и 40 гигабайт займет запросто.

И ничего сильно более быстрого тут не получится, если вам нужна вся матрица - придется пару минут ее считать в лучшем случае. Вот если вы ее используете для каких-то еще вычислений (например, вы для каждой строки считаете, сколько близких к ней есть в списке), то можно принципиально ускорить решение не вычисляя матрицу, а считая искомое количество сразу.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
@dmshar
Т.е. прошло больше года, а вы не сдвинулись ни на шаг?
https://qna.habr.com/q/740387
И скорее всего, даже не прочитали ответы, которые вам там дали.
Это отлично характеризует автора вопроса и подсказывает всем, что смысла отвечать на него нет никакого.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы