Tengo un método no mejorado, ¿cómo puedo mejorar su eficiencia?

Question

Tengo un método simple para comparar una matriz de objetos FileInfo con una lista de nombres de archivos para verificar qué archivos ya se han procesado. La lista no procesada se devuelve.

El bucle de este método itera para aproximadamente 250,000 objetos FileInfo. Esto está tomando una cantidad obscena de tiempo para competir.

La ineficacia es obviamente la llamada al método Contiene en la colección processedFiles.

Primero, ¿cómo puedo comprobar para asegurarme de que mi sospecha es cierta sobre la causa y, en segundo lugar, cómo puedo mejorar el método para acelerar el proceso?

public static List<FileInfo> GetUnprocessedFiles(FileInfo[] allFiles, List<string> processedFiles) 
{ 
List<FileInfo> unprocessedFiles = new List<FileInfo>(); 
foreach (FileInfo fileInfo in allFiles) 
{ 
    if (!processedFiles.Contains(fileInfo.Name)) 
    { 
     unprocessedFiles.Add(fileInfo); 
    } 
    } 
    return unprocessedFiles; 
} 

Answer 1

Un List<T> 's se ejecuta en tiempo lineal, ya que potencialmente tiene para enumerar la lista entera para probar la existencia/no -existencia de un artículo. Le sugiero que use un HashSet<string> o similar en su lugar. El método HashSet<T>Contains está diseñado para ejecutarse en tiempo constante O(1), es decir, no debe depender del número de elementos del conjunto.

Este pequeño cambio debería hacer que todo el método run en el tiempo lineal:

public static List<FileInfo> GetUnprocessedFiles(FileInfo[] allFiles, 
             List<string> processedFiles) 
{ 
    List<FileInfo> unprocessedFiles = new List<FileInfo>(); 
    HashSet<string> processedFileSet = new HashSet<string>(processedFiles); 

    foreach (FileInfo fileInfo in allFiles) 
    { 
     if (!processedFileSet.Contains(fileInfo.Name)) 
     { 
      unprocessedFiles.Add(fileInfo); 
     } 
    } 

    return unprocessedFiles; 
} 

Yo sugeriría 3 mejoras, si es posible:

1. Para adicional eficiencia, almacenar los archivos procesados ​​en un conjunto en la fuente, por lo que este método toma un ISet<T> como parámetro. De esta manera, no tendrá que reconstruir el conjunto cada vez.
2. Intente no mezclar y hacer coincidir las diferentes representaciones de la misma entidad (string y FileInfo) de esta manera. Elige uno y ve con él.
3. Es posible que también desee considerar el método HashSet<T>.ExceptWith en lugar de hacer el bucle usted mismo. Tenga en cuenta que esto mutará la colección.

Si puede utilizar LINQ, y puede permitirse el lujo de construir un conjunto en cada llamada, aquí es otra manera:

public static IEnumerable<string> GetUnprocessedFiles 
(IEnumerable<string> allFiles, IEnumerable<string> processedFiles) 
{ 
    // null-checks here 
    return allFiles.Except(processedFiles);  
} 

Answer 2

1. ordenar la matriz buscada por nombre de archivo
2. empleo Array.BinarySearch<T>() para buscar en la matriz. Esto debería aparecer con una eficiencia de aproximadamente O (logN).

Answer 3

para comprobar si una lista contiene un elemento es más rápido con una lista ordenada Contains método

Answer 4

me gustaría tratar de convertir la Lista processedFiles a un HashSet. Con una lista, necesita repetir la lista cada vez que llame contiene. Un HashSet es una operación O (1).

Answer 5

Puede usar una clase de diccionario/hastable para acelerar el proceso de búsqueda de manera significativa. Incluso traduzca la Lista entrante a una tabla hash una vez, y luego use esa será mucho más rápido que lo que está usando.

Answer 6

Sólo para estar excesivamente pedante ...

Si sabe que ambas listas se ordenan (FileInfo enumera a menudo vienen pre-ordenadas, por lo que este enfoque podría ser aplicable a usted), entonces se puede lograr una verdadera potencia lineal sin el tiempo y la sobrecarga de memoria de un hashset. La construcción de Hashset todavía requiere tiempo lineal para construir, por lo que la complejidad está más cerca de O (n + m); el hashset tiene que asignar internamente referencias de objetos adicionales para un máximo de 250k strings en su caso y eso va a costar en términos de GC.

Algo parecido a esta generalización a medias podría ayudar:

public static IEnumerable<string> GetMismatches(IList<string> fileNames, IList<string> processedFileNames, StringComparer comparer) 
    { 
     var filesIndex = 0; 
     var procFilesIndex = 0; 

     while (filesIndex < fileNames.Count) 
     { 
      if (procFilesIndex >= processedFileNames.Count) 
      { 
       yield return files[filesIndex++]; 
      } 
      else 
      { 
       var rc = comparer.Compare(fileNames[filesIndex], processedFileNames[procFilesIndex]); 
       if (rc != 0) 
       { 
        if (rc < 0) 
        { 
         yield return files[filesIndex++]; 
        } 
        else 
        { 
         procFilesIndex++; 
        } 
       } 
       else 
       { 
        filesIndex++; 
        procFilesIndex++; 
       } 
      } 
     } 

     yield break; 
    } 

yo muy de acuerdo con Ani que se pegue a un tipo genérico o canónico es una cosa muy buena efecto. Pero le doy a la mía -1 por generalización sin terminar y -1 por elegancia ...