Найти общие слова из двух файлов

Question

Учитывая два файла, содержащие список слов (около миллиона), нам нужно выяснить общие слова.

Использовать некоторый эффективный алгоритм, также недостаточно памяти (1 миллион, конечно, нет). Может помочь некоторый базовый код программирования на C.

Файлы не отсортированы ..Мы можем использовать какой-то алгоритм ... Пожалуйста, поддержите его базовым кодом ...

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

Любая игра для внешней сортировки файла ... Пожалуйста, поделитесь кодом для этого.

Answer 1

Еще один подход.

Общее . во-первых, обратите внимание, что выполнение этого последовательно занимает O(N^2). С N=1,000,000 это МНОГО. Сортировка каждого списка займет O(N*log(N)); затем вы можете найти пересечение за один проход путем объединения файлов (см. ниже). Таким образом, общая сумма составляет O(2N*log(N) + 2N) = O(N*log(N)).

Сортировка файла . Теперь давайте обратимся к тому факту, что работа с файлами намного медленнее, чем с памятью, особенно при сортировке, где необходимо перемещать объекты. Один из способов решить эту проблему - определить размер фрагмента, который можно загрузить в память. Загружайте файл по одному куску за раз, эффективно сортируйте и сохраняйте в отдельный временный файл. Сортированные фрагменты могут быть объединены (опять же, см. Ниже) в один отсортированный файл за один проход.

Слияние . Когда у вас есть 2 отсортированных списка (файлов или нет), вы можете легко объединить их в один отсортированный список за один проход: иметь 2 «указателя», изначально указывающих на первую запись в каждом списке. На каждом шаге сравнивайте значения, на которые указывают указатели. Переместите меньшее значение в объединенный список (тот, который вы строите) и продвиньте его указатель.

Вы можете легко изменить алгоритм слияния, чтобы он нашел пересечение - если указанные значения равны, переместите его к результатам (рассмотрите, как вы хотите работать с дубликатами).

Для объединения более 2 списков (как при сортировке файла выше) вы можете обобщить алгоритм для использования k указателей.

Answer 2

Если у вас было достаточно памяти, чтобы полностью прочитать первый файл в ОЗУ, я бы предложил прочитать его в словарь (слово -> индекс этого слова), перебрать слова второго файла и проверить, содержится ли словов этом словаре.Память на миллион слов сегодня невелика.

Если вам не хватает памяти, разбейте первый файл на части, которые помещаются в память, и выполните, как я сказал выше, для каждого из них.Например, заполните словарь первыми 100 000 слов, найдите каждое общее слово для этого, затем прочитайте файл во второй раз, извлекая слово от 100,001 до 200 000, найдите общие слова для этой части и т. Д.

А теперь сложная часть: вам нужна структура словаря, и вы сказали «базовый C».Когда вы готовы использовать «базовый C ++», существует структура данных hash_map, предоставляемая в качестве расширения стандартной библиотеки обычными поставщиками компиляторов.В базовом C вы также должны попытаться использовать готовую библиотеку для этого, прочитав этот пост SO * , чтобы найти ссылку на бесплатную библиотеку, которая, кажется, поддерживает это.

Answer 3

Я бы дал префикс деревья (иначе пытается ) выстрел.

Мой первоначальный подход состоял бы в определении максимальной глубины для дерева, которая бы хорошо вписывалась в мои пределы ОЗУ.Выберите произвольную глубину (скажем, 3, вы можете настроить ее позже) и создайте дерево до этой глубины для меньшего файла.Каждый лист представляет собой список «файловых указателей» на слова, которые начинаются с префикса, закодированного путем, по которому вы пошли, чтобы достичь листа.Эти «файловые указатели» сохраняют смещение в файле и длину слова.

Затем обрабатывают второй файл, читая каждое слово из него и пытаясь найти его в первом файле, используя созданное вами дерево.Это позволит вам быстрее потерпеть неудачу на словах, которые не соответствуют.Чем глубже ваша задача, тем быстрее вы можете потерпеть неудачу, но тем больше памяти вы бы потребляли.

Конечно, как сказал Стивен Чунг, вам все еще нужно ОЗУ для хранения достаточного количества информации, чтобы описать хотя бы один из файлов,если вам действительно нужен эффективный алгоритм.Если у вас недостаточно памяти - и, возможно, у вас ее нет, потому что, по моим оценкам, мой подход потребует примерно столько же памяти, сколько потребуется для загрузки файла, длина слова которого составляет 14-22 символа - тогда у вас естьобрабатывать даже первый файл по частям.В этом случае я бы порекомендовал использовать дерево для файла большего размера , а не для меньшего.Просто разбейте его на части, которые не больше, чем меньший файл (или не больше, чем позволяют ограничения вашей оперативной памяти), и выполните весь процесс, который я описал для каждой части.

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

Answer 4

Ваша проблема: учитывая два набора элементов, найдите промежуточное действие (элементы, общие для обоих), оставаясь в рамках ограничений нехватки ОЗУ (меньше, чем размер любого набора).

С момента нахожденияIntersaction требует сравнения / поиска каждого элемента в другом наборе, у вас должно быть достаточно оперативной памяти для хранения хотя бы одного из наборов (меньшего), чтобы иметь эффективный алгоритм.

Предположим, вы знаете, чтоintersaction намного меньше обоих наборов и полностью помещается в доступную память - в противном случае вам придется проделать дополнительную работу по сбросу результатов на диск.

Если вы работаете в условиях ограничений памяти, разбейте больше разбито на части, которые помещаются в 1/3 доступной памяти.Затем разделите набор меньший на части, соответствующие второй 1/3.Оставшаяся 1/3 памяти используется для хранения результатов.

Оптимизируйте, находя максимальные и минимальные значения раздела для набора большего .Это набор, который вы сравниваете с .Затем при загрузке соответствующего раздела из набора меньшего размера пропустите все элементы, находящиеся за пределами диапазона min-max.

Сначала найдите взаимодействие двух разделов через двойной цикл, сохраняя общие элементы длянабор результатов и удаление их из исходных наборов, чтобы сэкономить на сравнениях в дальнейшем.

Затем замените раздел в наборе меньший вторым разделом (пропуская элементы вне минимальногоМаксимум).Повторение.Обратите внимание, что раздел в наборе больше уменьшен - с уже удаленными общими элементами.

После прохождения всего набора меньшего повторите с следующим разделом больше .

Теперь, если вам не нужно сохранять два исходных набора (например, вы можете перезаписать оба файла), то вы можете выполнить дополнительную оптимизацию, удалив общие элементы с диска какЧто ж.Таким образом, эти элементы больше не нужно сравнивать в последующих разделах.Затем вы разбиваете наборы, пропуская удаленные.

Answer 5

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

with open(file1) as file_1:
  current_word_1 = read_to_delim(file_1, delim)
  while current_word_1:
    with open(file2) as file_2:
      current_word_2 = read_to_delim(file_2, delim)
      while current_word_2:
        if current_word_2 == current_word_1:
          print current_word_2
        current_word_2 = read_to_delim(file_2, delim)
    current_word_1 = read_to_delim(file_1, delim)

Я оставляю read_to_delim вам, но это крайний случай, который оптимален для памяти, но наименее оптимален по времени.

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