В Python я хотел бы быстро вычислить хеш-инвариант порядка для строк файла как способ идентифицировать "уникально" его содержимое. Эти файлы представляют собой, например, вывод select ... from table и, следовательно, порядок строк является случайным.
Вот пример, который достигает того, что я хочу (используя один из хэшеров в hashlib), но за счет необходимости сортировки строк. Обратите внимание, что сортировка строк - это просто способ достижения цели, то есть получить хэш, который не зависит от упорядочения строк в файле. Но ясно, что я бы хотел избежать стоимости 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
Что это лучший/быстрый способ сделать это?
Как отмечено в этом ответе, 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, потому что тогда мне не нужно разбить файл, и, таким образом, самым быстрым способом является сокращение фрагментов двоичных данных для обновления хэширования.
