Jump to content
Unity Insider Forum

Listentyp mit schnellem Suchalgorithmus


GaRv3

Recommended Posts

Hallo zusammen,

ich suche derzeit nach einem Listentyp, der auch bei extrem großen Datensätzen sehr schnell zu durchsuchen ist.

Grundsätzlich bietet sich hier ja ein HashSet mit überschriebenem HashCode und angepasster Equals-Methode an. Allerdings reicht mir die Equals/Contains-Suche nicht, da ich unterschiedliche Suchen durchführen muss, die teilweise auch mehrere Ergebnisse liefern sollen. Es können mehrere Mio. Objekte in der Liste sein.

Hier ein vereinfachtes Beispiel:
In der Liste sollen Objekte einer Klasse gespeichert werden, die die zwei Member-Variablen x und y enthält. Die Objekte sind alle unique. Das heißt, es gibt niemals mehrere Objekte, in denen x und y übereinstimmen (a.x == b.x && a.y == b.y). Auch invertiert sind diese niemals gleich. "a.x == b.y && a.y == b.x" gibt es also ebenso niemals. Allerdings kann es viele Objekte geben, in denen x ODER y identisch sind.

Nun muss ich folgende Suchen möglichst performant durchführen können:
1. Finde ein Objekt, in dem "(x == suche.x && y == suche.y) || (x == suche.y && y == suche.x)" -> Das Ergebnis ist ein einzelnes Objekt.
2. Finde alle Objekte, in denen "x == suche.x || y == suche.x" -> Das Ergebnis können mehrere Objekte sein.

Welchen Listentyp wähle ich hierfür?

Vielen Dank im Voraus und beste Grüße
garv3

Link zu diesem Kommentar
Auf anderen Seiten teilen

Da gibt's keinen praktischen, fertigen Listentyp für. Oder sonst irgendeine Sammlung. Wenn dir eine normale Liste mit Linq-Statement dran nicht schnell genug ist, musst du dir eine eigene Struktur schreiben. Ist aber grundlegend gar nicht mal so schwer, man muss nur ein bisschen algorithmisch denken.

In deinem Fall fällt mir direkt ein Dictionary von Listen ein:

Dictionary<int, List<Foo>> dict;

Wenn die Zahlen deiner Objekte mehr oder weniger zufällig sind, dann könntest du sie hier mit nach ihrer Summe einsortieren:

public void Add(Foo foo)
{
  var sum = foo.x + foo.y;
  dict[sum].Add(foo);
}

Da bei deiner Suche die Summe von x und y bei allen möglichen Ergebnissen gleich ist, brauchst du dann nur noch in der Liste mit der entsprechenden Summe zu suchen:

public List<Foo> FindAll(int x, int y)
{
  var results = new List<Foo>();
  var sum = x + y;
  foreach(var foo in dics[sum])
  {
    if(foo.x == x && foo.y == y
    || foo.x == y && foo.y == x)
    {
      results.Add(foo);
    }
  }
  return results;
}

Entsprechend schneller geht auch das Entfernen von Elementen, weil man nur in der richtigen Liste nach dem zu entfernenden Objekt(en) suchen muss.

Da muss dann überall noch ein bisschen Extracode rein, der checkt, ob der ausgesuchte Schlüssel überhaupt im Dictionary existiert.

Insgesamt ist das nicht viel anders als das, was HashSets auch machen - nur, dass wir statt eines technischen Hashes einen semantisch bedeutsamen Wert (die Summe) zum Speichern nehmen.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Hi Sascha,

Erstmal vielen dank für deine Antwort!
Das sieht grundsätzlich auch nach einer schönen Struktur aus. Leider wird diese in meinem Fall nicht funktionieren.
Das liegt im Wesentlichen an zwei Problemen:

1. x und y sind keine Zahlenwerte. Hier habe ich in meinem Beispiel wohl unschöne Bezeichner verwendet. Es handelt sich dabei um eher komplexe Datentypen bzw. u.U. Instanzen anderer Klassen. Daher kann ich leider nicht mit der Summe der beiden Variablen vorsortieren. Das könnte ich aber theoretisch über Hashwerte lösen.

2. Viel entscheidender ist, dass ich x und y (und deren Summe/Hash) eben nicht immer kenne. Im Fall meiner ersten Beispielsuche kenne ich sie, aber im zweiten Beispiel ist nur einer der beiden Werte (suche.x) bekannt. Dieser muss in x und y der Objekte in der Liste gesucht werden, aber unabhängig vom jeweils anderen Wert.

