AppendOnly
1.0.0
高速 C# の不変追加専用リスト。 (更新:23 9 月 24 日; 使用は推奨されません。根拠と代替案については下部の注を参照してください。)
dotnet add パッケージ AppendOnly
まず、既存の不変コレクションでは、追加、削除、および新しいコレクションを返す更新を行うことが非常に困難です。彼らは文字通り、たくさんのものをコピーしなければなりません。追加するだけの場合、LinkedList はあなたの友人であり、即座に「コピー」されたように見える可能性があります。
次に、既存の不変ライブラリは複雑で使いにくいです。ビルダー クラスと実際の仕組みをよく理解していることが必要です。そうでないと、パフォーマンスに重大な問題が発生します。
最後に: このクラスは、非常にタイトなループで使用しても完全に安全です。できるだけきつめに。
AppendOnly は内部で linkedList を使用し、新しい「不変」コピーを作成するときにコレクション項目をコピーしません。同じ内部の「変更可能な」linkedList を共有する新しいコレクション クラスを返すだけで、それを変更するメソッドは公開されず、コレクション内の最初 (n) 個の項目を反復処理するインタレーターのみが公開されます。
そのため、コレクションが大きくなるにつれて、コレクション クラスの以前の (古い) インスタンスは、リストの最後に追加された新しいエントリを決して認識することはありません (列挙子を介して公開されます)。 1000 個の新しい「トランザクション」を appendOnlytransactionCollection に追加すると、(新しく作成された各コレクションへの参照を保持していれば) それぞれ 1、2、3、4 などの項目を含むコレクションへのポインターが 1000 個存在しますが、追加のポインターはほぼゼロになります。メモリのオーバーヘッド。
ビルダーで他の不変ライブラリを使用する場合、ほとんどの場合、オブジェクトの少なくとも 500,000 インスタンスが提供されます。
間違っているかもしれませんが、これは出発点です。これを使用する場合はお知らせください。私は同様の方針に沿ってさらに多くのコレクションを作成するつもりです。
var move = new AppendOnlyList<Moves>();var new_moves = new AppendOnlyList<Moves>();Debug.Assert(moves.Length == 0);// 10 個のランダムな動きを追加 for(int i=0; i<10 ; i++) new_moves = new_moves.Add(randomMove());// new_list が追加したにもかかわらず、元の移動にはまだ項目がありません。 item to the List.Debug.Assert(moves.Length == 0);// new_list のコレクションには 10 個の項目がありますDebug.Assert(new_moves.Length == 10);// このリストは複数回繰り返しても安全であり、 threadsafe// 以下のコードは、リスト全体を 10 回反復することを示しています。これは、通常は列挙可能オブジェクトをキャッシュした場合、// 列挙可能オブジェクトに対してのみ実行する処理です。 local copy.// これはあまり役に立っていないように見えますが、これは非常に重要です。 // また、他のスレッドが同じ基礎となるコレクションへの追加で忙しいときにこれを実行しても安全です。 // これは、スレッドの世界では大して禁止されています。ここでは、完全に安全です。for(int i = 0; i<10; i++){foreach(var move in new_moves.Items) await DoSomethingFunkyAsync(move);}上記のコードでは、 new_movesと元のmoves同じ基礎となるリンク リストを共有します。 AppendOnlyList の新しいコピーが作成されるとき、新しいクローンは作成されず、リストの先頭へのポイントのみが作成され、長さは維持されます。
これは非常に高速であり、コピーが作成されないため、コピーを作成する他の不変コレクションよりも無限に高速です。
また、他のスレッドから列挙されている間、コレクションを反復処理することはスレッドセーフです。ブーム！ ... より具体的に言うと、「ブームがありません!」。
これはバージョン0.1.3であり、運用環境で使用する準備ができていないことを意味します。これは概念実証であり、上記の主張を証明するためにいくつかのスレッド テストを作成し、同僚にレビューして知らせるよう依頼する必要があります。
また、このコレクションと他のコレクションの速度比較、および並べての比較も行いたいと考えています。
このパッケージが気に入ったら、実際の実装を見てください。文字通り、 AppendOnlyListとLinkedListExtensions 2 つのクラスであり、それらは非常に小さいです。
どう思うか教えてください?
:D
ご質問がございましたら、私に連絡してください、
Alan Hemmings, twitter : @snowcode LinkedIn : https://www.linkedin.com/in/goblinfactory www : https://goblinfactory.co.uk
...あまり使わず、忘れていました。私がこれを書いて以来、物事 (C#) は大きく進歩しました。C# には多くの変更がありましたが、どれも物事を大幅に簡素化するものではありませんでした。残念ながら、新しい言語の変更を考慮して、このパッケージをいつ使用するかについての上記の私の考えはくだらないものであり、...かなり欠陥がある可能性があると思います。さらに何かを行う前にテストが必ず必要です。以下は、AI C# アーキテクトとの簡単なチャットからのメモで、このプロジェクトの見直しを示唆しています。 TBH このプロジェクトはまだ保証されるかもしれないと思いますが、おそらく、appendonly 型構造を適切に作成するためのさまざまな方法を中心とした DSL ラッパー (単純なファクトリー クラスの一種) としてです。ナフは言った。これがフィードバックです。
(草案メモ、テストして確認する必要があります!)
はい、C# では、 System.Collections.Generic.ArrayBuffer<T>またはSystem.Buffers.ArrayPool<T>を使用して、効率的に列挙できる追加専用構造とメモリ効率の高い構造を実現できます。ただし、より実用的で効率的な追加専用の構造が必要な場合は、次のオプションを検討してください。
ImmutableArray<T>.Builder
System.Collections.Immutableパッケージによって提供される追加専用の構造。
これにより効率的な追加が可能になり、ビルド中は変更可能ですが、 ImmutableArray<T>に変換されると不変になります。
var builder = ImmutableArray.CreateBuilder<int>();builder.Add(1);builder.Add(2);var immutableArray = builder.ToImmutable();
Memory<T>とSpan<T>とArrayPool<T>
最小限のメモリ割り当てで大きなデータ ブロックを効率的に処理できます。
メモリを自分で管理するため、 List<T>と比較して頻繁な再割り当てが回避されます。
メモリ使用量をさらに制御したいが、慎重な管理が必要な場合に適しています。
var pool = ArrayPool<int>.Shared;int[] array = pool.Rent(1000); // プールから配列をリクエストします// ここにデータを追加して管理しますpool.Return(array); // 完了したらプールに戻ります
ValueListBuilder<T> (System.Buffers から)
スタック割り当て方式でコレクションを構築する効率的な方法を提供します。
データ サイズが制限されていることがわかっていて、ヒープ割り当てなしで高いパフォーマンスが必要な場合に特に役立ちます。
Span<int>InitialSpan = stackalloc int[16]; var valueListBuilder = new ValueListBuilder<int>(initialSpan);valueListBuilder.Append(1);valueListBuilder.Append(2);ReadOnlySpan<int> スパン = valueListBuilder.AsSpan();
System.IO.Pipelines のSequence<T>
追加のみの方法で一連のデータを効率的に処理するのに適しています。
高性能の I/O 操作とストリーミング データを必要とするシナリオに適しています。
List<T> : 追加 (償却されたO(1) ) に適しており、連続したメモリにより高速な列挙が可能です。
ImmutableArray<T>.Builder : 追加して不変にするのに効率的です。
Memory<T>とArrayPool<T> : 割り当てを減らすのに最適です。
ValueListBuilder<T> : サイズがわかっている場合の効率的なスタックベースの構築。スタックベースで、一時的で効率的なコレクションに適しています。
Sequence<T> : 効率的な追加が必要な高スループットのシナリオ用。
特定のパフォーマンスとメモリ要件に基づいて選択してください。
ChatGPTは言いました。
C# のLinkedList<T>は追加専用メモリ構造のオプションですが、次の理由により、他の構造に比べて一般にメモリ効率が低く、列挙が遅くなります。
LinkedList<T>に関する考慮事項:メモリ オーバーヘッド: LinkedList<T>内の各ノードには次のノードと前のノードの両方への参照が含まれるため、配列やList<T>のような連続した構造と比較して大幅なメモリ オーバーヘッドが発生します。
キャッシュの非効率性: 連続したメモリに格納される配列やList<T>とは異なり、 LinkedList<T>ノードはヒープ全体に分散されます。これにより、キャッシュフレンドリー性が低下し、反復とアクセス時間が遅くなります。
列挙パフォーマンス: LinkedList<T>追加操作 (最後に追加する場合はO(1) ) には効率的ですが、キャッシュの局所性の利点がないため、列挙パフォーマンスは通常、配列やリストよりも遅くなります。
LinkedList<T>を使用する場合:両端または途中で頻繁に挿入または削除が必要な場合。
List<T>のように要素をシフトすることを避けたい場合。
LinkedList<T>追加専用のシナリオに使用できますが、一般に、 List<T>やその他の最新のデータ構造と比較して、列挙やメモリ使用量に関しては最も効率的な選択肢ではありません。
