Laden...

Schnelles Durchlaufen von Dateipfaden

Erstellt von BerndFfm vor einem Jahr Letzter Beitrag vor einem Jahr 1.105 Views
Hinweis von Abt vor einem Jahr

Abgeteilt von Listen für Suchen optimieren

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr
Schnelles Durchlaufen von Dateipfaden

Das gleiche problem habe ich auch gerade :

22 Millionen Dateien auf einer SSD. dateiname ist forlaufend nummeriert. Einige Dateien fehlen.

Alle durchgehen und mit File.Exists() abfragen dauert mehr als 20 Stunden.

Als Array einlesen mit GetFiles() dauert nur 10 Minuten und passt gut in den Hauptspeicher.

Ich werde mal ein dictionary anlegen und testen.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

T
2.219 Beiträge seit 2008
vor einem Jahr

@BerndFfm
Du könntest auch mit EnumerateFiles arbeiten.
Damit musst du nicht alle Dateinamen bzw. Pfade im Speicher halten.
Wenn du auch nur einen Teil der Namen brauchst, kannst du damit die Nummer aus dem Namen auslesen und diese in ein HashSet packen.

Nachtrag:
Doku:
Directory.EnumerateFiles Methode (System.IO)

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

16.806 Beiträge seit 2008
vor einem Jahr

Keine IO-Implementierung von .NET ist wirklich schnell im Vergleich zur Windows API.
Das liegt daran, dass - selbst beim Durchsuchen von Pfadangaben - .NET immer Zusatzoperationen implementiert hat.

Wer das nicht braucht, dafür aber ein performantes Verhalten, muss direkt mit der Windows API arbeiten, wie ichs damals mit QuickIO gemacht hab.
QuickIO.NET - Project Homepage
Damit war ich ca. 7x schneller als EnumerateFiles mit FileInfo (DirectoryInfo-Klasse) und 5x schneller als EnumerateFiles mit Pfadangaben (Directory-Klasse).

QuickIO pflege ich aber nicht mehr (zumindest derzeit).
Man kann sich aber die File Enumeration einfach abschauen.

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr

QuickIO pflege ich aber nicht mehr (zumindest derzeit).

Ich benutze es aber noch !

Ich werde das mal testen.

Hintergrund : Für meine Android und iOS App möchte ich Offline Karten erstellen. Die bestehen aus sehr viele kleinen Kacheln (Bildern). Die muss man errechnen oder fertig gerechnete runterladen. Beides dauert mehrere Tage bis Wochen oder Monate.

Zusätzlich möchte ich einen Webserver bauen, der alle Kartendaten allen Einsatzkräften in einem Einsatz zur Verfügung stellt. Wenn es kein Internet gibt. Im Ahrtal gab es 10 Tage kein Mobilfunk und kein Internet. Da musste man auf gedruckte Karten zurückgreifen. Der geplante Webserver ist praktisch ein lokaler Open Street Map Server. Bisher habe ich schon die Länder Deutschland, Österreich, Schweiz, Italien, Frankreich. Dazu topographische Karten von Deutschland. Dazu zweisprachige Karten von Tschechien, Slowakei, Polen, Ungarn, Rumänien, Ukraine und Belarus. Die Hardware gibt ein Rapsberry Pi 4B mit mehreren SSD. Nginx als Webserver mit Lastausgleich. Ich bin gespannt ob das alles klappt.

Diese Karten habe ich schon, die liegen auf einer SSD : https://finderwille.xddns.de:8086/

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

16.806 Beiträge seit 2008
vor einem Jahr

Dafür sind nackte Dateisystem nicht gedacht; weder in der Cloud noch On-Prem. Entsprechend läufst Du in Nachteile.

Für sowas würde man in der Cloud halt optimierte Systeme verwenden, zB Azure Blob Storage, Amazon S3, CloudFlare R2...
On Prem gibts Pendants wie MinIO, Clodian, Dell Elastic Storage....

