Оптимизация sed (модификация большого файла на основе меньшего набора данных) - PullRequest
8 голосов
/ 11 мая 2009

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

Моя последняя задача связана с редактированием строк на основе данных из другого файла.

Файл данных (который должен быть изменен) содержит 1500000 строк, каждая из которых, например, 800 символов в длину. Каждая строка уникальна и содержит только один идентификационный номер, каждый идентификационный номер уникален)

Файл модификатора, например, Длина 1800 строк, содержит идентификационный номер, сумму и дату, которые должны быть изменены в файле данных.

Я только что преобразовал (с помощью Vim regex) файл модификатора в sed, но он очень неэффективен.

Допустим, у меня есть такая строка в файле данных:

(some 500 character)id_number(some 300 character)

И мне нужно изменить данные в части с 300 символами.

Основываясь на файле модификатора, я придумываю строки sed, такие как:

/id_number/ s/^\(.\{650\}\).\{20\}/\1CHANGED_AMOUNT_AND_DATA/

Итак, у меня есть 1800 строк, подобных этой.

Но я знаю, что даже на очень быстром сервере, если я сделаю

sed -i.bak -f modifier.sed data.file

Это очень медленно, потому что он должен прочитать каждый шаблон x каждую строку.

Нет лучшего способа?

Примечание: Я не программист, никогда не изучал (в школе) алгоритмы. Я могу использовать awk, sed, устаревшую версию perl на сервере.

Ответы [ 6 ]

6 голосов
/ 11 мая 2009

Мои предлагаемые подходы (в порядке желательности) заключаются в обработке этих данных как:

  1. База данных (даже простая база данных на основе SQLite с индексом будет работать намного лучше, чем sed / awk для файла объемом 10 ГБ)
  2. Плоский файл с фиксированной длиной записи
  3. Плоский файл, содержащий переменную длину записи

Использование базы данных заботится обо всех тех мелких деталях, которые замедляют обработку текстовых файлов (поиск нужной вам записи, изменение данных, сохранение их обратно в БД). Взгляните на DBD :: SQLite в случае Perl.

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

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

3 голосов
/ 11 мая 2009

Я предлагаю вам программу, написанную на Perl (поскольку я не гуру sed / awk, и я не знаю, на что они способны).

Ваш «алгоритм» прост: вам нужно сначала создать хеш-карту, которая может дать вам новую строку данных для применения к каждому идентификатору. Это достигается чтением файла модификатора, конечно.

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

Я тоже не гуру Perl, но я думаю, что программа довольно проста. Если вам нужна помощь, чтобы написать это, попросите об этом: -)

2 голосов
/ 11 мая 2009

В perl вы должны использовать substr для получения id_number, особенно если id_number имеет постоянную ширину.

my $id_number=substr($str, 500, id_number_length);

После этого, если $ id_number находится в диапазоне, вы должны использовать substr для замены оставшегося текста.

substr($str, -300,300, $new_text);

Регулярные выражения Perl очень быстрые, но не в этом случае.

1 голос
/ 17 мая 2009

Я предлагаю не использовать базу данных. Хорошо написанный сценарий Perl будет превосходить базу данных в таком порядке. Поверьте мне, у меня есть много практического опыта с этим. Вы не будете импортировать данные в базу данных, когда Perl будет завершен.

Когда вы пишете 1500000 строк с 800 символами, мне кажется, что это 1,2 ГБ. Если у вас очень медленный диск (30 МБ / с), вы прочитаете его за 40 секунд. С лучшими 50 -> 24 с, 100 -> 12 с и так. Но скорость поиска perl hash (например, db join) на 2 ГГц процессоре выше 5Mlookups / s. Это означает, что работа, связанная с вашим ЦП, займет несколько секунд, а работа, связанная с вводом-выводом, - за десятки секунд. Если это действительно 10 ГБ, номера изменятся, но пропорция будет такой же.

Вы не указали, меняет ли модификация данных размер или нет (если модификация может быть выполнена на месте), поэтому мы не будем предполагать это и будем работать как фильтр. Вы не указали, в каком формате находится ваш «файл модификатора» и какие модификации. Предположим, что он разделен табуляцией чем-то вроде:

<id><tab><position_after_id><tab><amount><tab><data>

Мы будем читать данные из stdin и записывать в stdout, а скрипт может выглядеть примерно так:

my $modifier_filename = 'modifier_file.txt';

open my $mf, '<', $modifier_filename or die "Can't open '$modifier_filename': $!";
my %modifications;
while (<$mf>) {
   chomp;
   my ($id, $position, $amount, $data) = split /\t/;
   $modifications{$id} = [$position, $amount, $data];
}
close $mf;

# make matching regexp (use quotemeta to prevent regexp meaningful characters)
my $id_regexp = join '|', map quotemeta, keys %modifications;
$id_regexp = qr/($id_regexp)/;     # compile regexp

while (<>) {
  next unless m/$id_regexp/;
  next unless $modifications{$1};
  my ($position, $amount, $data) = @{$modifications{$1}};
  substr $_, $+[1] + $position, $amount, $data;
}
continue { print }

На моем ноутбуке требуется около полуминуты для 1,5 миллиона строк, 1800 идентификаторов поиска, 1,2 ГБ данных. Для 10GB это не должно быть более 5 минут. Это достаточно быстро для вас?

Если вы начинаете думать, что вы не привязаны к IO (например, если используете какое-то NAS), но привязаны к процессору, вы можете пожертвовать некоторой читабельностью и перейти к этому:

my $mod;
while (<>) {
  next unless m/$id_regexp/;
  $mod = $modifications{$1};
  next unless $mod;
  substr $_, $+[1] + $mod->[0], $mod->[1], $mod->[2];
}
continue { print }
0 голосов
/ 12 мая 2009

Хорошая сделка по решению sqlloader или datadump. Это путь.

0 голосов
/ 12 мая 2009

Вы почти наверняка должны использовать базу данных, как MikeyB предложил .

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

Если вы дойдете до того, что даже список изменений станет огромным, вам нужно отсортировать оба файла по их идентификаторам, а затем выполнить объединение списка - в основном:

  1. Сравните идентификатор в верхней части входного файла с идентификатором в верхней части файла изменений.
  2. Откорректируйте запись соответствующим образом, если они совпадают
  3. Запиши это
  4. Отбросить "верхнюю" строку из того файла, который имеет (в алфавитном или числовом виде) самый низкий идентификатор, и прочитать другую строку из этого файла
  5. Перейти к 1.

За кулисами база данных почти наверняка будет использовать объединение списков, если вы выполните это изменение с помощью одной команды SQL UPDATE.

...