So che se un calcolo prende il tempo lineare o linearithmic in base alla dimensione dell'input, è buono, e se impiega un tempo quadratico, allora non è così buono.
Tuttavia, per quanto riguarda l'utilizzo della memoria? Supponiamo che un programma prende un file come input e fa qualcosa con quel file. Va bene che l'utilizzo della memoria sia lineare nella dimensione del file o dovrebbe essere costante?
Se stai leggendo un file, è piuttosto difficile che sia una costante. In generale, queste regole non sono così rigide. Se i tuoi dati sono sempre molto piccoli, l'utilizzo di memoria / memoria quadratica (+) non è poi così male. Se è abbastanza buono per la tua situazione, è abbastanza veloce da non aver bisogno di refactoring.
In generale, però, vuoi il calcolo / memoria del tempo polinomiale perché qualsiasi cosa al di sopra di questo diventa troppo lenta con input anche relativamente piccoli.
Se l'utilizzo della memoria aumenta in modo lineare, allora c'è sempre la possibilità di esaurire la memoria, se l'input è molto grande. Quindi devi codificare tutto ciò scambiando alcune parti di dati sul disco (anche se potresti essere in grado di fare affidamento sul sistema operativo per farlo, ma in ogni caso rallenterà i tempi di elaborazione) o modificando il tuo modo di dati di processo. Quello che devi veramente chiedere è:
Is it likely that my input will be so large that the amount of memory necessary to process it will exceed the available memory?
Potrebbe esserci un modo per calcolare questo prima che inizierai l'elaborazione, probabilmente dipende dal problema specifico su cui stai lavorando.
... o acquista più memoria. ;)
Distinguerei due principali categorie di procedure / approcci:
Nel primo caso (es. lettura, modifica, salvataggio di un documento), l'utilizzo della memoria può essere lineare (o anche quadratico o più) nella dimensione dei dati di input: la dimensione maggiore per i dati di input sarà determinata dal quantità di memoria disponibile. Puoi utilizzare questo approccio quando i tuoi dati di input sono abbastanza piccoli rispetto alla memoria disponibile.
Nel caso dei secondi (ad esempio filtrando le informazioni rilevanti da un grande file di log) anche un utilizzo lineare della memoria può essere indesiderabile, dal momento che è facile esaurire la memoria non appena il flusso di input è abbastanza grande. Per problemi di categoria 2 accetterei solo una soluzione che può essere eseguita in memoria costante (stack e heap).
Se la tua soluzione rientra nella categoria 1 o 2 può dipendere dalla dimensione (prevista) dei dati. Prendi ad esempio l'ordinamento. Se è necessario ordinare 100 MB di stringhe, è sufficiente caricare i dati nella memoria principale e utilizzare un algoritmo in memoria. D'altra parte, se hai bisogno di ordinare 1 TB di dati, dovresti prendere in considerazione un algoritmo che utilizza la memoria principale costante (come alcune implementazioni di merge sort).
Il problema dell'input del file che potrebbe superare la memoria disponibile è un problema vecchio, ben noto e sostanzialmente risolto. Questo è ciò che un lettore di file buffered tratta. La dimensione del buffer è la quantità massima di memoria occupata dal file alla volta. L'idea è di leggere l'input fino alla dimensione massima del buffer, elaborare quel blocco, quindi leggere nel prossimo blocco. Questo rende costante l'utilizzo della memoria (nella peggiore delle ipotesi).
Che cosa succede se il tuo processo richiede più di quello che è disponibile in un blocco? Ci sono un sacco di algoritmi là fuori per affrontare anche questo genere di cose. Nel peggiore dei casi, potrebbe essere necessario un buffer più grande e possibilmente più memoria, ma dovrebbe comunque avere un valore massimo costante.
Leggi altre domande sui tag memory-usage