Come rendere questo script sed più veloce?

Question

ho ereditato questo frammento script sed che tenta di rimuovere alcuni spazi vuoti:

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

che opera su un file che è di circa 1 Gb di grandi dimensioni. Questo script viene eseguito per 2 ore sul nostro server Unix. Qualche idea su come accelerarlo?

rileva che il \ 's sta per uno spazio e \ T sta per una scheda, lo script vero utilizza lo spazio reale e scheda e non i simboli che

Il file di input è un file delimitato pipe ed è localizzato localmente non sulla rete. Le 4 linee sono in un file eseguiti con sed -f

Answer 1

Il meglio sono stato in grado di fare con sed, era questo script:

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

Nei miei test, questo è risultato circa il 30% più veloce del tuo script sed. L'aumento delle prestazioni deriva dalla combinazione dei primi due regexen e omettendo la flag "g" dove non è necessario.

Tuttavia, il 30% più veloce è solo un lieve miglioramento (dovrebbe essere necessario circa un'ora e mezza per eseguire lo script sopra nel file di dati da 1 GB). Volevo vedere se potevo fare di meglio.

Alla fine, nessun altro metodo che ho provato (awk, perl e altri approcci con sed) ha funzionato meglio, tranne - ovviamente - una semplice implementazione di C. Come ci si aspetterebbe con C, il codice è un po 'prolisso per la pubblicazione qui, ma se si desidera un programma che rischia di essere più veloce di qualsiasi altro metodo disponibile, si consiglia di eseguire take a look at it.

Nei miei test, l'implementazione C termina in circa il 20% del tempo necessario per il tuo script sed. Quindi potrebbero volerci circa 25 minuti circa per funzionare sul tuo server Unix.

Non ho dedicato molto tempo all'ottimizzazione dell'implementazione C. Senza dubbio ci sono un certo numero di posti in cui l'algoritmo potrebbe essere migliorato, ma francamente, non so se sia possibile radere una quantità significativa di tempo oltre ciò che già realizza. Se non altro, penso che sia sicuramente un limite superiore al tipo di prestazioni che ci si può aspettare da altri metodi (sed, awk, perl, python, ecc.).

Modifica: La versione originale aveva un bug secondario che causava la possibilità di stampare la cosa sbagliata alla fine dell'output (ad esempio, poteva stampare un "null" che non dovrebbe essere lì). Oggi ho avuto un po 'di tempo per dargli un'occhiata e sistemarlo. Ho anche ottimizzato una chiamata a strlen() che gli ha dato un altro leggero incremento di prestazioni.

Answer 2

Mi sembra dal vostro esempio che si pulisce lo spazio bianco dal inizio e la fine di pipe (|) campi delimitati in un file di testo. Se dovessi fare questo, vorrei cambiare l'algoritmo di seguito:

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. 

Vorrei anche usare un linguaggio diverso, come Perl o Ruby per questo.

Il vantaggio di questo approccio è che il codice che pulisce le linee ora gestisce meno caratteri per ogni chiamata e deve essere eseguito molto più rapidamente anche se sono necessarie più chiamate.

Answer 3

provare a cambiare le prime due righe a:

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

Answer 4

provare a farlo in un solo comando:

sed 's/[^|]*(|.*|).*/\1/' 

Answer 5

Hai provato Perl? Potrebbe essere più veloce.

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

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

Edit: In realtà, sembra essere circa tre volte più lento del programma di sed. Strano ...

Answer 6

Questo script in Perl dovrebbe essere molto molto più veloce

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

In sostanza, assicurarsi che le espressioni regolari sono compilate una volta (la 'o' bandiera), e non c'è bisogno bisogno di usare 'g' su regex che si applicano solo alla fine e all'inizio della riga.

Inoltre, [\ s \ t] * è equivalente a \ s *

Answer 7

Questo potrebbe funzionare. L'ho solo provato un po '.

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

Answer 8

Come su Perl:

#!/usr/bin/perl 

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

EDIT: cambiato l'approccio in modo significativo. Sulla mia macchina questo è quasi 3 volte più veloce del tuo script sed.

Se è davvero necessaria la massima velocità possibile, scrivere un programma C specializzato per eseguire questa operazione.

Answer 9

usare gawk, non sed.

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

Answer 10

I miei test indicavano che sed può essere facilmente collegata alla cpu in qualcosa di simile. Se si dispone di una macchina multi-core si può provare la deposizione delle uova fuori più processi sed con uno script che sembra qualcosa di simile:

#!/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 11

Penso che lo * nelle espressioni regolari nella domanda e nella maggior parte delle risposte possa essere un rallentamento maggiore rispetto all'utilizzo di +. Consideriamo la prima sostituzione della questione

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

le * corrisponde a zero o più elementi seguiti da un |, quindi ogni | è sostituito anche quelli che non sono da sostituire. Cambiare la sostituzione di essere

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

cambierà solo le | caratteri preceduti da uno o più spazi e tabulazioni.

Non ho disponibile sed, ma ho fatto un esperimento con Perl. Sui dati che ho usato con lo script * sono occorse circa 7 volte più lunghe rispetto allo script con +.

I tempi erano coerenti lungo le piste.Per la + la differenza tra i tempi minimi e massimi era del 4% della media e per il * era del 3,6%. Il rapporto tra i tempi medi è 1: 6.9 per + :: *.

dettagli dell'esperimento

testato utilizzando un file di 80 MB con poco più di 180.000 occorrenze di [st]\., questi sono i caratteri minuscoli s e t.

Il test ha utilizzato un file di comando batch con 30 di ciascuno di questi due comandi, stella alternata e più.

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

Uno script è al di sotto, l'altro semplicemente cambiato il *-+ e 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"; 

versione Perl usato:

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