Go Down

Topic: idee per velocizzare ricerca dati in array? (Read 816 times) previous topic - next topic

hiperformance71

Apr 12, 2014, 02:45 am Last Edit: Apr 12, 2014, 02:21 pm by hiperformance71 Reason: 1
Salve ragazzi, mi chiedevo se esiste un metodo più veloce per la ricerca di un dato all'interno di un'array, io sto usando cicli FOR ed IF per cercare all'interno dell'array se un valore vi è contenuto tra due dati contigui, esempio:  

Code: [Select]

MyArray[10]={5,10,20,30,40,50,60,70,80,90};

For (i==0; i<10; i++)
{
if (Valore_Ricercato > MyArray[ i ]  &&  Valore_Ricercato < MyArray[ i + 1 ] )

Val_Ricercato_inf = MyArray[ i ];
Val_Ricercato_sup = MyArray[ i + 1 ];

}
}


Questo metodo mi funziona bene, ma vedo che risulta alquanto lento (relativamente) specie se il dato si trova in fondo, con 16 dati (dichiarati byte), ottengo un tempo di esecuzione da circa 30 a 80 uS in base alla posizione dove il dato si trova, sono curioso di vedere se esiste un metodo più efficace per ottenere le info spendendo il minor tempo possibile.

Ringrazio in anticipo tutti coloro che interverranno con suggerimenti !

Grazie

"The only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle" - Steve Jobs

nid69ita

#1
Apr 12, 2014, 01:11 pm Last Edit: Apr 12, 2014, 01:14 pm by nid69ita Reason: 1
Dipende da come sono ordinati i dati nell'array. Se sono disordinati non credo puoi fare altro che cercare in ogni elemento.
L'array che tu metti nel tuo esempio è già ordinato. In quel caso si procede con ricerca dicotomica, ovvero parti da metà dell'array.

Se l'array è disordinato, nel tuo caso che vuoi fare una ricerca entro intervallo potresti spezzare l'if in due, solo se il valore è nel range per uno dei confronti allora verifichi anche l'altro estremo.
Sempre che il compilatore non abbia già ottimizzato quel if unico.
Code: [Select]
for (i=0; i<10; i++)
{ if (Valore_Ricercato > MyArray[ i ])
    if( Valore_Ricercato < MyArray[ i + 1 ] )
    {  Val_Ricercato_inf = MyArray[ i ];
    }
}
my name is IGOR, not AIGOR

hiperformance71

Ciao Nid69ita,

si, tutti i miei dati sono ordinati, e solitamente in ordine crescente, avevo letto qualcosa al riguardo tempo fa su un libro di programmazione C, ma molto superficialmente (è molto tosto da studiare ed il tempo è poco).  Bene e anche li parlavano di iniziare dal centro dell'array, se non ricordo male, lo chiamavano ricerca binaria, ricordo bene? ma non ho capito se lo stesso concetto sia applicabile al mio progetto (Sto lavorando ad una centralina gestione motore, ho già fatto tante sezioni del codice e molte mi funzionano già abbastanza bene, ma è ovvio che man mano mi faccio le cose, inizio a pensare ai colli di bottiglia che inevitabilmente andranno a formarsi, e quindi per ogni "scoglio" superato, mi vengono in mente quelli successivi ampliando sempre di più la mia visione d'insieme del progetto).

Del tue esempio, ho capito bene, esegue il primo if, se vero controlla il secondo, credi possa essere più efficiente dell'uso di un'unico if con && ?  farò qualche test al riguardo.

per ora, grazie dei consigli!
"The only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle" - Steve Jobs

nid69ita

#3
Apr 12, 2014, 02:36 pm Last Edit: Apr 12, 2014, 02:43 pm by nid69ita Reason: 1

Del tue esempio, ho capito bene, esegue il primo if, se vero controlla il secondo, credi possa essere più efficiente dell'uso di un'unico if con && ?  farò qualche test al riguardo.
per ora, grazie dei consigli!

Non ne sono sicuro perchè sia il compilatore che il C standard in genere ottimizza gli if con and && e quindi spezzarlo in due forse già lo fa il compilatore.

