c# - 配列内での配列セグメントの移動

Question

アイテムの配列がある場合:

1, 2, 3, 4, 5, 6, 7, 8

アイテムの範囲を選択し、それらを配列内の別の位置に移動したいと考えています。例えば：

1, 2, 5, 6, 7, 3, 4, 8

ここでは、5、6、7 セグメントがインデックス 2 に移動されています。

特に余分な配列コピーの数を制限するために、これを行う最も効率的な方法は何ですか。バージョンは動作していますが、効率が悪く、最適化しようとしているアルゴリズムの中心的な役割を果たしています。

ありがとう。

Answer 1

リンクされたリストを使用してみてください。リストのサブセクションを移動しているので、同じサブリスト内の個々の項目をコピーするよりも、サブリストの両端にある参照を移動する方がメモリ効率がはるかに高くなります。全体的な時間の複雑さは同じですが (リンクされたリストをトラバースするための Θ(n)、配列セグメントをコピーするための Θ(n) )、メモリの複雑さは向上します (Θ(n) ではなく定数 n) と継続的なメモリの割り当て/割り当て解除に関する問題が少なくなります。

Answer 2

効率のために配列のコピーを作成したくない場合は、それらを完全に回避できます。単一の値に最小限の変数を使用して、アイテムを新しい宛先に移動できます。このようなアルゴリズムは、メモリ上で非常に効率的であり、全体的にも効率的ですが、ネイティブで効率的な配列コピーを利用できないことは明らかです。