ImmutableListはaddメソッドで複雑さO（logN）を持つのはなぜですか？

N + 1個の新しいImmutableListが作成されると思います。したがって、その複雑さはO（N）でなければならない。ImmutableListはaddメソッドで複雑さO（logN）を持つのはなぜですか？

2016-05-18 Tian Xiao

まあ、彼らは素朴な実装よりも、それをより効率的にすることにしました。それのどこが悪いんだい？ –

より多くのアイテムを含む新しいリスト全体が作成されているというあなたの信念は間違っています。既存の構造の一部を安全に再利用して新しい構造を構築できることを覚えておいてください。その再利用は、多くのシナリオで高効率を実現します。 –

純粋に機能的なデータ構造についてもっと知りたければ、Chris Okasakiの本を見てみることをお勧めします。 – TheInnerLight

ImmutableListはO（Nログ）複雑さがhereに説明された理由は：

なぜ不変のタイプは可変タイプはO（1）である（ログn）時間Oしやすいがありますか？コレクションのインスタンス間で共有できる内部データ構造の結果です。たとえば、変更可能なHashSetは、単一の配列を割り当て、その配列をという配列に、そのハッシュコードで指定されたインデックスに格納します。このプロバイダー O（1）検索と保管時間。 ImmutableHashSetが同じのデータストレージを使用していた場合は、アレイ全体を再割り当てしてコピーするだけで、は、コレクションが大きく成長したときにパフォーマンスとGCの圧力を迅速に調整します。代わりに、これらの不変コレクションは 不変の平衡二分木を使用してデータを保存します。 は、コレクションの突然変異したインスタンス間で効率的なデータ共有を可能にします。しかしながら、結果として、すべてのルックアップまたは変更は、（最悪の場合に）O（log n）のアルゴリズム複雑度を有するツリートラバーサルを必要とする。

MSDN documentation for ImmutableArrayは、いくつかの洞察を提供し、ImmutableArrayとImmutableList間の複雑さの違いを示しています

出典

2016-05-18 15:47:45

このドキュメントは 'ImmutableList .Builder.ToImmutable（）'にあります。これは議論されている方法ではありません。 –

無効なリンクを削除しました。私はMSDNのドキュメントから別のものを探すつもりです。 –

ImmutableListはaddメソッドで複雑さO（logN）を持つのはなぜですか？

答えて

関連する問題