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

StackOverflow https://stackoverflow.com/questions/3926663

  •  30-09-2019
  •  | 
  •  

Вопрос

У меня есть два файла данных, 100 линий Char в каждом. Файл а: 108 строки, файл B: 106 линии И мне нужно найти все строки из файла B, которых нет в файле A.
Сначала я подумал о том, чтобы подавать оба файла в MySQL, но, похоже, он никогда не закончится создавать уникальный ключ на 108 записи

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

Это было полезно?

Решение

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

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

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

Другие советы

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

Для размеров, которые, как вы упоминаете, должны быть в состоянии сохранить все B в памяти одновременно, чтобы вы могли сделать упрощенную версию ответа Goldshteyn; что -то вроде этого в 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 Chars на строку на процессоре атома. Вывод из/usr/bin/время:

25.15user 0.27system 0:25.80elapsed 98%CPU (0avgtext+0avgdata 56032maxresident)k
0inputs+0outputs (0major+3862minor)pagefaults 0swaps
  60298   60298  509244
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top