34% più veloce algoritmo di conversione da intero a stringa

Algoritmo di conversione da intero a stringa 34% più veloce

Siamo abbastanza veloci nella stampa dei numeri interi?

1. Introduzione

Nella programmazione informatica, la conversione di un numero intero in una stringa è un’operazione comune, che dovrebbe essere eseguita ad esempio prima di stampare il numero intero sullo schermo o stamparlo su qualsiasi tipo di file di testo, come *.xml, *.json, *.csv, *.txt, ecc…

È risaputo che i numeri interi (così come tutto il resto) sono memorizzati nella memoria del computer in formato binario, ossia come sequenze di 0 e 1. Ad esempio:

• il numero 12 viene rappresentato in memoria come “1100”,
• e il numero 29 viene rappresentato come “11101”.

Questo è il motivo per cui è necessaria tale conversione ogni volta che vogliamo renderla leggibile dall’umanità, nel formato decimale.

• Previsioni di abbandono evolutive Navigare tra interventi e riaddestramento
• 9 Modi in cui l’IA sta potenziando la sicurezza dei data center
• Perché le GPU sono ottime per l’IA

In questa storia intendo:

• fare una panoramica dell’algoritmo standard utilizzato per tale conversione,
• osservare le ottimizzazioni esistenti,
• progettare il mio algoritmo e
• presentare il confronto sperimentale tra i due.

Vedremo che in media, il mio algoritmo è più veloce del 25-38% per i numeri interi a 32 bit e del 40-58% per i numeri interi a 64 bit, rispetto all’algoritmo standard ottimizzato. La sua implementazione nel linguaggio C++ può essere trovata su GitHub, come indicato alla fine.

Ovviamente, se l’applicazione stampa solo alcuni numeri interi durante la sua vita, l’algoritmo responsabile della conversione in stringhe non sarà mai il collo di bottiglia. Ma per casi in cui l’applicazione stampa tonnellate di dati su file di testo, l’efficienza dell’algoritmo di conversione diventa importante. Quando si lavora in campi come la Scienza dei dati o l’Apprendimento automatico, la necessità di convertire molti numeri interi in stringhe si presenta ad esempio nell’esportare un dataset in un file di testo come *.csv o *.json.

2. L’algoritmo standard di conversione

Poiché la conversione di numeri interi in stringhe è un’operazione comune, un algoritmo apposito è implementato in qualsiasi linguaggio di programmazione moderno, sia come parte del linguaggio stesso che come parte delle sue librerie standard. E l’algoritmo è quasi ovunque lo stesso: si basa sulla determinazione e sull’estrazione ripetuta dell’ultima cifra del numero intero e sulla continuazione con la sua parte rimanente.

Per ottenere l’ultima cifra di un dato intero N, basta calcolare il resto della sua divisione per 10:

“cifra := N mod 10”,

e per estrarla, si effettua la divisione intera stessa:

“N := N / 10”.

Si noti che, in questa storia, quando si dividono due numeri interi, si presume che venga presa solo la parte intera del risultato.

Come esempio di algoritmo completo, quando si stampa il numero “N = 2’167”, verranno effettuate le seguenti operazioni:

Note, quando si tratta di interi a una cifra (cioè nell’intervallo [0..9]), possiamo inviarli direttamente per la stampa, poiché i caratteri corrispondenti sono già fissati per ciascuna di quelle 10 cifre. E il resto della divisione per 10 è sempre un intero a una cifra.

Possiamo anche notare che questo algoritmo riporta le cifre di N in ordine inverso (qui abbiamo una sequenza di cifre ‘7’, ‘6’, ‘1’, ‘2’, invece di avere ‘2’, ‘1’, ‘6’, ‘7’), quindi c’è bisogno di invertire la sequenza prodotta alla fine.

Riassumendo, il suo pseudo-codice sarà così:

