Сортировка и поиск больших данных

Question

У меня есть два файла данных, по 100 строк символов в каждом.Файл A: 10 ⁸ строк, файл B: 10 ⁶ строк.И мне нужно найти все строки из файла B, которых нет в файле A.
Сначала я думал о том, чтобы передать оба файла в mysql, но похоже, что он никогда не завершит создание уникального ключа в 10 * 1006.* 8 records.

Я жду ваших предложений по этому вопросу.

Answer 1

Вы можете выполнить эту операцию без базы данных.Ключ в том, чтобы уменьшить размер A, так как A намного больше, чем B. Вот как это сделать:

Вычисление 64-битных хешей с использованием приличной хеш-функции для строк в B-файле.Сохраните их в памяти (в хеш-таблице), что вы можете сделать, потому что B мало.Затем построчно хэшируйте все строки в вашем A-файле и посмотрите, соответствует ли каждая из них хеш-функции для вашего B-файла.Любые строки с совпадающими хэшами (по одному из B) должны храниться в файле C.

Когда этот процесс завершится, файл C будет иметь небольшое подмножество A потенциально совпадающих строк (до B).Теперь у вас есть гораздо меньший файл C, с которым вам нужно сравнить строки B.Это сводит проблему к проблеме, когда вы можете фактически загрузить все строки из C в память (как хеш-таблицу) и сравнить каждую строку B, чтобы увидеть, находится ли она в C.

Answer 2

Вы можете немного улучшить ответ @ michael-goldshteyn (https://stackoverflow.com/a/3926745/179529). Так как вам нужно найти все строки в B, которых нет в A, вы можете удалить любой элемент из Hash Table элементов B , когда вы сравниваете и находите соответствие для него с элементами в A. Элементы, которые останутся в Хэш-таблице, являются элементами, которые не были найдены в файле A.

Answer 3

Для размеров, которые вы упомянули, вы должны иметь возможность хранить все B в памяти одновременно, чтобы вы могли сделать упрощенную версию ответа Гольдштейна;что-то вроде этого в python:

#!/usr/bin/python3

import sys

if __name__=='__main__':
  b = open(sys.argv[2],'r')
  bs = set()
  for l in b:
    bs.add(l.strip())
  b.close()
  a = open(sys.argv[1],'r')
  for l in a:
    l = l.strip()
    if l in bs:
      bs.remove(l)
  for x in bs:
    print(x)

Я проверил это на двух файлах размером 10 ^ 5 и 10 ^ 7 с ~ 8 символами на строку на атомном процессоре.Вывод из / usr / bin / time:

25.15user 0.27system 0:25.80elapsed 98%CPU (0avgtext+0avgdata 56032maxresident)k
0inputs+0outputs (0major+3862minor)pagefaults 0swaps
  60298   60298  509244