Dado que el orden de la lista de origen es significativo, puede mover cada elemento hacia abajo en la lista, saltándose los índices que se eliminarán y luego eliminar el final de la lista.

ACTUALIZACIÓN: tomó el código fuente de .Net Core para RemoveAll y lo modificó para obtener una lista de índices en lugar de un predicado.

ACTUALIZACIÓN 2: Optimizado para no repetir pruebas si es posible.

ACTUALIZACIÓN 3: Simplificado ya que la optimización con código adicional demostró ser más lenta en los puntos de referencia.

Teniendo src como la lista grande y removeAtList como los índices para eliminar en algún orden aleatorio, puede hacer lo siguiente:

 removeAtList.Sort(); var srcCount = src.Count; var ralCount = removeAtList.Count; var removeAtIndice = 1; var freeIndex = removeAtList[0]; var current = freeIndex+1; while (current < srcCount) { while (removeAtIndice < ralCount && current == removeAtList[removeAtIndice]) { ++current; ++removeAtIndice; } if (current < srcCount) src[freeIndex++] = src[current++]; } src.RemoveRange(freeIndex, srcCount-freeIndex);

Para una lista de mil millones de elementos enteros aleatorios y una lista de 1000 - 3000 elementos de índices aleatorios, obtengo 1,1 ms por eliminación con este algoritmo. Con RemoveAt , obtengo más de 232,77 ms por eliminación, por lo que es unas 200 veces más rápido.

Una forma de permitir que esto se paralelice sería dividir la lista en varios fragmentos; quizás inicialmente (arbitrariamente) losas separadas de 1 millón de elementos. Siempre que cada losa mantenga su propio recuento, puede dividir el trabajo por índice en eliminaciones de diferentes losas (basado únicamente en los recuentos) y luego realizar el trabajo de eliminación real al mismo tiempo. Si deja algo de capacidad libre en cada uno, también puede agregar elementos en el medio de manera más económica, ya que generalmente solo toca una losa. El acceso aleatorio será un poco más lento, ya que es posible que deba observar varios recuentos de losas para determinar la losa correcta, pero si los recuentos de losas se mantienen en un vector contiguo (en lugar de contra cada losa), debería tener un excelente éxito de caché de memoria mientras lo hace.

Cuando tiene varios elementos para eliminar de una List y reemplazar la List con una List nueva no es una opción, la forma más eficiente es usar el método RemoveAll en lugar de RemoveAt . RemoveAll reorganiza el estado interno de la List solo una vez, en lugar de hacerlo una vez por cada elemento eliminado.

RemoveAll acepta un Predicate<T> que se invocará una vez para cada elemento de la lista (la lista grande). Desafortunadamente, este delegado no recibe el índice del elemento probado actualmente. Sin embargo, podría depender de saber cómo se implementa RemoveAll . El código fuente revela que los elementos se prueban secuencialmente en orden ascendente. Entonces, en base a este conocimiento, podría eliminar los índices seleccionados de la lista, de manera muy eficiente, con este tres líneas:

 var indicesSet = new HashSet<int>(indices); int index = 0; largeList.RemoveAll(_ => indicesSet.Contains(index++));

Pero realmente no deberías . Esta solución fallará horriblemente si una versión futura de .NET viene con una implementación interna diferente de RemoveAll . Así que considere esto como un truco sucio, y no como una solución de calidad de producción para el problema.

El método List.RemoveAt copia todos los elementos siguientes del elemento eliminado. En su caso, esta copia 2.000 * 2.000.000.000 veces cada elemento (no realmente, pero la verdad está cerca).

Una solución es copiar manualmente el elemento entre el elemento eliminado y el siguiente elemento eliminado:

 static void Main(string[] args) { var largeList = Enumerable.Range(0, 2_000_000_000).ToList(); var indices = new List<int>(); var rand = new Random(); for (var i = 0; i < 20000; i++) { indices.Add(rand.Next(0, largeList.Count - 1)); } indices.Sort(); var watch = new Stopwatch(); watch.Start(); // You can convert the list to array with ToArray, // but this duplicate the memory use. // Or get the internal array by reflection, // but reflection on external library isn't recommended var largeArray = (int[])typeof(List<int>) .GetField("_items", BindingFlags.Instance | BindingFlags.NonPublic) .GetValue(largeList); var current = 0; var copyFrom = 0; for (var i = 0; i < indices.Count; i++) { var copyTo = indices[i]; if (copyTo < copyFrom) { //In case the indice is duplicate, //The item is already passed continue; } var copyLength = copyTo - copyFrom; Array.Copy(largeArray, copyFrom, largeArray, current, copyLength); current += copyLength; copyFrom = copyTo + 1; } //Resize the internal array largeList.RemoveRange(largeList.Count - indices.Count, indices.Count); watch.Stop(); Console.WriteLine(watch.Elapsed); Console.WriteLine(largeList.Count); }

Esta respuesta se basa en otras respuestas aquí; principalmente, estoy cambiando elementos dentro de la lista, como lo sugieren @Vernou (en su respuesta) y @BACON (en los comentarios). Este finalmente tiene un rendimiento (a diferencia de mis primeros enfoques) y es más rápido que otras soluciones publicadas hasta ahora, al menos en mis pruebas: probé la configuración de OP de 2_000_000_000 entradas y 2_000 índices: el tiempo de ejecución es inferior a 10 segundos en mi computadora portátil (i7 -8550U a 1,8 GHz, 16 GB de RAM):

 static void FilterOutIndicies(List<int> values, List<int> sortedIndicies) { int sourceStartIndex = 0; int destStartIndex = 0; int spanLength = 0; int skipCount = 0; // Copy items up to last index to be skipped foreach (var skipIndex in sortedIndicies) { spanLength = skipIndex - sourceStartIndex; destStartIndex = sourceStartIndex - skipCount; for (int i = sourceStartIndex; i < sourceStartIndex + spanLength; i++) { values[destStartIndex] = values[i]; destStartIndex++; } sourceStartIndex = skipIndex + 1; skipCount++; } // Copy remaining items (between last index to be skipped and end of list) spanLength = values.Count - sourceStartIndex; destStartIndex = sourceStartIndex - skipCount; for (int i = sourceStartIndex; i < sourceStartIndex + spanLength; i++) { values[destStartIndex] = values[i]; destStartIndex++; } values.RemoveRange(destStartIndex, sortedIndicies.Count); }