var result[0 .. 25] : Array di Caratteri  // Supponiamo al massimo 25 caratteri// La procedura prende l'intero 'N' da stampare e lo inserisce// le cifre decimali in un array 'result'procedura stampa( N: Integer )    i := 0  // Indice sull'array 'result'    mentre N > 0        result[ i ] := '0' + (N mod 10)  // Prende l'ultima cifra        N := ⌊ N / 10 ⌋   // Prende l'ultima cifra        i := i+1    result[ i ] := '\0'  // Aggiunge il carattere 'null' terminale    inverti l'array result[0 .. i-1]

L’algoritmo descritto è semplice e possiamo implementarlo facilmente in 3-4 righe di codice. Ma il suo punto debole è che utilizza 2 operazioni relativamente costose: la divisione intera e il calcolo del resto intero, per ogni cifra della notazione decimale di N. È noto che la divisione intera e il calcolo del resto richiedono in media 4-5 volte più tempo rispetto all’addizione, alla sottrazione o addirittura alla moltiplicazione di 2 interi. Qui possiamo osservare il benchmark temporale delle operazioni aritmetiche menzionate:

Gli esperimenti sono stati effettuati con Google Benchmark, con il seguente sistema:

CPU: Intel Core i7–11800H @ 2.30GHzRAM: 16,0 GBSO: Windows 11 Home, 64 bitCompiler: MSVC 2022 ( /O2 /Ob2 /MD /GR /Gd )

Vediamo se esistono metodi più veloci per la stampa di interi…

3. Ottimizzazioni esistenti

Ottimizzazione 1

Una comune ottimizzazione per l’algoritmo descritto consiste nell’eliminare l’ultimo passaggio di invertire la sequenza di cifre prodotta. Il trucco è ben presentato ad esempio in [1]. Con questa ottimizzazione scriveremo le cifre nel buffer direttamente nel loro ordine corretto. E poiché l’algoritmo stesso riporta le cifre dell’intero dato N da destra a sinistra, le scriveremo anche nel buffer da destra a sinistra.

Il pseudo-codice con questa ottimizzazione sarà così:

var result[0 .. 25] : Array di Caratteri  // Supponiamo al massimo 25 caratteri// La funzione prende l'intero 'N' da stampare e restituisce la posizione // del suo primo carattere convertito nell'array 'result'.funzione stampa( N: Integer ) : Integer    result[ 25 ] := '\0'  // Posta il carattere 'null' terminale alla fine    i := 25  // Indice sull'array 'result'    mentre N > 0        i := i-1  // Qui andiamo a sinistra, per posizionare la prossima cifra        result[ i ] := '0' + (N mod 10)  // Prende l'ultima cifra        N := ⌊ N / 10 ⌋   // Prende l'ultima cifra    restituisci i  // Posizione da cui inizia l'intero convertito

Nota, in questo e in tutti gli altri pseudo-codici all’interno di questa storia, non affrontiamo il caso di stampare il numero “0”. Secondo tutti gli algoritmi scritti, “0” risulterà come una sequenza senza cifre, ed è per questo che in quasi tutti gli algoritmi di stampa, la stampa del “0” viene effettuata in un ramo separato. Salteremo semplicemente quel ramo qui per compattezza.

Un altro piccolo vantaggio di questa ottimizzazione è che non è necessario scrivere il carattere di terminazione nullo dopo ogni conversione. Invece, possiamo scriverlo solo una volta nell’ultima posizione del buffer, poiché la posizione fisica dell’ultima cifra di N è fissa in anticipo e sarà sempre la penultima posizione nel buffer.

Lo svantaggio di questa ottimizzazione è che la posizione del primo carattere diventa variabile, in quanto dipende dal numero di cifre che ha l’intero N.

Tuttavia, praticamente, questo non diventa un problema perché gli interi convertiti vengono spesso inviati tempestivamente su un file di testo o sullo schermo, quindi non rimangono in memoria per molto tempo. E per tali scopi non è necessario che le cifre convertite vengano scritte a partire da una posizione specificata in anticipo nella memoria.

Ottimizzazione 2