La ricerca binaria o dicotomica di solito però serve per cercare esattamente un valore nell'array. Quello che serve a te mi sembra una cosa un pò diversa.
Però ottimizzazioni di sicuro possono essere fatte.
Mi viene in mente che il valore che tu cerchi prima di tutto deve essere maggiore di uno di quei valori. Allora visto che l'array è già ordinato la ricerca dicotomica può essere un inizio. Cercare per prima cosa la prima cella il cui valore è minore o uguale a quello da cercare (sfruttando la ricerca binaria).  
Partendo da metà array sai già se proseguire la ricerca a sinistra o a destra. Già questo ti dimezza l'array.
my name is IGOR, not AIGOR

gpb01

... spiegazione rapida e poco scientifica :

parti da metà array e ti chiedi "il mio valore è maggiore o minore del valore che ho qui a metà ?" ed in questo modo hai già eliminato una metà. A quel punto il tuo array si è dimezzato (... la sola metà in cui c'è il valore) e quindi ripeti la cosa considerando quella metà come il tuo nuovo array ... ti metti al centro (... ovvero alla metà della metà) e di nuovo ti chiedi "il mio valore è maggiore o minore del valore dove mi trovo ?" ... e così via.

Ti rendi conto che, ad ogni colpo, butti via una metà per cui ... molto velocemente raggiungi il tuo elemento ...  :smiley-mr-green:

Guglielmo
Search is Your friend ... or I am Your enemy !

MauroTec

Se i dati di MyArray sono quelli allora si può evitare la ricerca.

MyArray[10]={5,10,20,30,40,50,60,70,80,90};
MyArray[0] = 5
MyArray[1] = 10
MyArray[2] = 20
MyArray[3] = 30
MyArray[4] = 40
MyArray[5] = 50
MyArray[6] = 60
MyArray[7] = 70
MyArray[8] = 80
MyArray[9] = 90

aNumber = 38

min = aNumber/10 = 3          
max = aNumber/10 + 1 = 4
MyArray[min]
MyArray[max]

# Sembra funzionare
# Provo con 7
aNumber = 7
min = aNumber/10 = 0          
max = aNumber/10 + 1 = 1
# Sembra funzionare
# Provo con 2
aNumber = 2
min = aNumber/10 = 0          
max = aNumber/10 + 1 = 1
# Funziona come per aNumber = 7

mmm.. se fossero così pochi i dati potresti anche fare uno switch case
che è molto rapido in esecuzione.

Sicuramente i dati nell'array non sono quelli reali per cui vai di ricerca dicotomica.

Se fai come dice gpb01 e usi i puntatori e una funzione ricorsiva dovresti ottenere il massimo della velocità
possibile, almeno io un altro modo più rapido non lo conosco.

Ciao.
   
AvrDudeQui front end per avrdude https://gitorious.org/avrdudequi/pages/Home

hiperformance71

#6
Apr 12, 2014, 04:42 pm Last Edit: Apr 12, 2014, 04:52 pm by hiperformance71 Reason: 1

Se i dati di MyArray sono quelli allora si può evitare la ricerca.

MyArray[10]={5,10,20,30,40,50,60,70,80,90};
MyArray[0] = 5
MyArray[1] = 10
MyArray[2] = 20
MyArray[3] = 30
MyArray[4] = 40
MyArray[5] = 50
MyArray[6] = 60
MyArray[7] = 70
MyArray[8] = 80
MyArray[9] = 90

aNumber = 38

min = aNumber/10 = 3          
max = aNumber/10 + 1 = 4
MyArray[min]
MyArray[max]

# Sembra funzionare
# Provo con 7
aNumber = 7
min = aNumber/10 = 0          
max = aNumber/10 + 1 = 1
# Sembra funzionare
# Provo con 2
aNumber = 2
min = aNumber/10 = 0          
max = aNumber/10 + 1 = 1
# Funziona come per aNumber = 7

mmm.. se fossero così pochi i dati potresti anche fare uno switch case
che è molto rapido in esecuzione.

Sicuramente i dati nell'array non sono quelli reali per cui vai di ricerca dicotomica.

Se fai come dice gpb01 e usi i puntatori e una funzione ricorsiva dovresti ottenere il massimo della velocità
possibile, almeno io un altro modo più rapido non lo conosco.

Ciao.
   


il metodo che hai postato credo funzioni, si somiglia ad uno che fa la stessa cosa che ho trovato dentro uno sketch di una tesi di laurea di un Laureando in "Automotive Electronics Engineering" inglese che ha realizzato con arduino una centralina per motore monocilindrico con controllo Lambda e battito in retroazione (!) e dai filmati visti su yotube il motorino funziona benino.  Rispetto al mio codice è veramente ridotto all'osso, alcune cose le ho capite, tra cui, la tecnica per fare come hai indicato te, per esempio, nell'esempio che ho fatto di array, i valori indicati in essa, stanno arappresentare i gradi apertura farfalla, quindi se essi sono regolarmente distribuiti dividiamo per il valore che li separa uno dall'altro ed otteniamo un intero, che dovrebbe corrispondere con il valore dell'index array che lo contiene, ma non è molto efficiente se i valori in array non sono lineari.

@Guglielmo:

Grazie del chiarimento, era questo a cui mi riferivo prima, avevo letto qualcosa al riguardo della ricerca binaria e che è il metodo più veloce esistente in C per ricercare in arrays, il mio dubbio era se potevo applicare quella tecnica ad una MCU visto che il libro di cui parlo, tratta programmazione su Computer tradizionali, quindi non sistemi Embedded. Adesso vedo che la cosa è fattibile.

@Nid69ita:

ho fatto un test con array a 16 elementi, fa la ricerca sia con il metodo mio, che con il metodo suggerito da te, Avevi Ragione, il compilatore forse già ottimizza l'IF con operatore &&, infatti, i risultati sembrano essere identici, ho dovuto solo modificare uno dei operatori di comparazione perché se capitava un valore a metà strada tra quello inferiore e superiore, spesso il risultato era incerto, mentre così modificato, è perfetto.

Ecco il codice completo:

Code: [Select]

//*******************************************************************
//**    TEST TEMPO DI ESECUZIONE RICERCA INDICE ARRAY
//*******************************************************************

byte i;

byte MyArray[ 10 ] = {10,20,30,40,50,60,70,80,90,100};

unsigned long Tempo_Start=0;
unsigned long Tempo_Fine=0;
unsigned long Tempo_Delta=0;

byte Valore_Ricercato;
byte Val_Ricercato_inf;
byte Val_Ricercato_sup;

//*******************************************************************
void setup(){
 
Serial.begin(9600);

 
}

//*******************************************************************
void loop(){

Valore_Ricercato = map (analogRead(A0),0,1023,0,100);
 
Tempo_Start=micros();

//per testare i due metodi, semplicemente escludere l'altro metodo
//commentandolo in blocco.


//---metodo 1: Suggerito da Nid69ita--------- esegue da 4 a 20 uS
//(4 quando il valore ricercato é nel primo index e 20 quando è l'ultimo index dell'array)

/*
for (i = 0; i < 10; i++)
{ if (Valore_Ricercato >= MyArray[ i ])
   if( Valore_Ricercato < MyArray[ i + 1 ] )
   {  Val_Ricercato_inf = MyArray[ i ];
      Val_Ricercato_sup = MyArray[ i + 1 ];
      break;
   }
}
*/
//---metodo 2: il mio (hiperformance71)--- esegue in: 4 a 20 uS
//(4 quando il valore ricercato é nel primo index e 20 quando è l'ultimo index dell'array)

/*
for ( i = 0; i < 10; i++ )
{
if (Valore_Ricercato >= MyArray[ i ]  &&  Valore_Ricercato < MyArray[ i + 1 ] )
{
Val_Ricercato_inf = MyArray[ i ];
Val_Ricercato_sup = MyArray[ i + 1 ];
break;
}
}
*/
//---metodo 3: suggerito da MauroTec ----

Val_Ricercato_inf = Valore_Ricercato / 10;
Val_Ricercato_sup = Valore_Ricercato / 10 + 1;

Tempo_Fine=micros();
Tempo_Delta = Tempo_Fine - Tempo_Start;

Serial.print(i);
Serial.print(",");
Serial.print(Valore_Ricercato);
Serial.print(",");
Serial.print(Val_Ricercato_inf);
Serial.print(",");
Serial.print(Val_Ricercato_sup);
Serial.print(",");
Serial.println(Tempo_Delta);
 
}


ho voluto approfittare per includere anche il test del suggerimento di MauroTec, ed effettivamente, già così, è il più veloce e non viene influenzato dallo stato del Valore_Ricercato mentre gli altri metodi basati su FOR/IF per forza di cose, dipendendo da dove si trova il valore ricercato, incidono sul risultato. Questo impiega 8 uS, ma, diversamente dagli altri metodo, questa ricerca viene eseguita una volta a ciclo di loop() e non in un unico loop() come i FOR/IF, quindi quanto attendibile è eseguire 10 ricerche in 10 cicli loop?  è giusto pensare al prodotto matematico, ovvero 8 uS x 10 loop = 80 uS ?  se così fosse, allora sarebbe peggio dei FOR/IF,  mamma mia, adesso sono più confuso! Purtroppo, come accennato prima, questo metodo funzionerebbe se, come in questo caso, i valori in array fossere spaziati in modo regolare, quindi multipli direi, diversamente ho verificato tende a sbagliare alla fine (avevo fatto una prova con array a 16 elementi, così => {0,2,5,7,10,12,15,20,30,40,50,60,70,80,90,100}    ovviamente, il fatto di avere 16 elementi e non 10 ha mandato a monte il sistema, non ho verificato se usando /16 invece di /10 funziona. magari provo dopo.

Poi vedrò di studiare come fare per la ricerca binaria e fare un test in questo sketch.

PS. per come mi serve a me, non servirebbe nemmeno il select/case, avere già il riferimento dell'index inferiore e superiore già mi basta per poi inserirlo dentro la funzione che mi prende i valori nella mappa vera e propia per calcolare l'interpolazione lineare tra i due valori estratti da essa corrispondenti appunto dentro gli index appena trovati.
Resta da chiarire, in che modo possano essere vantaggiosi uno o l'altro metodo, dal mio modesto punto di vista, essere più veloce nell'esecuzione di un loop() lascia spazio ad una esecuzione più veloce ed efficiente di tutti i restanti componenti di codice, ma implica fare il tutto in più cicli clock, farlo con i FOR/IF aumenta il tempo richiesto per ciclo di loop() ma garantisce un calcolo finito, ancora non so quale dei due mi convenga, in realtà, dovrò suddividere tutte le operazioni in diverse funzioni che verranno chiamate in causa da un sistema schedulatore in base alla priorità che ogni funzione avrà, ci saranno funzioni che saranno chiamate più spesso ed altre a cadenze più lunghe perchè hanno dati che cambiano lentamente )come le temperature motore, temp. aria ecc che cambiano ogni 0,5-1 sec, quindi è inutile chiamarle ad ogni ciclo loop).


