Оптимизация удаления повторяющихся строк из большого файла

Question

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

file = open("sample.txt") 

output = [] 
alreadyseen = set()  

while True: 
    lines = file.readlines(100000) 
    if not lines: 
     break 
    for line in lines: 
     pass # do something 
     if line not in alreadyseen: 
      output.append(line) 
      alreadyseen.add(line) 
    print(output) 

Answer 1

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

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

Второй заключается в замене криптографического хэша на более длинную строку. Хэш будет фиксированным размером, независимо от того, как долго длится сама строка. Если вы беспокоитесь о возможности двух строк, производящих один и тот же хэш, не будьте - с достаточно большим хэшем вероятность того, что две строки, производящие один и тот же хеш, будут меньше вероятности сбой RAM, что позволяет использовать две разные строки сравните равные, даже принимая во внимание birthday paradox.

Сочетание обоих подходов выглядит примерно так:

import hashlib 

sha256 = hashlib.sha256() 
alreadyseen = set() 
with open("sample.txt") as file: 
    for line in file: 
     pass # do something 
     key = line if len(line) < 32 else sha256(line) 
     if key not in alreadyseen: 
      alreadyseen.add(key) 
      print(line) 

Answer 2

записи во временный файл, чтобы избежать хранения всех строк в списке, то просто заново как файлы, так и обновить file1 с содержанием file2:

alreadyseen = set() 
with open(file_1) as f1, open(file_2, "w") as f2: 
    while True: 
     lines = f1.readlines(100000) 
     if not lines: 
      break 
     for line in lines: 
      pass # do something 
      if line not in alreadyseen: 
       f2.write(line) 
       alreadyseen.add(line) 

with open(file1, "w") as f1, open(file_2) as f2: 
    for line in f2: 
     f1.write(line)