serie awk associativa cresce velocemente

Question

Ho un file che assegna numeri di md5sums amano segue:

0 0000001732816557DE23435780915F75 
1 00000035552C6F8B9E7D70F1E4E8D500 
2 00000051D63FACEF571C09D98659DC55 
3 0000006D7695939200D57D3FBC30D46C 
4 0000006E501F5CBD4DB56CA48634A935 
5 00000090B9750D99297911A0496B5134 
6 000000B5AEA2C9EA7CC155F6EBCEF97F 
7 00000100AD8A7F039E8F48425D9CB389 
8 0000011ADE49679AEC057E07A53208C1 

un altro file containts tre md5sums in ogni riga come segue:

00000035552C6F8B9E7D70F1E4E8D500 276EC96E149571F8A27F4417D7C6BC20 9CFEFED8FB9497BAA5CD519D7D2BB5D7 
00000035552C6F8B9E7D70F1E4E8D500 44E48C092AADA3B171CE899FFC6943A8 1B757742E1BF2AA5DB6890E5E338F857 

quello che voglio a è sostituire il primo e il terzo md5sum nel secondo file con i numeri interi del primo file. Attualmente sto provando il seguente script awk:

awk '{OFS="\t"}FNR==NR{map[$2]=$1;next} 
{print map[$1],$2,map[$3]}' mapping.txt relation.txt 

Il problema è che lo script ha bisogno di più che di RAM 16G, nonostante il fatto che il primo file è soltanto 5,7 g sul disco rigido.

Answer 1

Questo problema potrebbe essere risolto, come segue (file1.txt è il file con i numeri interi e md5sums mentre file2.txt è il file con le tre colonne di md5sums):

#!/bin/sh 
# First sort each of file 1 and the first and third columns of file 2 by MD5 
awk '{ print $2 "\t" $1}' file1.txt | sort >file1_n.txt 
# Before we sort the file 2 columns, we number the rows so we can put them 
# back into the original order later 
cut -f1 file2.txt | cat -n - | awk '{ print $2 "\t" $1}' | sort >file2_1n.txt 
cut -f3 file2.txt | cat -n - | awk '{ print $2 "\t" $1}' | sort >file2_3n.txt 
# Now do a join between them, extract the two columns we want, and put them back in order 
join -t' ' file2_1n.txt file1_n.txt | awk '{ print $2 "\t" $3}' | sort -n | cut -f2 >file2_1.txt 
join -t' ' file2_3n.txt file1_n.txt | awk '{ print $2 "\t" $3}' | sort -n | cut -f2 >file2_3.txt 
cut -f2 file2.txt | paste file2_1.txt - file2_3.txt >file2_new1.txt 

Per un caso in cui file1.txt e file2.txt sono ogni 1 milione di righe, questa soluzione e la soluzione di Ed Morton awk -adeguatamente sul mio sistema richiedono circa lo stesso tempo. Il mio sistema impiegherebbe molto tempo a risolvere il problema per 140 milioni di linee, indipendentemente dall'approccio utilizzato, ma ho eseguito un test per file con 10 milioni di righe.

Avevo ipotizzato che una soluzione basata su sort (che utilizza automaticamente i file temporanei quando richiesto) dovrebbe essere più veloce per un numero elevato di righe perché sarebbe O (N log N) runtime, mentre una soluzione che rilegge il file di mappatura per ogni riga dell'input sarebbe O (N^2) se i due file hanno dimensioni simili.

Timing risultati

mia ipotesi per quanto riguarda il rapporto prestazioni delle due soluzioni candidate si è rivelata difettosa per i casi di test che ho provato. Sul mio sistema, la soluzione basata su sort e la soluzione solo awk prendevano una quantità di tempo simile (inferiore al 30%) tra 1 milione e 10 milioni di file di input di linea, con la soluzione awk -solo più veloce in ogni Astuccio. Non so se quella relazione rimarrà vera quando le dimensioni del file di input aumentano di un altro fattore di oltre 10, ovviamente. Stranamente, il problema dei 10 milioni di linee ha richiesto circa 10 volte di più di entrambe le soluzioni per risolvere il problema di 1 milione di linee, il che mi imbarazza come mi sarei aspettato una relazione non lineare con la lunghezza del file per entrambe le soluzioni.

Answer 2

Se non si dispone di memoria sufficiente per memorizzare il primo file, allora avete bisogno di scrivere qualcosa di simile per cercare il primo file per ogni valore nel 2 ° del file:

awk 'BEGIN{OFS="\t"} 
{ 
    val1 = val3 = "" 
    while ((getline line < "mapping.txt") > 0) { 
     split(line,flds) 
     if (flds[2] == $1) { 
      val1 = flds[1] 
     } 
     if (flds[2] == $3) { 
      val3 = flds[1] 
     } 
     if ((val1 != "") && (val3 != "")) { 
      break 
     } 
    } 
    close("mapping.txt") 

    print val1,$2,val3 

}' relation.txt 

Sarà lento. È possibile aggiungere una cache di linee N getline-d per accelerarla, se lo si desidera.

