2020-04-03: weekly crystal #1した

やったこと

昨日出したRegex#matches?のPRの続き。
この議論絶対必要ないと思うんだけどな‥‥、と考えながら書いた。
何の根拠もなくeasily confusingとか言ってるし、そのあと話題が逸れるしでロクなことがない。

こっちは今日出したPR。
SemanticVersion::Prereleaseが<=>メソッドを定義してるのにComparableをincludeしていなくて不思議だったので。
基本的には部分なので無くてもそこまで問題じゃないけど、あって困るものでもないよなぁ、と思う。

まあこういうどうでもいいPRは放置されがちだし、ボクも別にやる気があるわけではないので放置されても別にいいかな、という思いでやっていく。
‥‥と思ったがあっさりマージされた。マジか。

Enumerable#firstにブロック渡す版を追加した。
なんかIndexableのfirstとかfirst?も消せるんじゃない、と言われたので対応したい。
明日やる。

Arrayとかが再帰的なときでも==とかhashが動くように修正した。
記念すべき9000番目のPull Request。やったぜ。

パフォーマンス的にどうなの、という疑問があるので、その辺どうなるかなぁ、と見守りたい。

Indexable#reverse_mapを追加した、というPRが出ていたのだけど、ベンチマークがあんまりだったのでmap.reverse!と比較してみたら、ほとんど速度が変わらなかった。
要素数増やしたらどうなるか微妙なところだけど‥‥。

これに関してはユースケースがあるとか、他の言語でどうかとかが大事かなぁ、という気がするけど、このPRの作者にそこまでやる気があるのかが不明。
first time contributorに厳しく当たりすぎているかもしれない。

やりたい。
が人が集まらない気がする。
2・3人いればいいんだけどな。

なんかやる気になったのでやった。
Hangoutでつないで、1時間くらいissueとかPRを見ていた。
色々と発見があった気がする。

一応見たissueなどはまとめてあるので、そのうち公開するかも。
(Slackには貼ってある)

永遠に理解できていないので、いい加減理解したい。

考えた人の名前を取ってCrochemore-Perrinのアルゴリズムとも言うらしい。

大本の論文:

解説:

日本語の解説があって良かった。
結局論文を読んだのだけど。

で、分かったこと:

文字列には周期という値と、文字列の各位置毎に局所周期という値があり、これらの最小の値が一致する位置(最小周期以下)がどんな文字列にも存在する、という定理がある。
この位置をcritical positionと呼び、Two-Way Searchでは探索する文字列のcritical positionを求め、これを中心に左右に分割した文字列を比較していく。
周期と局所周期の性質から、重複して文字の比較を行なわないようにすることができる。
critical positionは文字列の辞書式順序を上手く用いると、探索する文字列の長さの2倍の回数の比較、かつ定数のメモリで求めることができる。

という感じ。
正直そこまで分かっていないのだけど、これ以上は文字列アルゴリズムへの理解をもっと深めないと無理なのではないかという気がしている。

問題はこれをCrystalに実装する価値があるかどうかだなぁ。
パフォーマンス次第かな。