Подтвердить что ты не робот

Печать уникальных строк файла 10 ГБ

У меня есть файл размером 10 ГБ с 200 миллионами строк. Мне нужно получить уникальные строки этого файла.

Мой код:

 while(<>) {
     chomp;
     $tmp{$_}=1;
 }
 #print...

У меня только 2 ГБ памяти. Как я могу решить эту проблему?

4b9b3361

ОТВЕТЫ

Ответ 1

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

Попробуйте базу данных Berkeley, которая используется для включения в Unix (BDB). Теперь он, по-видимому, принадлежит Oracle.

Perl может использовать модуль BerkeleyDB для общения с базой данных BDB. Фактически вы можете даже tie хеш файл Perl в базу данных BDB. Как только это будет сделано, вы можете использовать обычные хеши Perl для доступа и изменения базы данных.

BDB довольно устойчив. Биткойны используют его, а также SpamAssassin, поэтому очень возможно, что он может обрабатывать тип базы данных, которую вы должны создать, чтобы найти повторяющиеся строки. Если у вас уже установлен DBD, написание программы для обработки вашей задачи не займет много времени. Если это не сработает, вы бы не потратили слишком много времени на это.

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

Добавление

Возможно, я уже думал об этом...

Я решил попробовать простой хеш. Здесь моя программа:

#! /usr/bin/env perl
use strict;
use warnings;
use feature qw(say);
use autodie;

use constant DIR => "/usr/share/dict";

use constant WORD_LIST => qw(words web2a propernames connectives);

my %word_hash;
for my $count (1..100) {
    for my $file (WORD_LIST) {
        open my $file_fh, "<", DIR . "/$file";
        while (my $word = <$file_fh>) {
            chomp $word;
            $word_hash{"$file-$word-$count"} = $word;
        }
    }
}

Файлы, которые читаются, содержат в общей сложности около 313 000 строк. Я делаю это 100 раз, чтобы получить хэш с 31 300 000 ключей в нем. Это примерно так же неэффективно, как может быть. Каждый ключ будет уникальным. Объем памяти будет массивным. Тем не менее,...

Это сработало. Потребовалось около 10 минут, чтобы бежать, несмотря на массовую неэффективность программы, и она превысила около 6 гигабайт. Однако большая часть из них была в виртуальной памяти. Как ни странно, несмотря на то, что он работал, поглощая память и принимая 98% процессора, моя система не сильно замедляла все это. Наверное, вопрос в том, какой тип производительности вы ожидаете? Если вы потратите около 10 минут на выполнение, это не так уж и важно для вас, и вы не ожидаете, что эта программа будет использоваться так часто, а затем, может быть, пойти на простоту и использовать простой хеш.

Теперь я загружаю DBD из Oracle, компилирую его и устанавливаю. Я попробую одну и ту же программу, используя DBD, и посмотрю, что произойдет.

Использование базы данных BDB

После выполнения работы я думаю, что если у вас установлен MySQL, использование Perl DBI будет проще. Мне пришлось:

  • Загрузите Berkeley DB из Oracle, и вам нужна учетная запись Oracle. Я не помню свой пароль и сказал ему, чтобы отправить мне электронное письмо. Никогда не получал электронное письмо. Я потратил 10 минут, пытаясь запомнить мой адрес электронной почты.
  • После загрузки он должен быть скомпилирован. Найденные направления для компиляции для Mac, и это казалось довольно простым.
  • Запустился запуск CPAN. Заканчивается, что CPAN ищет /usr/local/BerkeleyDB, и он был установлен как /usr/local/BerkeleyDB.5.3. Создание ссылки устранило проблему.

Все сказали, около 1/2 часа, чтобы установить BerkeleyDB. После установки, изменение моей программы было довольно простым:

#! /usr/bin/env perl
use strict;
use warnings;
use feature qw(say);
use autodie;

use BerkeleyDB;

use constant {
    DIR       => "/usr/share/dict",
    BDB_FILE  => "bdb_file",
};

use constant WORD_LIST => qw(words web2a propernames connectives);

unlink BDB_FILE if -f BDB_FILE;

our %word_hash;
tie %word_hash, "BerkeleyDB::Hash",
    -Filename => BDB_FILE,
    -Flags    => DB_CREATE
        or die qq(Cannot create DBD_Database file ") . BDB_FILE . qq("\n);

for my $count (1..10) {
    for my $file (WORD_LIST) {
        open my $file_fh, "<", DIR . "/$file";
        while (my $word = <$file_fh>) {
            chomp $word;
            $word_hash{"$file-$word-$count"} = $word;
        }
    }
}

Все, что мне нужно было сделать, это добавить несколько строк.

Запуск программы был разочарованием. Это было не быстрее, но намного, намного медленнее. Это заняло более 2 минут, в то время как использование чистого хэша заняло всего 13 секунд.

Однако он использовал намного меньше памяти. В то время как старая программа сожрала гигабайты, версия BDB почти не использовала мегабайт. Вместо этого он создал файл базы данных 20 МБ.

Но, в эти дни ВМ и дешевая память, она что-то достигла? В старые времена перед виртуальной памятью и хорошей обработкой памяти программа разбивала бы ваш компьютер, если бы использовала всю память (и память измерялась в мегабайтах, а не в гигабайтах). Теперь, если ваша программа хочет больше памяти, чем доступно, ей просто предоставляется виртуальная память.

