| -20,7 +20,7 |
|
| GNU grep은 잘 알려진 Boyer-Moore 알고리즘을 사용합니다. 이 알고리즘은 타겟 스트링의 마지막 글자를 먼저 찾고, 매치되지 않는 글자를 발견할 때마다 입력을 얼마나 건너뛸 수 있는지 알 수 있도록 룩업테이블을 사용합니다. |
|
| GNU grep은 또한 Boyer-Moore 알고리즘의 안쪽 루프를 풀어서(unroll) 최적화하고, Boyer-Moore 델타 테이블을 세팅하여 unroll된 모든 단계에서 루트 종료 검사를 할 필요가 없도록 하였습니다. 그 결과, 한도 내에서 GNU grep은 (많은 입력 바이트를 건너뛰고) 실제로 살펴보는 바이트 각각에 대해 평균 3개 미만의 x86 인스트럭션을 수행합니다. |
| GNU grep은 또한 Boyer-Moore 알고리즘의 안쪽 루프를 풀어서(unroll) 최적화하고, Boyer-Moore 델타 테이블을 세팅하여 unroll된 모든 단계에서 루프 종료 검사를 할 필요가 없도록 하였습니다. 그 결과, 한도 내에서 GNU grep은 (많은 입력 바이트를 건너뛰고) 실제로 살펴보는 바이트 각각에 대해 평균 3개 미만의 x86 인스트럭션을 수행합니다. |
|
| "Software: Practice & Experience" 저널 1991년 11월호에 있는, Andrew Hume과 Daniel Sunday가 쓴 "Fast String Searching"<footnote([http://onlinelibrary.wiley.com/doi/10.1002/spe.4380211105/abstract Fast string searching - Hume - 2006 - Software: Practice and Experience - Wiley Online Library])>을 보시면 Boyer-Moore 알고리즘 구현 기교들에 관한 좋은 논의들이 있습니다. 온라인에서 무료로 PDF를 얻을 수 있습니다. |
|
![[첫화면으로]](/raymundo_logo.jpg){kind=logo}
"Why GNU grep is fast" 페이지의 변경 내역