Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Listen für Suchen optimieren
DNS46
myCSharp.de - Member



Dabei seit:
Beiträge: 19

Themenstarter:

Listen für Suchen optimieren

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Abt
myCSharp.de - Team

Avatar #avatar-4119.png


Dabei seit:
Beiträge: 15.852

beantworten | zitieren | melden

Zitat von DNS46
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.
private Nachricht | Beiträge des Benutzers
DNS46
myCSharp.de - Member



Dabei seit:
Beiträge: 19

Themenstarter:

beantworten | zitieren | melden

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.
        //
private Nachricht | Beiträge des Benutzers
T-Virus
myCSharp.de - Member



Dabei seit:
Beiträge: 1.986
Herkunft: Nordhausen, Nörten-Hardenberg

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
DNS46
myCSharp.de - Member



Dabei seit:
Beiträge: 19

Themenstarter:

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
T-Virus
myCSharp.de - Member



Dabei seit:
Beiträge: 1.986
Herkunft: Nordhausen, Nörten-Hardenberg

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
JimStark
myCSharp.de - Member

Avatar #dOpLzh7hN1az1g0eGRc0.jpg


Dabei seit:
Beiträge: 306

beantworten | zitieren | melden

Linq kennst du aber? Kannst ja mit Und-Verknüpfungen arbeiten. Wenn es um optimierte abfragen generell geht: https://github.com/NetFabric/NetFabric.Hyperlinq
private Nachricht | Beiträge des Benutzers
Abt
myCSharp.de - Team

Avatar #avatar-4119.png


Dabei seit:
Beiträge: 15.852

beantworten | zitieren | melden

Zitat von DNS46
.. 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.
private Nachricht | Beiträge des Benutzers
chilic
myCSharp.de - Experte



Dabei seit:
Beiträge: 2.105

beantworten | zitieren | melden

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.
Zitat
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?
private Nachricht | Beiträge des Benutzers
Abt
myCSharp.de - Team

Avatar #avatar-4119.png


Dabei seit:
Beiträge: 15.852

beantworten | zitieren | melden

Zitat von chilic
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.
Zitat von chilic
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?
private Nachricht | Beiträge des Benutzers
chilic
myCSharp.de - Experte



Dabei seit:
Beiträge: 2.105

beantworten | zitieren | melden

Zitat
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"?
Zitat
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.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von chilic am .
private Nachricht | Beiträge des Benutzers
JimStark
myCSharp.de - Member

Avatar #dOpLzh7hN1az1g0eGRc0.jpg


Dabei seit:
Beiträge: 306

beantworten | zitieren | melden

Zitat von chilic
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:
Zitat
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);
private Nachricht | Beiträge des Benutzers
Th69
myCSharp.de - Experte

Avatar #avatar-2578.jpg


Dabei seit:
Beiträge: 4.358

beantworten | zitieren | melden

Dann hast du das wohl falsch verstanden. DNS46 möchte mal nach Street oder Zipcode suchen (nicht kombiniert):
Zitat von DNS46
Also so das die myAddresses z.B. einmal suchoptimiert für zipcode und ein andermal für street -Abfragen durchlaufen werden kann?
private Nachricht | Beiträge des Benutzers
DNS46
myCSharp.de - Member



Dabei seit:
Beiträge: 19

Themenstarter:

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Th69
myCSharp.de - Experte

Avatar #avatar-2578.jpg


Dabei seit:
Beiträge: 4.358

beantworten | zitieren | melden

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).
private Nachricht | Beiträge des Benutzers
DNS46
myCSharp.de - Member



Dabei seit:
Beiträge: 19

Themenstarter:

beantworten | zitieren | melden

Zitat
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
private Nachricht | Beiträge des Benutzers
Abt
myCSharp.de - Team

Avatar #avatar-4119.png


Dabei seit:
Beiträge: 15.852

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
DNS46
myCSharp.de - Member



Dabei seit:
Beiträge: 19

Themenstarter:

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers