logo标签列表

awk关联数组增长快速

awkout-of-memoryassociative-array
6

我有一个文件，按照以下方式为md5sum分配数字:

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

另一个文件每行包含三个md5sums，格式如下:

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

我想要的是用第一个文件中的整数替换第二个文件中的第一和第三个md5sum。目前，我正在尝试以下awk脚本：
awk '{OFS="\t"}FNR==NR{map[$2]=$1;next}
{print map[$1],$2,map[$3]}' mapping.txt relation.txt

问题在于，尽管第一个文件只有5.7G，但该脚本需要超过16G的内存。

1
除了将文件分割并分块处理，您的脚本无法采取其他措施来减少该数字。如果需要这样做，那就必须这样做。抱歉。另外，无关的提示 - 将 {OFS="\t"} 更改为 BEGIN{OFS="\t}"。 - Ed Morton
1
你没有说明第二个文件的大小。如果它与file1包含相同数量的行，则我不认为有解决你16G内存问题的方法。祝你好运。 - shellter
第二个文件的大小为什么很重要？脚本只是逐行打印并替换。 - pNRuag
你超过了16GB限制的数量有多少（估计）？如果只是一点点，可能值得将md5sums以更密集的格式存储或者使用子字符串处理... - Marcus Rickert
1
根据行长度判断，这应该大约是1.4亿条记录，意味着有2.8亿个短字符串--其中一半为32字节长，另一半甚至更短。在一个64位系统上（必须是这样的），仅字符串数据的指针就达到了2GB，这还不包括其他元数据。如果你想要一次性完成，我认为你不能使用脚本语言完成它。用本地语言可以将其缩减到大约6-7 GB左右的大小。是否接受使用常见库的C++解决方案？ - Wintermute
我不介意使用C++，但我更喜欢Java。不过我猜在Java中你可能需要处理垃圾回收限制的问题？ - pNRuag
3个回答
2

如果你的内存不足以存储第一个文件，那么你需要编写如下代码，在第二个文件中查找每个值的第一个文件：

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

这会很慢。如果您愿意，可以添加一个N行getline的缓存来加快速度。

我觉得这个速度太慢了。第二个文件大约有4亿条记录，这意味着要读取第一个文件4亿次。这将花费太多时间。我目前通过创建MySQL数据库并使用select into outfile解决了这个问题，但我感觉还有更轻量级的解决方案可以解决这种问题。 - pNRuag
就像我之前所说的，它确实很慢，如果太慢了，你可以将最后N行缓存到数组中，只有在所需值不存在时才执行getline操作。 - Ed Morton
1
以下是解决此问题的步骤（file1.txt 是包含整数和 md5sums 的文件，而 file2.txt 是包含三列 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

对于每个有100万行的file1.txt和file2.txt的情况，这个解决方案和Ed Morton的仅使用awk的解决方案在我的系统上花费的时间大致相同。无论使用哪种方法，我的系统都需要很长时间来解决含有1.4亿行的问题，但我进行了一个包含1000万行的文件的测试案例。
我曾经认为，对于大量行数，依赖于sort（自动在必要时使用临时文件）的解决方案应该更快，因为它的运行时间是O(N log N)，而每一行输入都会重新读取映射文件的解决方案如果两个文件的大小相似，则其运行时间将为O(N^2)。 定时结果 我的假设关于两个候选方案的性能关系，在我尝试的测试用例中被证明是错误的。在我的系统上，基于sort的解决方案和仅基于awk的解决方案在每个100万行和1000万行输入文件中所花费的时间相似（在30%以内），而在每种情况下，仅基于awk的解决方案更快。当然，我不知道当输入文件大小增加超过10倍时，这种关系是否仍然成立。
奇怪的是，对于两个解决方案，1000万行问题的运行时间大约比100万行问题长10倍，这让我感到困惑，因为我本来期望两个解决方案的文件长度与非线性关系。
1
感谢加入该程序，这正是我一直在寻找的。顺便提一下，第一个文件已经按哈希值排序，第三个文件已按第一行排序。所以我只需要执行以下操作： join -t $'\t' -12 -21 -o1.1,2.2,2.3 mapping.txt relation.txt | sort --parallel=4 -S4g -k3 > relation_step1.txt 和：join -t $'\t' -12 -23 -o2.1,2.2,1.1 mapping.txt relation_step1.txt > relation_result.txt - pNRuag
1

如果文件的大小导致awk耗尽内存，则可以使用另一个工具或完全不同的方法。

sed命令可能会使用更少的内存而成功。想法是读取索引文件并创建一个sed脚本来执行重新映射，然后在生成的sed脚本上调用sed。

下面的bash脚本是这个想法的一个实现。它包括一些标准错误输出以帮助跟踪进度。我喜欢为大数据集或其他类型的耗时处理问题生成跟踪进度的输出。

这个脚本已经在一个小的数据集上进行了测试；它也许可以在你的数据上运行。请试一试。

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

这里是两个文件：

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

这是一个样例运行：
$ ./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

最终，生成的文件为：
$ cat md5-data.txt
1    276EC96E149571F8A27F4417D7C6BC20    9CFEFED8FB9497BAA5CD519D7D2BB5D7
1    44E48C092AADA3B171CE899FFC6943A8    1B757742E1BF2AA5DB6890E5E338F857
这个解决方案看起来对我来说太复杂了，但无论如何我还是会接受它。 - pNRuag
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接