Laden...

Listen für Suchen optimieren

Erstellt von DNS46 vor einem Jahr Letzter Beitrag vor einem Jahr 792 Views
D
DNS46 Themenstarter:in
21 Beiträge seit 2020
vor einem Jahr
Listen für Suchen optimieren

Hallo,

ich möchte eine Liste von Objekten durchsuchen.


Item address = myAddresses.find(x => x.Street == "Schlossallee");

würde sich z.B. anbieten. Nun die Frage: Durchsucht diese Methode logarithmisch bzw. anderweitig optimiert oder einfach step by step?
Gibt es Möglichkeiten das nachzuvollziehen?

Falls .find() jetzt keine Optimierung enthält: hat jemand eine Empfehlung in welchen Datentyp Objekte gut verwaltet werden können, wenn diese nach mehreren Attributen suchoptimiert sein sollen. Also so das die myAddresses z.B. einmal suchoptimiert für zipcode und ein andermal für street -Abfragen durchlaufen werden kann?

Wär cool wenn ihr ne Idee habt 🙂
Danke schonmal

16.807 Beiträge seit 2008
vor einem Jahr

würde sich z.B. anbieten. Nun die Frage: Durchsucht diese Methode logarithmisch bzw. anderweitig optimiert oder einfach step by step?
Gibt es Möglichkeiten das nachzuvollziehen?

Keiner hier kann erkennen, von welchem Typ das Objekt myAddresses ist; daher kann Dir das auch niemand beantworten.
Es ist nicht mal ersichtlich ob das .NET ist - weil Methoden in .NET sind normalerweise Groß geschrieben.
Aber Du kannst einfach a) in die Dokumentation der Methode schauen oder b) in den Quellcode.

D
DNS46 Themenstarter:in
21 Beiträge seit 2020
vor einem Jahr

Ja den Typ hab ich jetzt unterschlagen ...
Ich meine natürlich:


System.Collections.Generic.List<Address> myAddresses;
Item address = myAddresses.Find(x => x.Street == "Schlossallee");

Ich kann anhand der Methodenbescheibung nur mutmaßen, dass hier step by step durchlaufen wird. Ist das korrekt?


        //
        // Zusammenfassung:
        //     Sucht nach einem Element, das die durch das angegebene Prädikat definierten Bedingungen
        //     erfüllt, und gibt das erste Vorkommen im gesamten System.Collections.Generic.List`1
        //     zurück.
        //

T
2.219 Beiträge seit 2008
vor einem Jahr

Ja, bei List<T> werden alle Einträe geprüft und beim ersten Treffer direkt das Ergebnis geliefert.
Wenn du nur eindeutige Einträge hättest, dann könntest du auch Dictionary<TKey, TValue> nehmen.
Dürfte vermutlich aber nicht dein Anwendungsfall sein.

Anbei die Doku zu List<T>:
List<T> Klasse (System.Collections.Generic)

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.

D
DNS46 Themenstarter:in
21 Beiträge seit 2020
vor einem Jahr

Ok Danke - dachte ich mir, war mit aber nicht sicher.
Dictionary lässt sich ja optimiert nach Keys durchsuchen. Bietet .Net auch einen Datentyp der das optimierte durchsuchen von mehreren Attributen ermöglicht ... analog zu indizierten Datenbankspalten?

so ...


System.Collections.Generic.List<Address> myAddresses;
Item address = myAddresses.Find(x => x.Street == "Schlossallee");
Item address = myAddresses.Find(x => x.ZipCode == 12345);

so etwas bräuchte ich, finde es nur nicht.

T
2.219 Beiträge seit 2008
vor einem Jahr

Wieviele Einträge hast du den und wie oft musst du nach Einträgen suchen?
Alternativ kannst du, wenn es nur um einzelne Attribute geht, diese auch in unterschiedliche Dictionaries packen.

Z.B. nutze ich auch eine eigene Klasse, die meine Einträge je nach Kriterium in eigene Dictionary packt.
Dadurch kann ich die Treffer direkt ermitteln.
Wenn du Attribute aber kombinieren musst, wird dieser Ansatz vermutlich nicht funktionieren.
Dann müsstest du auch sicherstellen, dass neue Einträe überall eingefügt werden.

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.

309 Beiträge seit 2020
vor einem Jahr

Linq kennst du aber? Kannst ja mit Und-Verknüpfungen arbeiten. Wenn es um optimierte abfragen generell geht: https://github.com/NetFabric/NetFabric.Hyperlinq

16.807 Beiträge seit 2008
vor einem Jahr

.. analog zu indizierten Datenbankspalten?

Das hat bei Datenbanken nichts mit dem Datentyp zutun.

