Wert im Array schnellstmöglich finden

[yaro]

Hallo Leute,
ich suche den schnellsten Algorithmus, um dieses Problem zu lösen:
ich habe ein Array mit 91 Elementen. Alles Zahlen von 0 bis 1000, nach der Größe sortiert.
Wie kann ich (schnellstmöglich!) ein Element finden, dass meiner Zahl (0-1000) am nächsten ist?

Meine Idee ist, dies mit Intervallschachtelung zu realisieren.
Gibt es vielleicht einen schnelleren Weg?

Gruß, Yaro

[yaro]

Da sich keiner gemeldet hat, habe ich es nun mit Intervallschachtellung gemacht.
Das Array besteht aus 91 Wörtern. Ich brauche ca. 250 Takte mit einem AVR (8bit), um das meiner Zahl nächste Element herauszufischen.
Wer sich für den Algorithmus interessiert, kann gerne fragen, dann poste ich ihn hier rein.

Gruß, Yaro

[SprinterSB]

Nach ca. 7 Arrayzugriffen und ebenso vielen Vergleichen sollte da Ergebnis gefunden sein. Wieso dauert das 250 Takte? Das wären ca. 30 Ticks pro Durchlauf...

http://de.wikipedia.org/wiki/Bin%C3%A4re_Suche

Schneller geht's mit einem inversen Array, das braucht aber dann 1000 Einträge.

Einfach mit dem Suchwert indizieren (nach Test, daß er in den Intervallgrenzen liegt), und du hast den Index 0...90 des nächsten Elements oder das Element selbst, je nach Implementierung.

[yaro]

Ich habe genau dieses Verfahren beutzt, zu dem du den Link gepostet hast. Zitat: "Das hier beschriebene binäre Suchverfahren nennt sich in der Mathematik Intervallschachtelung."

Dass es so "lange" dauert wird klar, wenn man sich damit auseinandersetzt, was der Prozessor tatsächlich macht, und wieviel Takte er für was braucht.
So dauert es z.B. 2T um einen Wert aus dem Arbeitsspeicher in ein Arbeitsregister zu laden (da das Array aus Wörtern besteht also 4t). Dann braucht man noch Zeit für die Vergleiche (auch hier Wörter => 2T), für Sprungbefehle (meißt rjmp 2T), und für allerlei andere interne Aufgaben. (natürlich kommt jedes der eben beschriebenen Elemente meißt mehrmals vor).
Außerdem habe ich nur 91 Elemente und eine Zahl von 0 bis 1000, was bedeutet, dass die Zahl möglicherweise garnicht im Array vorhanden ist. Dies muss berücksichtigt werden, was auch ein wenig Rechenzeit in Anspruch nimmt.

Insofern sind 250 Takte garnicht so viel, wie es klingt.
Hätte ich es mit ASM geschrieben, hätte ich vielleicht einige Takte einsparen können, aber auch nicht wirklich viele.

Gruß, Yaro

[SprinterSB]

Bei einem guten Compiler ist Assembler zu 99% überflüssig.

Aber der schnellste Algorithmus ist es wie gesagt nicht.

Wenn du zN ein Array mit 3 Werten aus [0..10] hast, zB 2,6,7 kannst du ein Array anlegen, daß für jede Eingabe eine nächste Zahl liefert:
2,2,2,2,2(6),6,6,7,7,7,7
wobei das nicht eindeutig ist wie für die 4, die gleichweit von 2 und 6 entfernt ist.

[yaro]

Das problem ist, dass mein Array keine (kaum) wiederholungen hat, und auch einem eher komplizierteren Muster folgt.
Ich kanns ja mal hier reinposten:


{1024,1023,1023,1022,1021,1020,1018,1016,1014,1011 ,1008,1005,1001,997,993,989,984
,979,973,968,962,955,949,942,935,928,920,912,904,8 95,886,877,868,858,848,838,828
,817,806,795,784,772,760,748,736,724,711,698,685,6 71,658,644,630,616,601,587,572
,557,542,527,512,496,480,464,448,432,416,400,383,3 66,350,333,316,299,282,265,247
,230,212,195,177,160,142,124,107,89,71,53,35,17,0}


