Если вы ничего не знаете о структуре файлов (например, отсортированы они или нет), есть много разных подходов, которые вы можете использовать для решения проблемы, в зависимости от ваших ограничений памяти иИспользование пространства, возможно, то, что вы ищете.
Если у вас есть свободные объемы оперативной памяти, одним из вариантов будет создание в памяти хеш-таблицы для хранения строк.Затем вы можете загрузить все строки из первого файла в хеш-таблицу.Затем загрузите каждую строку из второго файла по одной за раз.Для каждой строки проверьте, находится ли она в хеш-таблице.Если так, сообщите о совпадении.Этот подход использует O (m) памяти (где m - количество строк в первом файле) и занимает не менее Ω (m + n) времени и, возможно, больше, в зависимости от того, как работает хеш-функция.Это также (почти наверняка) самый простой и прямой способ решения проблемы.
Если у вас мало доступной оперативной памяти, но время не слишком ограничивает, вы можете использовать модифицированную версиюэто первый алгоритм.Выберите количество строк для загрузки из первого файла.Затем загрузите только эти строки в хеш-таблицу.Сделав это, отсканируйте весь второй файл, чтобы найти совпадения.Затем удалите все строки из хеш-таблицы и загрузите следующий набор строк из первого файла и повторите.Это имеет время выполнения Ω (mn / b), где b - размер блока (так как есть O (m / b) итераций полного линейного сканирования всех n байтов во втором файле).В качестве альтернативы, если вы знаете, что один файл намного меньше другого, вам может потребоваться просто загрузить весь этот файл в память и затем сканировать другой файл.
Если у вас мало доступной оперативной памяти, ноу вас есть возможность использовать больше дискового пространства, одним из вариантов может быть использование внешнего алгоритма сортировки для сортировки каждого из двух файлов (или, по крайней мере, создание каталога со списком строк каждого файла вотсортированный порядок).После того как файлы отсортированы, вы можете параллельно сканировать их, находя все совпадения.При этом используется более общий алгоритм поиска всех дублированных элементов в двух отсортированных диапазонах, который работает следующим образом:
- Отслеживайте два индекса, один в первом списке и один во втором списке, чтобы обаначинаются с нуля.
- В то время как в обоих списках остались пункты:
- Если элементы по соответствующим индексам совпадают, сообщить о совпадении.
- В противном случае, если элемент в первомсписок меньше, чем элемент во втором списке, увеличьте индекс до первого списка.
- В противном случае увеличьте индекс второго списка.
Этот алгоритм потребовал бы приблизительно O (n log n) времени для сортировки двух файлов, а затем провел бы O (n) сравнений, чтобы выполнить работу по поиску общих элементов в списках.Однако, поскольку сравнения строк не обязательно выполняются за время O (1) (на самом деле они часто занимают гораздо больше времени), фактическое время выполнения для этого может быть намного больше.Если мы предположим, что каждый файл состоит из n строк длины m, тогда время выполнения для сортировки будет O (mn log n), поскольку каждое сравнение занимает O (m) время.Аналогично, этап сравнения может занять время O (mn), поскольку сравнение каждой строки также может занимать время O (m).В качестве возможной оптимизации вы можете рассмотреть возможность вычисления небольшого хеш-кода (скажем, 16 или 32 бита).Предполагая, что хеш-код обеспечивает хорошую однородность, это может значительно сократить время, необходимое для сравнения строк, поскольку большинство неидентичных строк будут иметь разные хеш-коды и могут сравниваться за время O (1).
Наконец, если каждая строка файла достаточно длинная (скажем, не менее 8 символов), одним из вариантов может быть вычисление 64-разрядного или большего значения хеш-функции для каждой из строк файлов. Затем вы можете использовать любой из вышеперечисленных методов, чтобы попытаться увидеть, повторяются ли какие-либо хеш-коды в двух файлах (хранение всего в хеш-таблице, использование внешней сортировки и т. Д.). Предполагая, что в вашем хэш-коде достаточно битов, количество конфликтов должно быть небольшим, и вы сможете быстро находить совпадения и использовать гораздо меньше памяти.
Надеюсь, это поможет!
Woohoo! Это мой 1000-й ответ по переполнению стека! : -)