Hatten wir vor gar nicht allzu langer Zeit hier schon als Thema (inhaltlich gleiche Effekt).
ASP.NET Core File Read/Write Thread-Safe machen

T
50 Beiträge seit 2010
vor einem Jahr

Meine Erfahrung mit solchen großen Datenmengen ist, dass es Sinn macht, die Dinger in Ordnern (durchaus mehrere Ebenen) zu organisieren, sodass die Anzahl der Dateien maximal bei einigen Tausend liegt. Ich weiß nicht, ob es eine Auswirkung hat, wenn man große Dateimengen in .NET abfragt. Aber spätestens, wenn man sich die Dinger im Windows Explorer anzeigen lassen will, dann darf man warten.

T
2.219 Beiträge seit 2008
vor einem Jahr

Das sind aber zwei Paar Schuhe.
Der Explorer ist leider nicht gerade performant bei vielen Dateien und spielt hier erstmal keine Rolle.

Die .NET Lösung, ist wie Abt schon zu Recht sagt, auch nicht die performanteste Lösung, da hier sehr viele Rechteprüfungen etc. durchlaufen werden müssen.
Auch triviale Dinge wie das durchlaufen von großen Verzeichnis Strukturen können dann langsamer sein als Zugriffe über native System APIs wie die WinAPI.
Dadurch hat man aber wieder native Abhängigkeiten, die man eigentlich vermeiden möchte.

Mich würde aber interessieren ob sich hier zwischen .NET Framework und dem neueren .NET 5/6 schon was getan hat.
Oder ist hier ggf. zukünftig was geplant?

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

16.806 Beiträge seit 2008
vor einem Jahr

Meine Erfahrung mit solchen großen Datenmengen ist, dass es Sinn macht, die Dinger in Ordnern (durchaus mehrere Ebenen) zu organisieren, sodass die Anzahl der Dateien maximal bei einigen Tausend liegt. Ich weiß nicht, ob es eine Auswirkung hat, wenn man große Dateimengen in .NET abfragt.

Nein, das macht kein Sinn, wenn es um das reine API Verhalten geht.
Die Win32 arbeitet mit FileHandles, und die skalieren sehr gut. Es spielt hier quasi keine Rolle, wie groß ein Ordner ist - bzw. gibt es auf dieser Ebene gar keine Ordner.
Erst das Betriebssystem macht daraus Ordner.

Aber spätestens, wenn man sich die Dinger im Windows Explorer anzeigen lassen will, dann darf man warten.

Der Windows Explorer ist eine UI Implementierung - und wenn man tausende von Dingen anzeigen, dann ist das nie performant - egal obs Ordner sind oder andere Dinge.
Der Explorer ist nicht dafür gedacht (hundert)tausende von Elementen gleichzeitig anzuzeigen.

Nimm was anderes als eine solche UI Darstellung - boom: performant.

Die .NET Lösung, ist wie Abt schon zu Recht sagt, auch nicht die performanteste Lösung, da hier sehr viele Rechteprüfungen etc. durchlaufen werden müssen.

Das hat damit erstmal nichts zutun.

Das Win32 funktioniert über File Pointer.
Jeder Pointer hat dabei einen Eintrag aus Name und Daten. Diese Daten beinhalten immer eine Reihe von Attributen.


typedef struct _WIN32_FIND_DATAW {
  DWORD    dwFileAttributes;
  FILETIME ftCreationTime;
  FILETIME ftLastAccessTime;
  FILETIME ftLastWriteTime;
  DWORD    nFileSizeHigh;
  DWORD    nFileSizeLow;
  DWORD    dwReserved0;
  DWORD    dwReserved1;
  WCHAR    cFileName[MAX_PATH];
  WCHAR    cAlternateFileName[14];
  DWORD    dwFileType; // Obsolete. Do not use.
  DWORD    dwCreatorType; // Obsolete. Do not use
  WORD     wFinderFlags; // Obsolete. Do not use
} WIN32_FIND_DATAW, *PWIN32_FIND_DATAW, *LPWIN32_FIND_DATAW;