Gruß, Yaro

[phaidros]

Das mit den Wiederholungen ist doch egal. Die Frage ist nur, ob du Platz für ein Array mit 1025 Zahlen (0 bis 1024) hast.
Wenn ja, reicht ein einziger Zugriff (=2 Takte) !
Ansonsten sieht mir dein Array gar nicht so chaotisch aus. Lässt sich vielleicht einfach durch ein Polynom 2. Grades annähern. Einen Versuch wäre es wert.

[SprinterSB]

Ansonsten sieht mir dein Array gar nicht so chaotisch aus. Lässt sich vielleicht einfach durch ein Polynom 2. Grades annähern. Einen Versuch wäre es wert.

Selbst das würde nicht helfen. Wir wollen nicht das Array modellieren, sondern die Umkehrfunktion dazu. Die wäre in dem Fall wurzlig.

Das inverse Array würde so aussehen:


#include <stdint.h>

// min = 0
// max = 1024

const uint8_t data_inverse[] =
{
90, 90, 90, 90, 90, 90, 90, 90, 90, 89,
89, 89, 89, 89, 89, 89, 89, 89, 89, 89,
89, 89, 89, 89, 89, 89, 88, 88, 88, 88,
88, 88, 88, 88, 88, 88, 88, 88, 88, 88,
88, 88, 88, 88, 87, 87, 87, 87, 87, 87,
87, 87, 87, 87, 87, 87, 87, 87, 87, 87,
87, 87, 86, 86, 86, 86, 86, 86, 86, 86,
86, 86, 86, 86, 86, 86, 86, 86, 86, 86,
85, 85, 85, 85, 85, 85, 85, 85, 85, 85,
85, 85, 85, 85, 85, 85, 85, 85, 84, 84,
84, 84, 84, 84, 84, 84, 84, 84, 84, 84,
84, 84, 84, 84, 84, 84, 83, 83, 83, 83,
83, 83, 83, 83, 83, 83, 83, 83, 83, 83,
83, 83, 83, 82, 82, 82, 82, 82, 82, 82,
82, 82, 82, 82, 82, 82, 82, 82, 82, 82,
82, 81, 81, 81, 81, 81, 81, 81, 81, 81,
81, 81, 81, 81, 81, 81, 81, 81, 81, 80,
80, 80, 80, 80, 80, 80, 80, 80, 80, 80,
80, 80, 80, 80, 80, 80, 79, 79, 79, 79,
79, 79, 79, 79, 79, 79, 79, 79, 79, 79,
79, 79, 79, 79, 78, 78, 78, 78, 78, 78,
78, 78, 78, 78, 78, 78, 78, 78, 78, 78,
78, 77, 77, 77, 77, 77, 77, 77, 77, 77,
77, 77, 77, 77, 77, 77, 77, 77, 77, 76,
76, 76, 76, 76, 76, 76, 76, 76, 76, 76,
76, 76, 76, 76, 76, 76, 75, 75, 75, 75,
75, 75, 75, 75, 75, 75, 75, 75, 75, 75,
75, 75, 75, 75, 74, 74, 74, 74, 74, 74,
74, 74, 74, 74, 74, 74, 74, 74, 74, 74,
74, 73, 73, 73, 73, 73, 73, 73, 73, 73,
73, 73, 73, 73, 73, 73, 73, 73, 72, 72,
72, 72, 72, 72, 72, 72, 72, 72, 72, 72,
72, 72, 72, 72, 72, 71, 71, 71, 71, 71,
71, 71, 71, 71, 71, 71, 71, 71, 71, 71,
71, 71, 70, 70, 70, 70, 70, 70, 70, 70,
70, 70, 70, 70, 70, 70, 70, 70, 69, 69,
69, 69, 69, 69, 69, 69, 69, 69, 69, 69,
69, 69, 69, 69, 69, 68, 68, 68, 68, 68,
68, 68, 68, 68, 68, 68, 68, 68, 68, 68,
68, 68, 67, 67, 67, 67, 67, 67, 67, 67,
67, 67, 67, 67, 67, 67, 67, 67, 66, 66,
66, 66, 66, 66, 66, 66, 66, 66, 66, 66,
66, 66, 66, 66, 65, 65, 65, 65, 65, 65,
65, 65, 65, 65, 65, 65, 65, 65, 65, 65,
64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
64, 64, 64, 64, 64, 64, 63, 63, 63, 63,
63, 63, 63, 63, 63, 63, 63, 63, 63, 63,
63, 63, 62, 62, 62, 62, 62, 62, 62, 62,
62, 62, 62, 62, 62, 62, 62, 62, 61, 61,
61, 61, 61, 61, 61, 61, 61, 61, 61, 61,
61, 61, 61, 61, 60, 60, 60, 60, 60, 60,
60, 60, 60, 60, 60, 60, 60, 60, 60, 60,
59, 59, 59, 59, 59, 59, 59, 59, 59, 59,
59, 59, 59, 59, 59, 58, 58, 58, 58, 58,
58, 58, 58, 58, 58, 58, 58, 58, 58, 58,
57, 57, 57, 57, 57, 57, 57, 57, 57, 57,
57, 57, 57, 57, 57, 56, 56, 56, 56, 56,
56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
55, 55, 55, 55, 54, 54, 54, 54, 54, 54,
54, 54, 54, 54, 54, 54, 54, 54, 54, 53,
53, 53, 53, 53, 53, 53, 53, 53, 53, 53,
53, 53, 53, 52, 52, 52, 52, 52, 52, 52,
52, 52, 52, 52, 52, 52, 52, 51, 51, 51,
51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
51, 50, 50, 50, 50, 50, 50, 50, 50, 50,
50, 50, 50, 50, 50, 49, 49, 49, 49, 49,
49, 49, 49, 49, 49, 49, 49, 49, 48, 48,
48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
48, 48, 47, 47, 47, 47, 47, 47, 47, 47,
47, 47, 47, 47, 47, 46, 46, 46, 46, 46,
46, 46, 46, 46, 46, 46, 46, 46, 45, 45,
45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
44, 44, 44, 44, 44, 44, 44, 44, 44, 44,
44, 44, 43, 43, 43, 43, 43, 43, 43, 43,
43, 43, 43, 43, 42, 42, 42, 42, 42, 42,
42, 42, 42, 42, 42, 42, 41, 41, 41, 41,
41, 41, 41, 41, 41, 41, 41, 41, 40, 40,
40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
39, 39, 39, 39, 39, 39, 39, 39, 39, 39,
39, 38, 38, 38, 38, 38, 38, 38, 38, 38,
38, 38, 37, 37, 37, 37, 37, 37, 37, 37,
37, 37, 37, 36, 36, 36, 36, 36, 36, 36,
36, 36, 36, 35, 35, 35, 35, 35, 35, 35,
35, 35, 35, 34, 34, 34, 34, 34, 34, 34,
34, 34, 34, 33, 33, 33, 33, 33, 33, 33,
33, 33, 33, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 31, 31, 31, 31, 31, 31, 31,
31, 31, 30, 30, 30, 30, 30, 30, 30, 30,
30, 29, 29, 29, 29, 29, 29, 29, 29, 29,
28, 28, 28, 28, 28, 28, 28, 28, 27, 27,
27, 27, 27, 27, 27, 27, 26, 26, 26, 26,
26, 26, 26, 26, 25, 25, 25, 25, 25, 25,
25, 25, 24, 24, 24, 24, 24, 24, 24, 23,
23, 23, 23, 23, 23, 23, 22, 22, 22, 22,
22, 22, 21, 21, 21, 21, 21, 21, 21, 20,
20, 20, 20, 20, 20, 19, 19, 19, 19, 19,
19, 18, 18, 18, 18, 18, 17, 17, 17, 17,
17, 17, 16, 16, 16, 16, 16, 15, 15, 15,
15, 14, 14, 14, 14, 13, 13, 13, 13, 12,
12, 12, 12, 11, 11, 11, 11, 10, 10, 10,
9, 9, 9, 8, 8, 7, 7, 6, 6, 5,
5, 4, 3, 1, 0
};



