awk assoziatives Array wächst schnell

Question

Ich habe eine Datei, die Zahlen zu md5sums weist wie folgt:

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

eine andere Datei containts drei md5sums in jeder Zeile wie folgt:

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

Was ich will Ersetzen Sie die erste und dritte MD5-Datei in der zweiten Datei durch die Ganzzahlen der ersten Datei. Derzeit versuche ich den folgenden awk-Skript:

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

Das Problem ist, dass das Skript mehr, dass 16g ram trotz der Tatsache muss, dass die erste Datei nur 5,7 g auf der Festplatte ist.

Answer 1

Dieses Problem gelöst werden könnte, wie folgt (file1.txt ist die Datei mit den ganzen Zahlen und md5sums während file2.txt die Datei mit den drei Säulen von md5sums ist):

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

Für einen Fall, in dem file1.txt und file2.txt sind jede 1 Million Zeilen lang, diese Lösung und Ed Mortons awk -only Lösung nehmen ungefähr die gleiche Zeitdauer auf meinem System. Mein System würde sehr lange dauern, um das Problem für 140 Millionen Zeilen zu lösen, ungeachtet des verwendeten Ansatzes, aber ich führte einen Testfall für Dateien mit 10 Millionen Zeilen durch.

Ich hatte angenommen, dass eine Lösung, die auf sort (die automatisch temporäre Dateien bei Bedarf verwendet) verließ, sollte für eine große Anzahl von Zeilen schneller sein, da es O (N log N) Laufzeit wäre, während eine Lösung, die neu liest Die Zuordnungsdatei für jede Zeile der Eingabe wäre O (N^2), wenn die zwei Dateien eine ähnliche Größe haben.

Zeitgebungsergebnisse

Meine Vermutung in Bezug auf das Leistungsverhältnis der beiden Kandidatenlösungen erwies sich für die Testfälle fehlerhaft zu sein, die ich ausprobiert habe. Auf meinem System, die sort-basierte Lösung und die awk-only Lösung nahmen ähnliche (innerhalb von 30%) Zeit miteinander für jede von 1 Million und 10 Millionen Zeilen-Eingabedateien, mit der awk-only Lösung ist in jedem schneller Fall. Ich weiß nicht, ob diese Beziehung gilt, wenn die Größe der Eingabedatei natürlich um einen Faktor von mehr als 10 zunimmt.

Seltsamerweise dauerte das 10-Millionen-Linien-Problem mit beiden Lösungen etwa 10 mal so lange wie das 1-Millionen-Linien-Problem, was mich verwirrt, da ich für beide Lösungen eine nichtlineare Beziehung zur Dateilänge erwartet hätte.

Answer 2

Wenn Sie nicht genügend Speicher haben die erste Datei zu speichern, müssen Sie so etwas schreiben, die erste Datei für jeden Wert in der zweiten Datei suchen:

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 

Es wird langsam. Sie könnten einen Cache von N getline-d Zeilen hinzufügen, um es zu beschleunigen, wenn Sie möchten.

Answer 3

Wenn die Größe einer Datei dazu führt, dass awk nicht mehr genügend Arbeitsspeicher hat, dann verwenden Sie entweder ein anderes Werkzeug oder einen anderen Ansatz.

Der Befehl sed ist möglicherweise mit weniger Speicherverbrauch erfolgreich. Die Idee ist, die Indexdatei zu lesen und ein sed-Skript zu erstellen, das die Neuzuordnung durchführt und dann sed für das generierte sedscript aufruft.

Das folgende Bash-Skript ist eine Implementierung dieser Idee. Es enthält einige STDERR-Ausgaben, um den Fortschritt zu verfolgen. Ich mag es, Fortschritts-Tracking-Output für Probleme mit großen Datensätzen oder andere Arten von zeitaufwändiger Verarbeitung zu produzieren.

Dieses Skript wurde mit einer kleinen Datenmenge getestet. Es Mai arbeiten an Ihren Daten. Bitte versuchen Sie es.

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

Hier sind die beiden Dateien:

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 

Hier ist der Probelauf:

$ ./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 

Schließlich wird die resultierende Datei:

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