Как сравнить несколько последовательностей цифр между собой?

Question

[Shabunoff]

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

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

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

Пробовал и перебор массива (каждая цифра - отдельный элемент) и библиотеку fuzzywuzzy.

Хотелось бы побыстрее, очень медленно.

Снова вернулся к решению данного вопроса:

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

[Andrey Dugin]

Для начала покажите код

Answer 1

[longclaps]

Зачем "запоминать количество совпадений между ними", когда его можно мгновенно вычислить:

>>> import operator
>>> sum(map(operator.eq,'111111111111121','111111111111112'))
13

Comments

[Shabunoff]

Скорее правда дурачок, но..

Надо потом выбирать из этих 5000 определенные последовательности. исходя из того сколько совпадений у них с остальными.

т.е. например сравнил все со всеми, и выбрал ту - у которой 12 и больше совпадений с другими максимальное из остальных.

[longclaps]

Shabunoff, эти сопли не содержат критерия выбора.

[Ivan Yakushenko]

Shabunoff, itertools.combinations() и перебирай сколько влезет

[longclaps]

Shabunoff, смотри, вот 15 строк, в любой паре 13 совпадений:

111111111111112
111111111111121
111111111111211
111111111112111
111111111121111
111111111211111
111111112111111
111111121111111
111111211111111
111112111111111
111121111111111
111211111111111
112111111111111
121111111111111
211111111111111

как тут выбирать?

[o5a]

Shabunoff, больше похоже на XY problem, когда спрашиваешь о своем варианте решения проблемы, а не о самой изначальной проблеме. Лучше бы рассказать, для чего вообще это все нужно.

Answer 2

[Dimonchik]

hamming distance чем меньше, тем больше совпадений

Answer 3

[Сергей П]

А какие конкретно у вас пожелания на счет скорости? У вас сложность квадратичная, 25 миллионов сравнений. Ну можно бинарные операции подключить, можно последовательности как-то обрабатывать, например сортировать. Однако в этой формулировке не ясно что не так и какие у вас получились скорости. От чего-то ж надо отталкиваться. Покажите код и вам его здесь пооптимизируют.
А сейчас задача выглядит как "пойди туда - не знаю куда".
Так-то можно упороться и на шейдерах это решать за счет видеокарты. Вопрос только в том, для чего все эти извращения. Если простая учебная задача - то на то она и задача, чтобы самому решать, а не на Q&A, а если практическая, то попахивает проблемами в архитектуре на более ранних этапах. Не ясна причина почему нужно быстрее, это часто повторяющаяся задача? Если так, то, быть может, имеет смысл изначально оптимизировать? Эта задача инициируется пользователем? Так может имеет смысл прибегнуть к ленивым вычислениям или посчитать заранее,чтобы не фризить интерфейсы?
Короче, нужно больше подробностей.

Answer 4

[Android Developer]

int n, max, a, b;

cout<<"n=";cin>>n;
cin>>a;
cin>>b;
max = a + b;

for(int i =3;i <= n;i++){
cin>>a;
if(max < a + b){
max = a + b;
}
b = a;
}
cout<<"max="<
Рад помоч !