modificar - listas c#

Cómo quitar rápidamente elementos de una lista

Question

Estoy buscando una manera de eliminar rápidamente elementos de una List<T> C # List<T> . La documentación indica que las List.Remove() y List.RemoveAt() son ambas O(n)

• List.Remove
• List.RemoveAt

Esto está afectando seriamente mi aplicación.

Escribí algunos métodos de eliminación diferentes y los probé todos en una List<String> con 500,000 elementos. Los casos de prueba se muestran a continuación ...

Visión de conjunto

Escribí un método que generaría una lista de cadenas que simplemente contiene representaciones de cadenas de cada número ("1", "2", "3", ...). Luego intenté remove cada 5º elemento de la lista. Aquí está el método usado para generar la lista:

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

Prueba 1: RemoveAt ()

Aquí está la prueba que usé para probar el método RemoveAt() .

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

Prueba 2: Eliminar ()

Aquí está la prueba que usé para probar el método 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]);
}

Prueba 3: establecer en nulo, ordenar, luego EliminarRango

En esta prueba, hice un bucle en la lista una vez y establecí los elementos que se eliminarán en null . Luego, ordené la lista (por lo que null estaría en la parte superior) y eliminé todos los elementos en la parte superior que estaban configurados como nulos. NOTA: Esto reordenó mi lista, por lo que debo volver a colocarla en el orden correcto.

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

Prueba 4: cree una nueva lista y agregue todos los valores "buenos" a la nueva lista

En esta prueba, creé una nueva lista y agregué todos mis elementos de mantenimiento a la nueva lista. Luego, puse todos estos elementos en la lista original.

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

Prueba 5: establecer en nulo y luego FindAll ()

En esta prueba, configuré null todos los elementos que se eliminarán, luego usé la función FindAll() para encontrar todos los elementos que no son 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);
}

Prueba 6: establecer en nulo y luego quitar todo ()

En esta prueba, configuré null todos los elementos que se eliminarán, luego usé la función RemoveAll() para eliminar todos los elementos que no son 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);
}

Aplicación de cliente y salidas

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

Resultados

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

Notas y comentarios

• Las dos primeras pruebas en realidad no eliminan cada 5º elemento de la lista, porque la lista se está reordenando después de cada eliminación. De hecho, de 500,000 artículos, solo 83,334 fueron eliminados (deberían haber sido 100,000). Estoy de acuerdo con esto - claramente los métodos Remove () / RemoveAt () no son una buena idea de todos modos.

• Aunque traté de eliminar el quinto elemento de la lista, en realidad no habrá tal patrón. Las entradas que se eliminarán serán aleatorias.

• Aunque utilicé List<String> en este ejemplo, ese no siempre será el caso. Podría ser una List<Anything>

• No poner los elementos en la lista para empezar no es una opción.

• Los otros métodos (3 - 6) funcionaron mucho mejor, comparativamente , sin embargo, estoy un poco preocupado: en 3, 5 y 6 me vi obligado a establecer un valor null , y luego eliminar todos los elementos de acuerdo con este centinela . No me gusta ese enfoque porque puedo imaginar un escenario en el que uno de los elementos de la lista podría ser null y se eliminaría involuntariamente.

Mi pregunta es: ¿Cuál es la mejor manera de eliminar rápidamente muchos elementos de una List<T> ? La mayoría de los enfoques que he intentado son realmente feos y potencialmente peligrosos para mí. ¿Es una List la estructura de datos incorrecta?

En este momento, me inclino por crear una nueva lista y agregar los buenos artículos a la nueva lista, pero parece que debería haber una mejor manera.

Answer 1

Descubrí que cuando se trata de listas grandes, a menudo es más rápido. La velocidad de Eliminar y encontrar el elemento correcto en el diccionario para eliminar, más que compensa la creación del diccionario. Un par de cosas, sin embargo, la lista original tiene que tener valores únicos, y no creo que la orden esté garantizada una vez que haya terminado.

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

Answer 2

La lista no es una estructura de datos eficiente en lo que respecta a la eliminación. Sería mejor utilizar una lista de doble enlace (LinkedList) ya que la eliminación simplemente requiere actualizaciones de referencia en las entradas adyacentes.

Answer 3

Las listas son más rápidas que las LinkedLists hasta que n sea realmente grande. La razón de esto es porque los llamados fallos de caché se producen con bastante frecuencia utilizando LinkedLists que listas. Las búsquedas de memoria son bastante costosas. Como una lista se implementa como una matriz, la CPU puede cargar una gran cantidad de datos a la vez porque sabe que los datos necesarios se almacenan uno al lado del otro. Sin embargo, una lista vinculada no le da a la CPU ninguna pista acerca de qué datos se necesitan a continuación, lo que obliga a la CPU a realizar más búsquedas en la memoria. Por cierto. Con memoria de términos me refiero a RAM.

Para obtener más detalles, consulte: https://jackmott.github.io/programming/2016/08/20/when-bigo-foolsya.html

Answer 4

Las otras respuestas (y la pregunta en sí misma) ofrecen varias formas de lidiar con este "slug" (error de lentitud) utilizando las clases integradas de .NET Framework.

Pero si está dispuesto a cambiar a una biblioteca de terceros, puede obtener un mejor rendimiento simplemente cambiando la estructura de datos y dejando el código sin cambios, excepto para el tipo de lista.

Las bibliotecas de Loyc Core incluyen dos tipos que funcionan de la misma manera que List<T> pero pueden eliminar elementos más rápidamente:

• DList<T> es una estructura de datos simple que le da una aceleración de 2 veces sobre List<T> al eliminar elementos de ubicaciones aleatorias
• AList<T> es una estructura de datos sofisticada que le da una gran aceleración sobre List<T> cuando sus listas son muy largas (pero pueden ser más lentas cuando la lista es corta).

Answer 5

O podrías hacer esto:

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

...

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

Answer 6

Ok prueba RemoveAll usado así

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

esto solo se repite dos veces y elimina exactamente 100 000 elementos

Mi salida para este código:

00:00:00.0099495 
00:00:00.1945987 
1000000

Actualizado para probar 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;
    }

Esto me da:

00:00:00.0131586
00:00:00.1454723
100000

00:00:00.3459420
00:00:00.2122574
100000

Answer 7

Si el orden no importa, entonces hay un método simple O (1) List.Remove.

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

Esta solución es amigable para el recorrido de la memoria, por lo que incluso si necesita encontrar primero el índice, será muy rápido.

Notas:

• Encontrar el índice de un artículo debe ser O (n) ya que la lista debe estar desordenada.
• Las listas vinculadas son lentas en el cruce, especialmente para grandes colecciones con una larga vida útil.

Answer 8

Si está contento creando una nueva lista, no tiene que pasar por establecer los elementos a nulo. Por ejemplo:

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

Sin embargo, es posible que desee ver estructuras de datos alternativas, como LinkedList<T> o HashSet<T> . Realmente depende de qué características necesita de su estructura de datos.

Answer 9

Siempre puedes eliminar los elementos del final de la lista. La eliminación de lista es O (1) cuando se realiza en el último elemento, ya que todo lo que hace es recuento de decrementos. No hay desplazamiento de los siguientes elementos involucrados. (que es el motivo por el cual la eliminación de la lista es O (n) en general)

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

Answer 10

Siento que un HashSet , LinkedList o Dictionary te hará mucho mejor.