J'ai une méthode non-performant, comment puis-je améliorer son efficacité?

Question

J'ai une méthode simple pour comparer un tableau d'objets FileInfo à une liste de noms de fichiers pour vérifier quels fichiers ont déjà été traités. La liste non traitée est ensuite renvoyée.

La boucle de cette méthode parcourt environ 250 000 objets FileInfo. Cela prend une quantité de temps obscène pour rivaliser.

L'inefficacité est évidemment l'appel de méthode Contains sur la collection processedFiles. D'abord, comment puis-je vérifier si ma suspicion est vraie quant à la cause et, deuxièmement, comment puis-je améliorer la méthode pour accélérer le processus?

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

Une méthode de ContainsList<T> fonctionne en temps linéaire, car il a potentiellement d'énumérer toute la liste pour prouver l'existence/non -existence d'un objet. Je vous suggère d'utiliser un HashSet<string> ou similaire à la place. La méthode Contains d'un HashSet<T> est conçue pour fonctionner en temps constant O(1), c'est-à-dire qu'elle ne doit pas dépendre du nombre d'éléments dans l'ensemble.

Ce petit changement devrait rendre l'ensemble du déroulement de la méthode dans le temps linéaire:

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

Je suggère 3 améliorations, si possible:

1. Pour efficacité supplémentaire, stocker les fichiers traités dans le un ensemble à la source, de sorte que cette méthode prend un ISet<T> en tant que paramètre. De cette façon, vous n'aurez pas à reconstruire l'ensemble à chaque fois.
2. Essayez de ne pas mélanger et faire correspondre les différentes représentations de la même entité (string et FileInfo) de cette façon. Choisissez-en un et partez avec.
3. Vous pouvez également envisager la méthode HashSet<T>.ExceptWith au lieu de faire la boucle vous-même. Gardez à l'esprit que cela va muter la collection.

Si vous pouvez utiliser LINQ, et vous pouvez vous permettre de construire un ensemble à chaque appel, voici une autre façon:

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

Answer 2

1. Trier le tableau recherché par nom de fichier
2. emploient Array.BinarySearch<T>() pour rechercher le tableau. Cela devrait sortir à environ O (logN) efficacité.

Answer 3

pour vérifier si une liste contient un élément est plus rapide avec une liste triée

Answer 4

Je voudrais essayer de convertir la liste processedfiles à un HashSet. Avec une liste, il doit itérer la liste chaque fois que vous appelez contient. Un HashSet est une opération O (1).

Answer 5

Vous pouvez utiliser un dictionnaire/hastable comme classe pour accélérer le processus de recherche de manière significative. Même traduire la liste entrante en une table de hachage une fois, puis en utilisant celle-ci sera beaucoup plus rapide que ce que vous utilisez.

Answer 6

Juste pour être trop pédant ...

Si vous savez que les deux listes sont classés (liste FileInfo viennent souvent pré-tri, de sorte que cette approche pourrait être applicable à vous), vous pouvez obtenir une véritable performance linéaire sans le temps et les frais généraux de mémoire d'un hashset. La construction de Hashset nécessite encore un temps linéaire pour construire, donc la complexité est plus proche de O (n + m); le hashset doit allouer en interne des références d'objets supplémentaires pour au plus 250k chaînes dans votre cas et cela va coûter en termes de GC.

Quelque chose comme cette généralisation bancales pourrait aider:

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

Je fortement d'accord avec Ani qui colle à un type générique ou canonique est une très bonne chose en effet. Mais je vais donner le mien -1 pour la généralisation inachevée et -1 pour l'élégance ...