Forum » Programiranje » funkcijska aproksimacija grafa
funkcijska aproksimacija grafa
Vesoljc ::
moje matematicno znanje je tukaj "rahlo" omejeno, pa me zanima do kake stopnje bi se dalo aproksimirat nek poljuben graf sestavljen iz recimo 16 tock, ki so povezane zaporedno ter linearno, pac z daljicami AB,BC,CD,DE,...
vhod so, kot receno pari x,y koordinat, izhod pa funkcija v stilu: y = f( x );
za samo grajenje funkcije imam naceloma zadosti casa, izracun pa bi moral biti cim hitrejsi (recimo samo z uporabo osnovne aritmetike, ze kotne funkcije so problematicne).
kaksne ideje? :)
vhod so, kot receno pari x,y koordinat, izhod pa funkcija v stilu: y = f( x );
za samo grajenje funkcije imam naceloma zadosti casa, izracun pa bi moral biti cim hitrejsi (recimo samo z uporabo osnovne aritmetike, ze kotne funkcije so problematicne).
kaksne ideje? :)
Abnormal behavior of abnormal brain makes me normal...
- spremenil: Vesoljc ()
technolog ::
Če imaš recimo N točk, jih lahko čisto točno zapišeš kot polinom N-te stopnje.
Če ne, potem se stvar zakomplicira... Lahko delaš po metodi najmanjših kvadratov (regresijska premica)...
Na googlu je ogromno napisanega o tem.
Če ne, potem se stvar zakomplicira... Lahko delaš po metodi najmanjših kvadratov (regresijska premica)...
Na googlu je ogromno napisanega o tem.
Senitel ::
Polinom čez N točk dvomim, da bo rešitev, če ima zaporedje daljic (sicer boš zadel točke, falil pa vse ostalo).
Kaj pa dejansko rabiš? Samo y=f(x) al kakšen integral (ploščino pod grafom)?
Kaj pa dejansko rabiš? Samo y=f(x) al kakšen integral (ploščino pod grafom)?
sherman ::
Ti imaš odsekoma linearno funkcijo in bi jo rad aproksimiral z nečim? Zakaj pač med točkami ne interpoliraš z linearno premico? Izračun potem zahteva nekaj odločitev in par osnovnih aritmetičnih operacij. Ali je to prepočasno?
Senitel ::
Varianta bi bila, da preračuna koeficiente premic in potem izbere ustrezen interval glede na x. Ampak po mojem noče if-ov? 
Vesoljc ::
Ti imaš odsekoma linearno funkcijo in bi jo rad aproksimiral z nečim? Zakaj pač med točkami ne interpoliraš z linearno premico? Izračun potem zahteva nekaj odločitev in par osnovnih aritmetičnih operacij. Ali je to prepočasno?
tako zaenkrat tudi deluje. prvi korak je pac poiskat pravi odsek (for & compare), drugi pa uporabit linearno interpolacijo. prepocasno? ja recimo da je, ni pa samo to. drugi faktor je memory (tako usage kot bandwidth).
Senitel ma tudi prav, if-om bi se rad izognil na celi crti...
Symbolic regression
good stuff!
Abnormal behavior of abnormal brain makes me normal...
Zgodovina sprememb…
- spremenil: Vesoljc ()
Vesoljc ::
Kje je počasnost?
Nimaš dovolj memorya za teh par točk?
jah, imam, bi pa porabo rad zmanjsal... 256KB hitro nafilas ;)
problem pocasnosti je pa sicer rahlo sirsi, ampak tale interpolacija nekako najbolj ven skace...
bolj kot ne gledam "future" variante, kako zadevo optimizirat. prvi major step je reorganizacija podatkov iz AoS v SoA ter prepis kode z uporabo simd-a. ampak zaenkrat je to prevelik zalogaj, zato malo gledam za kakimi bliznjicami :)
Bo smiselno, če predlagam lookup tabelo, ali imaš prevelik range?
nope, lookup ne gre
Abnormal behavior of abnormal brain makes me normal...
Zgodovina sprememb…
- spremenil: Vesoljc ()
technolog ::
Če imaš posortiran seznam x-koordinat točk, lahko z binarnim iskanjem v O(lg n) (kar je super hitro) poveš na kateri interval pade točka. Preostane ti samo še to, da pogledaš levega in desnega soseda in interpoliraš po formuli.
Ne razumem pa kako 256 kilo hitro nafilaš... To je vendar 65000 32-bit integerjev oz. 30K točk...
Ne razumem pa kako 256 kilo hitro nafilaš... To je vendar 65000 32-bit integerjev oz. 30K točk...
Zgodovina sprememb…
- spremenil: technolog ()
Vesoljc ::
Če imaš posortiran seznam x-koordinat točk, lahko z binarnim iskanjem v O(lg n) (kar je super hitro) poveš na kateri interval pade točka. Preostane ti samo še to, da pogledaš levega in desnega soseda in interpoliraš po formuli.
Ne razumem pa kako 256 kilo hitro nafilaš... To je vendar 65000 32-bit integerjev oz. 30K točk...
seznam tock je posortiran, ampak je vecinoma precej kratek, max je kot receno 16, povprecje pa bolj 8 recimo. bom probal se z binarnim iskanjem ce bo kaka prakticna razlika...
256 kilo je pa v biti moj celoten memory, ki je na voljo. za code, stack ter "heap".
je pa ta interpolator spisan kot template, tako da je Y v vecini primerov ali float ali pa vector, X pa integer (precej hitreje kot fcmp).
Abnormal behavior of abnormal brain makes me normal...
Spura ::
Po vsem tem mi se vedno ni jasno kaj rabis in kaksno resitev hocem. Ko bi se vsaj izjasnil.
technolog ::
Če je točk max 16, kaj pol kompliciraš??? Pri tako malem številu bo vedno linear sweep najhitrejši. Drugače se ne da...
256 kilo je zvrhano rama za 16 točk.
256 kilo je zvrhano rama za 16 točk.
Vesoljc ::
Po vsem tem mi se vedno ni jasno kaj rabis in kaksno resitev hocem. Ko bi se vsaj izjasnil.
tema je zasla... kot sem napisal na zacetku sem iskal metode kako neko zaporedje tock v grafu predstavit kot funkcijo z uporabo preprostih aritmeticnih ukazov. Genetic mi je v biti podal super zadevo, a se je izkazalo, da so moji primeri verjetno prevec preprosti (ali pa prevec kompleksni, kakor gledas), da bi generirana funkcija bila dejansko hitresja od standardne (in trenutne uporabljene) metode:
- poisci pravi par tocke (Xn, Xn+1)
- naredi interpolacijo (v 90% je to linearna metoda, sem ter tja se pa vmes znajde tudi hermite)
Abnormal behavior of abnormal brain makes me normal...
Senitel ::
Čak, če je x integer, zakaj rabiš iskanje? Oziroma v vsakem primeru, če imaš sortirane, zakaj rabiš iskanje?
Če je x float lahko narediš nekaj ala:
Xn = floor(x)
Xn1 = ceil(x)
y = points[Xn] + (x - Xn1)*(points[Xn1] - points[Xn]);
Če je x float lahko narediš nekaj ala:
Xn = floor(x)
Xn1 = ceil(x)
y = points[Xn] + (x - Xn1)*(points[Xn1] - points[Xn]);
Zgodovina sprememb…
- spremenil: Senitel ()
technolog ::
Ja, jaz ga tudi ne razumem, ker za linearno interpolacijo je zadosti ena enostavna formula.
Vesoljc ::
Čak, če je x integer, zakaj rabiš iskanje? Oziroma v vsakem primeru, če imaš sortirane, zakaj rabiš iskanje?
Če je x float lahko narediš nekaj ala:
Xn = floor(x)
Xn1 = ceil(x)
y = points[Xn] + (x - Xn1)*(points[Xn1] - points[Xn]);
zato ker nimam vseh x,y parov ane :)
Abnormal behavior of abnormal brain makes me normal...
alexa-lol ::
preprosto.. z matriko... samo odloči se polinom katere stopnje bi rad...
Sloni pa vse na vektorskih prostorih
Sloni pa vse na vektorskih prostorih
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Navigacija za kolo (strani: 1 2 )Oddelek: Na cesti | 13033 (9209) | schurda |
| » | FunkcijeOddelek: Šola | 1307 (1052) | Yacked2 |
| » | Matematična analiza naloga (strani: 1 2 )Oddelek: Šola | 6429 (4779) | lebdim |
| » | Matematika - pomoč (strani: 1 2 3 )Oddelek: Šola | 26768 (23343) | daisy22 |
| » | Java ObjektiOddelek: Programiranje | 2236 (1930) | Mavrik |