태그 보관물: speed

speed

길거나 짧은 검색어로 Unix grep이 더 빨리 작동합니까? 5000 행이

길거나 짧은 검색어를 찾는 것이 더 빠릅니까? 아니면 속도에 전혀 영향을 줍니까? 다시 말해, 검색어를 최대한 정확하게 작성해야합니까?

100,000 개가 넘는 파일이 있으며 각 파일에는 20 행에서 5000 행이 넘는 데이터 행이 있습니다. 일반적으로 grep은 하나의 검색어 인스턴스 만 찾는 데 사용됩니다.

검색어가 SEARCHTERM이고 다음과 같은 행에 있다고 가정 해 보겠습니다 .

NAD+DP+1234567890:92++UNIQUE+NAME+SEARCHTERM++12345+FI'

“SEARCH”또는 “SEARCHTERM”을 찾는 것이 더 빠릅니까? 이 경우 다른 관련없는 라인에서 일치하는 항목을 찾더라도 신경 쓰지 않는다고 가정 해 봅시다.

이것이 내가 현재하는 방법입니다.

grep NAD+DP 123* | grep SEARCHTERM

그러나 여전히 느립니다. 거친 파일 이름을 아는 경우에도 데이터를 찾는 데 약 3-5 분이 걸리며 범위는 약 10 000 파일로 제한됩니다.

그렇다면 더 길거나 짧은 검색어가 도움이 되겠습니까? 내가 아는 한 grep은 특정 길이의 단어의 “블록”을 찾습니다.



답변

참고 자료 :

GNU grep은 잘 알려진 Boyer-Moore 알고리즘을 사용합니다.이 알고리즘은 대상 문자열의 마지막 문자를 먼저 찾고 조회 테이블을 사용하여 일치하지 않는 문자를 찾을 때마다 입력에서 건너 뛸 수있는 정도를 알려줍니다.

에서 왜 GNU 그렙은 빠르고 .

알고리즘은 검색중인 문자열 (패턴)을 전처리하지만 검색중인 문자열 (텍스트)은 처리하지 않습니다. […] 일반적으로 패턴 길이가 길수록 알고리즘이 더 빠르게 실행됩니다.

에서 보이어 – 무어 문자열 검색 알고리즘 .

결론 : 더 긴 문자열을 사용하십시오 .

이제 재미를위한 약간의 벤치 마크 :

# Initialisation
cd $(mktemp -d) && dd if=/dev/urandom of=random bs=1M count=1000
# Version
grep --v` # grep (GNU grep) 2.9
# Benchmark
(for s in 'short' 'this is not so short and we could even consider this as pretty long'; do for t in {1..10}; do time grep "$s" random; done; done ) 2> result

결과 : 짧은 문자열의 평균은 0.952 초이고 긴 문자열의 평균은 0.244 초입니다.

NB : 길이 만 고려할 기준은 아닙니다.


답변

SEARCH 또는 SEARCHTERM을 사용하여 시도해 볼 수 있습니다. 또한 두 grep 명령의 순서를 변경하십시오. 어쨌든 유일한 유용한 옵션은 하나의 검색에 여러 CPU 코어를 사용하는 것입니다. parallel명령을 참조하십시오 .


답변

더 구체적인 검색어를 지정하면 눈에 띄게 더 빠를 것이라고 생각하지 않습니다.

검색 할 파일이 너무 많으면 검색 속도를 높이기 위해 데이터를 색인화해야합니다.

몇 가지 방법을 제안 할 수 있습니다.

  • 데이터베이스 (PostgreSQL 또는 MySQL)를 생성하고 데이터를 데이터베이스로 가져옵니다 (한 행에 한 파일 씩). FTS (전체 텍스트 검색) 인덱스를 추가하십시오. 데이터베이스를 쿼리하는 유틸리티를 작성하십시오.

  • 보다 세밀한 방식으로 데이터베이스에 데이터를 가져 오십시오. 한 행에 하나의 행 (또는 여러 테이블에)이있을 경우 인덱스를 사용하여 데이터를 검색 할 수 있도록 인덱스를 작성하십시오. 데이터베이스를 쿼리하는 유틸리티를 작성하십시오.

  • 파일을 git리포지토리에 추가 하고을 사용하여 압축 한 다음 검색에 git gc사용하십시오 git grep. 내 경험상 10x-100x의 요소로 git grep표준보다 빠를 수 있습니다 grep.


답변

논리적으로, 짧은 용어로, 적은 CPU 시간을 필요로 grep하고있을 것

if (filechar[i] == pattern[i]) ...

적은 시간. 실제로, 나는 grepCPU 바인딩이 아닌 I / O 바인딩 이라고 생각 하므로 중요하지 않습니다.


답변