Eine Datenbank erreicht das, indem die gewünschte Sortierung auf Basis des Index schon vorher bekannt ist und kann dadurch Pagen.
Das kostet aber entsprechend mehr Speicher und auch Performance bei Schreib-Vorgängen - bekommt man also "nicht einfach so".

Wenn Du das selbst programmieren willst heisst das im Endeffekt: mehrere Listen, die jeweils bereits sortiert sind und immer die nehmen, nach der die Sortierung erfolgt ist.
Selten, dass sich das lohnt.

C
2.121 Beiträge seit 2010
vor einem Jahr

Es gibt die Methode BinarySearch für Listen und Arrays, hab ich soeben gefunden. Vielleicht hilft dir das ja.
Die erfordert aber dass die Liste sortiert ist. Sonst kann die Suche nicht wissen welche Listenelemente sie nicht überprüfen muss.
Denn wenn der Treffer überall stehen kann, muss alles durchsucht werden.

Dictionary lässt sich ja optimiert nach Keys durchsuchen.

Nicht ganz. Ein Dictionary merkt sich mittels Hashwerten wo ein Objekt liegt. Damit muss im Idealfall kaum gesucht werden, sondern es kann sich direkt ausrechnen wo das Objekt liegen müsste. In der Praxis liegen an dieser Stelle vielleicht auch mehrere Objetke, aber eben nicht alle sondern nur ein paar.

Wie sehr sich Optimierung lohnt hängt stark von deinem Anwendungsfall ab. Wenn ein Einzelplatzrechner der kaum was tut pro Tag 100 x 1 ms länger braucht wäre mir das egal. Wenn ein Server alle 10 Sekunden sehr viele Elemente durchsucht und dabei jeweils 0,5 Sekunden länger braucht ist es schlecht.

Dass reflexartig Linq erwähnt wird ohne der Frage viel zu nutzen ist man in diesem Forum gewohnt. Neu wäre der Hinweis auf UND Verknüpfungen - was könnte DNS46 damit anfangen?

16.807 Beiträge seit 2008
vor einem Jahr

Dass reflexartig Linq erwähnt wird ohne der Frage viel zu nutzen ist man in diesem Forum gewohnt.

Da Linq ein sehr sehr weit verbreitetes und Bullet-Proof Mittel für >99% der Anforderungen ist, passt das doch..?
Linq hat mittlerweile sehr sehr optimierte Implementierung in den Order()-Methoden; besonders bezogen auf den Key Selector.
Seine bereits verwendete Methode Find() basiert auf den Prinzipien von Linq; wir bewegen uns also im gleichen Spektrum.

Das ändert aber nichts, dass die grundlegende Performance einer Sortierung halt die Quelle ausmacht (weswegen Datenbanken genau das machen).

Dein Pauschalrundschlag ist also eher übers Ziel hinaus geschossen.
Sollte das Frust abbauen, oder welchen Sinn hat das? Denn Nutzen, den Du selbst ansprichst, hat das keinen - für niemanden.

Neu wäre der Hinweis auf UND Verknüpfungen - was könnte DNS46 damit anfangen?

Statt ein Quiz daraus zu machen, kann man ja einfach produktiv antworten, oder?

C
2.121 Beiträge seit 2010
vor einem Jahr

Sollte das Frust abbauen, oder welchen Sinn hat das? Denn Nutzen, den Du selbst ansprichst, hat das keinen - für niemanden.

Dass ich das anspreche hat noch keinen Nutzen. Aber vielleicht zeigt sich der Nutzen, wenn zukünftig jemand der mit dem Prinzip und Grundverständnis von Arrays und Listen und deren Handling schon überfordert ist, einen Hinweis bekommt was er falsch macht oder wo er etwas übersieht, statt einfach auf Linq verwiesen zu werden.
Was soll denn jemand mit Linq wenn die Grundlagen noch fehlen?

Wenn sich jemand verläuft und mich um Rat fragt dann erkläre ich ihm wo er sich gerade befindet, wo er falsch abgebogen ist und wie er richtig läuft. Sollte ich sagen "kannst auch mit Auto, Bus oder U-Bahn hinfahren - falls du selbst rausfindest wo du bist und wo du hin musst"?

Statt ein Quiz daraus zu machen, kann man ja einfach produktiv antworten, oder?

Mit meiner Frage wollte ich ausdrücken dass ich nicht weiß was eine Und Verknüpfung hier bringen sollte.

Frust direkt ist es nicht, aber schade finde ich sowas. Ich bilde mir ein in der Zeit als ich von hier sehr wertvolle Antworten für mein C# Wissen mitgenommen habe waren die Antworten anders.

309 Beiträge seit 2020
vor einem Jahr