La prossima ottimizzazione riguarda l’uso delle operazioni di divisione intera e di calcolo del resto per ottenere 2 cifre di N in un unico passaggio. Questo trucco è anche ben documentato in [1] e [2]. A questo scopo, anziché calcolare ripetutamente

“cifra := N mod 10”, seguito da “N := N / 10”,

calcoleremo:

“cifre := N mod 100”, seguito da “N := N / 100”,

che ci darà le ultime 2 cifre di N e poi le taglierà entrambe.

Si noti che, per poter stampare in modo efficiente quelle 2 cifre ottenute, qui dovremmo aver preparato un array di lunghezza 100 (con indici da 0 a 99, corrispondenti a tutti i possibili resti “N mod 100”), dove i valori saranno coppie di caratteri, a partire da “00”, “01”, “02”, … fino a “98”, “99”.

All’interno di questa ottimizzazione, il numero di divisioni intere e operazioni di calcolo del resto viene ridotto di quasi 2 volte.

Concludendo questa parte, vorrei attirare la vostra attenzione sul fatto che, anche con entrambe le ottimizzazioni descritte abilitate, dobbiamo comunque effettuare un numero di divisioni intere e operazioni di calcolo del resto, proporzionale al numero di cifre nell’intero N dato.

4. Il mio algoritmo

Sto per proporre un altro algoritmo che accelererà la stampa di interi di circa il 25-38% per gli interi a 32 bit e circa il 40-58% per gli interi a 64 bit. L’idea è: e se scegliessimo le cifre dell’intero N non dalla destra alla sinistra, ma dalla sinistra alla destra? Quindi all’inizio otterremo la cifra più significativa, quindi la cifra successiva più significativa e così via, fino a quando rimarrà solo la cifra meno significativa. Fare ciò diventa un po’ difficile se non conosciamo in anticipo il numero di cifre di N, ma mettiamola da parte per ora e assumiamo che sappiamo già che ci sono L cifre in N.

Come otterremo quindi la cifra più significativa? Di nuovo usando la divisione intera, ma questa volta come:

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

E come la prenderemo da N, per poter continuare con la parte rimanente? Dopo aver conosciuto il valore della cifra più significativa che è ‘d’, possiamo fare la seguente sottrazione:

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

In seguito ripeteremo le operazioni di divisione e sottrazione finché N diventerà un numero intero di 1 cifra (cioè nell’intervallo [0..9]), e infine stamperemo anche quella cifra. Vediamo come funzionerà l’algoritmo per il caso “N = 6’129”. Nota che ha 4 cifre, quindi iniziamo con “L=4”:

Potresti sostenere che il calcolo di diverse potenze di 10 richiede più tempo rispetto alla divisione intera o al calcolo del resto. E questo sarà assolutamente corretto tranne 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 tenerle tutte precalcolate 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 all’algoritmo standard che fa:

1 calcolo del resto e 1 divisione intera.

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

Il pseudocodice della parte principale del mio algoritmo potrebbe essere così:

var powers_of_10[0 .. 10] : Array of Integers   = { 1, 10, 100, 1'000, ..., 100'000'000, 1'000'000'000 }  // Potenze di 10 precalcolate, che verranno utilizzate durante la stampavar result[0 .. 25] : Array of Characters  // Assumiamo al massimo 25 caratteri// La procedura prende l'intero 'N' da stampare e riempie i suoi// cifre decimali nell'array 'result'.procedura stampa( N: Integer )    L := calcola_numero_cifre( N )    i := 0  // Indice sull'array 'result'    while L > 0        cifra := ⌊ N / powers_of_10[ L-1 ] ⌋  // Ottieni la cifra più a sinistra        result[ i ] := '0' + cifra   // Scrivila nell'array 'result'        N := N – cifra * powers_of_10[ L-1 ]  // Calcola la parte rimanente        L := L-1  // Adatta il conteggio delle cifre        i := i+1    result[ i ] := '\0'  // Aggiungi il carattere terminatore 'null'

Poiché il mio algoritmo stampa le cifre di N da sinistra a destra, voglio chiamarlo “Stampante da sinistra a destra” o semplicemente “Stampante SR”.