=> https://docs.microsoft.com/en-us/windows/win32/api/fileapi/nf-fileapi-findfirstfilea

Ganz egal ob dabei ein .NET Objekt FileInfo abgerufen wird, oder nur der Pfad. Mit dieser API zu arbeiten ist das performanteste, was bei Win32 möglich ist.
.NET ist aber passiv implementiert; es werden also gewisse Sicherheitsüberprüfungen (das hat mit Rechten erst mal nichts zutun) durchgeführt, bevor so ein FileHandle abgerufen wird.
Des weiteren werden beim Füllen des FileInfo Objekts mehr Daten benötigt, als das FileHandle liefert.

.NET macht - und das ist auch gut so - mindestens drei Calls (+ weitere eager loading properties) gegen die Win32 API - QuickIO aber maximal ein Call.
Dadurch kommt die Differenz zustande.

.NET IO wurde bereits überarbeitet; am Grundprinzip - und das ist wie gesagt gut so, da .NET generell passiv implementiert ist - bleibt aber.
zB das Ensuring bzw. dem sogenannten File Security State ist ein CLR-Only Feature.
.NET IO ist auch "freundlicher" gegenüber dem Entwickler, was Laufzeit kostet - QuickIO muss 100% korrekt angesprochen werden und nimmt dem Entwickler nichts ab.

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr

Habe gerade ein paar Test gemacht : File.Exist() und QuickIO.FileExist sind ähnlich schnell. Einlesen in string[] oder List<string> und dann Contains() ist 6 Mal langsamer.
Einlesen in ein Dictionary und dann ContainsKey() ist genauso schnell wie File.Exists.
Bei über 20 Millionen Einträgen reicht der Hauptspeicher aber nicht mehr.

teebeast: Die Dateien sind schon in Verzeichnissen organsiert. Eine Kachel (Bilddatei) für eine Karte hat 3 Werte : x, y und z, wobei z der Zoomlevel ist. Zoomlevel 0 ist die ganze Erde, Zoomlevel 21 ein Haus.
Die Datei findet man so : e:\osm{z}{x}{y}.png

Im Internet werden die Dateien genauso aufgerufen : https://finderwille.xddns.de:8086/osm/16/34207/22076.png

Im Explorer ist das alles schnell.

Das Kopieren der Dateien auf eine neue Platte im NAS dauert geschätzt 4 - 8 Wochen. Da muss ich mir noch was einfallen lassen.

Abt : Ich würde ja optimierte Systeme verwenden, aber ich weiß noch nicht woher ich die Dateien schneller bekommen kann, der Download oder das Rendern aus Vectordaten dauert Wochen oder Monate mit einem Rechner. Dazu weiß ich auch nicht wer mir performant Offline Karten erzeugen kann, das sind einfache SQLite Datenbanken.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

16.806 Beiträge seit 2008
vor einem Jahr

File.Exist() und QuickIO.FileExist sind ähnlich schnell.

QuickIO versucht die File Attribute abzurufen.Wenn Attribute gefunden und Attribute beinhalten NICHT Directory = dann true.
Mit .NET Core bzw. .NET 5 und höher passiert genau das gleiche (nur noch zusätzliches Sanitize) - ergo kann es da kaum ein zeitlichen Unterschied geben.

T
2.219 Beiträge seit 2008
vor einem Jahr

Gibt es dafür nicht fertige Lösungen von bzw. für OpenStreetMap?
Ich meine mich darin zu erinnern, dass wir was ähnliches bei uns verwenden, wenn auch nicht offline.
Wir rendern z.B. auch die OpenStreetMap Karte von einem eigenen Mapnik Server bei uns.
Wir lassen diese aber erst rendern, wenn diese benötigt werden und cachen diese dann über den Server.
Da wir die Daten auch ca. einmal im Monat updaten lassen, müssen diese auch neu gerendert werden.
Damit dürftest du auch am besten fahren.

