Seite 1 von 1
Such-/Vergleich-Algorithmus gesucht
Verfasst: 05.03.2008 17:52
von spider84
Gegeben ist ein Array(100) mit verschiedenen Helligkeitswerten als c.
Beispiel: meinArray(65)=33 -> Pixel 65 hat Helligkeit 33.
Nun habe ich in einer anderen Variable einen Wert wie 55 und suche, welcher Array-Wert am nähesten ist. Ich suche quasi das Pixel zu meiner Helligkeit.
Wenn jemand einen guten Suchalgorithmus für sowas kennt, dann her damit!
Verfasst: 05.03.2008 17:57
von STARGÅTE
Code: Alles auswählen
minAbstand = #MAXLONG
For n = 0 To 100
Abstand = Abs(meinArray(n)-meinWert)
If Abstand < minAbstand :
minAbstand = Abstand
ArrayFeld = n
EndIf
Next
Das vergleich jeden ArrayFeldWert mit deinem Wert und merkt sich den kleinsten Abstand. und am ende hast du dann dein ArrayFeld
Verfasst: 05.03.2008 18:05
von spider84
hmm, das hat einen hohen Aufwand. danke schonmal.
vlt überlege ich mir noch ein verfahren dass mir die liste sortiert, aber dafür muss es wohl ein 2dimensionales array werden damit die indizes nicht verloren gehen.
Verfasst: 05.03.2008 18:38
von NicTheQuick
Warum ein hoher Aufwand?
Die Laufzeit ist O(n).
Aber wenn die Werte in deinem Array sortiert sind, kannst du natürlich durch
einen angepassten QuickSort den gesuchten Wert mit O(log(n)) finden.
Verfasst: 05.03.2008 18:48
von Kaeru Gaman
was rein garnichts bringen würde, weil er schließlich die sortierung nur für diese suche durchführen würde.
und sortierung + optimierte suche dauert bestimmt mindestens so lange wie normale suche
Verfasst: 06.03.2008 11:39
von Froggerprogger
Aber wenn die Werte in deinem Array sortiert sind
Nic meinte ja den Fall, dass die Werte schon sortiert vorliegen. Dann kann man das Verfahren auf log(n) Suchschritte beschleunigen, indem man z.B. die binäre Suche leicht modifiziert.
Das Sortieren dauert definitiv schon länger als die lineare Suche wie in stargates Beispiel.
Verfasst: 06.03.2008 14:43
von spider84
ah, da hatten wohl noch mehr leute hier informatik erstes semester.*würg*
die sache ist, dass ich für mehrere pixel die helligkeit mit dem array abgleiche - somit hätt zwar mit quicksort im besten fall O(log n) zusätzlichen aufwand zum suchen, aber 100*n ist weniger als 100*(log n).
nur so nebenbei: gibts für trackbar ein change-event bzw. irgendwelche anderen?
Verfasst: 06.03.2008 15:21
von Froggerprogger
100*n > 100*(log n) für alle n>0
Aber iss klar, was du meinst.
[edit]
Folgender Code erzeugt bei mir (unter Linux) bei jeder Änderung des Trackbars ein #PB_Event_Gadget - Event.
Code: Alles auswählen
If OpenWindow(0, 0, 0, 300, 40, "TrackBarGadget", #PB_Window_SystemMenu | #PB_Window_ScreenCentered) And CreateGadgetList(WindowID(0))
TrackBarGadget(1, 5, 5, 290, 20, 0, 10000)
Repeat
event = WaitWindowEvent()
If event = #PB_Event_Gadget And EventGadget() = 1
Debug "Moved"
EndIf
Until event = #PB_Event_CloseWindow
EndIf
[/edit]
Verfasst: 06.03.2008 16:17
von ZeHa
Diese Art zu suchen, also das ähnlichste Element, nennt sich "Nearest Neighbour", vielleicht kannst Du mit diesem Stichwort ja irgendwo noch andere gute Ansätze finden.
Verfasst: 06.03.2008 19:51
von AND51
STARGÅTE hat geschrieben:Code: Alles auswählen
minAbstand = #MAXLONG
For n = 0 To 100
Abstand = Abs(meinArray(n)-meinWert)
If Abstand < minAbstand :
minAbstand = Abstand
ArrayFeld = n
EndIf
Next
Das vergleich jeden ArrayFeldWert mit deinem Wert und merkt sich den kleinsten Abstand. und am ende hast du dann dein ArrayFeld
Nicht vergessen: Wenn der Abstand sowieso =1 (minimalster abstand) oder <1 (identisch) ist, dann die SUche mit
Break abbrechen, um noch mal eine ordentliche Portion Zeit zu sparen!!