L’unica cosa che resta da fare è trovare in modo efficiente L, ovvero il numero di cifre decimali di N. E fortunatamente per noi, l’array precalcolato delle potenze di 10 ci aiuterà anche in questo caso. Possiamo semplicemente iterare su quell’array dalle potenze più piccole a quelle più grandi, fino a trovare la potenza 10^L che sarà maggiore di N. L’esponente L rappresenterà il numero di cifre di N.

Ad esempio, il calcolo del numero di cifre per “N = 23’504” sarà così:

Il pseudocodice di quella funzione potrebbe essere:

// La funzione prende l'intero 'N' e restituisce il numero delle sue cifre.funzione calcola_numero_cifre( N: Integer ) : Integer    // Controlla il caso dei numeri con il numero massimo di cifre    if N >= powers_of_10[ 9 ]  // Confronta con la massima potenza di 10        restituisci 10  // Numero di cifre per questi numeri    // Caso normale    L := 0    while N >= powers_of_10[ L ]         L := L+1    restituisci L

Con queste 2 parti stiamo fornendo un algoritmo completo per convertire gli interi in stringhe.

Nota che poiché la “Stampante SR” riporta le cifre di N da sinistra a destra, non c’è bisogno di invertire alla fine. Inoltre, a differenza dell’ottimizzazione esistente 1, qui manteniamo la possibilità di specificare dove in memoria deve essere posizionata la prima cifra di N convertito.

La “Stampante SR” può essere utilizzata per stampare numeri in qualsiasi base (non solo la base 10). Per farlo, dovremo solo sostituire le potenze di 10 precalcolate con le potenze precalcolate della nuova base.

L’implementazione della “Stampante SR” nel linguaggio C++ può essere trovata su GitHub a [3].

Ottimizzazione 2 per la “Stampante SR”

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 dato per un cifra alla volta, lo stampiamo in due cifre in un solo passaggio.

Vediamo come funzionerà ad esempio per il numero “N = 4’610’937”. Qui L=7, e iniziamo dividendo N per 10^(L-2)=10’000 questa volta:

Abilitando questa funzionalità, spenderemo:

1 divisione intera,1 moltiplicazione, e1 sottrazione,

per ogni 2 cifre del numero di input.

Qui ancora una volta, le cifre verranno ottenute nel loro ordine naturale — da sinistra a destra, quindi non è necessario invertirle alla fine.

L’implementazione del “LR printer” con la seconda ottimizzazione abilitata può essere trovata anche su GitHub a [3].

5. Confronto sperimentale con algoritmi esistenti

Fare un confronto sperimentale è essenziale per questo tipo di lavoro, quindi in questo capitolo presenterò i risultati del confronto tra i seguenti algoritmi di stampa interi:

• l’algoritmo standard con la prima ottimizzazione (denominato “Std”),
• il mio algoritmo “LR printer” (denominato “LR”),
• l’algoritmo standard con anche la seconda ottimizzazione (denominato “Std [2-dig]”), e
• il “LR printer” con la seconda ottimizzazione (denominato “LR [2-dig]”).

Ognuno di questi algoritmi viene testato sia su interi a 32 bit che a 64 bit, con un numero diverso di cifre dei numeri di input.

Stampa numeri in base=10:

I risultati della stampa in base=10 (il caso ordinario) sono:

Per gli interi a 32 bit, possiamo vedere che il vantaggio della “stampante LR” rispetto alla stampante standard è circa 30-38%. Il guadagno quando si stampa con la seconda ottimizzazione (stampa di 2 cifre in un solo passaggio) è inferiore, pari a 13-28%. Questo è del tutto prevedibile, poiché in generale compiamo solo 2 o 4 passaggi in quel caso.

Quando si tratta di stampare interi a 64 bit, le prestazioni del mio algoritmo sono ancora migliori. La “stampa LR” è circa 40-50% più veloce dell’algoritmo standard. E con la seconda ottimizzazione abilitata per entrambi, la “stampa LR” diventa 47-58% più veloce.