Das gesamte Material Offline zu speichern ist wegen der Masse kaum möglich.
Bei uns liegen ca. 800+ GB gerenderte Bilder rum.
Auch andere Dienste bieten dann nur einen Teilbereich der Daten offline an.

Nachtrag:
Wie kopiert ihr den die Daten auf das NAS?
Nutzt hier hier z.B. robocopy?
Dort könnt ihr auch mit Threads arbeiten, was die Performance u.U. noch mal steigert.
Nutze ich auch bei vielen kleinen Dateien.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr

Ich möchte die Karten ja in Gebieten nutzen in denen es kein Internet gibt. Da muss ich die Daten Offline speichern.

Für kleinere Gebiete oder für kleine Auflösungen geht das, aber für Europa bis Zoomlevel 20 sieht das anders aus.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

T
2.219 Beiträge seit 2008
vor einem Jahr

Ah okay.
Dann vermute ich mal, dass du über das Dictionary schon die Dateien vorcachen willst.
Also für X/Y/Level als Key und die Datei als Value im Dictionary.

Würde ich aber nicht machen, arbeite hier lieber mit dem Dateisystem Cache und lade die Bilder wenn diese benötigt werden.
Wenn du die Bilder auf den dichtesten Zoom Level nutzt, werden schon je nach Bereich einige GB anfallen.
Diese kannst du dann kaum cachen bzw. müsstest abhängig vom vorhandenen RAM Maßnahmen ergreifen.

Das Dictionary kann bei Geräten mit zugeringem Speicher schnell zum OutOfMemoryException führen.
Ebenfalls müsstest du dann selbst die Speicherverwaltung übernehmen z.B. beim Wechsel des Zoom Levels alle Eintärge für nicht passende Level wieder entfernen.
Und du musst fehlende Einträge, für die es auch lokal keine Datei gibt, dann mit einem Dummy Platzhalter liefern.

Im einfachsten Fall speicherst du die Bilder lokal wie auf dem Webserver und kannst den Pfad dann direkt bilden und abrufen.
Damit fährst du vermutlich am besten.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

G
154 Beiträge seit 2015
vor einem Jahr

Habe gerade ein paar Test gemacht : File.Exist() und QuickIO.FileExist sind ähnlich schnell. Einlesen in string[] oder List<string> und dann Contains() ist 6 Mal langsamer.
Einlesen in ein Dictionary und dann ContainsKey() ist genauso schnell wie File.Exists.
Bei über 20 Millionen Einträgen reicht der Hauptspeicher aber nicht mehr.

Die Datei findet man so : e:\osm{z}{x}{y}.png

Ich frag mal ganz dumm, weil ich die Sache nicht ganz verstanden habe:
Warum werden die Dateien alle abgefragt? Wegen des Kopierens für den Offline-Zugriff?
Die unterste Ordner-Schicht "y" hat 20 millionen Einträge? Oder alles zusammen? Wenn nur alles zusammen, warum dann alles im Speicher halten?

Wenn das fortlaufend und eindeutig nummeriert ist und es "nur" darum geht festzustellen, was fehlt, hilft es dann nicht eventuell, erst mal zu schauen, ob etwas fehlt und wenn ja in welchem Bereich? Dann könnte man sich Contains() sparen und die Anzahl der Abfragen möglichweise deutlich reduzieren.

Oder evtl., wenn eher viele Dateien fehlen und die dann sowieso runtergeladen werden müssen, EnumerateFiles nutzen und bei jedem Eintrag prüfen, ob zum vorherigen eine Lücke besteht (und wie groß die ist), die fehlenden Bezeichnungen in einem sinnvoll begrenzten Puffer halten und gleichzeitig zur Suche runterladen - und loggen bei welcher Datei man war, damit man nicht wieder von vorne anfängt.

Wäre halt blöd, wenn man wegen einer einzigen Datei x Stunden Pfade abfragt, oder man die Sache vielleicht nur eine begrenzte Zeit laufen lassen möchte und dann feststellt, dass man jedes mal die meiste Zeit mit Suchen und nicht mit runterladen/kopieren verbringt.

Und wenn es mehrere SSDs sind, könnte man das nicht evtl. auch gleichzeitig für jede Platte machen?

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr

T-Virus : Ein Mapnik Server ist natürlich eine tolle Sache. Er kann die Bilder auch nach Bedarf rendern, also erst erzeugen wenn sie abgefragt werden.

Die Ursprungsdaten von Open Street Map liegen als Vektordaten vor, ca. 2 TB für die ganze Erde. Wenn man daraus Bilder erzeugt ist das schnell Mal 100 oder 1000 Mal soviel Speicherplatz je nach Zoomfaktor, also wie genau man reinzoomen kann.

Für einen Server der auch schnell Rendern kann sind extrem hohe Anforderungen an die Hardware vorhanden. Ob ich das in einen kleinen mobilen Server packen kann der in einem Auto läuft weiß ich nicht. Dazu kommt dass ein Einsatz an vielen Stellen gleichzeitig sein kann, es geht nicht nur um einen Standort.
Die Bilder vorher zu berechnen ist auf jeden Fall einfacher, Speicherplatz ist ja kein Problem mehr (1 - 4 TB für die Deutschlandkarte).

Für Offline Karten die man aufs Handy oder aufs Tablet laden kann muss ich eh rendern. Die Bibliothek die ich benutze (Mapsui für Xamarin.Forms und WPF) kann aus Geschwindigkeitsgründen nur Raster-Karten anzeigen.

Gimmick : Ich frage die Dateien ab um zu sehen welche fehlen. Da die Dateien in der Regel in der nummerischen Reihenfolge berechnet bzw. geladen werden frage ich jetzt nur die erste und letzte Datei in einem Verzeichnis ab, so wird es sehr schnell.

Kopieren habe ich gerade nochmal getestet : xcopy ist schneller als robocopy. Kopieren über das Netzwerk aufs NAS ist ca. 3 Mal langsamer als von lokaler Platte auf eine andere lokale Platte. Damit kann ich leben.

Unten die Hardware für den Kartenserver.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr

Eine Erklärung : Eine Offline Karte im mbtiles-Fomat, wie es von den meisten Kartenprogrammen benutzt wird, ist nur eine SQLite-Datenbank.

Sie enthält eine Tabelle mit Zoomlevel, x- und y-Koordinate jeweils mit einer Graphik als BLOB gespeichert.

Eine mbtiles Datei kann man sogar mit dem DB-Browser öffnen und die Graphiken anzeigen lassen.

Egal ob Online oder Offline, das Kartenprogramm sagt welche Kachel es braucht mit Angabe von Zoomlevel, X- und Y-Koordinate. Die angezeigte Karte wird dann aus mehreren Kacheln dargestellt.

So einfach ist das.

Noch eine Frage zum Kopieren der Dateien : Da es über das Netz zu langsam ist möchte ich gerne von lokaler Platte auf andere lokale Platte kopieren.

Welches Format soll ich für die Festplatte im Raspberry Pi nehmen ? Ext4, exFAT oder NTFS ? Oder ist das egal ?
Die Festplatte enthält nur die Kartendaten und kann auch readonly gemounted werden.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

709 Beiträge seit 2008
vor einem Jahr

Ich persönlich nutze gern Btrfs.
Allein schon wegen der Snapshots, Copy on write und der Prüfsummen.

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr

Wenn das fortlaufend und eindeutig nummeriert ist und es "nur" darum geht festzustellen, was fehlt, hilft es dann nicht eventuell, erst mal zu schauen, ob etwas fehlt und wenn ja in welchem Bereich? Dann könnte man sich Contains() sparen und die Anzahl der Abfragen möglichweise deutlich reduzieren.

Eine einfache Umstellung hat viel gebracht : Anstatt Contains() schaue ich jetzt nach den Lücken. Beide Reihen, die ich vergleiche, sind ja sortiert :


for (int tx = point1.X - 1; tx < point2.X + 2; tx++)
	for (int ty = point2.Y - 1; ty < point1.Y + 2; ty++)
	{
		string file = verz + zoom.ToString() + "\\" + tx.ToString() + "\\" + ty.ToString() + ".png";
		while (files[index].ToLower().IsLess(file)) index++;
		if (files[index].ToLower() == file) tiles++;
	}

Die Geschwindigkeit nur für Hessen hat sich von 1:30 Stunden auf 26 Sekunden verbessert !!!

Ohne das Laden von files[]. Das reicht ja einmal am Anfang um dann mehrere Karten zu rechnen. Jetzt kommt ich an die Speichergrenzen. Wie kann ich den nutzbaren Speicher für string[] vergrößern ? Oder Pfadnamen verkürzen ?

Manchmal muss man beim Programmieren halt den Kopf einschalten.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

T
2.219 Beiträge seit 2008
vor einem Jahr

Im ersten Schritt solltest du das zusammensetzen des Pfad über Stringgebastel durch Path.Combine ersetzen.
Dadurch sparst du viele unnötige String Objekte, die jetzt im Speicher liegen bzw. aufwändig durch GCs entfernt werden müssen.

Ich würde auch folgenden Ansatz versuchen.

  1. HashSet für Koordinaten anlegen (String Aufbau Zoom|X|Y)
  2. HashSet mit allen vorhandenen Dateien befüllen
  3. Durch die Schleife durchlaufen, Keys bilden und prüfen ob vorhanden
  4. Wenn HashSet.Contains = false, dann hast du eine Lücke

Damit dürftest du noch etwas schneller sein und sehr viele unnötige String Objekte sparen 🙂
Anbei kannst du beim bilden des Key auch String Interpolation verwenden.
Dadurch hast du nur ein Objekt mehr am Ende.


HashSet<string> existingFiles = new HashSet<string>();

// HashSet mit vorhandnene Dateien befüllen
string[] files = Dicrectory.GetFiles(dir, "*.png", SearchOption.AllDirectories);

foreach(string file in files)
{
    // Pfad zerlegen um Zoom, X, Y zu ermitteln
    string zoom = bla;
    string x = blub;
    string y = blablub;

    string key = $"{zoom}|{x}|{y}";
    existingFiles.Add(key);
}

for (int tx = point1.X - 1; tx < point2.X + 2; tx++)
{
    for (int ty = point2.Y - 1; ty < point1.Y + 2; ty++)
    {
        string key = $"{zoom}|{x}|{y}";

        if(existingFiles.Contains(key))
            tiles++;
    }
}

Nachtrag:
Wenn du die Ermittlung des HashSet in eine eigene Methode packst, kann der GC das string[] auch direkt weg hauen.
Dadurch ist dein Speicher nur auf das HashSet als größtes Objekt limitiert.
Dürfte sich aber in Grenzen halten.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr

Gute Idee !

.Contains in einer List<> hatte ich schon probiert, das war 6 Mal langsamer als File.Exists(). HashSet() werde ich testen.

Dazu kommt dass ich das Übertragen von files[] nach Hash<> ja in mehrere Schritte aufteilen kann da es mehrere Verzeichnisse sind, um einen Speicherüberlauf zu verhindern.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

T
2.219 Beiträge seit 2008
vor einem Jahr

Contains bei einer Liste ist halt langsam, weil er alle Elemente durchgehen muss um zu schauen ob es einen Treffer gibt.
Dadurch hast du wieder eine lineare Suchdauer, die abhängig von der Anzahl der Elemente und der Position des gesuchten Elements ist.
Im schlimmsten Fall muss er bei Lücken dann alle Einträge durchlaufen um keinen Treffer zu ermitteln.

HashSet sowie Dictionary lösen dies, da beim HashSet der Eintrag und beim Dictioanry der Key über einen ermittelten HashCode (int) via GetHashCode berechnet werden.
Dieser wird dann als Suchposition intern verwendet, was eine Suche extrem beschleunigt.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr

Test mit string[] :

Zeit : 42 Sekunden
Hauptspeicher : 228 MB

Test mit HashSet<> :

Zeit : 9 Sekunden
Hauptspeicher : 208 MB

Wenn ich ganz Deutschland rechne :

File.Exists() : Zeit 9 Stunden 23 Minuten 19 Sekunden

HashSet<> : Zeit 35 Sekunden

Genial !!!

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

G
154 Beiträge seit 2015
vor einem Jahr

Nach den weiteren Änderungen ist das wahrscheinlich schon schnell genug und ich weiß auch nicht, das was ich mir dachte noch was bringt und es ist vielleicht etwas kompliziert gedacht, aber nichtsdestotrotz 😄...

Wenn die Ordner alle nummeriert sind, gibt Directory.EnumerateFiles() immer die gleiche Reihenfolge zurück und man sieht direkt am Pfad, ob beim ersten oder zwischen n und n+1 Einträge fehlen. Dann würde ein Durchlauf reichen und das Array muss nicht komplett in den Speicher.

Setzt aber vorraus, dass man genau weiß, was kommen sollte 😉.

T
2.219 Beiträge seit 2008
vor einem Jahr

@Gimmick
Wäre auch möglich aber man müsste einiges mehr an Prüfungen durchführen.
Man muss z.B. beachten, dass auf allen Ebenen des Pfad Teile fehlen können.
Also z.B. eine Zoomstufe am Anfang (0), Ende (21) oder mitten (1-20) drin.
Das gleiche gilt für X Ordner und die Y Dateien.

Entsprechend müsstest du dir die aktuelle Zoomstufe merken.
Abhängig davon musst du die unterschiedliche X/Y Mengen beachten, da jede Zoomstufe ihre eigene Menge an X/Y Kombinationen hat.

Zusätzlich könnte man den HashSet Ansatz noch beschleunigen, wenn man die Prüfungen auf mehrere Kerne verteilt.
Hier könnte man z.B. pro Zoomstufe mit Parallel.For die Daten gegenprüfen.
Da X/Y pro Zoomstufe in der gleichen Anzahl vorliegen müssten, könnte man damit noch die Abfragen beschleunigen.
Bei größeren Prüfungen wie z.B. bei gößeren Ländern wie Deutschland etc. kann man noch einige Sekunden einsparen.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

16.806 Beiträge seit 2008
vor einem Jahr

Zusätzlich könnte man den HashSet Ansatz noch beschleunigen, wenn man die Prüfungen auf mehrere Kerne verteilt.
Hier könnte man z.B. pro Zoomstufe mit Parallel.For die Daten gegenprüfen.

Wahrscheinlicher ist, dass bei diesem Fall der notwendige Overhead mehr Zeit kosten dürfte, als eingespart wird.

BerndFfm Themenstarter:in
3.825 Beiträge seit 2006
vor einem Jahr

Directory.EnumerateFiles() um eine Hash Tabelle zu füllen ist wohl die beste Lösung !

Sehr Speicherplatz sparend und schnell.

Zwischenstand :

Topographische Karte : 2.080.881 Dateien

Zweisprachige Open Street Map Karte : 17.032.875 Dateien

Open Street Map Karte : 32.806.336 Dateien

Insgesamt 450 GB.

T-Virus : Das ist jetzt so schnell dass ich es nicht auf mehrere Kerne verteilen muss. Ich habe ja noch mehr Aufgaben wie ich anderen Kerne beschäftigen kann : Karten Download, Karten Statistik aus dem Hash erstellen, Karten Datei berechnen.

Grüße Bernd

Workshop : Datenbanken mit ADO.NET
Xamarin Mobile App : Finderwille Einsatz App
Unternehmenssoftware : Quasar-3

T
2.219 Beiträge seit 2008
vor einem Jahr

Dann passt es ja 🙂

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.