☰

快速计算大型字符串中的匹配数

tag-icon • tag-icon shell-script sed find
快速计算大型字符串中的匹配数

我有大量文本数据，一行中没有空格，也没有其他行。实际上，流是 0.2 Gb/s，类似的情况这里，但在此任务中，计算出现次数比仅计算空行更具挑战性。比赛是

585e0000fe5a1eda480000000d00030007000000cd010000

示例数据子集是这里被称为30.6.2015_数据.txt及其完整的二进制数据这里被称为0002.raw。比赛发生 1 次于30.6.2015_数据.txt但在完整数据中是10倍0002.raw在一行中。我通过 准备了txt数据xxd -ps 0002.raw > /tmp/1 && fold -w2 /tmp/1 > /tmp/2 && gsed ':a;N;$!ba;s/\n//g' /tmp/2 > /tmp/3。实施越快越好。要在列中准备大型字符串，您可以使用此xxd -ps 0002.raw > /tmp/1 && fold -w2 /tmp/1 > /tmp/2.我当前的速率是每场比赛 0.0012 秒，即完整数据文件中每十场比赛 0.012 秒，这很慢。

Grep 按行执行此操作，因此无法计数。在 Vim 中，%s/veryLongThing//gn不足以完成任务。该命令wc仅给出字符、字节和行，因此不是正确的工具，但可能将其与其他东西组合起来。可能是 GNU Find 和 Sed 的组合，但所有实现似乎都太复杂了。

Mikeserv 答案的输出

$ cat 1.7.2015.sh 
time \
    ( export ggrep="$(printf '^ \376Z\36\332H \r \3 \a \315\1')" \
             gtr='\1\3\a\r\36HZ^\315\332\376'
             LC_ALL=C
      gtr -cs "$gtr" ' [\n*]' |
      gcut -sd\  -f1-6       |
      ggrep -xFc "$ggrep"
    ) <0002.raw

$ sh 1.7.2015.sh 
1

real    0m0.009s
user    0m0.006s
sys 0m0.007s

-----------

$ cat 1.7.2015.sh 
time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  ggrep="$(shift;IFS=\\;printf "\\$*")"    \
                gtr='\0\1\3\a\r\36HXZ^\315\332\376'      \
                LC_ALL=C i=0
        while [ "$((i+=1))" -lt 1000 ]
        do    gcat 0002.raw; done            |
        gtr -cd "$gtr" |gtr 'X\0' '\n '      |
        gcut -c-23    |ggrep -xFc "$ggrep"
    ) 

$ sh 1.7.2015.sh 
9990

real    0m4.371s
user    0m1.548s
sys 0m2.167s

其中所有工具都是 GNU coreutils，它们具有您在代码中提供的所有选项。但它们可能与 GNU devtools 不同。Mikeserv 运行他的代码 990 次，有 10 个事件，因此总共 9990 个事件是正确的。

如何有效地计算超级字符串中的匹配数？

答案1

GNU 实现grep（也出现在大多数现代 BSD 中，尽管最新版本是完整的（大部分兼容）重写）支持-o输出选项全部匹配的部分。

LC_ALL=C grep -ao CDA | wc -l

然后会计算所有出现的次数。

LC_ALL=C grep -abo CDA

通过它们的字节偏移量来定位它们。

LC_ALL=C确保grep不会尝试执行一些昂贵的 UTF-8 解析（尽管这里使用固定的 ASCII 字符串搜索，grep应该能够自行优化 UTF-8 解析）。-a是另一个 GNUism 告诉我们grep要考虑二进制文件。

答案2

所以我拿了你的十六进制字符串并将其打印为字节，但我将 NUL 交换为 <spaces>（主要是因为我不知道如何在模式中获得 NUL grep）:

time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  grep="$(shift;IFS=\\;printf "\\$*")"    \
                tr='\0\1\3\a\r\36HXZ^\315\332\376'      \
                LC_ALL=C i=0
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw; done     |
        tr -cd "$tr" |tr 'X\0' '\n ' |
        cut -c-23    |grep -xFc "$grep"
    )

那里的变量tr由十六进制字符串的字节值的八进制转义/ASCII 字符组成，因为我想tr删除-d它的补码。然后，我确保最长的行grep可以尝试匹配的是-c-23带有 的字节cut，并且该字符串始终通过tr将 X 字符转换为\newlines 来作为一行的标题，同时还将 NUL 替换为 <spaces>。

我cat在这里将原始二进制文件在管道中运行了 999 次。由于文件中有 10 个匹配项，因此结果为：

9990
1.06s user 0.94s system 65% cpu 3.054 total

现在我也测试了...

time \
    (  set      x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  LC_ALL=C i=0 grep="$(IFS=\\;printf "\\$*")"
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw;  done    |
        tr '\0 ' ' \0'   |
        grep -aFo "$grep"| wc -l
    )

我在那里使用，但在我的测试中，使用和完全删除wc -l似乎对执行时间没有任何影响。无论如何，计数都是相同的。结果如下：-caFowc

9990
1.56s user 1.46s system 82% cpu 3.648 total

现在这两套命令并不等同。虽然它似乎通过首先挤出不需要的字节来更快地完成tr，但这意味着虽然您可以获得计数，但您无法像在第二个示例中添加-b开关一样获得偏移量......grep

time \
   (    set     x58 x5e x20 x20 xfe x5a x1e xda \
                x48 x20 x20 x20 x0d x20 x03 x20 \
                x07 x20 x20 x20 xcd x01 x20 x20
        export  LC_ALL=C i=0 grep="$(IFS=\\;printf "\\$*")"
        while [ "$((i+=1))" -lt 1000 ]
        do    cat 0002.raw;  done    |
        tr '\0 ' ' \0'     |
        grep -baFo "$grep" | sed -n l
   )

...

241133568:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241157720:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241181872:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241206024:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241230176:X^  \376Z\036\332H   \r \003 \a   \315\001  $
241254328:X^  \376Z\036\332H   \r \003 \a   \315\001  $

1.59s user 1.41s system 85% cpu 3.496 total

所以我想你选择哪一个将取决于你想要什么。仅算一下，可能tr -cd会更好 - 它每次都比其他方法快半秒 - 但它不是那么通用，所以如果您grep愿意支持它，也许它grep -baFo可能是您所需要的。

相关内容