Zu jedem Wert in 0...1024 gibt es den Index in das Array der Originaldaten, zu dem der Wert kleinsten Abstand hat.

[yaro]

Hmm stimmt! Jetzt verstehe ich die Idee =)
Danke für den Tipp!
Ich muss mal schauen, wieviel Platz ich später noch übrig haben werde( habe insgesammt 2kb intern). Und wäge dann ab, ob die Zeitersparniss sich Lohnt.

Die Funktion im Array ist übrigens cos(x)*1024. Ich brauche das, um Arccos(x*1024) zu berechnen.
Das Problem ist, dass math.h acos(x) nur im Bogenmaß hat, und sehr lange braucht, da es mit fließkommazahlen rechnet (entsprechend ist aber auch die Genauigkeit). Die Umrechnung in Winkelmaß kommt auch noch hinzu... (eine normale float*float multiplikation dauert ca 130Takte).
das *1024 ist dazu da, eine genauigkeit von 1° zu sichern. Ich rechne nur mit 8 und 16 bit, da es viel schneller geht.

So ähnlich, wie ich das Program zu acos(x) hier geschreiben habe (es ist,wenn keine Nachkommastellen braucht, ca 8 so schnell wie in math.h), habe ich auch die Funktion sqrt(x) umgeschrieben, um mit Verzicht auf die Nachkommastellen Zeit zu gewinnen(ca 3 mal schneller als math.h). Es wird eine Wurzel aus einer 16bit Zahl gezogen, das ergebniss ist dann auf 8bit gerundet. Das Programm funktioniert auch mit Intervallschachtelung, nur werden die Werte nicht in einem Array gespeichert, sondern immer neu berechnet (die Mega-Familie verfügt über hardware-Multiplikation, was es sehr schnell macht). Dies hat den Vorteil, dass man nicht mal zusätzlichen Speicherplatz braucht.

