Удалите дубликаты из двух больших текстовых файлов, используя unordered_map

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

У меня есть два больших текстовых файла, около 160 МБ каждый (около 700000 строк каждый). Мне нужно удалить из файла2 все повторяющиеся строки, которые появляются в файле1. Для этого я решил использовать unordered_map со строкой из 32 символов в качестве ключа. Строка из 32 символов — это первые 32 символа каждой строки (этого достаточно для уникальной идентификации строки).

В любом случае, я просто просматриваю первый файл и помещаю 32-символьную подстроку каждой строки в unordered_map. Затем я просматриваю второй файл и проверяю, существует ли строка в файле2 в моем файле unordered_map. Если он не существует, я записываю полную строку в новый текстовый файл.

Это отлично работает для файлов меньшего размера (по 40 МБ каждый), но для этих файлов размером 160 МБ требуется очень много времени для вставки в хэш-таблицу (прежде чем я даже начну смотреть файл2). Около 260 000 вставок... кажется, что он остановился или работает очень медленно. Возможно ли, что я достиг предела памяти? Если да, то может ли кто-нибудь объяснить, как это вычислить? Если нет, есть ли что-то еще, что я мог бы сделать, чтобы сделать это быстрее? Может быть, выбрать пользовательскую хэш-функцию или указать некоторые параметры, которые помогут ее оптимизировать?

Моя ключевая пара объектов в хеш-таблице — это (string, int), где длина строки всегда составляет 32 символа, а int — это счетчик, который я использую для обработки дубликатов. Я использую 64-битную ОС Windows 7 с 12 ГБ оперативной памяти.

Любая помощь будет принята с благодарностью.. спасибо, ребята!!


c++ unordered-map tr1
person ntsue    schedule 13.06.2011    source источник
comment
Убедитесь, что вы не используете operator [] при проходе через второй файл, иначе размер карты будет увеличиваться без необходимости.   -  person Mark Ransom    schedule 13.06.2011

Ответы (2)


arrow_upward
3
arrow_downward

Вам не нужна карта, потому что у вас нет ассоциативных данных. Неупорядоченный набор сделает эту работу. Кроме того, я бы выбрал реализацию набора хэшей с эффективным использованием памяти, например sparse_hash_set< /а>. Он очень эффективно использует память и может хранить содержимое на диске.

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

person Community    schedule 13.06.2011
comment
Чтобы немного перефразировать ваше второе предложение, вы хотите разбить первый файл на 10 блоков, а затем сделать 10 проходов по второму файлу. - person Mark Ransom; 13.06.2011

arrow_upward
0
arrow_downward

Я бы не стал писать для этого программу на C++, а воспользовался бы некоторыми существующими утилитами. В Linux, Unix и Cygwin выполните следующие действия:

cat два файла в 1 большой файл:

# cat file1 file2 > file3

Используйте sort -u для извлечения уникальных строк:

# sort -u file3 > file4

Предпочитайте использовать утилиты операционной системы, а не (пере)писывать свои собственные.

person Thomas Matthews    schedule 13.06.2011
comment
Хорошая идея, но она не соответствует спецификации. Уникальные строки должны исходить только из файла file2. Предположительно они должны быть и в первоначальном порядке, хотя об этом не говорится. - person Mark Ransom; 13.06.2011
comment
Марк правильный. Строки должны исходить только из файла2. Есть ли способ использовать эти системные утилиты с этим ограничением? - person ntsue; 13.06.2011