Как сделать этот скрипт Sed быстрее?

Question

Я унаследовал этот фрагмент сценария sed, который пытается удалить определенные пустые места:

s/[\s\t]*|/|/g
s/|[\s\t]*/|/g
s/[\s] *$//g
s/^|/null|/g

, который работает с файлом размером около 1 ГБ.Этот скрипт работает в течение 2 часов на нашем Unix-сервере.Есть идеи, как это ускорить?

Отмечает, что \ s обозначает пробел, а \ t обозначает вкладку, фактический скрипт использует фактическое пространство и символ табуляции, а не эти символыФайл представляет собой файл с разделителями каналов и находится локально, а не в сети.4 строки находятся в файле, который выполняется с помощью sed -f

Answer 1

Лучшее, что я смог сделать с помощью sed, - это скрипт:

s/[\s\t]*|[\s\t]*/|/g
s/[\s\t]*$//
s/^|/null|/

В моих тестах это работало примерно на 30% быстрее, чем ваш скрипт sed. Увеличение производительности происходит за счет объединения первых двух регулярных выражений и отсутствия флага «g» там, где он не нужен.

Тем не менее, 30% -ное ускорение - это лишь незначительное улучшение (для запуска вышеуказанного сценария в вашем файле данных объемом 1 ГБ все равно потребуется около полутора часов). Я хотел посмотреть, смогу ли я сделать что-нибудь лучше.

В конце концов, ни один другой метод, который я пробовал (awk, perl и другие подходы с помощью sed), не оказался лучше, за исключением, конечно, простой реализации на C. Как и следовало ожидать от C, код немного многословен для публикации здесь, но если вы хотите, чтобы программа работала быстрее, чем любой другой метод, вы можете взглянуть на нее .

В моих тестах реализация C завершается примерно за 20% времени, необходимого для вашего сценария sed. Поэтому запуск вашего сервера Unix может занять около 25 минут.

Я не тратил много времени на оптимизацию реализации C. Без сомнения, есть ряд мест, где алгоритм может быть улучшен, но, честно говоря, я не знаю, можно ли сэкономить значительное количество времени сверх того, что он уже достиг. Во всяком случае, я думаю, что это определенно накладывает верхний предел на то, какую производительность вы можете ожидать от других методов (sed, awk, perl, python и т. Д.).

Редактировать: В оригинальной версии была небольшая ошибка, из-за которой в конце вывода могла быть напечатана неправильная вещь (например, могла выводиться ноль, которой там быть не должно). Сегодня у меня было время взглянуть на это и исправить это. Я также оптимизировал вызов на strlen(), что дало ему еще один небольшой прирост производительности.

Answer 2

Мое тестирование показало, что sed может довольно легко привязаться к процессору на чем-то подобном. Если у вас многоядерный компьютер, вы можете попробовать запустить несколько процессов sed с помощью скрипта, который выглядит примерно так:

#!/bin/sh
INFILE=data.txt
OUTFILE=fixed.txt
SEDSCRIPT=script.sed
SPLITLIMIT=`wc -l $INFILE | awk '{print $1 / 20}'`

split -d -l $SPLITLIMT $INFILE x_

for chunk in ls x_??
do
  sed -f $SEDSCRIPT $chunk > $chunk.out &
done

wait 

cat x_??.out >> output.txt

rm -f x_??
rm -f x_??.out

Answer 3

Попробуйте изменить первые две строки на:

s/[ \t]*|[ \t]*/|/g

Answer 4

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

for each line
    split the line into an array of fields
    remove the leading and trailing white space
    join the fields back back together as a pipe delimited line handling the empty first field correctly.

Я бы также использовал для этого другой язык, такой как Perl или Ruby.

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

Answer 5

используйте gawk, а не sed.

awk -vFS='|' '{for(i=1;i<=NF;i++) gsub(/ +|\t+/,"",$i)}1' OFS="|"  file

Answer 6

Как насчет Perl:

#!/usr/bin/perl

while(<>) {
    s/\s*\|\s*/|/g;
    s/^\s*//;
    s/\s*$//;
    s/^\|/null|/;
    print;
}

РЕДАКТИРОВАТЬ: значительно изменил подход. На моей машине это почти в 3 раза быстрее, чем ваш скрипт.

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

Answer 7

Это может сработать. Я только немного протестировал.

awk  'BEGIN {FS="|"; OFS="|"} {for (i=1; i<=NF; i++) gsub("[ \t]", "", $i); $1=$1; if ( $1 == "" ) $1 = "null"; print}'

Answer 8

Этот Perl-скрипт должен быть намного быстрее

s/\s*|\s*/|/go;
s/\s *$//o;
s/^|/null|/o;

По сути, убедитесь, что ваши регулярные выражения скомпилированы один раз (флаг 'o'), и нет необходимости использовать 'g' для регулярных выражений, которые применяются только к концу и началу строки.

Кроме того, [\ s \ t] * эквивалентно \ s *

Answer 9

Я думаю, что * в регулярных выражениях в вопросе и в большинстве ответов может быть серьезным замедлением по сравнению с использованием +. Рассмотрим первую замену в вопросе

s/[\s\t]*|/|/g

* соответствует нулю или нескольким элементам, за которыми следует |, следовательно, каждый | заменяется даже теми, которые не нуждаются в замене. Изменение замены на

s/[\s\t]+|/|/g

изменит только символы |, которым предшествуют один или несколько пробелов и символов табуляции.

У меня нет доступного sed, но я провел эксперимент с Perl. На данных, которые я использовал, сценарий с * занял почти в 7 раз больше времени, чем сценарий с +.

Время было одинаковым для всех трасс. Для + разница между минимальным и максимальным временем составила 4% от среднего значения, а для * - 3,6%. Соотношение средних времен составило 1 :: 6,9 для + :: *.

Детали эксперимента

Протестировано с использованием файла размером 80 Мб с немногим более 180000 экземпляров [st]\., это строчные буквы s и t.

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

perl -f TestPlus.pl input.ltrar > zz.oo
perl -f TestStar.pl input.ltrar > zz.oo

Один скрипт ниже, другой просто изменил * на + и star на plus.

#! /bin/usr/perl
use strict;
use warnings;
use Time::HiRes qw( gettimeofday tv_interval );

my $t0 = [gettimeofday()];
while(<>)
{
    s/[st]*\././g;
}

my $elapsed = tv_interval ( $t0 );
print STDERR "Elapsed star $elapsed\n";

Используемая версия Perl:

c:\test> perl -v
This is perl 5, version 16, subversion 3 (v5.16.3) built for MSWin32-x64-multi-thread
(with 1 registered patch, see perl -V for more detail)

Copyright 1987-2012, Larry Wall

Binary build 1603 [296746] provided by ActiveState http://www.ActiveState.com
Built Mar 13 2013 13:31:10

Answer 10

Вы пробовали Perl? Это может быть быстрее.

#!/usr/local/bin/perl -p

s#[\t ]+\|#|#g;
s#\|[\t ]+#|#g;
s#[\t ]*$##;
s#^\|#null|#;

Редактировать: На самом деле, кажется, что он примерно в три раза медленнее, чем программа sed. Странно ...