Ist Zeichenfolge vorhanden, überprüfen Sie 20k mal

Question

Ich habe eine ITunes-Bibliothek XML-Datei-Sicherungsdatei - ca. 15 MB.

Ich habe 20K Musikdateien auf meinem C-Laufwerk und ca. 25K Dateien auf E-Laufwerk unter genau ähnlichen Ordnerstrukturen.

Ich durchquere den ersten Ort und gehen Datei für Datei und prüfen, ob die Datei an der zweiten Stelle exiss. Dieser Teil funktioniert für mich.

Jetzt, für alle solche doppelte Dateien, wenn der Dateipfad von Laufwerk E in der XML vorhanden ist, aber der C-Laufwerkspfad nicht in der XML vorhanden ist, möchte ich die Datei aus dem Laufwerk C löschen.

Was ist meine beste Art zu prüfen, ob eine Zeichenfolge in der XML-Datei existiert (ich muss das mindestens 20K mal machen)?

Answer 1

Alphabetisch sortieren Sie Ihre Liste der Zeichenfolgen, auf denen Sie übereinstimmen, dann erstellen Sie ein Indexarray, das Ihnen angibt, wo der Anfang Ihrer Liste für jedes Zeichen ist, das ein Startzeichen für eine der Zeichenfolgen ist 2. Zeichen, abhängig von der Breite der Auswahl und ob Ihre Übereinstimmung die Groß- und Kleinschreibung berücksichtigt oder nicht.

Lesen Sie die Datei Zeichen für Zeichen mit einem Stream, um den Speicherbedarf zu minimieren. Überprüfen Sie im Indexarray, wo dieses Zeichen beginnt und endet in der Liste der Zeichenfolgen, damit Sie diese Zeichenseite auslesen können diese Zeichenkombinationen. Dann weiter Filtern innerhalb der Seite, bis Sie eine Übereinstimmung übrig haben und das nächste Zeichen macht 0.

Entfernen Sie diese Zeichenfolge aus der Liste der Zeichenfolgen zu entsprechen, fügen Sie es in eine andere Liste, wenn Sie möchten. Dann beginne, deinen Index auf das nächste Zeichen zu überprüfen und mache das jedes Mal, wenn du keine Übereinstimmungen findest.

Der Index gibt Ihnen ein effizienteres Aggregat, um die Anzahl der iterierten Elemente zu minimieren.

Sie Dies könnte einen zweistelligen Tiefenhub geben:

Dictionary<string,int> stringIndex = new Dictionary<char,int>(); 
for(int i = 0; i < sortedSearchStrings.Length; i++;) 
{ 
    if (!stringIndex.Keys.Contains(sortedSearchStrings[i][0])) stringIndex[sortedSearchStrings[i][0]] = i; 
    if (!stringIndex.Keys.Contains(sortedSearchStrings[i][0] + sortedSearchStrings[i][1])) stringIndex[sortedSearchStrings[i][0] + sortedSearchStrings[i][1]] = i; 
} 

dann den Startindex in der Liste finden Sie nur Zugang:

int startOfCurrentCharPage = stringIndex[string.Format("{0}{1}", lastChar, currentChar)]; 

Answer 2

Je nachdem, ob Sie zählen möchten, wie oft eine Zeichenfolge auftritt, oder wenn Sie nur nach der Existenz der Zeichenfolgen suchen, ist Ihr Ansatz etwas anders. Aber das sind die beiden Möglichkeiten, die ich in Betracht ziehen würde, es zu tun:

Wenn Sie es mit einem minimalen Speicher zu tun:

Laden Sie die Datei Zeile für Zeile (oder, wenn Ihr XML ist nicht so formatiert , Knoten für Knoten mit einem XML-Parser ... Ich glaube, es gibt XML-Parser, die dies tun können). Führen Sie für jede Zeichenfolge eine Suchoperation in der Zeile aus. Wenn Sie die letzte Zeile korrekt überschreiben, befindet sich immer nur eine Zeile/ein Knoten im Speicher. Der Nachteil ist, dass es länger dauert und die Datei länger geöffnet ist.

Wenn Sie es schnell tun wollen:

Legen Sie die gesamte Datei in den Speicher, stören sie nicht das Parsen, und nur die Suche für jede Saite.

EDIT

