Ich habe eine nicht-performante Methode, wie kann ich die Effizienz verbessern?

Question

Ich habe eine einfache Methode, um ein Array von FileInfo-Objekten mit einer Liste von Dateinamen zu vergleichen, um zu überprüfen, welche Dateien bereits verarbeitet wurden. Die unverarbeitete Liste wird dann zurückgegeben.

Die Schleife dieser Methode iteriert für etwa 250.000 FileInfo-Objekte. Das dauert eine obszöne Zeit, um zu konkurrieren.

Die Ineffizienz ist offensichtlich der Aufruf der Contains-Methode für die collectionedFiles-Auflistung.

Zuerst, wie kann ich überprüfen, um sicherzustellen, dass mein Verdacht über die Ursache wahr ist und zweitens, wie kann ich die Methode verbessern, um den Prozess zu beschleunigen?

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

A List<T> ‚s Contains Verfahren in linearer Zeit laufen, da es möglicherweise die Existenz/Nicht zu beweisen, die gesamte Liste aufzuzählen hat - Vorhandensein eines Gegenstandes Ich würde vorschlagen, dass Sie stattdessen eine HashSet<string> oder ähnliches verwenden. Eine HashSet<T>Contains Methode ist entworfen, um in konstanter O(1) Zeit zu laufen, d. H. Es sollte nicht von der Anzahl der Elemente in der Menge abhängen.

sollten Diese kleine Änderung des gesamten Verfahrens Lauf in linearer Zeit machen:

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

I 3 Verbesserungen vorschlagen würde, wenn möglich:

1. Für zusätzliche Effizienz speichern die bearbeiteten Dateien in ein Set an der Quelle, so dass diese Methode eine ISet<T> als Parameter verwendet. Auf diese Weise müssen Sie das Set nicht jedes Mal neu erstellen.
2. Versuchen Sie nicht, verschiedene Darstellungen der gleichen Einheit (string und FileInfo) auf diese Weise zu mischen und anzupassen. Wähle einen aus und geh mit ihm.
3. Sie können auch die HashSet<T>.ExceptWith-Methode in Betracht ziehen, anstatt die Schleife selbst durchzuführen. Denken Sie daran, dass dies die Sammlung mutieren wird.

Wenn Sie LINQ verwenden können, und Sie können es sich leisten einen Satz bei jedem Anruf aufzubauen, hier ist eine andere Art und Weise:

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

Answer 2

1. Sortieren Sie die gesuchte Array von Dateinamen
2. beschäftigen Array.BinarySearch<T>() das Array zu suchen. Dies sollte bei etwa O (logN) Effizienz herauskommen.

Answer 3

zu überprüfen, ob eine Liste ein Element enthält schneller mit einer sortierten Liste ist

Answer 4

ich versuchen würde, die processedFiles Liste zu einem HashSet zu konvertieren. Bei einer Liste muss die Liste jedes Mal durchlaufen werden, wenn Sie call enthält. Ein HashSet ist eine O (1) -Operation.

Answer 5

Sie könnten ein Wörterbuch/hasable wie Klasse verwenden, um den Lookup-Prozess erheblich zu beschleunigen. Auch wenn Sie die eingehende Liste einmal in eine Hashtabelle umwandeln, ist die Verwendung dieser Liste viel schneller als die von Ihnen verwendete.

Answer 6

Nur um allzu pedantisch ...

Wenn Sie wissen, dass beide Listen sortiert werden (Fileinfo listet häufig kommen vorsortiert, so dass dieser Ansatz könnte Sie anwendbar sein), dann können Sie echte lineare Leistung erzielen ohne den Zeit- und Speicheraufwand eines Hashsets. Hashset-Konstruktion benötigt immer noch eine lineare Zeit, so dass die Komplexität näher bei O (n + m) liegt; Das Hashset muss intern zusätzliche Objektreferenzen für maximal 250k Strings zuweisen, und das kostet in GC-Bedingungen.

So etwas wie diese unausgegorene Verallgemeinerung könnte helfen:

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

ich stark mit Ani zustimmen würde, dass ein generischen oder kanonischen Typen klebt A die Tat sehr gute Sache ist. Aber ich gebe meins -1 für unfertige Generalisierung und -1 für Eleganz ...