Druckbare Version
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
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
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.
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
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.
Das problem ist, dass mein Array keine (kaum) wiederholungen hat, und auch einem eher komplizierteren Muster folgt.
Ich kanns ja mal hier reinposten:
Gruß, YaroCode:{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,895,886,877,868,858,848,838,828
,817,806,795,784,772,760,748,736,724,711,698,685,671,658,644,630,616,601,587,572
,557,542,527,512,496,480,464,448,432,416,400,383,366,350,333,316,299,282,265,247
,230,212,195,177,160,142,124,107,89,71,53,35,17,0}
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.
Selbst das würde nicht helfen. Wir wollen nicht das Array modellieren, sondern die Umkehrfunktion dazu. Die wäre in dem Fall wurzlig.Zitat:
Zitat von phaidros
Das inverse Array würde so aussehen:
Zu jedem Wert in 0...1024 gibt es den Index in das Array der Originaldaten, zu dem der Wert kleinsten Abstand hat.Code:#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
};
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
Das passt alles nicht zusammen. Unten schreibst du was von ATmega.Zitat:
Zitat von yaro
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.
Klaro, float auf nem AVR-Hänfling ist Overkill.Zitat:
Zitat von yaro
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?Zitat:
Zitat von yaro