Уведомления

Группа в Telegram: @pythonsu

#1 Июль 18, 2014 12:59:01

Shaman
Зарегистрирован: 2013-03-15
Сообщения: 1369
Репутация: +  88  -
Профиль   Отправить e-mail  

Удалить дубликаты строк

FishHook
Что если попробовать хранить строки в словаре с ключом - хеш строки?
Что это даст кроме затрат на вычисление хешей?

Офлайн

#2 Июль 18, 2014 14:41:45

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 10015
Репутация: +  857  -
Профиль   Отправить e-mail  

Удалить дубликаты строк

>>> 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']
>>>



Отредактировано py.user.next (Июль 18, 2014 14:43:47)

Офлайн

#3 Июль 18, 2014 17:06:23

FishHook
От:
Зарегистрирован: 2011-01-08
Сообщения: 8312
Репутация: +  568  -
Профиль   Отправить e-mail  

Удалить дубликаты строк

Shaman
Что это даст кроме затрат на вычисление хешей?
А зачем их вычислять еще раз?
file ="""Мама мыла раму
Мама мыла раму
Мама мыла Раму
Мама мыла Рому
Шла Саша по шоссе
Шла Саша по шоссе"""
unic = {hash(l): l for l in file.split("\n")}
print (unic)



Офлайн

#4 Июль 18, 2014 17:08:02

FishHook
От:
Зарегистрирован: 2011-01-08
Сообщения: 8312
Репутация: +  568  -
Профиль   Отправить e-mail  

Удалить дубликаты строк

FishHook
Что это даст кроме затрат на вычисление хешей?
Хеш вычисляется только один раз, а извлекается по нему очень быстро и без затратно.
Сравнивать строки в цикле - гораздо накладнее.



Офлайн

#5 Июль 18, 2014 21:44:52

Shaman
Зарегистрирован: 2013-03-15
Сообщения: 1369
Репутация: +  88  -
Профиль   Отправить e-mail  

Удалить дубликаты строк

Высокая вероятность нарваться на коллизию.
Для ускорения можно ограничится заменой типа контейнера просмотренных со списка на множество и модифицировать алгоритм, если удаляются только серии повторений.

Офлайн

#6 Июль 18, 2014 22:04:31

FishHook
От:
Зарегистрирован: 2011-01-08
Сообщения: 8312
Репутация: +  568  -
Профиль   Отправить e-mail  

Удалить дубликаты строк

Shaman
Высокая вероятность нарваться на коллизию.
Чо????



Офлайн

#7 Июль 19, 2014 00:52:31

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 10015
Репутация: +  857  -
Профиль   Отправить e-mail  

Удалить дубликаты строк

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() не подходит.



Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version