はじめに
C# で配列内の要素を削除するのは一般的な操作です。この記事では、通常削除とスワップ削除（高速削除）という2つのよく使われる方法を紹介します。それぞれの時間計算量を比較し、使用例を示すコードも提供します。
通常削除
通常削除とは、配列を走査し要素を移動させて指定された要素を削除する方法です。この方法の時間計算量は O(n) で、n は配列の長さではなく、削除する要素の位置によって変わります。指定された配列要素を削除した後、後ろの要素を前方に移動させる必要があるため、削除操作の時間計算量は高くなります。
以下は通常削除のサンプルコードです。
int[] array = new int[] { 1, 2, 3, 4, 5 };
int index = 2; // 削除する要素のインデックス
for (int i = index; i < array.Length - 1; i++)
{
array[i] = array[i + 1];
}
Array.Resize(ref array, array.Length - 1);
foreach (int element in array)
{
Console.WriteLine(element);
}
出力結果は以下の通りです。
1
2
4
5
スワップ削除（高速削除）
スワップ削除とは、要素の位置を交換することで配列内の要素を削除する方法です。具体的な手順は次の通りです。
- 削除したい要素と配列の最後の要素を交換します。
- 配列の最後の要素を削除します。
この方法の時間計算量は O(1) です。なぜなら、1回の交換と1回の削除操作のみで済み、最後の要素を削除するだけなら操作は1回だけだからです。1 は固定された操作回数を指すのではなく、配列の長さに関係なく操作回数が一定であることを意味します。
以下はスワップ削除のサンプルコードです。
int[] array = new int[] { 1, 2, 3, 4, 5 };
int index = 2; // 削除する要素のインデックス
if (index < array.Length - 1)
{
array[index] = array[array.Length - 1];
}
Array.Resize(ref array, array.Length - 1);
foreach (int element in array)
{
Console.WriteLine(element);
}
出力結果は以下の通りです。
1
2
5
4
まとめ
通常削除とスワップ削除（高速削除）の時間計算量を比較すると、スワップ削除の方がほとんどの場合で効率的であることがわかります。通常削除は配列を走査して要素を移動させる必要があるため時間計算量が O(n) であるのに対し、スワップ削除は1回の交換と1回の削除操作のみで済むため O(1) です。
ただし、スワップ削除は順序がバラバラな配列にのみ適用できる点に注意が必要です。なぜなら、交換操作によって要素の相対的な順序が変わるからです。配列がソート済みの場合、スワップ削除はその順序を壊してしまい、配列を再ソートする必要があります。
また、スワップ削除は配列の連続性を維持する必要がある場合にも適していません。削除操作によって配列の長さが短くなるためです。配列の連続性を維持する必要がある場合は、List<T> や LinkedList<T> などの他のデータ構造の使用を検討してください。
この記事が、C# の配列内の要素を高速に削除する方法の理解に役立てば幸いです。ご質問やご提案があれば、お気軽にコメントをお寄せください。