Galleggiante galleggiante di precisione in Python

Question

Ho bisogno di implementare un algoritmo di programmazione dinamica per risolvere il problema del venditore ambulante nel tempo che batte la ricerca della forza bruta per calcolare le distanze tra i punti. Per questo ho bisogno di indicizzare i sottoproblemi per dimensione e il valore di ogni sottoproblema sarà un float (la lunghezza del tour). Comunque tenere la matrice in memoria richiederà circa 6 GB di RAM se utilizzo i float python (che in realtà hanno una precisione doppia) e quindi per provare a dimezzare quella quantità (ho solo 4 GB di RAM) avrò bisogno di usare float di precisione singola. Comunque non so come posso ottenere float a precisione singola in Python (sto usando Python 3). Qualcuno potrebbe dirmi dove posso trovarli (non sono stato in grado di trovare molto su questo su internet). Grazie.

EDIT: noto che numpy ha anche un tipo float16 che consente un risparmio ancora maggiore di memoria. Le distanze tra i punti sono intorno a 10000 e ci sono 25 punti unici e la mia risposta deve essere al numero intero più vicino. Float16 fornirà una precisione sufficiente o devo usare float32?

Answer 1

Come primo passo, è necessario utilizzare una matrice NumPy per memorizzare i dati anziché un elenco Python.

Come si osserva correttamente, un float Python utilizza la doppia precisione internamente e il valore a doppia precisione sottostante a un float Python può essere rappresentato in 8 byte. Ma su una macchina a 64 bit, con l'implementazione di riferimento CPython di Python, un oggetto Python float occupa 24 byte di memoria: 8 byte per il valore di precisione doppia sottostante, 8 byte per un puntatore al tipo di oggetto, e 8 byte per un conteggio dei riferimenti (usato per la garbage collection). Non esiste un equivalente dei tipi "primitivi" di Java o dei tipi "value" di .NET in Python: tutto è in scatola. Ciò semplifica la semantica del linguaggio, ma significa che gli oggetti tendono a essere più grassi.

Ora, se stiamo creando un elenco Python di float oggetti, c'è l'overhead aggiunto della lista stessa: un puntatore oggetto di 8 byte per Python float (ancora assumendo una macchina a 64 bit qui). Quindi, in generale, un elenco di oggetti n Python float ti costerà oltre 32n byte di memoria. Su una macchina a 32 bit, le cose vanno un po 'meglio, ma non molto: i nostri oggetti float prenderanno 16 byte ciascuno, e con i puntatori di lista useremo 20n byte di memoria per un elenco di float s di lunghezza n. (Caveat:. Questa analisi funziona non proprio nel caso che l'elenco si riferisce alla stesso Python float oggetto da più indici delle liste, ma che non è un caso particolarmente comune)

Al contrario, una matrice NumPy di I galleggianti a doppia precisione n (utilizzando NumPy's float64 dtype) memorizzano i dati in formato "compresso" in un singolo blocco di dati di 8n byte, quindi, consentendo i metadati dell'array, il requisito di memoria totale sarà leggermente superiore a 8n byte.

Conclusione: basta passare da un elenco Python a un array NumPy per ridurre le esigenze di memoria di circa un fattore 4. Se ciò non è ancora sufficiente, potrebbe essere opportuno prendere in considerazione la riduzione della precisione da doppio a singolo precisione (NumPy's float32 dtype), se questo è coerente con le vostre esigenze di precisione.Il tipo di dati di NumPy float16 richiede solo 2 byte per float, ma registra solo circa 3 cifre decimali di precisione; Sospetto che sarà quasi inutile per l'applicazione che descrivi.

Answer 2

È possibile provare il tipo c_float dalla libreria standard ctypes. In alternativa, se sei in grado di installare pacchetti aggiuntivi, potresti provare il pacchetto numpy. Include il tipo float32.