"The only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle" - Steve Jobs

MauroTec

Quote
ovviamente, il fatto di avere 16 elementi e non 10 ha mandato a monte il sistema, non ho verificato se usando /16 invece di /10 funziona.


No non funziona in questo caso, avevo intuito che i dati realmente usati non erano quelli mostrati.

Le tavole di corrispondenza sono un altro modo molto più rapido della ricerca, ma occupano memoria
e sono complicate e non è facile metterle su e il mal di testa è assicurato.

Mentre la ricerca suggerita da gpb01 è fattibile, sia con gli indici che con i puntatori e la ricorsione, metterla su in modo efficiente non è banale per me, ma lo considero fattibile in un paio di ore. Io penso che qualcosa in rete si trovi già, prova a fare una ricerca.

Di quanti elementi e composto l'array reale su cui effettuare la ricerca?

Ciao.
AvrDudeQui front end per avrdude https://gitorious.org/avrdudequi/pages/Home

gpb01


...
Mentre la ricerca suggerita da gpb01 è fattibile, sia con gli indici che con i puntatori e la ricorsione, metterla su in modo efficiente non è banale per me, ma lo considero fattibile in un paio di ore. Io penso che qualcosa in rete si trovi già, prova a fare una ricerca.
...


Probabilmente si tovano centinaia di esempi già fatti ... essendo il metodo più veloce quando hai array ordinati. ;)

[OT]
Giusto per ricordare un po il passato ...
... mi divertii a studiare tutte le tecniche di ordinamento  e ricerca, nei lontani anni '70, nella Bibbia di questo argomento  : "Donald Knuth, The Art of Computer Programming, Vol III, Sorting and Searching".
All'epoca avevo un Apple IIe con due unità a floppy esterne e la scheda USCD Pascal ... in Pascal scrissi l'intera gestione di un mini Database che organizzava il file di chiavi in un "balanced binary tree" ... oh ... con tutto che erano floppini lentissimi, ricercava un record su diverse migliaia in pochi secondi ...  :)
Un gioiellino ...  XD
[/OT]

Guglielmo
Search is Your friend ... or I am Your enemy !

hiperformance71

Allora, diciamo, in maniera sommaria, io ho degli array semplici costituiti da 8 a 16 elementi che rappresentano i breakpoint degli assi X e Y delle mappe corrispondenti vere e propie, che saranno multidimensionali con lo stesso numero di elementi per ogni asse, ovvero, se ho 10 elementi nell'asse delle X e 10 nell'asse delle Y, allora la X saranno le Colonne, e la Y saranno le righe di un'array tipo:  Mappa[10][10]={......}   la ricerca dei breakpoint mi darà dei valori (diciamo un "i" ed un "j" ) pari all'index in array, a sua volta nel calcolo dell'interpolazione andiamo ad assegnare a delle variabili specifiche il contenuto dell'array mappa[ i ][ j ]   per facilitare il lavoro, ho deciso di usare solo array come byte,  e ricorrere a fattori di conversione per risalire alle misure ingegneristiche di tale parametro, così ho semplificato sia la gestione delle array in RAM, che in EEPROM visto che poi, le dovrò memorizzare li per poi caricarle in RAM all'avvio del sistema, potrei farlo in flash, ma credo che in EEPROM vada bene, su questo, poi si vedrà.

Diciamo che l'ideale sarebbe avere i breakpoint RPM e Load configurabili in base a necessità dettate dalla singola applicazione su cui poi, questa "pseudo" centralina andrà a montarsi, questo perché se ho due motori diametralmente diversi, magari uno da moto di piccola cilindrata tanti giri ed uno da vettura poco efficiente e da pochi giri, la prerogativa sarà distribuire i breakpoint in maniera da essere più ravvicinati dove i cambiamenti di rendimento volumetrico provocano altrettanti cambiamenti nella curva di coppia sviluppata (ricordate quando sui programmi di F1 si parla dei "buchi di coppia" ecco, questo per esempio, richiede una maggiore capillarità di breakpoint giri per tentare di limitare al massimo le perdite in quella zona).

Per fortuna, nell'applicazione che ho in mente, i giri sono pochi, quindi avere 16 breakpoint giri è più che sufficiente, mentre per il carico motore, me ne bastano 8 quindi una mappa da [8][16] basterebbe, ovviamente, di mappe che si sovrappongono ce ne sono diverse, ma queste da 8x16 sono le principali e più grandi, le altre sono da 10x10 e 8x8.

Stasera vedo di studiare un po il tema della ricerca binaria.  

Purtroppo ho visto che non è la ricerca la parte più "lenta" della funzione dove ho intenzione di posizionare questi calcoli, ma i calcoli di interpolazione in se.  Ho una bella formula che mi fa l'interpolazione dei 4 punti entro cui il motore sta funzionando in quel momento, da come l'ho testato funziona, ma utilizza dei valori float che costano un botto in tempi di eseczione come voi ben mi avete insegnato, ho tentato di evitare l'uso di float a favore di valori int/unsigned int ma siccome ad un certo punto del calcolo, poi avrei bisogno di dividere svariate volte per riportare i valori calcolati a valori "reali" tutto quello che ho risparmiato passando da float ad int lo perdo eseguendo le divisioni.  Adesso mi è venuta l'idea di vedere se posso gestire i valori int così come escono fuori per poi dividerli solo all'ultimo, con un'unica divisione.

"The only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle" - Steve Jobs

hiperformance71

@Guglielmo,
sono sempre affascinato dalle storie degli albori dell'informatica, d'altronde, io c'ho avuto a che fare con i pc dagli anni 84-85, allora 14 enne circa, un amico aveva comprato un 8086 con 4 MHz (8 con il "Turbo") e 640 kb RAM, disco da 10 mega o qualcosa del genere, monitor mono verde, che ricordi, con lui ho imparato un pelino di programmazione in Basic e DOS, poi ho lavorato con sistemi Epson PCM, ecc...  poi lui è diventato un informatico, ed io presi la strada dell' automotive. All'epoca non vedevo oltre il mio naso, adesso sarebbe stato diverso. 
"The only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle" - Steve Jobs

MauroTec

:smiley-eek: :smiley-eek:
Ci avessi capito qualcosa.
Ha grandi linee i buchi di coppia so cosa sono, cioè il grafico della coppia in relazione al numero
di giri non è "lineare" e ci sono punti in cui la coppia anziché aumentare si riduce, superato quel
punto la coppia riprende ad aumentare. Es Honda NS 125 primo modello in basso era vuota, 4000 a salire coppia
omogenea fino a xx non lo ricordo. C'è un numero di giri nei dintorni del quale era inguidabile.

Al di la della comprensione di tecnica motoristica io ho fatto delle deduzioni ma chissà se sono corrette.
Quote

per facilitare il lavoro, ho deciso di usare solo array come byte,  e ricorrere a fattori di conversione per risalire alle misure ingegneristiche di tale parametro, così ho semplificato sia la gestione delle array in RAM, che in EEPROM visto che poi, le dovrò memorizzare li per poi caricarle in RAM all'avvio del sistema, potrei farlo in flash, ma credo che in EEPROM vada bene, su questo, poi si vedrà.


Invece come le dovresti scrivere le informazioni in eeprom, cioè quale problema hai incontrato che ti
ha portato ad usare array di byte e da questi ricavare/calcolare alla misura ingegneristica?
Ci sono buone possibilità che le difficoltà incontrate in questo frangente siano superabili facilmente.

Quote

Ho una bella formula che mi fa l'interpolazione dei 4 punti entro cui il motore sta funzionando in quel momento, da come l'ho testato funziona, ma utilizza dei valori float che costano un botto in tempi di eseczione come voi ben mi avete insegnato, ho tentato di evitare l'uso di float a favore di valori int/unsigned int ma siccome ad un certo punto del calcolo, poi avrei bisogno di dividere svariate volte per riportare i valori calcolati a valori "reali" tutto quello che ho risparmiato passando da float ad int lo perdo eseguendo le divisioni.  Adesso mi è venuta l'idea di vedere se posso gestire i valori int così come escono fuori per poi dividerli solo all'ultimo, con un'unica divisione.


I calcoli in generale sono lenti e si mangiano la flash, se avessi un processore con FPU il problema scomparirebbe, es un ARM M4. La divisione e moltiplicazione di interi per 2, 4, 8, 16, ecc sono eseguite con rapidità, perché il compilatore usa lo shift. La tecnica di moltiplicare per 128 e fare i calcoli e poi dividere per 128 e castare a double e pratica comune. Penso che usi la MEGA che ti permette di aggiungere memoria RAM esterna che fa sempre comodo, per la eeprom esterna conviene sempre su bus ISP.

Ciao.


AvrDudeQui front end per avrdude https://gitorious.org/avrdudequi/pages/Home

hiperformance71

#12
Apr 12, 2014, 08:58 pm Last Edit: Apr 12, 2014, 09:01 pm by hiperformance71 Reason: 1
in realtà ci hai capito abbastanza, è proprio quello il problema nello scegliere i breakpoint giri e carico motore.

Scusa se non sono stato troppo chiaro, è difficile descrivere in poche parole i concetti dietro quello che dovrebbe fare una gestione motore (io da profano in elettronica e programmazione, sto facendo una specie di reverse engineering, dal funzionamento lato utente finale sto risalendo a ritroso su "come" lavora una ECU in firmware... non sono bruscoline...)

Comunque alla base di ciò che affermavo, vi è che sarebbe opportuno poter spaziare i breakpoint RPM in base alla curva di coppia del motore perchè, dove esso si comporta linearmente, io aumento il divario di giri a cui fa il controllo mappa, mentre nelle zone dove il motore è più imprevedibile, per facilitare le cose, spesso sono costretto ad aumentare il numero di breakpoint in quella zona ravvicinando i giri di controllo (ovvero i breakpoint) ti faccio un'esempio:

ho un motore che deve funzionare liscio a filo di gas in citta,  poi il motore sale con una progressione abbastanza lineare fino a 5000 rpm, da li al massimo numero di giri utili (diciamo 6000) del motore diventa poco lineare.   Quindi se la mia mappa ha 16 breakpoint RPM,  affinchè vengano inglobati tutto il range di funzionamento, quindi i miei breakpoint potrebbero essere:
    0 ,        1 ,        2 ,         3,         4,          5,         6,          7,          8,         9,       10,        11,         12,        13,        14,        15,    
    0,    500, 1000, 1500, 2000, 2500, 3000, 3500, 4000, 4500, 5000, 5500, 6000, 6500, 7000, 7500

Questo qui sopra sarebbe uno spreco di breakpoint tutti spaziati ogni 500 giri e partendo da 0 e superando i giri utili.