Answer 3

Se la dimensione di un file fa sì che awk esaurisca la memoria, utilizzare un altro strumento o un altro approccio completamente.

Il comando sed può riuscire con molto meno utilizzo della memoria. L'idea è di leggere il file indice e creare uno script sed che esegua il remapping e quindi invocare sed sul copriptato generato.

Lo script di bash di seguito è un'implementazione di questa idea. Include alcuni output STDERR per aiutarti a monitorare i progressi. Mi piace produrre output di monitoraggio progressivo per problemi con set di dati di grandi dimensioni o altri tipi di elaborazione che richiedono molto tempo.

Questo script è stato testato su un piccolo insieme di dati; it può lavorare sui dati. Si prega di fare un tentativo.

#!/bin/bash 

# md5-indexes.txt 
# 0 0000001732816557DE23435780915F75 
# 1 00000035552C6F8B9E7D70F1E4E8D500 
# 2 00000051D63FACEF571C09D98659DC55 
# 3 0000006D7695939200D57D3FBC30D46C 
# 4 0000006E501F5CBD4DB56CA48634A935 
# 5 00000090B9750D99297911A0496B5134 
# 6 000000B5AEA2C9EA7CC155F6EBCEF97F 
# 7 00000100AD8A7F039E8F48425D9CB389 
# 8 0000011ADE49679AEC057E07A53208C1 

# md5-data.txt 
# 00000035552C6F8B9E7D70F1E4E8D500 276EC96E149571F8A27F4417D7C6BC20 9CFEFED8FB9497BAA5CD519D7D2BB5D7 
# 00000035552C6F8B9E7D70F1E4E8D500 44E48C092AADA3B171CE899FFC6943A8 1B757742E1BF2AA5DB6890E5E338F857 

# Goal replace field 1 and field 3 with indexes to md5 checksums from md5-indexes 

md5_indexes='md5-indexes.txt' 
md5_data='md5-data.txt' 

talk() { echo 1>&2 "$*" ; } 
talkf() { printf 1>&2 "$@" ; } 
track() { 
    local var="$1" interval="$2" 
    local val 
    eval "val=\$$var" 
    if ((interval == 0 || val % interval == 0)); then 
    shift 2 
    talkf "$@" 
    fi 
    eval "(($var++))" # increment the counter 
} 

# Build a sedscript to translate all occurances of the 1st & 3rd MD5 sums into their 
# corresponding indexes 

talk "Building the sedscript from the md5 indexes.." 

sedscript=/tmp/$$.sed 

linenum=0 
lines=`wc -l <$md5_indexes` 
interval=$((lines/100)) 

while read index md5sum ; do 
    track linenum $interval "..$linenum" 
    echo "s/^[[:space:]]*[[:<:]]$md5sum[[:>:]]/$index/" >>$sedscript 
    echo "s/[[:<:]]$md5sum[[:>:]]\$/$index/"   >>$sedscript 
done <$md5_indexes 
talk '' 

sedlength=`wc -l <$sedscript` 

talkf "The sedscript is %d lines\n" $sedlength 

cmd="sed -E -f $sedscript -i .bak $md5_data" 
talk "Invoking: $cmd" 

$cmd 

changes=`diff -U 0 $md5_data.bak $md5_data | tail +3 | grep -c '^+'` 

talkf "%d lines changed in $md5_data\n" $changes 

exit 

Qui ci sono i due file:

cat md5-indexes.txt 
0 0000001732816557DE23435780915F75 
1 00000035552C6F8B9E7D70F1E4E8D500 
2 00000051D63FACEF571C09D98659DC55 
3 0000006D7695939200D57D3FBC30D46C 
4 0000006E501F5CBD4DB56CA48634A935 
5 00000090B9750D99297911A0496B5134 
6 000000B5AEA2C9EA7CC155F6EBCEF97F 
7 00000100AD8A7F039E8F48425D9CB389 
8 0000011ADE49679AEC057E07A53208C1 

cat md5-data.txt 
00000035552C6F8B9E7D70F1E4E8D500 276EC96E149571F8A27F4417D7C6BC20 9CFEFED8FB9497BAA5CD519D7D2BB5D7 
00000035552C6F8B9E7D70F1E4E8D500 44E48C092AADA3B171CE899FFC6943A8 1B757742E1BF2AA5DB6890E5E338F857 

Ecco l'esempio di esecuzione:

$ ./md5-reindex.sh 
Building the sedscript from the md5 indexes.. 
..0..1..2..3..4..5..6..7..8 
The sedscript is 18 lines 
Invoking: sed -E -f /tmp/83800.sed -i .bak md5-data.txt 
2 lines changed in md5-data.txt 

Infine, il file risultante:

$ cat md5-data.txt 
1 276EC96E149571F8A27F4417D7C6BC20 9CFEFED8FB9497BAA5CD519D7D2BB5D7 
1 44E48C092AADA3B171CE899FFC6943A8 1B757742E1BF2AA5DB6890E5E338F857