auf Präzisierungen Basierend, würde ich zuerst alle doppelten Dateinamen in einem Array, sammeln und dann gehen Sie jede Zeile der XML-Datei mit meiner ersten Methode (siehe oben) zu scannen. Wenn Sie bereits 20K-Dateinamen im Speicher speichern, würde ich zögern, die gesamte 15MB-XML-Datei gleichzeitig zu laden.

Answer 3

Ein Vorschlag: Laden Sie als Text, verwenden Sie einen regulären Ausdruck, um die gewünschten Strings zu extrahieren (ich nehme an, sie sind mit einem bestimmten Tag eingeschlossen) und bauen Sie eine Hash-Liste mit ihnen. Sie können die Liste verwenden, um die Existenz zu überprüfen.

Answer 4

jede Zeichenfolge aus dem XML lesen und schreiben sie in eine HashSet<string>. Wenn Sie eine Zeichenfolge suchen möchten, suchen Sie im HashSet nach. Die Kosten werden O (n) sein, um das XML zu lesen, und O (n), um die n Suchen nach dem HashSet durchzuführen. Versuchen Sie nicht, wiederholt im XML-Code zu suchen (führen Sie stattdessen 20.000 Suchvorgänge im HashSet durch), da XML nicht für die Suche indiziert/optimiert ist.

Answer 5

Wäre es möglich, direkt aus dem XML-Dokument heraus zu arbeiten und den ersten Schritt zu überspringen?

Wenn dies der Fall ist, können Sie einfach Xml.XmlDocument und von dort Xml.XmlNode.SelectNodes (string) verwenden und xpath verwenden, um durch das Dokument zu navigieren. Ich weiß nicht, welche Art von Information in dem Dokument vorhanden ist, aber die Art, wie Sie die zweite Stufe formuliert haben, lässt vermuten, dass manchmal sowohl der Pfad auf C: \ als auch der Pfad auf E: \ vorhanden sind. Wenn ja, wäre es so einfach wie zwei IO.File.Exists prüft und dann eine IO.File.Delete().

Was ich meine zu sagen ist, dass, anstatt Ihre XML-Dokument N-mal für eine Zeichenfolge, suchen Sie durch das Dokument und löschen Duplikate, wie Sie gehen, so dass Sie nur durch das Dokument einmal durchlaufen.

Ich benutze iTunes nicht oder habe eines seiner Bibliothekssicherungen zur Hand, um zu sagen, ob es funktionieren könnte oder nicht.

Answer 6

Hier ist eine einfache Lösung mit Linq. Wird für die einmalige Verwendung ausreichend schnell ausgeführt:

using System; 
using System.IO; 
using System.Linq; 
using System.Xml.Linq; 

class ITunesChecker 
{ 
    static void Main(string[] args) 
    { 
     // retrieve file names 
     string baseFolder = @"E:\My Music\"; 
     string[] filesM4a = Directory.GetFiles(baseFolder, "*.m4a", SearchOption.AllDirectories); 
     string[] filesMp3 = Directory.GetFiles(baseFolder, "*.mp3", SearchOption.AllDirectories); 
     string[] files = new string[filesM4a.Length + filesMp3.Length]; 
     Array.Copy(filesM4a, 0, files, 0, filesM4a.Length); 
     Array.Copy(filesMp3, 0, files, filesM4a.Length, filesMp3.Length); 

     // convert to the format used by iTunes 
     for (int i = 0; i < files.Length; i++) 
     { 
      Uri uri = null; 
      if (Uri.TryCreate(files[i], UriKind.Absolute, out uri)) 
      { 
       files[i] = uri.AbsoluteUri.Replace("file:///", "file://localhost/"); 
      } 
     } 

     // read the files from iTunes library.xml 
     XDocument library = XDocument.Load(@"E:\My Music\iTunes\iTunes Music Library.xml"); 
     var q = from node in library.Document.Descendants("string") 
       where node.ElementsBeforeSelf("key").Where(n => n.Parent == node.Parent).Last().Value == "Location" 
       select node.Value; 

     // do the set operations you are interested in 
     var missingInLibrary = files.Except(q, StringComparer.InvariantCultureIgnoreCase); 
     var missingInFileSystem = q.Except(files, StringComparer.InvariantCultureIgnoreCase); 
     var presentInBoth = files.Intersect(q, StringComparer.InvariantCultureIgnoreCase); 
    } 
}