Найти - Пользователи
Полная версия: Удалить дубликаты строк
Начало » Python для новичков » Удалить дубликаты строк
1 2
Shaman
FishHook
Что если попробовать хранить строки в словаре с ключом - хеш строки?
Что это даст кроме затрат на вычисление хешей?
py.user.next
>>> import hashlib
>>> 
>>> def gethash(s):
...     return hashlib.md5(s.encode('utf-8')).hexdigest()
... 
>>> text = """
... aa aa
... bb bb
... cc cc
... aa aa
... bb bb
... bb bb
... cc cc
... cc cc
... cc cc
... """
>>> 
>>> hst = set()
>>> out = []
>>> 
>>> for i in text.splitlines():
...     h = gethash(i)
...     if h not in hst:
...         hst.add(h)
...         out.append(i)
... 
>>> out
['', 'aa aa', 'bb bb', 'cc cc']
>>>
FishHook
Shaman
Что это даст кроме затрат на вычисление хешей?
А зачем их вычислять еще раз?
file ="""Мама мыла раму
Мама мыла раму
Мама мыла Раму
Мама мыла Рому
Шла Саша по шоссе
Шла Саша по шоссе"""
unic = {hash(l): l for l in file.split("\n")}
print (unic)
FishHook
FishHook
Что это даст кроме затрат на вычисление хешей?
Хеш вычисляется только один раз, а извлекается по нему очень быстро и без затратно.
Сравнивать строки в цикле - гораздо накладнее.
Shaman
Высокая вероятность нарваться на коллизию.
Для ускорения можно ограничится заменой типа контейнера просмотренных со списка на множество и модифицировать алгоритм, если удаляются только серии повторений.
FishHook
Shaman
Высокая вероятность нарваться на коллизию.
Чо????
py.user.next
FishHook
Чо???

help(hash)
hash(...)
hash(object) -> integer

Return a hash value for the object. Two objects with the same value have
the same hash value. The reverse is not necessarily true, but likely.

Если у двух объектов один хеш, из этого не следует, что у них одинаковое содержимое. Встроенный хеш слишком короткий для анализа большого числа разных строк.

FishHook
unic = {hash(l): l for l in file.split("\n")}

Хеши нужны, чтобы не хранить встретившиеся строки (для экономии памяти). Строка может занимать много байт, а хеш - всегда фиксированное небольшое количество.

FishHook
Хеш вычисляется только один раз, а извлекается по нему очень быстро и без затратно.
А зачем там словарь? Подойдёт просто set(fin). Просто строк могут быть миллионы и все разные, да и порядок сохранить не мешало бы. Потому set() не подходит.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB