c - 効率的なリストデータ構造

Question

プロジェクトに実装するには、リストタイプのデータ構造が必要です。実際には、ある種のリストである必要はありませんが、高速である必要があり、データ（他のデータ構造）を常に挿入/削除/取得するために使用します。何かを挿入、検索、再挿入、削除、再検索などを行う可能性があるため、アクションはランダムです。

これまでのところスキップリストが最速であることがわかりましたが、それよりも速いものは何ですか？

Answer 1

ハッシュテーブル/hashmap/dictionaryはあなたが望むもののように聞こえます。たとえば、Pythonの辞書。

Answer 2

あなたはBTreeを調べるかもしれません

Answer 3

選択する言語に大きく依存します。C を使用すると、最終的なデータ構造を最大限に制御でき、最速の実装の 1 つになります。もちろん、自分の足を撃つことは非常に簡単です。むしろ悪い。Python は多くのリスト データ構造を抽象化しており、一貫して高速であることがわかりますが、それほど強調しているわけでもありません。

タスクに再利用できるビルド済みの C ライブラリのフレッシュミートをチェックすることをお勧めします。おそらく、ウィキペディアのスキップ リストに関するページを参照してください: http://en.wikipedia.org/wiki/Skip_list

データ構造は、大きな O 表記法と、「速度」と「効率」について話すときにそれが何を意味するかについての適切な基礎を必要とする深い主題です。そうしないと、客観的な比較を行うことができなくなります。最後に、すべてにトレードオフがあります。データとその操作方法の両方を最もよくモデル化するデータ構造を選択します。タスクがかなりランダムな場合は、設計段階に戻り、データ構造に到達する前に何が起こるかをどのように改善できるかを自問してください。つまり、アルゴリズムを練り上げてから、それを補完するデータ構造を選択します。