【レポート】GNU grepが高速な理由 | エンタープライズ | マイコミジャーナル

FreeBSD - The Power To Serve why GNU grep is fast (なぜGNU grepは高速なのか)といったタイトルの興味深いメールがFreeBSD開発者メーリングリストに投函された。メールを出したのはGNU grepのオリジナル開発者であるMike Haertel氏。Mike Haertel氏はFreeBSDユーザでもあり、FreeBSD開発者メーリングリストで興味深いやりとりがあったため、このメールを流したとしている。Mike Haertel氏の紹介する内容はgrep(1)の実装のみならず、高速な文字列処理を実現するひとつの方法として参考になる。紹介されているGNU grep高速さの秘訣は次のとおり。 GNU grepは入力バイトのすべてをチェックするようなことは避けている。 GNU grepはバイトごとに適用する操作を極力最小限に減らしている。 G

[suzuki09]

algorithm grep

[sora_h]

ほえー

[kabiy]

ほえー

[ming_mina]

興味深い

[hattara]

mmap - map pages of memory

[deep_one]

自分が書いたツールを再実装しようとしている人に、高速化の秘訣を助言する。This is Open-Source mind?

[mnshtn]

速さの秘訣が9項目。

[tuto0621]

Boyer-Mooreアルゴリズムを使っている

[n2s]

ちなみに、LANGにC以外を指定すると異様に遅くなるよね… / https://news.mynavi.jp/techplus/article/20100825-why-gnu-grep-is-fast-than-bsd/ / mmapはこの記事の時点で失敗とされた模様、2.6からは使われていない

[paella]

GNU grepが高速である理由の概要説明。マルチバイト文字でもこの方法が速いのかどうかは、ここだけでは分からなかったけどメモ

[mrkn]

意外なものではなくて、昔から良く知られたテクニックを組み合わせてるだけだね。

[moccos_info]

文字列検索

[manaten]

ボイヤー-ムーア文字列検索アルゴリズム - Wikipedia http://goo.gl/HJ8N

[masterq]

GNU grep高速さの秘訣は次のとおり。 GNU grepは入力バイトのすべてをチェックするようなことは避けている。 GNU grepはバイトごとに適用する操作を極力最小限に減らしている。 GNU grepはBoyer-Mooreアルゴリズムとルックアップテ

[mooz]

BM 法とルックアップテーブル. mmap.

[tinsep19]

Boyer Moore法って?

[iww]

『GPLライセンスのツールをBSDライセンスで開発して置き換える取り組み』 そんなことやっちゃっていいの？ソース見ながら再実装して大丈夫なのかな

[t_ita]

GNU grepの早さの秘訣。なるほど、参考になる。