Frage So entfernen Sie schnell Elemente aus einer Liste


Ich bin auf der Suche nach einem Weg, um Elemente aus einem C # schnell zu entfernen List<T>. Die Dokumentation besagt, dass die List.Remove() und List.RemoveAt() Operationen sind beides O(n)

Dies beeinträchtigt meine Anwendung erheblich.

Ich habe ein paar verschiedene Remove-Methoden geschrieben und alle auf a getestet List<String> mit 500.000 Artikeln. Die Testfälle sind unten gezeigt ...


Überblick

Ich schrieb eine Methode, die eine Liste von Zeichenfolgen erzeugen würde, die einfach Zeichenfolgedarstellungen jeder Zahl ("1", "2", "3", ...) enthält. Ich versuchte es dann remove jeder fünfte Artikel in der Liste. Hier ist die Methode, um die Liste zu erstellen:

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;
}

Test 1: RemoveAt ()

Hier ist der Test, den ich verwendet habe, um das zu testen RemoveAt() Methode.

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

Test 2: Entfernen ()

Hier ist der Test, den ich verwendet habe, um das zu testen Remove() Methode.

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]);
}

Test 3: Auf null setzen, sortieren und RemoveRange

In diesem Test habe ich die Liste einmal durchlaufen und die zu entfernenden Elemente festgelegt null. Dann sortierte ich die Liste (also würde Null an der Spitze sein) und entfernte alle Elemente an der Spitze, die auf Null gesetzt waren. HINWEIS: Dies hat meine Liste neu geordnet, sodass ich sie möglicherweise in der richtigen Reihenfolge zurückstellen muss.

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...
}

Test 4: Erstellen Sie eine neue Liste und fügen Sie alle "guten" Werte zur neuen Liste hinzu

In diesem Test habe ich eine neue Liste erstellt und alle meine Aufbewahrungselemente zur neuen Liste hinzugefügt. Dann lege ich alle diese Elemente in die ursprüngliche Liste.

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);
}

Test 5: Setzen Sie auf Null und dann FindAll ()

In diesem Test setze ich alle zu löschenden Elemente auf null, dann benutzt FindAll() um alle Elemente zu finden, die nicht 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);
}

Test 6: Setzen Sie auf null und dann RemoveAll ()

In diesem Test setze ich alle zu löschenden Elemente auf null, dann benutzt RemoveAll() Feature, um alle Elemente zu entfernen, die nicht vorhanden sind 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);
}

Client-Anwendung und -Ausgaben

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();

Ergebnisse

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()

Anmerkungen und Kommentare

  • Die ersten zwei Tests entfernen nicht wirklich jedes fünfte Element aus der Liste, da die Liste nach jeder Entfernung neu geordnet wird. Tatsächlich wurden von 500.000 Artikeln nur 83.334 entfernt (sollte 100.000 sein). Ich bin damit einverstanden - klar, die Remove () / RemoveAt () Methoden sind sowieso keine gute Idee.

  • Obwohl ich versuchte, den fünften Punkt von der Liste zu entfernen, Wirklichkeit Es wird kein solches Muster geben. Zu entfernende Einträge sind zufällig.

  • Obwohl ich a List<String> In diesem Beispiel wird das nicht immer der Fall sein. Es könnte sein List<Anything>

  • Die Elemente in die Liste zu setzen ist nicht nicht eine Option.

  • Die anderen Methoden (3 - 6) haben alle viel besser abgeschnitten, verhältnismäßigaber ich bin ein wenig besorgt - In 3, 5 und 6 war ich gezwungen, einen Wert zu setzen null, und entfernen Sie dann alle Elemente gemäß diesem Sentinel. Ich mag diesen Ansatz nicht, weil ich mir ein Szenario vorstellen kann, in dem eines der Elemente in der Liste enthalten sein könnte null und es würde unbeabsichtigt entfernt werden.

Meine Frage ist: Was ist der beste Weg, um schnell viele Gegenstände aus einem zu entfernen List<T>? Die meisten Ansätze, die ich versucht habe, sehen für mich sehr hässlich und potentiell gefährlich aus. Ist ein Listdie falsche Datenstruktur?

Ich bin gerade dabei, eine neue Liste zu erstellen und die guten Artikel der neuen Liste hinzuzufügen, aber es scheint, als sollte es einen besseren Weg geben.


