큰 문자열의 일치 항목 수를 빠르게 계산

Question 1

GNU 구현 grep(최신 버전은 완전한(대부분 호환) 재작성이지만 대부분의 최신 BSD에도 있음)은 -o출력 옵션을 지원합니다.모두일치하는 부품.

LC_ALL=C grep -ao CDA | wc -l

그러면 모든 발생 횟수가 계산됩니다.

LC_ALL=C grep -abo CDA

바이트 오프셋으로 찾으십시오.

LC_ALL=Cgrep비용이 많이 드는 UTF-8 구문 분석을 시도하지 않도록 하십시오 (여기서 고정된 ASCII 문자열 검색을 사용하면 grep자체적으로 UTF-8 구문 분석을 최적화할 수 있어야 하지만). 바이너리에 대해 생각하라고 -a말하는 것은 또 다른 GNUism입니다 .grep

Answer

GNU 구현 grep(최신 버전은 완전한(대부분 호환) 재작성이지만 대부분의 최신 BSD에도 있음)은 -o출력 옵션을 지원합니다.모두일치하는 부품.

LC_ALL=C grep -ao CDA | wc -l

그러면 모든 발생 횟수가 계산됩니다.

LC_ALL=C grep -abo CDA

바이트 오프셋으로 찾으십시오.

LC_ALL=Cgrep비용이 많이 드는 UTF-8 구문 분석을 시도하지 않도록 하십시오 (여기서 고정된 ASCII 문자열 검색을 사용하면 grep자체적으로 UTF-8 구문 분석을 최적화할 수 있어야 하지만). 바이너리에 대해 생각하라고 -a말하는 것은 또 다른 GNUism입니다 .grep

Question 2

그래서 16진수 문자열을 바이트로 인쇄했지만 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"
    )

거기에 있는 변수는 16진수 문자열의 바이트 값에 대한 8진수 이스케이프/ASCII 문자로 구성됩니다. 왜냐하면 그 보수를 제거 tr하고 싶기 때문입니다 . 그런 다음 일치시키려고 시도할 수 있는 가장 긴 줄이 가 있는 바이트 인지 확인 하고 X 문자를 ewline으로 변환하는 동시에 NUL을 <spaces>로 대체하여 문자열이 항상 줄의 제목이 되도록 했습니다 .tr-dgrep-c-23cuttr\n

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더 나을 것입니다. 매번 다른 방법보다 0.5초 더 빠릅니다. 하지만 그렇게 일반적이지는 않으므로 기꺼이 grep지원한다면 grep -baFo필요할 수도 있습니다.

Answer