Sida 1 av 2
Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 16:58:03
av Korken
Godagens!
Jag sitter och arbetar på en lookup table som jag funderar på hur man ska söka i.
Det jag har funderat på är att hoppa till mitten av tabellen och läsa värdet där, om värdet jag söker är mindre så hoppa till mitten av den "lägre hälften" eller om det är större hoppa till mitten av den "högre hälften" och sen köra detta tills man kommit fram till det sökta värdet.
Denna metod fungerar ganska bra, men finns det några andra bra sökalgoritmer som folk rekommenderar?
Tack på förhand!
Re: Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 17:12:36
av Icecap
Hur menar du?
Varför skulle man leta upp i en tabell, grejen är ju just att man kan indexera direkt eller hur?
Eller är det så att du har en tabell med 2 värden per inlägg och ska hitta närmsta?
Jag har faktisk aldrig skulle leta upp något i tabell på detta vis och jag har ändå programmerat sedan 1982.
Re: Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 17:26:48
av Korken
Då ska jag ska förtydliga.

Det är egentligen nog inte en lookup table, utan snarare bara en tabell med massa data.
Jag har tabellen för att göra fixed point arctangens.
Såhär ser min tabell ut (fast enbart fixed point värdena):
arctan_table_1.png
Och såhär blir tabellen sen:
arctan_table_2.png
Så om jag vill ha, säg, arctan(12.36753) så måste jag söka mig fram till det värde som är närmast i tabellen.
Så jag har en array med data i flash som jag ska söka mig genom.
Hoppas det förtydligade.

Re: Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 17:45:17
av sodjan
OK, du vill alltså ha en arctan-funktion med hjälp av en tan-tabell ?
Du kan även studera en del exempel "out there". t .ex
http://www.dattalo.com/technical/softwa ... arctan.asm.
(Du har inte heller angivit vilken processor arkitektur det handlar om...)
Re: Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 17:49:25
av Korken
Tackar, de va ett spännande sätt att göra det på.
>> (Du har inte heller angivit vilken processor arkitektur det handlar om...)
De har du så rätt i!
Jag använder en Cortex-M3 processor (NXP LPC1769).
Re: Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 17:52:07
av sodjan
Jahaja, där gör man det kanske inte riktigt på samma sätt
som på en standard AVR eller PIC. Den har väl helt andra
resurser...
Re: Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 21:41:43
av Korken
Sant så sant