62
2017-08-03 12:37


Ursprung


Antworten:


Liste ist keine effiziente Datenstruktur, wenn es um das Entfernen geht. Sie sollten besser eine doppelt verkettete Liste (LinkedList) verwenden, da zum Entfernen lediglich Referenzaktualisierungen in den angrenzenden Einträgen erforderlich sind.


33
2017-08-03 12:41



Wenn Sie eine neue Liste erstellen möchten, müssen Sie die Elemente nicht auf null setzen. Beispielsweise:

// This overload of Where provides the index as well as the value. Unless
// you need the index, use the simpler overload which just provides the value.
List<string> newList = oldList.Where((value, index) => index % 5 != 0)
                              .ToList();

Möglicherweise möchten Sie jedoch alternative Datenstrukturen wie z LinkedList<T> oder HashSet<T>. Es hängt wirklich davon ab, welche Funktionen Sie von Ihrer Datenstruktur benötigen.


15
2017-08-03 12:42



Ich fühle ein HashSet, LinkedList oder Dictionary wird dich viel besser machen.


11
2017-08-03 12:41



Wenn die Reihenfolge keine Rolle spielt, gibt es eine einfache O (1) List.Remove-Methode.

public static class ListExt
{
    // O(1) 
    public static void RemoveBySwap<T>(this List<T> list, int index)
    {
        list[index] = list[list.Count - 1];
        list.RemoveAt(list.Count - 1);
    }

    // O(n)
    public static void RemoveBySwap<T>(this List<T> list, T item)
    {
        int index = list.IndexOf(item);
        RemoveBySwap(list, index);
    }

    // O(n)
    public static void RemoveBySwap<T>(this List<T> list, Predicate<T> predicate)
    {
        int index = list.FindIndex(predicate);
        RemoveBySwap(list, index);
    }
}

Diese Lösung ist für das Speicher-Traversal geeignet, und selbst wenn Sie den Index zuerst finden müssen, wird er sehr schnell sein.

Anmerkungen:

  • Das Finden des Index eines Elements muss O (n) sein, da die Liste unsortiert sein muss.
  • Verknüpfte Listen sind beim Traversieren langsam, insbesondere bei großen Sammlungen mit langer Lebensdauer.

11
2018-06-01 17:51



Sie können die Elemente immer am Ende der Liste entfernen. Die Listenentfernung ist O (1), wenn sie für das letzte Element ausgeführt wird, da dies nur eine Dekrementzählung ist. Es gibt keine Verschiebung der nächsten Elemente beteiligt. (Dies ist der Grund, warum Listenentfernung generell O (n) ist)

for (int i = list.Count - 1; i >= 0; --i)
  list.RemoveAt(i);

4
2018-02-13 05:13



Ok probiere RemoveAll wie folgt aus

static void Main(string[] args)
{
    Stopwatch watch = new Stopwatch();
    watch.Start();
    List<Int32> test = GetList(500000);
    watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
    watch.Reset(); watch.Start();
    test.RemoveAll( t=> t % 5 == 0);
    List<String> test2 = test.ConvertAll(delegate(int i) { return i.ToString(); });
    watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());

    Console.WriteLine((500000 - test.Count).ToString());
    Console.ReadLine();

}

static private List<Int32> GetList(int size)
{
    List<Int32> test = new List<Int32>();
    for (int i = 0; i < 500000; i++)
        test.Add(i);
    return test;
}

Dies wiederholt nur zweimal und entfernt 100.000 Elemente

Meine Ausgabe für diesen Code:

00:00:00.0099495 
00:00:00.1945987 
1000000

Aktualisiert, um ein HashSet zu testen