Mit meiner Frage wollte ich ausdrücken dass ich nicht weiß was eine Und Verknüpfung hier bringen sollte.

Für mich hört sich die Fragestellung:

System.Collections.Generic.List<Address> myAddresses;
Item address = myAddresses.Find(x => x.Street == "Schlossallee");
Item address = myAddresses.Find(x => x.ZipCode == 12345);

so etwas bräuchte ich, finde es nur nicht.

nach sowas an:


Item address = myAddresses.Find(x => x.Street == "Schlossallee" && x.ZipCode == 12345);

4.931 Beiträge seit 2008
vor einem Jahr

Dann hast du das wohl falsch verstanden. DNS46 möchte mal nach Street oder Zipcode suchen (nicht kombiniert):

Also so das die myAddresses z.B. einmal suchoptimiert für zipcode und ein andermal für street -Abfragen durchlaufen werden kann?

D
DNS46 Themenstarter:in
21 Beiträge seit 2020
vor einem Jahr

Wow - Gute Ideen. Ich danke euch allen.
Den Ansatz mit der doppelten Datenhaltung in 2 Dictionaries find ich jetzt gar nicht übel.
LINQ kannte ich auch noch nicht. Das würde den Code echt schlank halten. Ich mach mal ein paar Performance Tests damit.

4.931 Beiträge seit 2008
vor einem Jahr

Hast du denn so große Listen (in Memory), daß sich das lohnt?

Im Internet habe ich dazu auch Multi-key Generic Dictionary gefunden.
Oder du benutzt gleich eine In-Memory Datenbank, wie z.B. NMemory, MemState oder auch SQLite (s. SQLite-In-Memory-Datenbank).

D
DNS46 Themenstarter:in
21 Beiträge seit 2020
vor einem Jahr

Im Internet habe ich dazu auch Multi-key Generic Dictionary gefunden.

Geil 👍 Genau das brauche ich


MultiKeyDictionary<string, string, string> dictionary = new MultiKeyDictionary<string, string, string>();
                                    
dictionary.Add("99112", "Schlossalle", "address of sombody in 99112 Schlossalle"); //primary key, subkey, value
dictionary.Add("99113", "Poststraße", "address of sombody in 99113 Poststraße");
dictionary.Add("99114", "Wasserwerk", "address of sombody in 99114 Wasserwerk");
            
string zipCode = "99112";
string street = "Schlossalle";
string returnvalue;          

dictionary.TryGetValue_PrimarykeySearch(zipCode, out returnvalue);
Console.WriteLine(String.Format("value for zip code search [{0}] = " + returnvalue, zipCode));

dictionary.TryGetValue_Subkey_Search(street, out returnvalue);
Console.WriteLine(String.Format("value for street search [{0}] = " + returnvalue, street));

// result:
// value for zip code search [99112] = address of sombody in 99112 Schlossalle
// value for street search [Schlossalle] = address of sombody in 99112 Schlossalle


Ich probier mal wie schnell das läuft.
Ja und zu den Datenmengen und so ... das werden am Ende einige 100.000 Records denke ich. Es ist ein ETL Prozess der von einer Applikation liest, transformiert und in ein Ziel DB Schema updatet. Die API Belastung der Quell-App soll möglichst gering gehalten werden. Der Prozess teilt sich das Ziel DB Schema mit anderen Prozessen die genauso Updaten wollen. Sobald der Prozess gestartet wird setzt er deshalb nen DB LOCK auf die Tabellen. Um die LOCK Zeit möglichst kurz zu halten, sollten die Transformationen zügig laufen. Rechenintensiv dürfen sie aber sein.

Dankeschön

16.807 Beiträge seit 2008
vor einem Jahr

Na, dann bin ich ja gespannt, wann Du Dich hier wieder meldest wegen einer OutOfMemoryException 🙂
Da wäre eine InMemory DB deutlich schlauer, da solche sich um das Speichermanagement kümmern und zur Not auslagern.

Geschweige denn, wenn möglich, dass eine DB Bulk Operation i.d.R. der performanteste Weg wäre, um auch das Lock zu optimieren.
Daher macht es Sinn, wenn Du dem Forum von Anfang an sagst, was das eigentliche Ziel ist, sodass Dir möglichst früh der beste Weg vorgeschlagen werden kann.

D
DNS46 Themenstarter:in
21 Beiträge seit 2020
vor einem Jahr

Die OutOfMemoryException kam bei > 1 Mio Test Records 🙂 Bis dahin ist aber gut Luft und ich kann noch optimieren
Aufgabenstellungen sind im Dateil halt gar nicht so leicht zu beschreiben (erst recht nicht, wenn sie dazu noch fragwürdig sind)
Per BULK funktioniert leider nicht. Eure Tipps waren aber echt gut