Als Beispiel habe ich obj01 - obj07 angenommen, die jeweils in x oder y der Listenelemente stecken können. Hier die Beispielliste (Die Nummerierung ist nur zur Veranschaulichung. Die Liste muss nicht sortiert oder sortierbar sein!):

1. x=obj05; y=obj02
2. x=obj01; y=obj04
3. x=obj04; y=obj03
4. x=obj07; y=obj01
5. x=obj06; y=obj07
6. x=obj04; y=obj01

Beispielsuche 1: "Finde alle Elemente mit obj01 und obj04, also "(x == obj01 && y == obj04) || (x == obj04 && y == obj01)". Das ergibt dann die Einträge 2 und 6.

Beispielsuche 2: "Finde alle Objekte, die obj04 enthalten, also "x == obj04 || y == obj04". Das ergibt die Einträge 2, 3 und 6. Hier ist der jeweils andere Wert vor der Suche nicht bekannt. Dadurch kann ich auch nicht nach einem vorher definierten Hasch (oder einer Summe) vorsortieren.

Hast du (oder jemand anders) vielleicht noch eine Idee?

Dank und Gruß
garv3

Link zu diesem Kommentar
Auf anderen Seiten teilen

Du hast im Endeffekt nicht viele Möglichkeiten einen Suchvorgang zu verkürzen. Bei einer Datenbank werden diese Prinzipien verwendet.

a ) du bildest einen Hash über alle Objekte, über diesen Hash kann sehr schnell auf die Elemente zugegriffen werden oder gesucht werden
Die Daten werden über einen Hash "einsortiert". Dieser Hash kann über "beliebige" Elemente des "Datensatzes" gebildet werden.
b )  du sortierst die Daten der Liste anhand eines Attributes vor

Zitat

1. Finde ein Objekt, in dem "(x == suche.x && y == suche.y) || (x == suche.y && y == suche.x)" -> Das Ergebnis ist ein einzelnes Objekt.
2. Finde alle Objekte, in denen "x == suche.x || y == suche.x" -> Das Ergebnis können mehrere Objekte sein.

Würde ich mal "ansatzweise" so probieren:
1) ein Hashtable mit X und Y als Hashschlüssel, dabei wird 2x im Hash gesucht:
- 1x über Hash gebildet aus "suche.x+suche.y"
- 1x über Hash gebildet aus "suche.y+suche.x"
=> kann 0, 1 oder 2 Treffer ergeben.
2) bei mehreren Objekten wobei X den gleichen Wert haben kann wird es schwierig, hier müsste man im Vorfeld Sublisten erstellen mit Objekten wo X den gleichen Wert hat (also eine Art "Vorsortierung").
Zusätzlich Sublisten wo Y den gleichen Wert hat. Diese Sublisten werden wiederum Hashes untergeordnet (Hash#1 über X und Hash#2 über Y)
Für die Abfrage folgt dann:
- finde Hash#1 Subliste mit "suche.x"
- finde Hash#2 Subliste mit "suche.x"
Am Ende beide Treffermengen addieren.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Danke für den Denkanstoß!

Also erstelle ich drei Hashtables. Aus jedem Objekt erstelle ich dann den jeweiligen Hashcodes und füge es in alle drei Hashtables ein.

Bei einer Suche des ersten Typs suche ein oder ggf. zwei mal im ersten Hashtable.
Bei einer Suche des zweiten Typs suche ich im zweiten und dritten Hashtable.

War das so deine Idee?

Grundsätzlich eine gute Idee, obwohl dies natürlich den dreifachen Speicher erfordert.

Jetzt stellt sich mir noch die Frage, wie ich eindeutige Hashes erstellen kann. Oder ich nehme HashSets. Die benötigen ja keine eindeutigen Hashes.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Zitat

Grundsätzlich eine gute Idee, obwohl dies natürlich den dreifachen Speicher erfordert.

Stimmt so nicht ganz, der Speicher wird nur für die Hashtables (Hash + Speicheradresse)  verbraucht. Die Datensätze (die erzeugten Instanzen der Klassen) sollten nur 1x im Speicher vorhanden sein.

Und ja für den Hashtable müssen die erzeugten Schlüssel eindeutig sein. Daher sollte man ja vorher alle Objekte mit gleichen Werten z.b. ein ein HashSet (oder Liste) packen und diese dann in den Hashtable "einhängen". Ist also hier nur eine Frage der "Vorsortierung". Auch wenn man später wieder Objekte entnimmt oder einfügt, muss zuerst in den Hashtable geschaut werden, die Liste (oder Hashset) herausgeholt werden, das einzelne Objekt dann im Hashset gelöscht oder eingefügt werden.
Sind alles klassische Beispiele dafür was eine Datenbank so "treibt", wenn Datensätze in eine Tabelle eingefügt werden.

Link zu diesem Kommentar
Auf anderen Seiten teilen

vor 7 Stunden schrieb Zer0Cool:

Stimmt so nicht ganz, der Speicher wird nur für die Hashtables (Hash + Speicheradresse)  verbraucht. Die Datensätze (die erzeugten Instanzen der Klassen) sollten nur 1x im Speicher vorhanden sein.

Das ist der Unterschied zwischen Klassen und Structs. Wenn du deinen Datentyp als Klasse definierst, sind die Objekte einmalig im Heap und werden von deinen Sammlungen nur referenziert (eine Nummer pro Element), wohingegen ein Struct direkt in den Listen stünde, und entsprechend pro Auftauchen als Element einmal vollständig existiert.

Der Grundgedanke meines Posts bleibt übrigens derselbe. Versuche, eine Art zu finden, wie du deine Objekte sinnvoll sematisch sortieren kannst. Ein HashSet sortiert nach Hash, welcher nur dadurch ermittelt werden kann, dass du genau dieselben Daten abfragst wie die, die das Objekt hat. Wie du selber schon geschrieben hast, kannst du damit nicht so sortieren, dass du mehrere Ergebnisse findest - weil diese ja nicht genau denselben Hash-Wert haben. Wenn du allerdings statt eines richtigen Hashes eine andere Größe findest, die bei allen Ergebniselementen derselben Suche gleich ist, dann kannst du die Objekte nach dieser Größe sortiert lagern und beim Suchen ausschließlich im richtigen "Lager" nachschauen.

Beachte übrigens bei HashSets/HashTables, dass alles kaputt geht, wenn sich der Hash des Objekts ändert, während es eingelagert ist.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ja, das sind alles valide Argumente. Ich glaube, das ganze könnte letztendlich doch etwas komplizierter werden. Sobald ich es komplett durchdacht habe, werde ich hier mal die Klassen und meinen Lösungsansatz posten. Ich denke, dann wird alles ziemlich deutlich.

Derzeit habe ich sogar eine Theorie im Kopf, die mit einem einzigen HashSet funktionieren könnte, aber das muss ich erst noch überprüfen.

Vielen, vielen Dank schon mal für eure Hilfe!

Link zu diesem Kommentar
Auf anderen Seiten teilen

Ich habe gerade noch einmal nach dem Unterschied zwischen Hashtable und Dictionary gesucht. Hier eine interessante Info dazu:
The "System.Collections.Generic.Dictionary" generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the "System.Collections.Generic.Dictionary" class is implemented as a hash table.

Das meint allerdings nicht, das die Klasse "Dictionary" von "HashTable" erbt (es geht hier um die verwendete Technik)! Natürlich gibt es noch mehr Unterschiede, hier ist eine ganz gute Auflistung. Ich denke mal generell formuliert, Dictionary ist eine typisierte (generische) Collection die auf der Technik von Hashtables basiert.
https://stackoverflow.com/questions/301371/why-is-dictionary-preferred-over-hashtable

Link zu diesem Kommentar
Auf anderen Seiten teilen

vor 8 Minuten schrieb GaRv3:

Hehe, also ist ein Dictionary praktisch nur eine handlichere Version eines HashTables!?

Ich werde erst mal diesen Weg gehen. Vielleicht haut es ja hin. Ich muss halt nur immer eindeutige Hashes erzeugen.

Könnte man so sagen. Ich vermute ein Hashtable macht nur Sinn, wenn man vieles umschreiben möchte, d.h. eine eigene Logik implementieren möchte. Und der Hashtable scheint geeigneter für einen parallelen Zugriff, wobei es dafür eben die spezialisierte Klasse "ConcurrentDictionary" gibt.

Link zu diesem Kommentar
Auf anderen Seiten teilen

Archiviert

Dieses Thema ist jetzt archiviert und für weitere Antworten gesperrt.

×
×
  • Neu erstellen...