Comment supprimer rapidement des éléments d'une liste

Question

Je cherche un moyen de supprimer rapidement des éléments d'un fichier C#. List<T> . La documentation indique que le List.Remove() y List.RemoveAt() Les opérations sont à la fois O(n)

• Liste.
• Liste.RemoveAt

Cela affecte gravement ma candidature.

J'ai écrit plusieurs méthodes de retrait différentes et je les ai toutes testées sur une List<String> avec 500 000 articles. Les cas de test sont présentés ci-dessous...

---

Vue d'ensemble

J'ai écrit une méthode qui génère une liste de chaînes de caractères contenant simplement les représentations de chaque nombre ("1", "2", "3", ...). J'ai ensuite essayé de remove tous les 5 éléments de la liste. Voici la méthode utilisée pour générer la liste :

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

Voici le test que j'ai utilisé pour tester le RemoveAt() méthode.

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

Test 2 : Remove()

Voici le test que j'ai utilisé pour tester le Remove() méthode.

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 : Définir à null, trier, puis RemoveRange.

Dans ce test, j'ai parcouru la liste en boucle une fois et j'ai défini les éléments à supprimer comme suit null . Ensuite, j'ai trié la liste (de façon à ce que null soit en haut de la liste), et j'ai supprimé tous les éléments en haut de la liste qui avaient la valeur null. REMARQUE : Cette opération a réorganisé ma liste, il se peut donc que je doive la remettre dans le bon ordre.

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 : Créez une nouvelle liste, et ajoutez toutes les "bonnes" valeurs à la nouvelle liste.

Dans ce test, j'ai créé une nouvelle liste, et j'ai ajouté tous mes éléments à conserver à cette nouvelle liste. Ensuite, j'ai placé tous ces éléments dans la liste originale.

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 : Définir à null et ensuite FindAll()

Dans ce test, j'ai défini tous les éléments à supprimer comme suit null puis a utilisé le FindAll() pour trouver tous les éléments qui ne sont pas 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 : Définir à null et ensuite RemoveAll()

Dans ce test, j'ai défini tous les éléments à supprimer comme suit null puis a utilisé le RemoveAll() pour supprimer tous les éléments qui ne sont pas 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);
}

---

Application et résultats du client

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

Résultats

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

Notes et commentaires

• Les deux premiers tests ne suppriment pas réellement tous les 5 éléments de la liste, car la liste est réorganisée après chaque suppression. En fait, sur 500 000 éléments, seuls 83 334 ont été supprimés (cela aurait dû être 100 000). Je suis d'accord avec cela - il est clair que les méthodes Remove()/RemoveAt() ne sont pas une bonne idée de toute façon.

• Bien que j'aie essayé de supprimer le 5e élément de la liste, en réalité il n'y aura pas un tel schéma. Les entrées à retirer seront aléatoires.

• Bien que j'aie utilisé un List<String> dans cet exemple, ce ne sera pas toujours le cas. Il pourrait s'agir d'un List<Anything>

• Ne pas mettre les articles dans la liste pour commencer est no une option.

• Les autres méthodes (3 - 6) ont toutes donné de bien meilleurs résultats, en comparaison, Cependant, je suis un peu inquiet. En 3, 5 et 6, j'ai été forcé de définir une valeur à null et ensuite supprimer tous les éléments en fonction de cette sentinelle. Je n'aime pas cette approche car je peux envisager un scénario où l'un des éléments de la liste pourrait être null et il serait supprimé involontairement.

Ma question est la suivante : quelle est la meilleure façon de supprimer rapidement de nombreux éléments d'un fichier de type List<T> ? La plupart des approches que j'ai essayées me paraissent vraiment hideuses, et potentiellement dangereuses. Est-ce qu'un List la mauvaise structure de données ?

Pour l'instant, je penche pour la création d'une nouvelle liste et l'ajout des bons éléments à la nouvelle liste, mais il me semble qu'il devrait y avoir un meilleur moyen.

Answer 1

La liste n'est pas une structure de données efficace lorsqu'il s'agit de suppression. Vous feriez mieux d'utiliser une liste doublement liée (LinkedList) car la suppression nécessite simplement la mise à jour des références dans les entrées adjacentes.

Answer 2

Si vous vous contentez de créer une nouvelle liste, vous n'avez pas besoin de passer par le réglage des éléments sur null. Par exemple :

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

Toutefois, vous pouvez envisager d'autres structures de données, telles que les suivantes LinkedList<T> o HashSet<T> . Cela dépend vraiment des fonctionnalités dont vous avez besoin pour votre structure de données.

Answer 3

Je sens un HashSet , LinkedList o Dictionary vous fera beaucoup mieux.

Answer 4

Vous pouvez toujours retirer les éléments de la fin de la liste. Le retrait de la liste est O(1) lorsqu'il est effectué sur le dernier élément, car il ne fait que décrémenter le compte. Il n'y a pas de décalage des éléments suivants. (c'est la raison pour laquelle la suppression d'une liste est généralement O(n)).

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

Answer 5

Ok, essayez RemoveAll utilisé comme ceci

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

Cela ne fait que deux boucles et supprime environ 100 000 éléments.

Mon résultat pour ce code :

00:00:00.0099495 
00:00:00.1945987 
1000000

Mise à jour pour essayer un HashSet

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

Cela me donne :

00:00:00.0131586
00:00:00.1454723
100000

00:00:00.3459420
00:00:00.2122574
100000