Vediamo questo caso di studio, "1 billion row challenge": il contest di per sé è semplice ovvero inizializzare un array con un miliardo di elementi (che sia random oppure import da file), calcolare minimo, massimo e media. Il punto è rendere l'algoritmo efficiente e riguardo a questo ci ho fatto delle considerazioni a parte. Ho scritto il codice in linguaggio Python.
Vediamo quindi gli aspetti principali:
- array che viene inizializzato in modo random, fra un valore minimo di -9999 e un valore massimo di +9999
- per risparmiare operazioni, calcoliamo la media inizialmente come somma e alla fine dividiamo il valore per il numero di elementi (non avrebbe senso fare avg/N ad ogni singola operazione); calcoliamo poi minimo e massimo, volutamente inizializzati agli estremi opposti
- RAM vs CPU: questo è l'aspetto chiave, infatti:
- creare
V=np.zeros(1000000000)
è il metodo più semplice ma occupa moltissima memoria RAM (un array da un miliardo di elementi, generalmente Int32 significa 32/8=4 byte
per ogni numero intero, un miliardo di elementi signifca 4 GB occupati in memoria solo da questo array)
- quindi possiamo suddividere il problema ovvero creare un certo numero K di volte un array di dimensione N, tale che
N*K=1000000000
- secondo questo principio, vediamo che computazionalmente è più efficiente, veloce ripetere poche volte tutta la procedura (inizializzazione array random, calcolo di media, massimo, minimo) ma occupa più RAM, dato che significa aver allocato un array di dimensione più grande; viceversa, ripetere l'operazione tante volte su un array più piccolo, occupa meno memoria RAM ma a discapito della velocità complessiva, quindi va trovato il giusto compromesso
Vediamo quindi i risultati, facendo variare i due parametri Nmax e Kmax.
- 109 = 5000 volte array da 200000 elementi: tempo totale di esecuzione (media su più prove) 650 secondi (in realtà per comodità valori interpolati x100)
- 109 = 20000 volte array da 50000 elementi: tempo totale di esecuzione (media su più prove) 670 secondi
- 109 = 40000 volte array da 25000 elementi: tempo totale di esecuzione (media su più prove) 680 secondi
Il tempo di esecuzione in questi casi non varia moltissimo, ma rende comunque l'idea. Il concetto base quindi è questo: suddividere l'array, ripetendo ciclicamente le operazioni consente di risparmiare spazio in memoria (RAM) a discapito di un tempo di esecuzione complessivo più elevato. A seconda delle necessità, si può valutare quindi il giusto compromesso.
Ecco il codice in Python, in questo caso con i valori Nmax=25000 e Kmax=40000.
import numpy as np
import random as rd
import time
V=np.zeros(25000)
Nmax=25000
Kmax=40000 # Nmax*Kmax = 1e9
MIN=-9999
MAX=9999
avg=0
min=MAX # init
max=MIN # init
start=time.time()
# compromesso RAM - CPU // k piccolo più RAM occupata ma più velocità e viceversa
for k in range(Kmax):
for i in range(Nmax):
V[i]=rd.randint(MIN,MAX)
for i in range(Nmax):
avg=avg+V[i]
if V[i]<min:
min=V[i]
elif V[i]>max:
max=V[i]
avg/=1e9
end=time.time()
print("time=",end-start,"s")
print("avg=",avg)
print("max=",max)
print("min=",min)