noi Tuner del settore Racing, dove queste cose sono all'ordine del giorno, in base a questo ipotetico motore faremmo:

      0 ,         1 ,        2 ,         3,         4,          5,          6,         7,          8,          9,       10,        11,        12,       13,        14,       15,    
1000,  1250,  1500, 1750, 2000,  2500, 3000, 3500, 4000, 4500, 5000, 5250, 5500, 5750, 6000, 6250,

come vedi, ho evitato lo 0, quando il motore è fermo la ECU resta in "ascolto" del segnale giri quindi in stand by, appena vede "girare" il motore, attua altre strategie specifiche della partenza (cranking)  superato una certa soglia giri, passa allo stato "running" e qui, entra in funzione la nostra bella mappa. quindi i nostri giri iniziano intorno alla zona di minimo che magari sarà intorno ai 900-1000 giri, per una buona erogazione, si predispongono breakpoint ogni 250 giri poi si passa a 500 giri alla volta (nella zona dove il motore è linare, ed infine, nella zona dove il motore è un po più irregolare e vicino alla potenza massima, si ritorna di nuovo a spaziare ogni 250 giri.  Ovviamente, questo dipende molto dal tipo di centralina che ho per mani e dal motore, ho centraline che hanno solo 16 breakpoint giri disponibili e con motori che fanno tantissimi giri diventa un problema trovare la spaziatura giusta, altre ECu invece, gestiscono fino a 32 breakpoint giri x 24 carico motore a mappa (e consentono i 250 giri dappertutto).

Visto che la mia idea è per un motore specifico e conosco le mappe originali, mi bastano i 16 breakpont giri ed anzi, forse userò anche la spaziatura originale, questo lo deciderò al momento delle fasi finali, se ci arriverò, della messa in moto di un motore cavia, ma per ora, quel momento è lontanuccio, meglio concentrarsi sui problemi uno ad uno separatamente e poi andare ad inglobarli uno alla volta fino ad ottenere il firmware completo e funzionante.

Quindi da qui, la mia preoccupazione per rendere fin da subito, più ottimizzato il codice, magari anche con queste lacune, sarebbe funzionante, ma essendo io profano, preferisco pensare al massimo risparmio di risorse per garantire velocità di riserva in caso di guai non previsti, quindi per esempio, per le funzioni di ricerca breakpoint sensori temperatura vari e relativo calcolo valori ingegneristici (sensore NTC non lineari, richiedono la linearizzazione mediante array, rieccoci !! capite?) l'ho ottimizzato inglobando le ricerche in una unica funzione Universale, che viene invocata da ogni funzione sensore da calcolare invece di fare una funzione per ogni sensore (sono 3 al momento i sensori). così ho risparmiato diversi byte di flash, codice più breve, e qualcosina a livello di uso SRAM (forse il compilatore gia di per se ottimizzava tantissimo prima), adesso sto facendo la stessa cosa con queste altre mappe, se non le ho inglobate in quella "universale" è per la differenza di numero breakpoints, e per quieto vivere, ho preferito farne una specifica per le mappe di gestione, ma una volta capito bene come fare, l'idea è inglobare anche queste ricerche in quella unica funzione "universale" come se fosse una libreria.  Le librerie, per ora, non ne uso nessuna, ma l'idea sarebbe anche verificare se conviene o meno, trasferire queste funzioni universali in librerie in modo da rendere il codice più trasportabile e corto (nello sketch ovviamente).  La strada è lunga.... :(

PS. sai che la tecnica che descrivi di dividere/moltiplicare per 128 l'ho vista tantissime volte sulle ECU di vecchia generazione? anche loro a corto di risorse e senza FPU.







"The only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle" - Steve Jobs

hiperformance71

Ciao, in risposta alla domanda del perchè l'uso di byte per le array...

Diciamo che principalmente perché avendo la necessità di avere in SRAM tante array (mappe) caricate per velocità di calcolo, e per poter usufruire della UNO l'ho impostato fin dall'inizio sulla riduzione di memoria occupata.  Non vorrei memorizzare i dati delle mappe in flash, quindi preferisco siano memorizzati in EEPROM,  diciamo che allo stato attuale, dal conteggio che ho, sommariamente, mettendo tutti i dati byte che ho in arrays e singoli dati variabile/costanti, sto già sulla soglia del limite della EEPROM della UNO, ma se non dovessi apportare ulteriori aggiunte o ampliazioni, mi avanzerebbero circa 70-90 bytes su 1024 disponibili.  Comunque adesso questo non è un problema, presto passerò il progetto su Atmega1284P che di flash ne ha 128Kb, di EEPROM ne la bel 4Kb e di SRAM ben 16Kb. 

Per ora, con la SRAM, considerando che non ho ancora tutto funzionante e quindi tutto quello che ho in teoria inizializzato come variabili, costanti e arrays non utilizzate da nessuna parte, il compilatore semplicemente le esclude, ma una buona parte è già funzionante, usando "freeRam" messo sparso un po dappertutto a fine funzioni, ottengo che ho ancora circa 1400-1450 bytes di SRAM,  non male, ma ovviamente, credo che a fine progetto, ne resteranno si e no 400-500 liberi e non so fino a che punto siano sufficienti per fare cose che non posso misurare dove stanno messe.  Per fortuna il passaggio alla 1284p risolverà indirettamente, anche questo ipotetico eventuale problema che potenzialmente potrò incontrare.

In realtà la scelta della 1284p è stata dettata per vari fattori:

1-ha 2 timers 16 bit, mi servono assolutamente.
2-ha 2 timers 8 bit, necessari per alcune funzioni da implementare in secondo momento.
3-funziona a 20 MHz (anche la UNO potrebbe farlo, la MEGA da datasheet NO) quindi un buon 25% di potenza in più.
4-Ha 128Kb di Flash (anche se per ora, non uso tanta flash da saturare la UNO).
5-Ha 4 Kb di EEPROM, mi darebbe respiro e consentirebbe anche l'implementazione di multi mappe, feature molto richiesta nel motorsport, e mi piacerebbe inserirla se possibile.
6-Ha 16 kb di SRAM e questo non può che giovare al progetto.
7-il formato TQFP44 è perfetto per un progetto stand alone, lo posso saldare agevolmente quello della MEGA non tanto.
8-il chip 1284P costa meno della metà di quello della MEGA.

della Mega invidio solo i 4 timers a 16 bit, adesso che ho visto cosa si può fare sfruttando i timers con OCRnX, più ce ne sono meglio è.

Altra ragione dell'uso di byte per la memorizzazione dei dati, è che essendo queste organizzate in byte, se dovessi memorizzare un dato "int" o "unsigned int" essi occuperebbero 2 byte giusto? formando una word a 16 bit giusto? un double 4 byte e i float? non me lo ricordo, ma il consiglio che ho visto spesso in giro é:  evitarli come la peste, si mangiano Flash, RAM ed EEPROM come niente e inchiodano le prestazioni.  E qui, le prestazioni sono tutto o quasi, siamo quasi nel "Real Time" e voi mi insegnate...
Quindi anche per mia facilità, memorizzare/leggere un byte è più facile che con una word, dove poi devo andare a decidere di leggere il MSB e LSB, con i quali ancora faccio fatica a ragionarci, e si sa, "make it simple" recita un famoso detto gringo, ed ha ragione.
Consapevole delle mie grandi lacune Tecniche in materia Hardware/programmazione tento di ridurre tutto a codice che per me sia comprensibile, almeno fin tanto non imparo nuove cose, purtroppo questo rende le prestazioni del sistema più lente o addirittura inutilizzabili...
Ho analizzato il codice sorgente di diversi progetti di ECU basati su Arduino/Freescale ecc e ho riscontrato diverse strade per fare le stesse cose, questo mi da da pensare, che la strada non è standarizzata, e quello che per me può essere un'incubo per qualcun'altro sarà normale amministrazione...


 
"The only way to do great work is to love what you do. If you haven't found it yet, keep looking. Don't settle" - Steve Jobs

leo72


Altra ragione dell'uso di byte per la memorizzazione dei dati, è che essendo queste organizzate in byte, se dovessi memorizzare un dato "int" o "unsigned int" essi occuperebbero 2 byte giusto? formando una word a 16 bit giusto? un double 4 byte e i float? non me lo ricordo, ma il consiglio che ho visto spesso in giro é:  evitarli come la peste, si mangiano Flash, RAM ed EEPROM come niente e inchiodano le prestazioni. 

La Flash è organizzata a 16 bit, quindi word. Difatti se ci fai caso, quando compili uno sketch, non vedrai MAI un'occupazione di Flash data con un numero dispari, sempre pari!  ;) ;)
Uno sketch compilato che occupa 1013 byte prende in Flash 1014 byte, per capirsi.

Go Up