Итак, в конце концов, использование базы данных Berkeley не является хорошим решением. Все, что я сохранил во время программирования с помощью tie, было потрачено впустую на процесс установки. И это было медленно.

Использование BDB просто использовало DBD файл вместо памяти. Современная ОС будет делать то же самое и быстрее. Зачем работать, когда ОС будет обрабатывать его для вас?

Единственная причина использовать базу данных - если ваша система действительно не имеет необходимых ресурсов. 200 миллионов строк - большой файл, но современная ОС, вероятно, будет в порядке. Если ваша система действительно не имеет ресурса, используйте базу данных SQL в другой системе, а не базу данных DBD.

Ответ 2

Как я прокомментировал ответ Дэвида, база данных - это путь, но хороший может быть DBM::Deep с момента его чистого Perl и прост в установке и использование; его по существу хеш Perl привязан к файлу.

use DBM::Deep;
tie my %lines, 'DBM::Deep', 'data.db';

while(<>) {
    chomp;
    $lines{$_}=1;
}

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

Ответ 3

Если вы не заботитесь о сохранении порядка, я уверен, что следующее быстрее, чем ранее опубликованные решения (например, DBM:: Deep):

sort -u file

Ответ 4

Вы можете подумать о вычислении хэш-кода для каждой строки и отслеживании (хеширования, позиции) сопоставлений. Для этого вам не нужна сложная хеш-функция (или даже большой хэш); на самом деле "меньший" лучше, чем "более уникальный", если основной проблемой является использование памяти. Даже CRC, или суммирование кодов символов, может сделать. Дело не в том, чтобы гарантировать уникальность на данном этапе - это просто сузить кандидатские матчи с 200 миллионов до нескольких десятков.

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

Заметьте, я говорю "позиция", а не "номер строки". Чтобы это работало менее чем за год, вы почти наверняка должны были бы искать право на линию, а не находить свой путь к строке # 1392499.

Ответ 5

Если вам не нужны ограничения времени /IO, а также ограничения на диске (например, у вас есть еще 10 ГБ пространства), вы можете сделать следующий немой алгоритм:

1) Прочитайте файл (похоже, он имеет 50 символов). При сканировании, запомните самую длинную длину строки $L.

2) Проанализируйте первые 3 символа (если вы знаете, что char # 1 идентичен - скажите "[" - проанализируйте 3 символа в позиции N, которые могут иметь более разнообразные).

3) Для каждой строки с 3 символами $XYZ добавьте эту строку в файл 3char. $XYZ и сохраните количество строк в этом файле в хеше.

4) Если весь ваш файл разбит таким образом, у вас должен быть целая группа (если файлы имеют только AZ, а затем 26 ^ 3) меньших файлов и не более 4 файлов, размер которых составляет > 2 ГБ.

5) Переместите исходный файл в папку "Обработанный".

6) Для каждого из больших файлов ( > 2 ГБ) выберите следующие 3 символьные позиции и повторите шаги # 1- # 5 с новыми файлами 6char. $XYZABC

7) Намочите, промойте, повторите. В итоге вы получите один из двух вариантов:

8a) Букет из меньших файлов, каждый из которых имеет размер менее 2 ГБ, все из которых имеют разные строки, и каждый (из-за его размера) может обрабатываться индивидуально стандартным решением "ставить в хэш" в вашем вопросе.

8b) Или, большинство файлов меньше, но вы превысили все символы $L, повторяя шаг 7 для файлов > 2 ГБ, и у вас все еще есть от 1 до 4 больших файлов. Угадайте, что - с эти до четырех больших файлов имеют одинаковые символы в файле в позициях 1.. $L, их также можно обрабатывать с помощью метода "stash into a hash" в вашем вопросе, поскольку они не будут содержать больше, чем несколько различных линий, несмотря на их размер!

Обратите внимание, что это может потребовать - при наихудших возможных дистрибутивах - 10GB * L / 3 дискового пространства, но ТОЛЬКО потребуется 20 ГБ дискового пространства, если вы измените шаг 5 с "move" на "delete".

Voila. Готово.

В качестве альтернативного подхода рассмотрите хеширование ваших строк. Я не эксперт по хэшированию, но вы должны иметь возможность сжимать строку в хэш-листе в 5 раз больше ИМХО.

Если вы хотите представить себе это, вы будете проводить частотный анализ последовательностей символов на первом проходе, а затем делать сжатие/кодирование таким образом.

Ответ 6

Если у вас больше процессора и у вас есть свободное место на 15 ГБ и ваше хранилище достаточно быстро, вы можете попробовать это. Это будет обрабатываться в паралеле.

split --lines=100000 -d 4 -d input.file
find . -name "x*" -print|xargs -n 1 -P10 -I SPLITTED_FILE sort -u SPLITTED_FILE>unique.SPLITTED_FILE
cat unique.*>output.file
rm unique.* x*

Ответ 7

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

Для этого может потребоваться некоторое время, но если вы ограничены в памяти, тогда работа над файлом и работа над его частями будут работать.

Возможно, можно выполнить сравнение при записи файла, но это будет немного сложнее.

Ответ 8

Зачем использовать perl для этого? posix shell:

sort | uniq

сделано, отпустите пиво пива.