簡潔ビットベクトルでRubyをlog N倍速くした - クックパッド開発者ブログ
技術部のフルタイムRubyコミッタの遠藤（@mametter）です。昨日の Hackarade #04 の開催報告に続き、2日連続で記事を投稿します。 今回は、ある条件下でのRubyの実行速度を高速化した話を紹介します。この改善はすでにMRIの先端にコミットされていて*1、年末リリース予定のRuby 2.6に含まれる予定です。 ひとことで言うと、「簡潔ビットベクトルを索引に使うことで、プログラムカウンタから行番号を計算するアルゴリズムをO(log N)からO(1)に改善した。これにより、TracePoint有効時やコードカバレッジ測定下で、長さ N のメソッドの実行が O(N log N) から O(N) に高速化される」ということです。順に説明します。 背景：Rubyのバイトコードの構造 この最適化を理解するにはまず、Rubyのバイトコードのある特徴を知る必要があります。 たとえば x
Rational を10進小数展開するアルゴリズムを実装した - mrkn 記
CRuby の Feature #8850 で提案されている Rational を10進小数展開する機能を実装してみた。 循環節の検出は、セルオートマトンの周期解を検出するときに使った手法を応用した。 この手法では、1桁ずつの展開 (標準展開) と2桁ずつの展開 (倍速展開) を同時に進め、両者の状態 (剰余) が等しくなったときに循環を見付けたことになる。 標準展開の末尾の位置と倍速展開の末尾の位置の差が循環節の長さに一致する。 循環節の先頭位置を見付けるには、標準展開と倍速展開のそれぞれの末尾から1桁ずつ前に戻りながら桁の値を比較していけば良い。 たとえば、循環を検出した時点で以下のような小数展開が得られたとしよう。 123.4567891357924680123450987613579246801234 ^ 標準展開の末尾 ^ 倍速展開の末尾 標準展開の末尾と倍速展開の末尾にあるカー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
