|
(Moderator)
Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
Delphi 2007 Enterprise
|
Re: (C#) Listensuche optimieren
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")
|