У меня есть два текстовых файла по 3 ГБ, в каждом файле около 80 миллионов строк. И они имеют 99,9% одинаковых строк (в файле А 60 000 уникальных строк, в файле Б 80 000 уникальных строк).
Как я могу быстро найти эти уникальные строки в двух файлах? Есть ли для этого готовые инструменты командной строки? Я использую Python, но полагаю, что найти эффективный метод Pythonic для загрузки файлов и сравнения будет сложнее.
Любые предложения приветствуются.
Если порядок имеет значение, попробуйте утилиту comm. Если порядок не имеет значения, sort file1 file2 | uniq -u.
diff?
- person bstpierre; 23.08.2010
diff обычно квадратична, а сортировка обычно n log n в среднем случае (быстрая сортировка).
- person tonfa; 23.08.2010
Я думаю, что это самый быстрый метод (будь то на Python или на другом языке, не должно иметь большого значения, IMO).
Примечания:
1. Я сохраняю хеш каждой строки только для экономии места (и времени, если может произойти пейджинг)
2. Из-за вышеизложенного я распечатываю только номера строк; если вам нужны настоящие строки, вам просто нужно снова прочитать файлы
3. Я предполагаю, что хеш-функция не приводит к конфликтам. Это почти, но не совершенно точно.
4. Я импортирую hashlib, потому что встроенная функция hash() слишком короткая, чтобы избежать конфликтов.
import sys
import hashlib
file = []
lines = []
for i in range(2):
# open the files named in the command line
file.append(open(sys.argv[1+i], 'r'))
# stores the hash value and the line number for each line in file i
lines.append({})
# assuming you like counting lines starting with 1
counter = 1
while 1:
# assuming default encoding is sufficient to handle the input file
line = file[i].readline().encode()
if not line: break
hashcode = hashlib.sha512(line).hexdigest()
lines[i][hashcode] = sys.argv[1+i]+': '+str(counter)
counter += 1
unique0 = lines[0].keys() - lines[1].keys()
unique1 = lines[1].keys() - lines[0].keys()
result = [lines[0][x] for x in unique0] + [lines[1][x] for x in unique1]
Имея 60 000 или 80 000 уникальных строк, вы можете просто создать словарь для каждой уникальной строки, сопоставив ее с числом. mydict["hello world"] => 1 и т. д. Если ваша средняя строка составляет около 40-80 символов, это будет около 10 МБ памяти.
Затем прочитайте каждый файл, преобразовав его в массив чисел через словарь. Они легко поместятся в памяти (2 файла по 8 байт * 3 ГБ / 60 тыс. строк меньше 1 МБ памяти). Затем diff списки. Вы можете инвертировать словарь и использовать его для печати текста строк, которые отличаются .
ИЗМЕНИТЬ:
В ответ на ваш комментарий вот пример сценария, который присваивает номера уникальным строкам при чтении из файла.
#!/usr/bin/python
class Reader:
def __init__(self, file):
self.count = 0
self.dict = {}
self.file = file
def readline(self):
line = self.file.readline()
if not line:
return None
if self.dict.has_key(line):
return self.dict[line]
else:
self.count = self.count + 1
self.dict[line] = self.count
return self.count
if __name__ == '__main__':
print "Type Ctrl-D to quit."
import sys
r = Reader(sys.stdin)
result = 'ignore'
while result:
result = r.readline()
print result
Если я правильно понимаю, вам нужны строки этих файлов без дубликатов. Это делает работу:
uniqA = set(open('fileA', 'r'))
В Python есть библиотека difflib, которая утверждает, что вполне конкурентоспособна с другими утилитами сравнения. См.: http://docs.python.org/library/difflib.html
