Эффективный и точный способ сжатия и сравнения списков Python?

Question

Я пытаюсь сделать несколько сложную разницу между отдельными строками в двух файлах CSV. Мне нужно убедиться, что строки из одного файла не появятся в другом файле, но мне не дают никакой гарантии порядка строк в обоих файлах. В качестве отправной точки я пытался сравнить хэши строковых представлений строк (то есть списков Python). Например:

import csv

hashes = []
for row in csv.reader(open('old.csv','rb')):
  hashes.append( hash(str(row)) )

for row in csv.reader(open('new.csv','rb')):
  if hash(str(row)) not in hashes:
    print 'Not found'

Но это с треском проваливается. Я ограничен искусственно наложенными ограничениями памяти, которые я не могу изменить, и поэтому я использовал хеш-коды вместо непосредственного хранения и сравнения списков. Некоторые файлы, которые я сравниваю, могут иметь размер сотен мегабайт . Любые идеи для способа точного сжатия списков Python, чтобы их можно было сравнить с точки зрения простого равенства с другими списками? То есть система хеширования, которая на самом деле работает? Бонусные баллы : почему не работает вышеуказанный метод?

EDIT:

Спасибо за все замечательные предложения! Позвольте мне уточнить некоторые вещи. «Несчастный сбой» означает, что две строки с одинаковыми данными после считывания объектом CSV.reader не хешируют одно и то же значение после вызова str объекта списка. Я попробую hashlib в некоторых предложениях ниже. Я также не могу сделать хэш для необработанного файла, так как две строки ниже содержат одинаковые данные, но разные символы в строке:

1, 2.3, David S, Monday
1, 2.3, "David S", Monday

Я также уже занимаюсь такими вещами, как разбор строк, чтобы сделать данные более однородными, но, похоже, это бесполезно. Я не ищу чрезвычайно умной логики сравнения, то есть 0 совпадает с 0.0.

РЕДАКТИРОВАТЬ 2:

Проблема решена. Что в основном сработало, так это то, что мне нужно было немного больше предварительного форматирования, например, конвертировать целые и плавающие числа и т. Д. И Мне нужно было изменить функцию хеширования. Оба эти изменения, казалось, сделали работу для меня.

Answer 1

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

Единственная причинапочему я могу представить, что вышеприведенное не работает так, как написано, потому что ваша хеш-функция не всегда дает одинаковый вывод для данного ввода.Вы можете проверить, что второй прогон old.csv генерирует тот же список.Это может иметь отношение к ошибочным пробелам, символам табуляции вместо пробелов, разной капитализации, «автоматическому

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

После того, как вы заполните свою переменную hashes, вам следует рассмотреть возможность преобразования ее в набор (hashes = set(hashes)), чтобы ваши поиски могли выполняться быстрее, чем линейные.

Answer 2

Учитывая слабое синтаксическое определение CSV, возможно, что две строки будут семантически равны, но при этом лексически различны. Различные определения диалекта дают две подсказки, как два ряда могут быть индивидуально правильно сформированы, но несопоставимы. И этот пример показывает, как они могут быть на одном диалекте, а не на строковом эквиваленте:

0, 0
0, 0.0

Дополнительная информация поможет лучше ответить на ваш вопрос.

Answer 3

Я почти уверен, что строка «неудачно провал» относится к провалу во времени, который происходит из-за того, что ваш текущий алгоритм равен O (N ^ 2), что довольно плохо для определения размера ваших файлов. Как уже упоминалось, вы можете использовать set для решения этой проблемы (станет O (N)) или, если по какой-то причине вы не можете этого сделать, вы можете отсортировать список хэшей и использовать бинарный поиск на нем (станет O (N log N), что также выполнимо. Вы можете использовать модуль bisect, если идете по пути двоичного поиска.

Также было упомянуто, что у вас может быть проблема столкновения в хешах: две строки дают один и тот же хеш, когда строки не совсем одинаковые. Если вы обнаружите, что это проблема, с которой вы столкнулись, вам нужно будет хранить информацию с каждым хешем о том, где искать строку, соответствующую хешу в файле old.csv, а затем искать строку и сравнивать две строки.

Альтернативой вашему текущему методу является предварительная сортировка двух файлов (возможно, с использованием сортировки слиянием на диске или сортировки оболочки) и, сохраняя указатели на строки в каждом файле, сравнивают две строки. Проверьте, совпадают ли они, а если нет, продвиньте линию, которая измеряется как меньшая. Этот алгоритм также является O (N log N), если для сортировки используется метод O (N log N). Сортировку также можно выполнить, поместив каждый файл в базу данных и отсортировав базу данных.

Answer 4

Потребуется больше информации о том, что именно означает «неудача». Если вы просто не получаете правильное сравнение между ними, возможно, Hashlib может решить эту проблему.

Раньше у меня возникали проблемы при использовании встроенной хэш-библиотеки, и я решил ее с помощью этого.

Редактировать: Как кто-то предложил в другом посте, проблема может заключаться в предположении, что два файла должны иметь точно такую ​​же строку. Возможно, вы захотите попытаться выполнить синтаксический анализ полей csv и добавить их в строку с одинаковым форматированием (возможно, обрезать пробелы, принудительно вводить строчные буквы и т. Д.) Перед вычислением хэша.

Answer 5

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

Answer 6

Вы должны сказать, в чем ваша проблема на самом деле.Ваше описание «Мне нужно убедиться, что строка из одного файла не появляется в другом файле», соответствует телу вашего второго цикла if hash(...) in hashes: print "Found (an interloper)", а не тому, что у вас есть.

Мы не можемскажите вам, «почему не работает вышеуказанный метод», потому что вы не сказали нам, каковы симптомы «с треском провалились» и «не сработали».

Answer 7

Вероятно, это проблема с (неправильным) использованием hash. См. этот ТАК вопрос ; Как показывают ответы, вы, вероятно, захотите hashlib.