DjangoBB LoFi version

Полная версия: Сравнение на расстояние Хэмминга

Начало » Python для новичков » Сравнение на расстояние Хэмминга

valentjedi

Май 4, 2014 12:59:49

Всем привет!
В цикле получается последовательность из интовых 1 и 0, которая записывается в строку. И таких строк 2 Собственно, вопрос в том, как наиболее правильно (Python way) будет найти расстояние Хэмминга (то есть количество попарно различных символов).
Пока это решается примерно так (hash_original и hash_to_check - строки):

for i in range(len(hash_to_check)):
    if hash_to_check[i] != hash_original[i]:
        diff_sym += 1

Может, лучше вообще не строками, а еще на этапе генерации записывать все в byte array или еще куда?
Если что, использую Python 3.4

FishHook

Май 4, 2014 13:08:01

Есть один надежный способ определения говнокода в питоне. Если у Вас есть конструкция

range(len(...))

значит код скорее всего некудышный. Попробуйте как то так

sum(1 for x,y in zip(hash_to_check, hash_original) if x!= y)

или так

len((set(hash_to_check).difference(set(hash_original))))

valentjedi

Май 4, 2014 13:56:57

FishHook
Прочитал про zip, map и lambda. Круто, спасибо! А второй вариант не подходит, потому что подсчитывает различия в алфавите строк, если я правильно понял. Так как обе строки содержат нули и единицы, то

len((set(hash_to_check).difference(set(hash_original))))

возвращает 0.

А как можно из входного цикла генерировать не строку, а какую-нибудь битовую структуру, чтобы затем сравнивать xor-ом? Или это не будет быстрее и не имеет смысла?

doza_and

Май 4, 2014 16:34:52

valentjedi
не будет быстрее и не имеет смысла?

Питон больше язык для быстрого прототипирования приложения. Если хотите быстро то.
1 В самом начале определитесь что такое быстро (по сравнению с чем быстро). может оно и так быстро.
2 Если надо быстрее, попробуйте использовать готовые модули. http://docs.scipy.org/doc/scipy-0.13.0/reference/generated/scipy.spatial.distance.hamming.html
3 Если не получилось пишите свои модули на C.

valentjedi

Май 4, 2014 17:28:08

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

py.user.next

Май 4, 2014 22:38:06

>>> def f(s1, s2):
...     assert len(s1) == len(s2)
...     return sum(i != j for i, j in zip(s1, s2))
... 
>>> f('abaaaba', 'abbabba')
2
>>>