Gruß, Yaro

[SprinterSB]

Hmm stimmt! Jetzt verstehe ich die Idee =)
Danke für den Tipp!
Ich muss mal schauen, wieviel Platz ich später noch übrig haben werde( habe insgesammt 2kb intern). Und wäge dann ab, ob die Zeitersparniss sich Lohnt.

Das passt alles nicht zusammen. Unten schreibst du was von ATmega.
ATmega haben doch mehr als 2kB Programmspeicher. So eine Tabelle legt man natürlich nicht ins RAM sondern ins Flash, denn sie enthält nur Konstanten, die zur Laufzeit nicht geändert werden müssen und alle zur Compilezeit feststehen.


Die Funktion im Array ist übrigens cos(x)*1024. Ich brauche das, um Arccos(x*1024) zu berechnen.
Das Problem ist, dass math.h acos(x) nur im Bogenmaß hat, und sehr lange braucht, da es mit fließkommazahlen rechnet (entsprechend ist aber auch die Genauigkeit). Die Umrechnung in Winkelmaß kommt auch noch hinzu... (eine normale float*float multiplikation dauert ca 130Takte).
das *1024 ist dazu da, eine genauigkeit von 1° zu sichern. Ich rechne nur mit 8 und 16 bit, da es viel schneller geht.

Klaro, float auf nem AVR-Hänfling ist Overkill.


So ähnlich, wie ich das Program zu acos(x) hier geschreiben habe (es ist,wenn keine Nachkommastellen braucht, ca 8 so schnell wie in math.h), habe ich auch die Funktion sqrt(x) umgeschrieben, um mit Verzicht auf die Nachkommastellen Zeit zu gewinnen(ca 3 mal schneller als math.h). Es wird eine Wurzel aus einer 16bit Zahl gezogen, das ergebniss ist dann auf 8bit gerundet. Das Programm funktioniert auch mit Intervallschachtelung, nur werden die Werte nicht in einem Array gespeichert, sondern immer neu berechnet (die Mega-Familie verfügt über hardware-Multiplikation, was es sehr schnell macht). Dies hat den Vorteil, dass man nicht mal zusätzlichen Speicherplatz braucht.

Also ich kenn deinen Code ja nicht, aber wenn deine Wurzel-Berechnung nur 3x schneller ist als ne Lib-Funktion, dann machst du was grundsätzliches falsch. Entweder mit der Zeitmessung, mit deinem Code, deinem Algorithmus, oder mit deinem Compiler. Oder verwendest du etwa BASCOM?

