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言語の連想配列の従来実
双方向連結リスト
概要 「片方向連結リスト」でも説明しましたが、 ノードと呼ばれる物を1つずつ連結して作るコレクションを連結リスト と呼びます。 「片方向連結リスト」では、各ノードに「次のノード」の情報を持たせることで、 ノードを連結していました。 これに対して、 各ノードが「次のノード」だけでなく「前のノード」の情報も持っているものを双方向連結リスト（bidirectional linked list）と呼びます。 「片方向連結リスト」には制限が多く、用途の幅がそれほど広くないのに対して、 こちらはコレクションとしていろいろと応用が利きます。 片方向連結リスト 特徴 双方向連結リストは以下のような利点を持っています。 「片方向連結リスト」と同様に、常に要素数分のメモリだけ確保しておける。 あるノードの直後および直前に新しい要素を挿入する場合、一定時間（O(1)）で行える。 あるノードの削除を一定時間（O(
B-treeインデックス入門 - Qiita
B-treeがMySQLで使用されている背景から、B-treeインデックスの構造、そしてそれに基づいたインデックスの使用方法の入門編です。以下の流れに沿ってまとめていきます。 インデックスってなに？ B-treeってなんでインデックスに使われているの？ B-treeインデックスの構造 インデックスの使用方法 ※ 勉強をかねてまとめていることもあり、間違っている箇所がございましたら教えていただけると嬉しいです。 インデックスってなに？ 全体の内容の中から特定部分を探すために使用する、本の索引のような概念のことです。これを用いることで、検索を高速化することができます。 特定の項目が本のどこに載っているかを確認するために索引を調べることで、全ページを順に調べなくても、その項目が登場するページ番号がわかる MySQLのストレージエンジンでも、インデックスが同様の方法で利用されており、インデックスの
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Microsoft PowerPoint - ad13-代行2.ppt [互換モード]
http://www.dais.is.tohoku.ac.jp/~shioura/teaching/ad11/ad11-02.pdf
一週間で身につくアルゴリズムとデータ構造|入門編5日目：アルゴリズムの例②
俺とお前とlaysakura
