リストから項目をすばやく削除する方法

質問

私は、C# の List<T> . ドキュメントによると List.Remove() と List.RemoveAt() の操作は、どちらも O(n)

• リスト.削除
• リスト.RemoveAt

これは私のアプリケーションに深刻な影響を及ぼしています。

私はいくつかの異なる削除方法を書き、それらをすべて List<String> でテストしました。 テストケースは以下の通りです...

概要

私は、各数字の文字列表現 ("1", "2", "3", ...) を単に含む文字列のリストを生成するメソッドを書きました。 次に、私は remove を5番目の項目ごとに実行しました。 以下は、リストを生成するために使用されるメソッドです。

private List<String> GetList(int size)
{
    List<String> myList = new List<String>();
    for (int i = 0; i < size; i++)
        myList.Add(i.ToString());
    return myList;
}

テスト1：RemoveAt()

以下は、私がテストに使った RemoveAt() メソッドを使用したテストです。

private void RemoveTest1(ref List<String> list)
{
     for (int i = 0; i < list.Count; i++)
         if (i % 5 == 0)
             list.RemoveAt(i);
}

テスト2：Remove()

以下は、私がテストに使用した Remove() メソッドを使用したテストです。

private void RemoveTest2(ref List<String> list)
{
     List<int> itemsToRemove = new List<int>();
     for (int i = 0; i < list.Count; i++)
        if (i % 5 == 0)
             list.Remove(list[i]);
}

テスト3：nullに設定、ソート、そしてRemoveRange

このテストでは、リストを1回ループして、削除される項目を null . それから、リストをソートして (null が一番上になるように)、一番上にある null に設定されたすべての項目を削除しました。 注: これによってリストの順序が変わったので、正しい順序に戻さなければならないかもしれません。

private void RemoveTest3(ref List<String> list)
{
    int numToRemove = 0;
    for (int i = 0; i < list.Count; i++)
    {
        if (i % 5 == 0)
        {
            list[i] = null;
            numToRemove++;
        }
    }
    list.Sort();
    list.RemoveRange(0, numToRemove);
    // Now they're out of order...
}

テスト4: 新しいリストを作成し、すべての "good" 値を新しいリストに追加します。

このテストでは、新しいリストを作成し、すべての keep-item を新しいリストに追加しました。それから、これらの項目をすべて元のリストに入れました。

private void RemoveTest4(ref List<String> list)
{
   List<String> newList = new List<String>();
   for (int i = 0; i < list.Count; i++)
   {
      if (i % 5 == 0)
         continue;
      else
         newList.Add(list[i]);
   }

   list.RemoveRange(0, list.Count);
   list.AddRange(newList);
}

テスト5：nullに設定してからFindAll()

このテストでは、削除される予定のすべての項目を null に設定し、次に FindAll() でないものをすべて見つけるために null

private void RemoveTest5(ref List<String> list)
{
    for (int i = 0; i < list.Count; i++)
       if (i % 5 == 0)
           list[i] = null;
    list = list.FindAll(x => x != null);
}

テスト6：nullに設定してからRemoveAll()する。

このテストでは、削除されるすべての項目を null に設定し、次に RemoveAll() 機能を使って、すべての null

private void RemoveTest6(ref List<String> list)
{
    for (int i = 0; i < list.Count; i++)
        if (i % 5 == 0)
            list[i] = null;
    list.RemoveAll(x => x == null);
}

クライアントアプリケーションと出力

int numItems = 500000;
Stopwatch watch = new Stopwatch();

// List 1...
watch.Start();
List<String> list1 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest1(ref list1);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 2...
watch.Start();
List<String> list2 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest2(ref list2);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 3...
watch.Reset(); watch.Start();
List<String> list3 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest3(ref list3);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 4...
watch.Reset(); watch.Start();
List<String> list4 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest4(ref list4);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 5...
watch.Reset(); watch.Start();
List<String> list5 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest5(ref list5);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

// List 6...
watch.Reset(); watch.Start();
List<String> list6 = GetList(numItems);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

watch.Reset(); watch.Start();
RemoveTest6(ref list6);
watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
Console.WriteLine();

結果

00:00:00.1433089   // Create list
00:00:32.8031420   // RemoveAt()

00:00:32.9612512   // Forgot to reset stopwatch :(
00:04:40.3633045   // Remove()

00:00:00.2405003   // Create list
00:00:01.1054731   // Null, Sort(), RemoveRange()

00:00:00.1796988   // Create list
00:00:00.0166984   // Add good values to new list

00:00:00.2115022   // Create list
00:00:00.0194616   // FindAll()

00:00:00.3064646   // Create list
00:00:00.0167236   // RemoveAll()

備考・コメント

• 最初の 2 つのテストは、実際にはリストから 5 番目の項目すべてを削除していません。なぜなら、削除のたびにリストが並べ替えられるからです。実際、500,000 の項目のうち、83,334 の項目だけが削除されました (100,000 であるべきでした)。 私はこれで良いと思います。明らかにRemove()/RemoveAt()メソッドは、いずれにしても良いアイデアではありません。

• リストから5番目の項目を削除しようとしましたが、中の 現実 では、そのようなパターンはありません。 削除される項目はランダムになります。

• を使ったものの List<String> を使いましたが、常にそうなるとは限りません。 これは List<Anything>

• そもそもリストに項目を入れないのは ではなく というオプションがあります。

• 他の方法 (3 ～ 6) はすべて、はるかに優れたパフォーマンスを示しました。 比較的に しかし、少し心配なことがあります。3, 5, 6 では、値を null に設定し、このセンチネルに従ってすべてのアイテムを削除することを余儀なくされました。 なぜなら、リスト内のアイテムの1つが null であり、意図せずに削除されてしまう可能性があるからです。

私の質問は：多くのアイテムを素早く List<T> ? 私が試したアプローチのほとんどは、私には本当に醜く、潜在的に危険なものに見えます。 というのは List は間違ったデータ構造なのでしょうか？

今は、新しいリストを作成して、良い項目を新しいリストに追加する方向に傾いていますが、もっと良い方法があるように思います。

どのように解決するのですか？

削除に関しては、リストは効率的なデータ構造ではありません。削除には隣接するエントリの参照更新が必要なだけなので、二重リンクリスト (LinkedList) を使用する方がよいでしょう。