Tengo una lista muy grande de números enteros (alrededor de 2 mil millones de elementos) y una lista con índices (un par de miles de elementos) en la que necesito eliminar elementos de la primera lista. Mi enfoque actual es recorrer todos los índices en la segunda lista, pasando cada uno al método RemoveAt() de la primera lista:
indices.Sort(); indices.Reverse(); for (i = 0; i < indices.Count; i++) { largeList.RemoveAt(indices[i]); }Sin embargo, tarda unos 2 minutos en terminar. Realmente necesito realizar esta operación mucho más rápido. ¿Hay alguna forma de optimizar esto?
Tengo una CPU Intel i9X con 10 núcleos, entonces, ¿tal vez alguna forma de procesamiento paralelo?
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:
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 (basándose ú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.