static void Main(string[] args)
    {
        Stopwatch watch = new Stopwatch();
        do
        {
            // Test with list
            watch.Reset(); watch.Start();
            List<Int32> test = GetList(500000);
            watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
            watch.Reset(); watch.Start();
            List<String> myList = RemoveTest(test);
            watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
            Console.WriteLine((500000 - test.Count).ToString());
            Console.WriteLine();

            // Test with HashSet
            watch.Reset(); watch.Start();
            HashSet<String> test2 = GetStringList(500000);
            watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
            watch.Reset(); watch.Start();
            HashSet<String> myList2 = RemoveTest(test2);
            watch.Stop(); Console.WriteLine(watch.Elapsed.ToString());
            Console.WriteLine((500000 - test.Count).ToString());
            Console.WriteLine();
        } while (Console.ReadKey().Key != ConsoleKey.Escape);

    }

    static private List<Int32> GetList(int size)
    {
        List<Int32> test = new List<Int32>();
        for (int i = 0; i < 500000; i++)
            test.Add(i);
        return test;
    }

    static private HashSet<String> GetStringList(int size)
    {
        HashSet<String> test = new HashSet<String>();
        for (int i = 0; i < 500000; i++)
            test.Add(i.ToString());
        return test;
    }

    static private List<String> RemoveTest(List<Int32> list)
    {
        list.RemoveAll(t => t % 5 == 0);
        return list.ConvertAll(delegate(int i) { return i.ToString(); });
    }

    static private HashSet<String> RemoveTest(HashSet<String> list)
    {
        list.RemoveWhere(t => Convert.ToInt32(t) % 5 == 0);
        return list;
    }

Das gibt mir:

00:00:00.0131586
00:00:00.1454723
100000

00:00:00.3459420
00:00:00.2122574
100000

3
2017-08-03 13:34



Ich habe festgestellt, wenn es um große Listen geht, ist dies oft schneller. Die Geschwindigkeit, mit der Remove und das richtige Element im Wörterbuch entfernt werden, macht das Erstellen des Wörterbuchs mehr als wett. Ein paar Dinge aber, die ursprüngliche Liste muss eindeutige Werte haben, und ich glaube nicht, dass die Reihenfolge garantiert ist, sobald Sie fertig sind.

List<long> hundredThousandItemsInOrignalList;
List<long> fiftyThousandItemsToRemove;

// populate lists...

Dictionary<long, long> originalItems = hundredThousandItemsInOrignalList.ToDictionary(i => i);

foreach (long i in fiftyThousandItemsToRemove)
{
    originalItems.Remove(i);
}

List<long> newList = originalItems.Select(i => i.Key).ToList();

2
2018-05-13 00:10



Oder Sie könnten dies tun:

List<int> listA;
List<int> listB;

...

List<int> resultingList = listA.Except(listB);

2
2017-07-11 20:47



Listen sind schneller als LinkedLists, bis n wirklich groß wird. Der Grund dafür ist, dass so genannte Cache-Misses mit LinkedLists häufiger auftreten als mit Listen. Memory-Look-Ups sind ziemlich teuer. Da eine Liste als Array implementiert ist, kann die CPU eine Menge Daten gleichzeitig laden, da sie weiß, dass die benötigten Daten nebeneinander gespeichert sind. Eine verkettete Liste gibt der CPU jedoch keinen Hinweis darauf, welche Daten als nächstes benötigt werden, was die CPU dazu zwingt, ziemlich viele Speicher-Lookups durchzuführen. Apropos. Mit Termspeicher meine ich RAM.

Für weitere Details werfen Sie einen Blick auf: https://jackmott.github.io/programming/2016/08/20/when-bigo-foolsya.html


1
2017-10-13 08:59



Die anderen Antworten (und die Frage selbst) bieten verschiedene Möglichkeiten, um mit diesem "Slug" (Langsamkeitsfehler) mit den integrierten .NET Framework-Klassen umzugehen.

Wenn Sie jedoch zu einer Bibliothek eines Drittanbieters wechseln möchten, können Sie eine bessere Leistung erzielen, indem Sie einfach die Datenstruktur ändern und den Code bis auf den Listentyp unverändert lassen.

Die Loyc Core-Bibliotheken enthalten zwei Typen, die auf dieselbe Weise funktionieren wie List<T>aber kann Elemente schneller entfernen:

  • DList<T> ist eine einfache Datenstruktur, die Ihnen eine 2x Beschleunigung gibt List<T> beim Entfernen von Objekten von zufälligen Orten
  • AList<T> ist eine anspruchsvolle Datenstruktur, die Ihnen eine große Beschleunigung bietet List<T> wenn Ihre Listen sehr lang sind (aber möglicherweise langsamer, wenn die Liste kurz ist).

0
2018-02-26 05:22