Повышение производительности при работе с огромным файлом

10

У меня есть FILE_A, который имеет более 300 000 строк и FILE_B, который имеет более 30 миллионов строк. Я создал скрипт Bash, который обрабатывает каждую строку в FILE_A над FILE_B и записывает результат grep в новый файл.

Весь этот процесс занимает более 5 часов.

Как я могу улучшить производительность моего скрипта?

Я использую в grep -F -m 1качестве команды grep. FILE_A выглядит так:

123456789 
123455321

и FILE_B выглядит так:

123456789,123456789,730025400149993,
123455321,123455321,730025400126097,

Поэтому в Bash у меня есть whileцикл, который выбирает следующую строку в FILE_A и отображает ее в FILE_B. Когда шаблон найден в FILE_B, я записываю его в файл result.txt.

while read -r line; do
   grep -F -m1 $line 30MFile
done < 300KFile
rogerio_marcio
источник

Ответы:

17

Попробуйте использовать grep --file==FILE_A. Он почти наверняка загружает шаблоны в память, то есть сканирует FILE_B только один раз.

grep -F -m1 --file==300KFile 30MFile
Горт Робот
источник
Это будет работать только при условии, что у меня достаточно памяти, верно?
rogerio_marcio
Честно говоря, я сам не пробовал это на файлах такого размера, но я считаю, что это значительно повысит вашу скорость. Если вы работаете на современном компьютере, у вас не должно возникнуть проблем с сохранением файла 300 КБ в памяти. (Или 30M один в этом отношении.)
Gort Робот
когда я использовал опцию -f (--file), он в основном воссоздал 30MFile. Я делаю что-то неправильно?
rogerio_marcio
Хм ... может быть, в файле 300K есть пустая строка?
Gort the Robot
прямо на месте! это было это! это сработало отлично, это закончилось за 30 секунд! благодарю вас!!
rogerio_marcio
2

Вот Perl ответ для потомков. Я обычно делаю это для сопоставления 1М строк с 30-35М линиями. Это займет около 10 секунд, чтобы закончить.

Сначала хешируем FILE_A:

my %simple_hash;
open my $first_file, '<', 'FILE_A' or die "What have you done?! $!";
while (<$first_file>) {
  chomp;                 ## Watch out for Windows newlines
  $simple_hash{$_} = 1;  ## There may be an even faster way to define this
}
close $first_file;

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

open my $second_file, '<', 'FILE_B' or die "Oh no, not again.. $!";
while (<$second_file>) {
  my ($col1, undef) = split ',';
  if (exists($simple_hash{$col1}) {
    print $_;
  }
}
close $second_file;

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

Mintx
источник
1

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

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

Вся процедура выполняется за время O (n + Nm), если n - это длина FILE_B, Nэто количество строк в, FILE_Aа m - это длина самой длинной строки в FILE_A- это, по сути, линейное время выполнения. Превосходит квадратичное время, необходимое вашему первоначальному подходу, по величинам.

Рафаэль
источник
1

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

--mmap If  possible, use the mmap(2) system call to read input, instead
      of the default read(2) system call.  In some situations,  --mmap
      yields  better performance.  However, --mmap can cause undefined
      behavior (including core dumps) if an input file  shrinks  while
      grep is operating, or if an I/O error occurs.

Смотрите это или это для получения дополнительной информации о mmap.

Рамзи Кахил
источник
Я определенно собираюсь дать этому шанс, и я дам вам знать, как это происходит. Насколько вероятно, что я столкнусь с дампом ядра?
rogerio_marcio
@rogerio_marcio Ну, как я понимаю, «если файл сжимается во время работы grep или если возникает ошибка ввода-вывода». Не совсем вероятно, но вы должны знать это лучше. (Если, как я полагаю, файл не тронут, а grep - этого не должно быть)
Рамзи Кахил
Для проверки, что --mmapдоза ничего не сбрасывает, я бы порекомендовал пробежать с --mmap, а один без. А затем используйте, wcчтобы увидеть, что у вас одинаковое количество выходных данных - это должен быть надежный тест, учитывая, что мы выполнили 2 раза grep, и только флаг отличался.
Рамзи Кахил
@rogerio_marcio Вы пробовали это? Есть идеи?
Рамзи Кахил
-1

почему бы вам не поместить этот файл в базу данных? Базы данных действительно хороши в эффективном объединении, хэше, вложенном цикле, как это. И они действительно хороши в использовании виртуальной памяти

Энди Смит
источник
Все, что вы делаете со всеми остальными ответами - это заново изобретаете колесо базы данных
Andyz Smith