木の代わりにSean Parentの「靴ひもと豆」のデータ構造を見つけるには

Question

Sean ParentのCppCon 2015のトーク「Better Code: Data Structures」を見て、ツリーの代わりに「靴ひもと豆」 データ構造を提案しました。

どのようにそれを見つけるのですか？これは木より優れていると思いますか？その強さはどういう価格ですか？

Answer 1

あなたが測定したものによりますが常に良いです。
ここでは品質メトリクスのためのいくつかの可能性：

• メモリ使用量
• ランダムアクセス速度
• トラバーサルスピード
• ...

あなたはまた、最悪の場合の動作や平均を見ることができますケースの挙動。

だから、「より良い」とは、どのような環境条件/制限の下でそれを使用するかによって大きく左右されます。

少なくとも、キャッシュミス（キャッシュプリフェッチ）特性は通常のツリー構造よりも優れています。これは、要素がメモリ内を走査する順序にある​​ためです。

Answer 2

対応するツリーの左の再帰的な降下に対応するので、靴ひもは作りやすくなります。だから、木から始めて、それを一度降りてレースをダイナミックに構築するだけです。その後、レースは単純に左側の再帰的降下のように順序付けられた要素のリンクリストであるため、再帰はもう必要ありません。

ツリーよりも良い？それはあなたがしたいことにかかっています。