awk asocjacyjna rośnie szybko

Question

Mam plik, który przypisuje numery do sumy kontrolne md5 lubią następująco:

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

innym containts plik trzystronicowy sumy kontrolne MD5 w każdej linii jak następuje:

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

Co chcę, aby zastępuje pierwszą i trzecią liczbę md5 w drugim pliku liczbami całkowitymi pierwszego pliku. Obecnie próbuję następujący skrypt awk:

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

Problemem jest to, że skrypt potrzebuje więcej niż 16g barana pomimo faktu, że pierwszy plik jest tylko 5,7 g na dysku twardym.

Answer 1

Ten problem można rozwiązać w następujący sposób (file1.txt jest plik z liczb całkowitych i sumy kontrolne MD5 podczas file2.txt jest plik z trzech kolumn sumy kontrolne md5):

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

Dla przypadku, gdy file1.txt i file2.txt są każde 1 milion linii długich, to rozwiązanie i awk Eda Mortona - tylko jedno zajmuje mniej więcej tyle czasu w moim systemie. Mój system wymagałby bardzo długiego czasu rozwiązania problemu dla 140 milionów linii, niezależnie od zastosowanego podejścia, ale przeprowadziłem testowanie dla plików z 10 milionami linii.

Założono, że rozwiązanie polegające na sort (które automatycznie używa plików tymczasowych, gdy jest to wymagane) powinno być szybsze dla dużej liczby linii, ponieważ byłoby to środowisko wykonawcze O (N log N), natomiast rozwiązanie, które ponownie czyta plik mapujący dla każdego wiersza wejścia będzie miał postać O (N^2), jeśli oba pliki mają podobny rozmiar.

Timing wyniki

moje założenie w odniesieniu do relacji wydajności obu rozwiązań kandydujących okazał się wadliwy przypadków testowych, które próbowałem. W moim systemie, rozwiązanie oparte na sort i na rozwiązaniu awk-podobnym (w 30%) czasie dzieliło się od siebie nawzajem na każdy z 1 miliona i 10 milionów plików wejściowych linii, przy czym tylko jedno rozwiązanie było szybsze w każdym z nich. walizka. Nie wiem, czy ta relacja będzie prawdziwa, gdy rozmiar pliku wejściowego wzrośnie o kolejny czynnik większy niż 10, oczywiście.

Dziwnie, problem z 10 milionami linii trwał około 10 razy dłużej w przypadku obu rozwiązań niż problem z milionem linii, co jest dla mnie zagadką, ponieważ spodziewałem się nieliniowego związku z długością pliku dla obu rozwiązań.

Answer 2

Jeśli nie ma wystarczającej ilości pamięci do przechowywania pierwszy plik, a następnie trzeba napisać coś takiego patrzeć 1st pliku dla każdej wartości w 2 pliku:

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 

Będzie powolny. Możesz dodać pamięć podręczną N linii getline-d, aby przyspieszyć, jeśli chcesz.

Answer 3

Jeśli rozmiar pliku powoduje awk do wyczerpania pamięci, użyj innego narzędzia lub innego podejścia.

Komenda sed może odnieść sukces z mniejszym wykorzystaniem pamięci. Chodzi o to, aby odczytać plik indeksu i utworzyć skrypt sed, który wykonuje ponowne mapowanie, a następnie wywołać sed na wygenerowanym sedscript.

Poniższy skrypt bash jest implementacją tego pomysłu. Zawiera trochę danych wyjściowych STDERR, aby pomóc śledzić postępy. Lubię tworzyć wyjścia śledzenia postępu w przypadku problemów z dużymi zbiorami danych lub innymi rodzajami czasochłonnego przetwarzania.

Ten skrypt został przetestowany na małym zestawie danych; to może pracować nad swoimi danymi. Proszę spróbować.

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

Oto dwa pliki:

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 

Oto run próbki:

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

Wreszcie plik wynikowy:

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