La percentuale nel titolo di questa storia è stata scelta considerando il caso più comune: quando siamo in base=10, lavorando con interi a 32 bit e assumendo che abbiano molte cifre. Per questo caso, il guadagno di prestazioni della “stampante LR” rispetto all’algoritmo standard era del 30-38%, quindi prendendo la media si avvicina al 34%.

Stampa numeri in base=3:

Vediamo anche se i risultati differiranno significativamente quando si stampa interi in un’altra base. Osserveremo la stampa in base=3:

Come possiamo vedere qui, per gli interi a 32 bit, il guadagno di prestazioni della “stampa LR” rispetto all’algoritmo standard è di circa 25-33%, che corrisponde generalmente alla differenza nelle prestazioni delle operazioni aritmetiche utilizzate.

E per gli interi a 64 bit, il guadagno di prestazioni della “stampa LR” è di circa 50-55% per numeri brevi (8 cifre) e 27-30% per numeri lunghi (36 cifre).

Osservazioni globali

In generale, la base in cui vengono stampati gli interi non influenza molto il guadagno di prestazioni relativo, poiché il numero di operazioni da eseguire durante la stampa è proporzionale al numero di cifre che hanno i numeri di input e non al numero di valori possibili che quelle cifre potrebbero avere.

Quasi sempre è il caso che maggiore è il numero di cifre, maggiore sarà il vantaggio della “stampa LR” (o della variante “stampa LR [2-dig]”) rispetto all’algoritmo di stampa standard (o alla sua variante “2-dig”). Ciò è anche chiaro, perché più cifre abbiamo, meno impatto avranno le istruzioni esterne al ciclo (come la chiamata di una funzione all’interno di un’altra o il posizionamento del carattere di terminazione nullo).

E in generale, quando si stampa interi a 64 bit, i risultati sono più impressionanti sia per la “stampa LR” che per la variante “stampa LR [2-dig]”.

Personalmente, ritengo che questi risultati siano piuttosto notevoli.

6. Conclusione

Abbiamo presentato un nuovo algoritmo per la conversione degli interi in stringhe, chiamato “stampa LR”. Risulta essere 25-38% più veloce per gli interi a 32 bit e 40-58% più veloce per gli interi a 64 bit rispetto all’algoritmo di conversione standard ottimizzato. Il nostro algoritmo può funzionare in qualsiasi base numerica (non solo nella base 10 ordinaria).

L’algoritmo che converte gli interi in stringhe non è mai un collo di bottiglia per le applicazioni che stampano solo pochi numeri durante la loro esecuzione. Ma per altri tipi di applicazioni, che generano automaticamente file di testo come *.csv, *xml o *.json, l’efficienza dell’algoritmo di conversione è importante. Questo è particolarmente vero se quei file di testo conterranno molti numeri, come nel caso dell’esportazione di grandi set di dati.

Grazie infinite per aver letto fino alla fine! Sarà un piacere leggere tutti i commenti qui sotto!

Esprimo il mio ringraziamento a David Ayrapetyan (https://www.linkedin.com/in/davidayrapetyan/), per la scrupolosa revisione della bozza di questa storia e per le numerose migliorie contestuali e correzioni grammaticali proposte.

Riconoscenza a Hayk Aslanyan (https://www.linkedin.com/in/haykaslanyan/), per la revisione tecnica della bozza e per le altre migliorie proposte.

Design delle illustrazioni di Asya Papyan: https://www.behance.net/asyapapyan

Se hai apprezzato la lettura di questa storia, puoi trovarmi su LinkedIn su: https://www.linkedin.com/in/tigran-hayrapetyan-88989b12/

Riferimenti

[1]: “Conversione da intero a stringa” – https://tia.mat.br/posts/2014/06/23/integer_to_string_conversion.html

[2]: “Tre consigli per l’ottimizzazione in C++” – https://www.facebook.com/notes/10158791579037200/

[3]: “Implementazione della stampante LR in linguaggio C++” – https://github.com/tigranh/lr_printer