AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

(C#) Listensuche optimieren

Ein Thema von DGL-luke · begonnen am 6. Jan 2006 · letzter Beitrag vom 7. Jan 2006
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von DGL-luke
DGL-luke

Registriert seit: 1. Apr 2005
Ort: Bad Tölz
4.149 Beiträge
 
Delphi 2006 Professional
 
#1

(C#) Listensuche optimieren

  Alt 6. Jan 2006, 14:45
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...
Lukas Erlacher
Suche Grafiktablett. Spenden/Gebrauchtangebote willkommen.
Gotteskrieger gesucht!
For it is the chief characteristic of the religion of science that it works. - Isaac Asimov, Foundation I, Buch 1
  Mit Zitat antworten Zitat
zappel

Registriert seit: 30. Jan 2004
65 Beiträge
 
Delphi 2005 Personal
 
#2

Re: (C#) Listensuche optimieren

  Alt 6. Jan 2006, 16:00
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.
  Mit Zitat antworten Zitat
Benutzerbild von DGL-luke
DGL-luke

Registriert seit: 1. Apr 2005
Ort: Bad Tölz
4.149 Beiträge
 
Delphi 2006 Professional
 
#3

Re: (C#) Listensuche optimieren

  Alt 6. Jan 2006, 16:03
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.
Lukas Erlacher
Suche Grafiktablett. Spenden/Gebrauchtangebote willkommen.
Gotteskrieger gesucht!
For it is the chief characteristic of the religion of science that it works. - Isaac Asimov, Foundation I, Buch 1
  Mit Zitat antworten Zitat
zappel

Registriert seit: 30. Jan 2004
65 Beiträge
 
Delphi 2005 Personal
 
#4

Re: (C#) Listensuche optimieren

  Alt 6. Jan 2006, 16:09
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.
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#5

Re: (C#) Listensuche optimieren

  Alt 6. Jan 2006, 16:20
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von DGL-luke
DGL-luke

Registriert seit: 1. Apr 2005
Ort: Bad Tölz
4.149 Beiträge
 
Delphi 2006 Professional
 
#6

Re: (C#) Listensuche optimieren

  Alt 6. Jan 2006, 17:51
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.
Lukas Erlacher
Suche Grafiktablett. Spenden/Gebrauchtangebote willkommen.
Gotteskrieger gesucht!
For it is the chief characteristic of the religion of science that it works. - Isaac Asimov, Foundation I, Buch 1
  Mit Zitat antworten Zitat
Benutzerbild von faux
faux

Registriert seit: 18. Apr 2004
Ort: Linz
2.044 Beiträge
 
Turbo Delphi für Win32
 
#7

Re: (C#) Listensuche optimieren

  Alt 6. Jan 2006, 18:00
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
Faux Manuel
Wer weiß, dass er nichts weiß, weiß mehr, als der der nicht weiß, dass er nichts weiß.
GoTrillian
  Mit Zitat antworten Zitat
LarsMiddendorf

Registriert seit: 4. Sep 2003
Ort: Hemer
104 Beiträge
 
Turbo Delphi für Win32
 
#8

Re: (C#) Listensuche optimieren

  Alt 6. Jan 2006, 18:51
Das generische Dictionary<K,V> ist eine Hashtable.
  Mit Zitat antworten Zitat
Benutzerbild von DGL-luke
DGL-luke

Registriert seit: 1. Apr 2005
Ort: Bad Tölz
4.149 Beiträge
 
Delphi 2006 Professional
 
#9

Re: (C#) Listensuche optimieren

  Alt 6. Jan 2006, 19:05
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...
Lukas Erlacher
Suche Grafiktablett. Spenden/Gebrauchtangebote willkommen.
Gotteskrieger gesucht!
For it is the chief characteristic of the religion of science that it works. - Isaac Asimov, Foundation I, Buch 1
  Mit Zitat antworten Zitat
LarsMiddendorf

Registriert seit: 4. Sep 2003
Ort: Hemer
104 Beiträge
 
Turbo Delphi für Win32
 
#10

Re: (C#) Listensuche optimieren

  Alt 6. Jan 2006, 19:30
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;
}
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 05:52 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf