В Python я хотел бы быстро вычислить хеш-инвариант порядка для строк файла как способ идентифицировать «уникально» его содержимое. Этими файлами являются, например, вывод select ... from table, и, таким образом, порядок строк является случайным.Order-инвариантный хеш в Python
Вот пример, который достигает того, что я хочу (используя один из хэширов в хэшлибе), но за счет необходимости сортировки строк. Обратите внимание, что сортировка строк - это просто способ достижения цели, то есть получить хэш, который не зависит от упорядочения строк в файле. Но ясно, что я бы хотел избежать стоимости O (n * log (n)), особенно. когда файлы намного дольше.
def get_hexdigest(filename, hasher, blocksize=65536, order_invariant=False):
if not os.path.isfile(filename):
return None
if order_invariant:
with open(filename, 'r') as f:
for line in sorted(f):
hasher.update(line.encode())
else:
with open(filename, 'rb') as f:
while True:
buf = f.read(blocksize)
hasher.update(buf)
if len(buf) < blocksize:
break
return hasher.hexdigest()
Так, например, 1MB, 50K строк файла:
%%time
get_hexdigest('some_file', hashlib.sha1())
# Wall time: 1.71 ms
Но:
%%time
get_hexdigest('some_file', hashlib.sha1(), order_invariant=True)
# Wall time: 77.4 ms
Что лучше/быстрее способ сделать это?
Как отмечено in this answer, Scala имеет хеш-инвариант порядка на основе Murmurhash, но я предполагаю, что это 32-разрядная версия mmh3 (слишком подверженная конфликтам для моего использования), а также я бы предпочел использовать некоторую стандартную библиотеку доступный в Python, вместо того, чтобы внедрять что-то в C или в Cython. Murmurhash3 имеет 128-битную версию, но ее выход отличается от x64 vs x86. Я хотел бы получить независимые от машины результаты.
Итак, в заключении, я хотел бы:
- результатов различных машинных архитектур
- низкой скорости столкновения, то есть по крайней мере, 128 бит с хорошей дисперсией (но мне не нужен хэш быть криптографический)
- достаточно быстрая, т.е. не менее 5 мс для 1 МБ, 50 К строк файла.
- легкодоступный, если возможно, как библиотека на PyPi или Conda.
- подходит для файлов с повторяющимися строками (так что хеширование XORing для строк не является стартером, так как любая пара идентичных строк будет отменять друг друга).
редактирует и примечание: Благодаря несколько комментариев, приведенный выше код обновляется для сортировки строк в памяти. Оригинальная версия для order_invariant is True был:
with os.popen('sort {}'.format(filename)) as f:
for line in f:
hasher.update(line.encode(encoding='utf-8'))
return hasher.hexdigest()
ассоциируемое время стены (для файла, используемого выше) затем 238 мс. Теперь это уменьшено до 77 мс, но все еще медленнее, чем не сортировка строк. Сортировка добавит стоимость n * log (n) для n строк.
Кодирование (до UTF-8) и чтение в режиме 'r' или 'rb' необходимо при чтении строк, так как тогда мы получаем строки не байтов. Я не хочу полагаться на предположение, что файлы содержат только данные ASCII; чтение в 'rb' может привести к тому, что линии не будут правильно разделены. У меня нет такой же озабоченности, когда order_invariant False, потому что тогда мне не нужно разделить файл, и, таким образом, самым быстрым способом является сокращение фрагментов двоичных данных для обновления хэширования.
первого улучшение: вы, вероятно, 'sort' строки питона с помощью' для строк в отсортированном (е) 'вместо вызова внешнего процесса ... –
Как примечание стороны, если вы работаете с линиями (основанный на _'order-инвариантном хеше для строк файла__), почему вы используете буфер в «упорядочивающем» случае? Просто прокатите 'hasher' с' .readline() 'output. – zwer
Кроме того: возможно, намного быстрее закодировать весь файл и * затем разбить строки, а затем вызвать '.encode' в каждой строке:' open (...) как f: для строки в сортировке (f.read () .encode ('utf-8'). split ('\ n')): hasher.update (строка) '(да, он загружает весь файл в память, но сортировка * требует * этого). – Bakuriu