performance - リスト全体をコピーして要素を追加することは、単に追加するよりも効率的ですか?

Question

不変リストに追加する方が効率的であると主張する人もいます。これは本当ですか？どのように？

Answer 1

不変オブジェクトは、同期なしでスレッド間で共有できます。同期はスケーリングに悪影響を及ぼし、コピーよりもコストがかかる可能性があります。

Answer 2

変更されたバージョンを保持するのに十分な大きさの配列を割り当て、変更されていないすべての要素をコピーすることによってリストの変更されたバージョンを生成することは、変更が追加、挿入、削除、置換、またはその他のものであるかどうかに関係なく、いくらかコストがかかります。 . このコストは、リストの変更されていないが別個のコピーを作成するコストとほぼ同じです。

オブジェクトFooが変更されたときにのみ変更できるように要素のリストを維持したい場合、Fooそれを行うために使用できる一般的な方法が 2 つあります。

1. これまでに外部の世界に公開されたインスタンスが同じオブジェクトのシーケンスを永久に保持することを保証する「不変リスト」タイプを使用できます。オブジェクト `Foo` は、誰も変更できないため、このリストへの参照を自由に公開できます。たとえば、`Foo` がそのリストに項目を追加したい場合、リスト内のすべての項目と新しい項目を含む新しい不変リストを生成し、古い項目の代わりにそれへの参照を保持し始めます。
2. 変更可能なリスト オブジェクトを作成できますが、外部の世界には決して公開されません。誰かがリストから項目のシーケンスを取得する必要がある場合、`Foo` はリストの内容を新しいリストにコピーし、呼び出し元は `Foo` のリストに影響を与えずに適切と思われる方法で使用できます。

アプローチ #1 を使用する場合、リストを変更するたびにFoo、新しい「不変リスト」インスタンスを作成する必要がありますがFoo、リストのコンテンツをコピーすることなく要求に答えることができます。アプローチ 2 を使用する場合、リストへのアイテムの追加 (およびその他の変更) は安価になりますが、リストの内容に対する要求に答えるには、リストをコピーする必要があります。アプローチ 1 とアプローチ 2 のどちらを使用するのが良いかは、リストが更新される頻度と、アプリケーションがリストのコピーを必要とする頻度によって異なります。