[yaro]

Ich verwende einen ATmega32. An den Programm-Flash habe ich ehrlich gesagt garnicht gedacht (und wusste bis jetzt auch garnicht, wie man Variablen dort abspeichern kann). Habe nämlich C zuerst mit einem PC gelernt, und dort stellt sich diese Frage nicht. Ich weiß zwar, wie man das in ASM macht, dachte aber, dass der C-Compiler alle Variablen (und Konstanten) zuerst in den Flash kopiert, und dann mit ihnen arbeitet. Aber nun werde ich wohl wirklich einfacheine Tabelle anlegen, und aus ihr rauslesen. Werde wohl kaum alle 32kb Flash brauchen...

Der code für sqrt sieht folgendermaßen aus (in C):




uint8_t squareroot(uint16_t value){
uint8_t pos = 128, posdiff = 64;
uint16_t squarepos = 128*128;

while(posdiff){ //Intervallschachtellung
if(squarepos < value){
pos += posdiff;
}else if(squarepos > value){
pos -= posdiff;
}else{
return pos;
break;
}
posdiff /= 2;
squarepos = pos*pos;
}

if(squarepos < value){ //Annäherung der Variable an eine ganze Zahl
if((int)((value - squarepos) - ((pos+1)*(pos+1) - value)) > 0){
return ++pos;
}else{
return pos;
}
}else if(squarepos > value){
if((int)((squarepos - value) - (value - (pos-1)*(pos-1))) > 0){
return --pos;
}else{
return pos;
}
}else{
return pos;
}
}


Die Optimiertung ist auf Stufe s.
Für eine Wurzel brauche ich ca.250T. Math.h braucht im Durchschnitt 820.
Hättest du einen Verbesserungsvorschlag für die Funktion?

Gruß, Yaro

[mare_crisium]

Hallo yaro und SprinterSB,

ihr habt zwar schon eine praktische Lösung gefunden, es gibt aber noch einen Weg nach Rom (oder ins RAM?) ;-) ! Die Beschreibung ist ein bisschen holprig, ich hoffe aber, dass die Beispiele das wieder ausbügeln.

Ciao,

mare_crisium

Edit: Anhang gelöscht wg. Upload-Limit

[yaro]

Ja... das mit den vielen Wegen ist wohl wahr =)
Am interessantesten finde ich das mit der Berechnung der nächstfolgenden RAM-Adresse.

Gruß, Yaro

[Richard]

Hallo yaro und SprinterSB,

ihr habt zwar schon eine praktische Lösung gefunden, es gibt aber noch einen Weg nach Rom (oder ins RAM?) ;-) ! Die Beschreibung ist ein bisschen holprig, ich hoffe aber, dass die Beispiele das wieder ausbügeln.

Ciao,

mare_crisium

Moin moin.

Etwas Holprig ist guuut... Aber wenn die Zahlen im Arry vorher feststehen,
kann man diese doch auch vor dem Abspeichern der Größe nach sortieren.

Bei der Abfrage fängt man in der Mitte vom Arry an und prüft auf
gleich, >, < als der Wert der Speicherstelle. Ist die gesuchte Zahl
größer, halbeirt man den oberen Rest des Arrys. Ist der Wert kleiner
halbiert man die untere Hälfte vom Arry und wiederholt das ganze bis
die Zahl = dem Arry Inhalt ist. Es ist lange her (noch unter Dos und
Quik-Basic), wenn ich es richtig in Erinnerung habe soll egal wie groß
das Arry b.z.w. die Datei ist, nach spätestens 11 Zugriffen der gesuchte
Wert gefunden sein???? Ich hatte seinerzeit damit Random Dateien
durchsucht aber fragt mich nicht wozu ich das seinerzeit gebraucht
habe. :-)

Grüße Richard

[yaro]

Das ist genau das, was ich gemacht habe =) (es nennt sich Intervallschachtellung)
Aber ganz so einfach, wie du e bschrieben hast, ist es nicht, denn eine Vorkehrung muss man noch machen: wenn der Wert nicht im array drin ist, muss das auch erkannt werden und dann der ihm nähste wert genommen werden.

Gruß, Yaro