Such-/Vergleich-Algorithmus gesucht

[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!

[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

[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.

[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.

[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

[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.

[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?

[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]

[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.

[AND51]

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!!