(C#) Listensuche optimieren

[DGL-luke]

Hallo,

ich muss hier ne Suche optimieren. Und zwar habe ich eine Klasse NetNode : AStarNode mit einem public Point Coords.
Ich will jetzt in einer Liste suchen, ob es schon ein Objekt gibt, das diese Koordinaten hat, und das so schnell wie möglich.
Wie macht man das?
Ich hätte übrigens auch schon NetNode.IsSameState(NetNode Node), das genau das überprüft.
Bekomme ich das mit irgend einer Sortierung oder ähnlichem hin? Es gibt doch auch so IComparer-Sachen...
Mein jetziger Code sieht so aus:

Code:

foreach (AStarNode NodeClosed in FClosedList)
                    {
                        if (NodeClosed.IsSameState(NodeSuccessor))
                        {
                            SkipNode = true;
                            break;
                        }
                    }

Und ist wohl nicht besonders performant...

EDIT: was ich gerne verhindern möchte, ist die komplette Datenstruktur umzustellen, also zum Beispiel in ein Array of Point oder ähnliches...

[zappel]

Hallo!

Um die Suche schneller zu gestalten, müsstest du die Listenstruktur schon verändern.
Dazu könntest du mit dynamischen Listen eine Art Matrix erzeugen. In den Elementen der ersten Liste wird die x-Position gespeichert und jeweils eine neue Liste, die die y-Position speichert. Darin wird zusätzlich das Objekt mit den entsprechenden Koordinaten gespeichert.

Kleines Beispiel zum Verdeutlichen:
Du suchst du ein Objekt mit der Position (3,5). Dazu wird zuerst in der ersten Liste nach dem Element mit der Position 3 gesucht. Gibt es ein solches Element wird in der daran angehängten Liste nach dem Element mit der Position 5 gesucht.

Ich hoffe, das ist so verständlich.

[DGL-luke]

jupp.... nachdem ich meine maximalgröße kenne, also einfach ein AStarNode[,] closedLocs = new AstarNode[200,200]();

Und wenn ich das eh mit den Referenzen kombiniere... mal sehen... schade dass dann die generik verloren geht. aber was solls, ist ja ne implementation und kein sample für die codelib.

[zappel]

Du brauchst eigentlich keine feste Größe nehmen. Du kannst eine dynamische Liste nehmen, so dass nur dann ein Element mit der x-Position 3 eingefügt wird, wenn es auch ein Objekt mit entsprechenden Koordinaten gibt. Hast du also die Koordinaten (3,5), (3,1) (2,2), dann gäbe es in der ersten Liste nur zwei Elemente (mit x=5 und x=2) und die daran hängenden Listen hätten auch nur wenige Elemente. Dadurch bleibt das Ganze dynamisch und spart Speicherplatz.

[alzaimar]

Alter Schwede wird das nicht ein wenig gross? Was ist bei Coords von [1000,1000]?

Nimm lieber eine Hashtabelle und erzeuge einen Hashwert aus X,Y . Ich weiss nicht, ob es sowas für C# schon gibt (Hashtabellen). WEnn nicht, und wenn du zu 'faul' bist, dir so eine Klasse selbst zu basteln, dann würde ich die Liste einfach sortieren. Dann kannst Du mit einem "binary search" relativ fix suchen.

Zum Vergleich:
Iteratives Suchen (for each) : O(N)
binary search : O(log n)
hash tabellen : O(1)

Also: Bei einer Verdoppelung der Listenlänge dauert das iterative suchen auch doppelt so lange, binary search dauert dann nur unwesentlich länger, und der hash-tabelle ist es völlig egal, ob die Liste 1, 100 oder 100.000.000.000 Elemente umfasst: Sie findet (oder nicht) das element immer SOFORT (ein paar taktzyklen dauert es natürlich)

Noch eine sehr schnelle Variante: SkipListen. Da diese Struktur sehr schnell ist, dürfte es eventuell schon so eine Klasse geben.

[DGL-luke]

Hm... ne.. ich habe jetzt ein bool[200,200].
Für eine generische A*-Implementation würde ich dir natürlich recht geben udn versuchen, eine effiziente Datenstruktur zu implementieren, aber ich weiss, dass mein grid nie größer als 200|200 wird.

[faux]

Zitat von alzaimar:

Nimm lieber eine Hashtabelle und erzeuge einen Hashwert aus X,Y . Ich weiss nicht, ob es sowas für C# schon gibt (Hashtabellen).

Meinst du vielleicht System.Collections.Hashtable?

Grüße
Faux

[LarsMiddendorf]

Das generische Dictionary<K,V> ist eine Hashtable.

[DGL-luke]

Hm... kann ich da auch irgendwie "doppelt indizieren", indem ich meine offene Liste sowohl nach Kosten als auch nach Koordinaten-Hash indiziere?

Ist das irgendwie machbar? Es müssen ja dann entweder zwei Listen vorliegen mit Referenzen oder man muss nach Priorität sortieren...
Ich kenn mich mit solchen Datenstrukturen leider überhaupt nicht aus...

[LarsMiddendorf]

Das ginge eventuell durch geeignet Wahl des Hashcodes:
Dann würden die Koordinaten gleich als Code genommen.

Code:

public override int GetHashCode()
{
  return (x << 16) | y;
}