Algoritmo di conversione da numero intero a stringa più veloce del 34% | di Tigran Hayrapetyan | Dicembre 2023 | Intelligenza-Artificiale

Proporrò un altro algoritmo, che accelererà di circa la stampa dei numeri interi 25-38% per numeri interi a 32 bit e dintorni 40-58% per numeri interi a 64 bit. L’idea è: cosa succede se scegliamo le cifre da un dato numero intero? N non da destra a sinistra, ma da sinistra a destra? Quindi prima otterremo la sua cifra più significativa, poi la successiva cifra significativa e così via, finché rimarrà solo la cifra meno significativa. Fare questo diventa un po’ difficile se non conosciamo il conteggio delle cifre di N in anticipo, ma mettiamo da parte per ora la questione e assumiamo che sappiamo già che esistono l cifre dentro N.

Come otterremo allora la cifra più significativa? Ancora una volta usando la divisione intera, ma questa volta come:

“cifra:= N / 10^(L-1)”

E come lo tireremo fuori? Nper poter proseguire con la restante parte? Dopo aver conosciuto il valore della cifra più significativa è ‘D‘, possiamo fare la seguente sottrazione:

“N := N — d*10^(L-1)”

Successivamente ripeteremo le operazioni di divisione e sottrazione, fino a N diventerà un numero intero di 1 cifra (cioè nell’intervallo (0..9)) e infine stamperà anche quella cifra. Vediamo come funzionerà l’algoritmo per il caso “N = 6’129”. Nota, ha 4 cifre, quindi qui iniziamo con “l=4”:

Si potrebbe sostenere che il calcolo delle diverse potenze di 10 richiede più tempo rispetto alla divisione di numeri interi o al calcolo del resto. E questo sarà assolutamente corretto tranne che per un dettaglio: possiamo precalcolare tutte le potenze di 10 necessarie e usarle durante l’intera esecuzione del programma. Per gli interi a 32 bit, ci sono solo 10 diverse potenze di 10, e per gli interi a 64 bit, ci sono 20 potenze di 10. Quindi mantenerli tutti precalcolati in memoria non sarà un problema.

Quindi cosa abbiamo in generale? Per stampare una cifra di N con il mio algoritmo facciamo:

1 divisione intera,
1 moltiplicazione e
1 sottrazione,

rispetto agli algoritmi standard:

1 calcolo del resto e
1 divisione intera.

Nella prossima sezione vedremo che il mio approccio è effettivamente migliore, perché la moltiplicazione e la sottrazione insieme richiedono meno tempo della CPU rispetto al calcolo del resto. Il confronto sperimentale del consumo di tempo di tali operazioni aritmetiche è stato presentato nel capitolo 2.

Lo pseudocodice della parte principale del mio algoritmo potrebbe assomigliare a questo:

var powers_of_10(0 .. 10) : Array of Integers 
= { 1, 10, 100, 1'000, ..., 100'000'000, 1'000'000'000 }
// Precalculated powers of 10, which will be used during print
var result(0 .. 25) : Array of Characters  // Assume at most 25 characters
// The procedure takes integer 'N' to be printed, and fills its
// decimal characters into the 'result' array.
procedure print( N: Integer )
L := calculate_digits_count( N )
i := 0  // Index over 'result' array
while L > 0
digit := ⌊ N / powers_of_10( L-1 ) ⌋  // Obtain left-most digit
result( i ) := '0' + digit   // Write it to the 'result' array
N := N – digit * powers_of_10( L-1 )  // Calculate remaining part
L := L-1  // Adjust its count of digits accordingly
i := i+1
result( i ) := '\0'  // Append the terminating 'null' character

Poiché il mio algoritmo stampa le cifre di N da sinistra a destra, voglio chiamarla “stampante da sinistra a destra” o brevemente “stampante LR”.

L’unica cosa che resta ancora è trovare in modo efficiente l — conteggio delle cifre decimali di N. E fortunatamente per noi, anche in questo caso la serie precalcolata delle potenze di 10 ci aiuterà. Possiamo semplicemente scorrere quell’array dalle potenze piccole a quelle più grandi, fino a trovare tale potenza 10^l che sarà maggiore di N. Poi l’esponente l rappresenterà esso stesso il conteggio delle cifre in N.

Ad esempio, ottenendo il conteggio delle cifre per “N = 23’504″ apparirà come segue:

Lo pseudocodice di quella funzione potrebbe essere simile a:

// The function takes integer 'N' and returns count of its digits.
function calculate_digits_count( N: Integer ) : Integer
// Check case of numbers with maximal count of digits
if N >= powers_of_10( 9 )  // Compare with maximal power of 10
return 10  // Count of digits for such numbers
// Regular case
L := 0
while N >= powers_of_10( L ) 
L := L+1
return L

Con queste 2 parti forniamo l’algoritmo completo per convertire i numeri interi in stringhe.

Notare che la “stampante LR” riporta le cifre di N da sinistra a destra, non è necessario effettuare alcuna inversione alla fine. Inoltre, a differenza dell’ottimizzazione 1 esistente, qui manteniamo la possibilità di specificare se è in memoria la prima cifra da convertire N dovrebbe essere posizionato.

La “stampante LR” può essere utilizzata per stampare numeri in qualsiasi base (non solo in base 10). Per fare ciò dovremo solo sostituire le potenze precalcolate di 10 con le potenze precalcolate della nuova base.

L’implementazione della “stampante LR” nel linguaggio C++ è disponibile su GitHub all’indirizzo (3).

Ottimizzazione 2 per “stampante LR”

Il mio algoritmo può essere migliorato con la seconda ottimizzazione descritta nella sezione “Ottimizzazioni esistenti” e documentata in (1) e (2). Se fatto, invece di stampare il numero specificato per 1 cifra in un singolo passaggio, lo stamperemo per 2 cifre in un singolo passaggio.

Vediamo come andrà ad esempio sul numero”N = 4’610’937”. Qui l=7, e iniziamo dividendo N oltre 10^(L-2)=10’000 questa volta:

Abilitandolo, spenderemo:

1 divisione intera,
1 moltiplicazione e
1 sottrazione,

per 2 cifre del numero immesso.

Anche in questo caso, le cifre verranno ottenute nel loro ordine naturale, da sinistra a destra, quindi non è necessario invertirle alla fine.

L’implementazione della “stampante LR” con la seconda ottimizzazione abilitata è disponibile anche su GitHub all’indirizzo (3).