Il passaggio di una variabile con una grande quantità di dati costa molto tempo e memoria in Mathematica?

Sto codificando un algoritmo per la costruzione di un albero di suffissi in Mathematica basato sull'algoritmo di Ukkonen.Il passaggio di una variabile con una grande quantità di dati costa molto tempo e memoria in Mathematica?

La domanda che ho è, passerà la mia intera struttura ad albero (che ho memorizzato in una lista) ad una funzione per cercare, costa al mio programma molta memoria e tempo dato che devo usare alcune delle funzioni più volte nell'algoritmo?

Ad esempio, ho una funzione che cerca i figli di un nodo specifico e utilizzo la funzione Select per cercare l'intero albero.

getChildren[parentID_] := Select[tree, #[[3]] == parentID &];

Tuttavia ho bisogno di accedere all'albero, quindi è ragionevole passare l'intera struttura ad albero alla funzione? Dal momento che non sembra che ci sia un modo per rendere una variabile globale per l'intero notebook. O c'è un modo alternativo per aggirare questo?

fonte

2011-11-30 Steve

cosa si intende per "non v'è alcun modo per fare una variabile globale per l'intero notebook "? se si definisce 'tree = 5',' tree' è 5 ovunque nel contesto 'Global' (che è il default). è globale per impostazione predefinita, a meno che tu non stia cercando un altro comportamento. – acl

No, non costa più memoria per passare le espressioni. Come di consueto nei linguaggi funzionali, gli oggetti Mathematica sono immutable: non possono essere modificati, ma viene creato un nuovo oggetto quando li si trasforma utilizzando alcune funzioni. Questo significa anche che se non li trasformi, non vengono copiati, non importa quanto li passi tra le funzioni.

Dal punto di vista dell'utente, Mathematica espressioni sono alberi, ma credo che internamente questi sono memorizzati come directed acyclic graphs, vale a dire lo stesso sottoespressione può essere memorizzato una sola volta in memoria, indipendentemente da quante volte appare nella espressione completa (vedere ad esempio la pagina doc di Share[]).

Ecco un esempio per illustrare:

prima cosa, assicurarsi In/Out non occupano ulteriore memoria:

In[1]:= $HistoryLength = 0;

utilizzo di controllo della memoria:

In[2]:= MemoryInUse[] 
Out[2]= 13421756

Facciamo un espressione che occupa una notevole quantità di memoria:

In[3]:= s = [email protected][1000000]; 

In[4]:= MemoryInUse[] 
Out[4]= 17430260

Ora ripetete questa espressione un centinaio di volte ...

In[5]:= t = ConstantArray[s, 100];

... e notare che l'utilizzo della memoria aumenta a malapena:

In[6]:= MemoryInUse[] 
Out[6]= 18264676

ByeCount[] è fuorviante perché non riporta il reale memoria fisica utilizzata, ma la memoria che sarebbe stata utilizzata se le sottoespressioni comuni non fossero autorizzate a condividere la stessa memoria:

In[7]:= ByteCount[t] 
Out[7]= 400018040

Un punto interessante da notare: se si rimuove f[...] da s, e fare sia s e t una matrice numerica normale, allora questo la condivisione della memoria non accadrà, e l'utilizzo della memoria salterà ~ 400 MB.

Se si effettua tree una variabile globale o di un argomento di getChildren, non farà una differenza di utilizzo della memoria.

fonte

2011-11-30 10:58:12 Szabolcs

Ottima risposta! Per confermare ulteriormente l'immagine che hai descritto, uno può eseguire un assegnamento a qualche elemento in 't', ad esempio in questo modo:' t [[1, 1, 1]] = 2; ', e notiamo un salto immediato nel consumo di memoria corrispondente alla dimensione di una singola istanza' s'. La ragione per ciò che hai osservato con l'array numerico è sottile: questo è * solo * perché "Range" produce matrici compresse, * e * hai usato 'ConstantArray' (e non per esempio' Table'). Il punto è, 'ConstantArray' produrrà una matrice compressa da un array compresso, e non è possibile condividere la memoria in un array di grandi dimensioni, dal momento che è ... –

... basato sul layout di memoria C diretto. Dovresti aver usato '' ur = Developer'FromPackedArray [Range [1000000]]; t = ConstantArray [ur, {100}] '' o 'r = Range [1000000]; t = Table [r, {100}];', e avresti osservato la stessa condivisione di memoria, dal momento che il risultato non è pieno (significa che ci sono dei puntatori intermedi, e la condivisione è possibile - o almeno questa è la mia immagine di questo al momento). –

Modificherei leggermente la dichiarazione sull'immutabilità per qualcosa di simile: "non possono essere modificati, a meno che non siano memorizzati in una variabile" - Mathematica non è un linguaggio puramente funzionale e la mutabilità è possibile. –

A seguito di Szabolcs risposte, se si ha bisogno di modificare i dati si possono trovare a questa domanda il passaggio per riferimento utile:

simple question on passing data between functions

fonte

2011-11-30 11:16:19

Dato che hai sollevato questo argomento, lascia che ti accenni che mentre la risposta accettata a quella domanda funziona In generale, sconsiglio di usare "Non valutato" in questo modo, dal punto di vista della progettazione del programma: si dovrebbero progettare funzioni autonome, mentre la funzione funzionerà solo se l'utente non dimenticherà di racchiudere "Non valutato" attorno all'argomento, e inoltre, non c'è modo di cogliere questa omissione per la funzione stessa. IMO, gli attributi Hold sono fortemente preferiti a "Non Valutati" in casi come quello. –

@ Leonid - Ho modificato il collegamento per fare riferimento alla risposta. (Questa era la mia prima intenzione in ogni caso.) –

Grazie, ma la mia risposta non è anche una raccomandazione generale - la domanda era limitata dalle restrizioni della CDF dove gli attributi di Hold espliciti non possono essere collegati a un simbolo. Apparentemente, nessuno ancora qui su SO ha fatto una semplice domanda intitolata "Pass-by-reference in Mathematica" (o almeno ne sono ana- no), mentre avere una discussione SO per questo argomento sembra molto desiderabile. –

Il passaggio di una variabile con una grande quantità di dati costa molto tempo e memoria in Mathematica?

risposta

Problemi correlati