■_
DEC 25 == OCT 31
2015年10月25日
■_
木枯らし「一号」とかいつ頃から言い始めたんすかね。
そしてまた「ナンバーカード」が連呼される時期に。
世界の艦船の最新号で「ビッグ7」特集なんだけど、 実際のところアメリカやイギリスでその呼称を使っていたのは疑わしいし (アメリカでは自分のところの大きいの5隻で「Big 5」と呼んでいたような記述が うぃきぺ(英文)にあったし、イギリスはネルソン/ロドネーよりもフッドの方がお気に入りっぽい)、 そもそも戦前からあった言葉なんですかね＞「ビッグ7」 The Big 5
世界の艦船 2015年 12 月号 [雑誌]
Ships of the world mainmenu(J)
■_
以前他の記事で見たことのあるblogだけど くわしく GNU grep のこと追いかけてた。 まもなくgrep 2.22リリース - 気ままなブログ の後半部分から。
まもなくgrep 2.22リリース - 気ままなブログ 今後追加される見込みの改善内容 マルチスレッド化GNU grepは高速に動作しますが、シングルスレッドで動作するため、 複数のプロセッサを搭載したマシン上でもそのマシン性能を十分生かすことができませんでした。 現在のリリースでもGNU parallelなどと組み合わせれば並列化できますが、 マルチスレッド化されることで単体で並列化できるようになります。
grep -Fで複数パターンを指定した時のアルゴリズムの変更現在のリリースではgrep -Fで複数パターンを指定するとBeate Commentz-Walterアルゴリズムを使用します。 Beate Commentz-WalterアルゴリズムはBoyer-Mooreアルゴリズムを複数パターンで使えるように拡張したものですが、 プロセッサのキャッシュの仕組みを十分に活かすことができないため、あまり高速ではありませんでした。 さらに、Beate Commentz-Walterアルゴリズムには、 Boyer-Moore法に適用できるガリル規則を適用することができないため、 最悪のケースではO(m*n)となってしまう欠点がありました。
提案されている方法は、grep -Fで複数パターンを検索するときのアルゴリズムを、 Beate Commentz-Walterアルゴリズムから、Aho-Corasickアルゴリズムに置き換えるものです。 これにより上記の欠点が解消され、大幅な性能改善が期待されます。
非UTF-8マルチバイトロケールで「.」を含むパターンによる検索の高速化非UTF-8マルチバイトロケールにおける「.」*1は、 事前に入力文字の現在位置から何バイト消費するか判断することが難しいため、 この部分を事前にコンパイルすることが難しく、インタプリタ的に動作していました。
提案されている方法は、非UTF-8マルチバイトロケールで「.」 に対するステート遷移の結果をキャッシュすることで高速化が図られています。
■_
もういっこ。 GNU sedのパフォーマンス - 気ままなブログ
ちなみに、私見ですがGNU sed、GNU awk、GNU grepの中では、
GNU sedのソースコードがいちばんきれいで読みやすいと思います。
GNU sed はあまりりよく覚えてないんだけど(ここ数年いじってないし)、 たしかに残り二つは(ry