Anledningen att jag frågar är att jag behöver den att vara snabb.
Vill helst att den ska ta 100-150 klockcykler som max, så ska se om det går att hitta en snabbare lösning än min. (vilket det oftast finns)
Re: Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 22:42:54
av monstrum
Så som jag själv implementerat egna look-up tabeller med linjärinterpolering så vet man redan vid kompilering hur tabellen ser ut. Argumentet är helt linjärt proportionellt i förhållande till index, dvs man kan använda en enkel faktor och multiplicera argumentet med denna för att direkt hamna på rätt index i tabellen.
I ditt fall verkar du ha en tabell för tan, och sedan göra en bakvänd lookup för att beräkna arctan. Om du inte har platsbrist så är det mycket effektivare att ha en egen tabell för arctan direkt, även om den eventuellt behöver fler index för att få samma precision (ifall argumentet skall vara linjärt).
Re: Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 23:08:56
av twse
I ditt fall verkar du ha en tabell för tan, och sedan göra en bakvänd lookup för att beräkna arctan. Om du inte har platsbrist så är det mycket effektivare att ha en egen tabell för arctan direkt, även om den eventuellt behöver fler index för att få samma precision (ifall argumentet skall vara linjärt).
Ja, absolut, men kanske inte i det här fallet. tan(v) = sin(v)/cos(v), så tan(v) går mot oändligheten när v går mot pi/2. Vi behöver förstås inte räkna med oändligheten, men över en linjär skala för v kommer tan(v) att få en väldigt skev spridning. tan(v) går förstås bra att göra en direkt lookup-tabell för, men inte arctan(x), där skulle man behöva en väldigt stor linjär tabell för att få en tillräcklig noggrannhet runt v = pi / 2.
Men det går eventuellt att göra enklare, beror på tillämpningen! När man räknar arctan(x) så är det egentligen arctan2(x,y) man vill ha, som ger en vinkel "hela varvet runt", med rätt tecken och utan att behöva bry sig om fallet x = 0. Du kanske ska göra en arctan2-tabell istället, där du normaliserar x och y (dividerar med det högsta absolutvärdet) och slår upp vinkeln? Det funkar från v = 0 till pi/4, resten får man spegla.
Re: Effektiv "lookup table"-sökalgoritm
Postat: 12 februari 2011, 23:30:38
av monstrum
Man måste såklart inte ha en linjär tabell. Steglängden kan ju t.ex. dubbleras mellan varje element i tabellen och börja väldigt liten. Det går fortfarande snabbt att beräkna indexet (bitskift).
Re: Effektiv "lookup table"-sökalgoritm
Postat: 14 februari 2011, 08:44:26
av Korken
>> I ditt fall verkar du ha en tabell för tan, och sedan göra en bakvänd lookup för att beräkna arctan.
Precis så jag gör! Jag gör så för att jag vill ha en viss precision och det går snabbt även om jag ökar storleken på tabellen (ca 200 klockcykler nu när tabellen har 180 element).
Jag ska kolla på arctan2 funktionen och se om den förenklar mitt program.
Edit: Sitter och optimerar koden, och har ramlar över en konstig error.
(alla variabler är pekare)
Kod: Markera allt
ptr = (start + end)/2; ger error: invalid operands to binary + (have ‘int *’ and ‘int *’) men,
ptr = start + (end - start)/2; fungerar
Hur kan det bli så?
Re: Effektiv "lookup table"-sökalgoritm
Postat: 14 februari 2011, 10:42:17
av dangraf
vad ska du använda uträkningen till?
Funderar på om det är till en regler-loop eftersom det behöver ske så väldigt snabbt. I många fall kan man linjärisera med hjälp av taylerutveckling (ett exempel
http://www.mecca.org/~halfacre/MATH/taylorseries.htm).
när man kör ett mattematiskt uttryck så tar det alltid lika lång tid vilket det inte alltid gör om man ska leta i en tabell. (såvida man t.ex inte ska dividera med 0)
t.ex kan man beräkna sin, cos mm som en funktion: arctan(x) = x- (x^3)/3 +(x^5)/5... x^n går att beräkna på ett effektivt sätt i C men för tillfället kommer jag inte ihåg hur. Kanske värt att kolla upp om detta skulle kunna vara en alternativ lösning?
Re: Effektiv "lookup table"-sökalgoritm
Postat: 14 februari 2011, 11:20:41
av monstrum
Att det tar olika lång tid i en tabell man ska leta i spelar ju mindre roll. Det är ju maxtiden som är intressant.
Tricket ifall man vill att det ska gå fort är att ha en tabell man inte behöver leta i, utan där man "vet" var man hittar svaret.
Re: Effektiv "lookup table"-sökalgoritm
Postat: 14 februari 2011, 11:25:02
av jesse
Om lookupvärdet går mot oändligheten så kanske du kan använda 1/x istället som sökvärde?
Och om värdet går mot noll i andra änden så kan du dela upp det i två tabeller, varav den ena är linjärt proportionell och den andra inverterad (1/x).
Re: Effektiv "lookup table"-sökalgoritm
Postat: 14 februari 2011, 12:10:59
av twse
Korken skrev:Jag ska kolla på arctan2 funktionen och se om den förenklar mitt program.

Vad sägs om följande lösning?
Kod: Markera allt
#define MY_ARCTAN_TABLE_SIZE ...
#define MY_ARCTAN_PI ...
/* Värden från 0 grader till 45 grader, index är (MY_ARCTAN_TABLE_SIZE * y)/x för y < x. */
int my_arctan_table[MY_ARCTAN_TABLE_SIZE] = {...};
int my_arctan2(int x, int y)
{
if (x > 0) {
if (y > 0) {
return my_arctan2_bothpositive(x, y);
} else if (y == 0) {
return 0;
} else {
return 2 * MY_ARCTAN_PI - my_arctan2_bothpositive(x, -y);
}
} else if (x == 0) {
if (y > 0) {
return MY_ARCTAN_PI / 2;
} else if (y == 0) {
return 0;
} else {
return MY_ARCTAN_PI + MY_ARCTAN_PI / 2;
}
} else {
if (y > 0) {
return MY_ARCTAN_PI - my_arctan2_bothpositive(-x, y);
} else if (y == 0) {
return MY_ARCTAN_PI;
} else {
return MY_ARCTAN_PI + my_arctan2_bothpositive(-x, -y);
}
}
}
int my_arctan2_bothpositive(int x, int y)
{
if (y < x) {
return my_arctan_table[(MY_ARCTAN_TABLE_SIZE * y) / x];
} else if (y == x) {
return MY_ARCTAN_PI / 4;
} else {
return MY_ARCTAN_PI / 2 - my_arctan_table[(MY_ARCTAN_TABLE_SIZE * x) / y];
}
}
Skissade ihop det spontant nu, bäst att testa i datorn först! Fördelen med denna metod är att du bara behöver ha intervallet från 0 till 45 grader i tabellen, där spridningen är någorlunda linjär.
Har du inte x och y utan bara en kvot så kan du ju anropa my_arctan2(1, kvot), då blir y / x = kvot / 1 = kvot.
Edit: Sitter och optimerar koden, och har ramlar över en konstig error.
(alla variabler är pekare)
Kod: Markera allt
ptr = (start + end)/2; ger error: invalid operands to binary + (have ‘int *’ and ‘int *’) men,
ptr = start + (end - start)/2; fungerar
Hur kan det bli så?
Du kan inte plussa ihop två pekare! Om kompilatorn inte varnade skulle du få en pekare som är åt tjottaheitti. Om (start = base + index_start) och (end = base + index_end) så är (start + end) lika med (base + base + index_start + index_end) - du ser felet?
Okej, du dividerar resultatet med två. Men då är problemet att du kan hamna mellan två index, beroende på datatypens storlek. Gör så här istället: ptr = base + (index_start + index_end) / 2. Helst ska du räkna med index så långt som möjligt och blanda in tabellpekaren först när du läser ur minnet.