PHPとPythonとRubyの連想配列のデータ構造が同時期に同じ方針で性能改善されてた話 - hnwの日記
PHPとPythonとRubyの連想配列のデータ構造がそれぞれ4〜5年ほど前に見直され、ベンチマークテストによっては倍以上速くなったということがありました。具体的には以下のバージョンで実装の大変更がありました。 PHP 7.0.0 HashTable高速化 (2015/11) Python 3.6.0 dictobject高速化 (2016/12) Ruby 2.4.0 st_table高速化 (2016/12) これらのデータ構造はユーザーの利用する連想配列だけでなく言語のコアでも利用されているので、言語全体の性能改善に貢献しています1。 スクリプト言語3つが同時期に同じデータ構造の改善に取り組んだだけでも面白い現象ですが、さらに面白いことに各実装の方針は非常に似ています。独立に改善に取り組んだのに同じ結論に至ったとすれば興味深い偶然と言えるでしょう2。 本稿では3言語の連想配列の従来実
Ruby競プロTips(基本・罠・高速化108 2.7x2.7)
計測方法は、(10**6).times{ }のような最小限のコードです。 実際、制限時間が2秒だとして、10の7乗台前後から、想定解法でも厳しくなってくる印象です。 それ以前の1,000,000回(10の6乗)で2秒超えてTLEするなら、自分の書いたアルゴリズムを疑いましょう。 今のC++は10の7乗だと「余裕をもって間に合う」レベルらしいので、C++と比べるとRubyは10倍遅い感じです。 競技プログラミングでは、問題に与えられた要素数も 方針・アルゴリズムを考えるヒントになるので、このあたりの感覚はもっておくとよさそうです。 高速化手法のまとめ・見方 先に高速化のまとめがあった方が親切かと思い、簡単にまとめておきます。 (まとめの方にしか書いてないのもあります……) 本記事は、アルゴリズムの話も少し混じっていますが、アルゴリズムはRubyに限らないので、ほぼ触れてません。 「アルゴリズ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
