View Full Version : [C] Valore assoluto di un numero + velocemente possibile
Ciao Ragazzi,
sapete dirmi qul'è secondo voi il modo più veloce per ottenere il valore assoluto di un numero siccome lo devo calcolare tante volte? Io pensavo alla seguente funzione:
int abs(int x)
{
return (x > 0) ? x : -x;
}
che ne dite?
marko.fatto
12-02-2008, 21:53
unsigned int :stordita:
unsigned int :stordita:
In uscita voglio che sia dello stesso tipo che in ingresso. Poi è ovvio che sarà positivo. :)
#define ABS(x) ((x) > 0) ? (x) : -(x);
Non va bene.
Considera (è in java, ma non cambia):
class twocompl {
public static void main(String[] args) {
int x = -2147483648;
System.out.println(myAbs(x));
}
private static int myAbs(int x) {
return (x > 0) ? x : -x;
}
}
c:\> java twocompl
-2147483648 <-- OMG!!1
In pratica, fallisce con il minor numero rappresentabile. Ma è la logica del complemento a due.
Il tuo problema è più accentuato perchè stai lavorando in C, quindi la dimensione dell'int varia da macchina a macchina.
Fatti due conti.
Credo che il più veloce sia questo:
unsigned int iabs(int a)
{
return ~a + 1;
}
La condizione inline mette sempre in gioco il branch predictor, sicuramente un branch è veloce, ma l'altro no ;)
Credo che il più veloce sia questo:
unsigned int iabs(int a)
{
return ~a + 1;
}
La condizione inline mette sempre in gioco il branch predictor, sicuramente un branch è veloce, ma l'altro no ;)
Ma sei sicuro che la tua funzione non faccia solamente un cambio di segno? cioè se a = 5 => ritorno = -5 e se a = -8 => ritorno = 8
Sì che testa :muro:
Di nulla figurati :)
Mi sa che la più veloce è la mia... Ho provato con il quadrato al posto del valore assoluto e ho avuto un miglioramento di circa il 25% sulla velocità totale dell'algoritmo. Però dai un modo più veloce ci deve essere :)
Con il quadrato però perdi parte dello spazio degli interi.
wingman87
13-02-2008, 12:23
Ma com'è codificato in bit un numero positivo e uno negativo? Lo avevo fatto alle superiori ma non me lo ricordo più...
Ma com'è codificato in bit un numero positivo e uno negativo? Lo avevo fatto alle superiori ma non me lo ricordo più...
Se il primo bit partendo da destra è uguale a 0 allora è positivo altrimenti è negativo. Ricorda però il complemento a 1.
Con il quadrato però perdi parte dello spazio degli interi.
Purtroppo lo so ed è per questo che non lo voglio usare. Era per fare una prova di quanto succhia l'if. :)
hai provato la macro?
La macro da gli stessi risultati della mia funzione. :)
Ho provato a costruirmi un Look Up Table e sono passato dai 19ms con la mia funzione a 13ms. :)
Peccato però che debba usare quella LUT che è abbastanzza grande.
wingman87
13-02-2008, 13:24
Se il primo bit partendo da destra è uguale a 0 allora è positivo altrimenti è negativo. Ricorda però il complemento a 1.
Ah ecco, grazie! Solo una cosa, non si guardava il primo bit da sinistra?
^TiGeRShArK^
13-02-2008, 14:13
...ovviamente hai effettuato un profiling per verificare incontrovertibilmente che ottimizzando quella funzione otterresti *sensibili* vantaggi in esecuzione spero... :mbe:
Altrimenti hai solo perso tempo sottraendolo alla scrittura di codice utile.... :fagiano:
Se si tratta di studiare il problema sono d'accordo con TigerShark. E' sempre bene usare un profiling se si tratta di ottimizzare qualcosa.
E prima di ottimizzare con il profiling la maggior parte delle volte e' quasi sempre un problema di modello dati inadeguato.
Una volta aggiustato il modello dati la situazione migliora da sola.
Comunque non penso che questo caso sia effettivamente migliorabile, mantenendo la leggibilita' e l'universalita', rispetto a quanto ottenibile con la macro.
Se invece si tratta di una gara, poiche' sono l'unico ad essere rimasto in ufficio durante la pausa pranzo, e poiche' da solo mi rompo abbastanza, io provo con questo:
int __inline absasm(int x)
{
__asm{
mov eax,x
cdq
xor eax,edx
sub eax,edx
}
}
Senza salti.
Ovviamente e' ben poco universale. Molto poco.
Se si prova a compilare con le __inline function si guadagna un 10% rispetto alla versione Macro (che penso sia comunque la preferibile e universale).
MFSPO=DBGPOF
13-02-2008, 16:03
prova così:
int abs(int x)
{
int b=0x80000000,c=30;
return (x*(((x&b)>>c)+1));
}
MFSPO=DBGPOF
13-02-2008, 16:14
Ho chiesto, e pare che così è meglio:
int abs(int x)
{
return ((x^(x>>31))-(x>>31));
}
Ho chiesto, e pare che così è meglio:
int abs(int x)
{
return ((x^(x>>31))-(x>>31));
}
cross platform soprattutto :D
MFSPO=DBGPOF
13-02-2008, 16:32
cross platform soprattutto :D
:rolleyes: vabbe, metto a posto
int abs(int x)
{
return ((x^(x>>((sizeof(int)<<3)-1)))-(x>>((sizeof(int)<<3)-1)));
}
Contento?
Guardate che io avevo barato.
L'implementazione piu' veloce e' esattamente quella che abbiamo imparato, ovvero usare la
funzione gia' disponibile nella stdlib.h (e nella math.h)
Ovvero
int abs(int x)
gia' dichiarata e pronta per tutti.
Il mio codice infatti non era altro che il Disassembly del codice generato da tale funzione.
Fra l'altro il codice generato dalla soluzione di MFSPO=DBGPOF e' easttamente equivalente, a parte il
CDQ generato dalla ABS di libreria
e il (SAR registro,31) generato dalla soluzione.
entrambi vogliono riempire un registro con quello che e' il bit piu' significativo, ovvero il segno, della nostra variabile in questione.
Usare la ABS di libreria secondo me e' quindi piu' veloce, piu' leggibile e piu' cross-platform di qualunque altro metodo.
MFSPO=DBGPOF
13-02-2008, 17:20
Guardate che io avevo barato.
L'implementazione piu' veloce e' esattamente quella che abbiamo imparato, ovvero usare la
funzione gia' disponibile nella stdlib.h (e nella math.h)
Ovvero
int abs(int x)
gia' dichiarata e pronta per tutti.
Il mio codice infatti non era altro che il Disassembly del codice generato da tale funzione.
Fra l'altro il codice generato dalla soluzione di MFSPO=DBGPOF e' easttamente equivalente, a parte il
CDQ generato dalla ABS di libreria
e il (SAR registro,31) generato dalla soluzione.
entrambi vogliono riempire un registro con quello che e' il bit piu' significativo, ovvero il segno, della nostra variabile in questione.
Usare la ABS di libreria secondo me e' quindi piu' veloce, piu' leggibile e piu' cross-platform di qualunque altro metodo.
Quoto gugoXX. Ho disassemblato la abs(x) della stdlib.h, e il codice x86 generato è pari pari quello proposto da gugoXX. La abs() di stdlib.h è la più veloce possibile.
Ragazzi vedo che vi siete impegnati per darmi la soluzione... :)
Ovviamente ho fatto un attento profiling ed il collo di bottiglia è proprio il calcolo del valore assoluto che è da calcolarsi il più velocemente possibile... Ho provato anche ad utilizzare la funzione abs di libreria come dite voi ma la LUT continua ad essere la soluzione più veloce... :)
Mi spieghi come hai fatto la lookup table per l'abs ?
Mi spieghi come hai fatto la lookup table per l'abs ?
siccome il mio numero da "assolutizzare" va da -23000 a +23000 per ognuno di quesi numeri mi sono fatto una tabella lunga 46001 elementi mettendoci il risultato. Questa tabella l'ho generata con Matlab su un file di testo che poi ho dato in pasto al C. :)
Sicuramente è molto veloce, ma fare il quadrato e poi la divisione era molto più lento ?
Sicuramente è molto veloce, ma fare il quadrato e poi la divisione era molto più lento ?
Guarda ti faccio un piccolo schema:
Funzione abs di libreria => 16ms
Mia funzione citata nel primo post => 14ms
Quadrato e poi divisione => 13ms
LUT => 9ms
Se consideri che tale algoritmo lo voglio fare in real-time anche se formalmente più brutto preferisco la LUT. :)
In real time intendi in so real time ? In tal caso ti capisco ;)
^TiGeRShArK^
13-02-2008, 20:32
Guarda ti faccio un piccolo schema:
Funzione abs di libreria => 16ms
Mia funzione citata nel primo post => 14ms
Quadrato e poi divisione => 13ms
LUT => 9ms
Se consideri che tale algoritmo lo voglio fare in real-time anche se formalmente più brutto preferisco la LUT. :)
ma non è tantissimo 9ms? :mbe:
...spero che non sia per un'esecuzione sola... :fagiano:
siccome il mio numero da "assolutizzare" va da -23000 a +23000 per ognuno di quesi numeri mi sono fatto una tabella lunga 46001 elementi mettendoci il risultato. Questa tabella l'ho generata con Matlab su un file di testo che poi ho dato in pasto al C. :)
La prossima volta spiega bene il problema allora.
46KB*4 di memoria non sono nulla
4GB*4 potrebbero esserlo.
Nelle valutazioni quantitative devi anche considerare che quella lookup table sono sempre 200KB di cache che usi solo per il calcolo del valore assoluto, e che potrebbero essere usati per altro.
^TiGeRShArK^
13-02-2008, 20:42
ma non è tantissimo 9ms? :mbe:
...spero che non sia per un'esecuzione sola... :fagiano:
ho fatto una semplicissima prova in ruby sul mio A64 3000+@4000+ (2520mhz e RAM 186 mhz se non sbaglio):
startTime = Time.new
for i in 0..1000000
a = -2.abs
end
puts Time.new - startTime
risultato... 350 msec per un milione di iterazioni....
e ruby è notoriamente molto lento come implementazione (ho usato la versione 1.8.6 non la ben + veloce 1.9.0 :p)
In real time intendi in so real time ? In tal caso ti capisco ;)
Esatto :)
ma non è tantissimo 9ms? :mbe:
...spero che non sia per un'esecuzione sola... :fagiano:
9ms impiega tutto l'algoritmo al cui interno ci sono diverse migliaia di valori assoluti
La prossima volta spiega bene il problema allora.
46KB*4 di memoria non sono nulla
4GB*4 potrebbero esserlo.
Nelle valutazioni quantitative devi anche considerare che quella lookup table sono sempre 200KB di cache che usi solo per il calcolo del valore assoluto, e che potrebbero essere usati per altro.
Ti ringrazio per la precisazione. Anche se prendesse 200KB di cache preferisco la velocità. :)
ho fatto una semplicissima prova in ruby sul mio A64 3000+@4000+ (2520mhz e RAM 186 mhz se non sbaglio):
startTime = Time.new
for i in 0..1000000
a = -2.abs
end
puts Time.new - startTime
risultato... 350 msec per un milione di iterazioni....
e ruby è notoriamente molto lento come implementazione (ho usato la versione 1.8.6 non la ben + veloce 1.9.0 :p)
Occhio, non conosco Ruby, ma il C++ in quel caso avrebbe saltato la valutazione dell'ABS.
Avrebbe messo direttamente +2 nella variabile a.
Anzi, se tutto va bene, dato che la variabile a non e' usata, avrebbe proprio saltato tutta la riga...
Ti ringrazio per la precisazione. Anche se prendesse 200KB di cache preferisco la velocità. :)
Chiaro.
Quello che dico e' che nel complesso mangiare 200KB di cache potrebbe rallentare il sistema. Valuta bene.
Poi a me vedere un array che nella cella 1 c'e' scritto 1
nella cella 2 c'e' scritto 2
nella cella X c'e' scritto X
Mi fa irritare un po'... ma passa subito non preoccuparti.
Chiaro.
Quello che dico e' che nel complesso mangiare 200KB di cache potrebbe rallentare il sistema. Valuta bene.
Poi a me vedere un array che nella cella 1 c'e' scritto 1
nella cella 2 c'e' scritto 2
nella cella X c'e' scritto X
Mi fa irritare un po'... ma passa subito non preoccuparti.
:)
^TiGeRShArK^
13-02-2008, 20:51
Occhio, non conosco Ruby, ma il C++ in quel caso avrebbe saltato la valutazione dell'ABS.
Avrebbe messo direttamente +2 nella variabile a.
Anzi, se tutto va bene, dato che la variabile a non e' usata, avrebbe proprio saltato tutta la riga...
ah non ho idea di come si comporti l'interprete... :fagiano:
così:
startTime = Time.new
b = 0
for i in 0..1000000
a = -2.abs
b = a + 1
end
c = b
puts Time.new - startTime
mi sa 750 msec per 1 milione di iterazioni...
e così:
startTime = Time.new
b = 0
c = 1
for i in 0..1000000
a = -2.abs
b = a + 1
c = b.abs
end
d = c
puts Time.new - startTime
930msec...
quindi ad occhio direi che il calcolo lo faceva sempre già nel primo giro :p
Vedi, non sapevo proprio cosa fosse Ruby.
Se avessi saputo che e' interpretato e non compilato non avrei neppure fatto l'osservazione.
amedeoviscido
14-02-2008, 11:40
Figata, conoscevo il codice a 32 bit...
CWD
XOR AX,DX
SUB AX,DX
Scommetto che la maggior parte di voi non sa nemmeno come funziona... che figata, mi ricorda i tempi delle superiori quando stupii il prof che si ostinava a fare:
CMP AX,0
JGE SKIP
NEG AX
SKIP:
fiiiigaaataaaaa
variabilepippo
14-02-2008, 12:22
Figata, conoscevo il codice a 32 bit...
Scommetto che la maggior parte di voi non sa nemmeno come funziona...
Quote:CWD
XOR AX,DX
SUB AX,DX
Quello proposto da te non mi sembra codice "a 32 bit"... :rolleyes:
Meglio questo:
cdq
xor eax, edx
sub eax, edx
amedeoviscido
14-02-2008, 17:07
Hem sorry intendevo 16 bit :D
cdimauro
15-02-2008, 07:31
Guarda ti faccio un piccolo schema:
Funzione abs di libreria => 16ms
Mia funzione citata nel primo post => 14ms
Quadrato e poi divisione => 13ms
LUT => 9ms
Se consideri che tale algoritmo lo voglio fare in real-time anche se formalmente più brutto preferisco la LUT. :)
Per pura curiosità, potresti testare il tempo d'esecuzione di questa:
int __inline absasm(int x)
{
__asm{
mov edx,eax
neg eax
cmovs eax,edx
}
}
?
P.S. La tua LUT si può dimezzare come spazio occupato.
Appena possibile provo la tua funzione poi ti faccio sapere... La LUT certo che si può dimezzare però diminuisco la velocità nell'accesso in memoria... :)
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.