Quali ambienti di programmazione possono essere utilizzati per illustrare e confrontare la complessità dello spazio non ottimizzata di un algoritmo?

Question

Quali ambienti di programmazione possono essere utilizzati per illustrare e confrontare la complessità dello spazio non ottimizzata di un algoritmo?

#1 da (0 voti)
#2 da (0 voti)

-1

Quale linguaggio di programmazione insieme all'implementazione e al compilatore posso usare per studiare la complessità dello spazio pura e non ottimizzata di un algoritmo arbitrario? E quali metodi posso usare per farlo?

Ad esempio, Scheme ed Elixir implementano l'ottimizzazione delle chiamate tail. Se l'algoritmo che ho scritto fosse ricorsivo, qualunque metodo potessi usare per ottenere nello stack potrebbe mostrare O(1) di complessità spaziale.

Un altro esempio, NodeJS implementa la garbage collection. Per qualsiasi struttura di dati che inizializzo nel mio algoritmo, non saprò se sono allocate nello stack o nell'heap, quindi chiamare il metodo process.memoryUsage() non mi consentirà di eseguire il benchmark in modo coerente.

Se posso selezionare un ambiente per analizzare la complessità dello spazio di base di un algoritmo, posso quindi confrontarlo con altri ambienti e quindi scegliere lo strumento giusto per il lavoro.

algorithms memory memory-usage big-o algorithm-analysis

posta Ryan Jarvis 15.10.2016 - 18:31

fonte

2 risposte

Leggi altre domande sui tag algorithms memory memory-usage big-o algorithm-analysis

Sovrascrivi la memoria usando le classi quando si usano gli elenchi in python Come si adattano gli array di k-length al numero di array più grandi?

score 0 · Answer 1

I linguaggi di programmazione e le implementazioni non esistono nel vuoto. Sono il prodotto di varie ottimizzazioni che potrebbero essere applicate in qualsiasi momento senza che tu lo sappia e, in caso contrario, hai a che fare con un linguaggio e un'implementazione ingenui e le loro prestazioni non saranno comunque ottimali.

In altre parole, il fatto che Scheme usi Tail Call Optimization è una funzione , non un bug. Devi tenerne conto come parte della tua complessità spaziale. Se vuoi sapere come è fatto senza TCO, devi sconfiggerlo (rendendo la chiamata ricorsiva non una coda), o usare la tua pila invece della lingua.

Per l'utilizzo della memoria, ti suggerisco di contare semplicemente il numero di oggetti che il tuo algoritmo utilizza, piuttosto che cercare di ottenere l'utilizzo di memoria grezza dal sistema operativo.

Non dimenticare che Big O può essere calcolato senza mai eseguire il tuo programma.

score 0 · Answer 2

L'ambiente migliore è probabilmente carta e matita.

Che mettere da parte, se stai cercando uno strumento per dimostrare un comportamento diverso sull'hardware del mondo reale (ma in ambiente sintetico, cioè non ottimizzato ecc.), cioè accademico, vai per qualcosa che è

abbastanza flessibile da consentire tutti i tuoi esperimenti
abbastanza facile da programmare (cioè supporto per concetti di livello superiore)
fornisce il controllo sull'ottimizzazione in fase di compilazione / runtime
mantiene la misurazione pulita, ovvero non viene fornita con spese generali imprevedibili
fornisce funzionalità per misurare l'utilizzo di memoria / tempo

Nel mio libro, il C ++ si adatta al progetto. Ovviamente molto versatile, ha anche molte librerie disponibili che supportano i tuoi esperimenti (non preoccuparti di implementare il vettore o l'hashtable tu stesso). E la maggior parte dei compilatori ti lascerà andare con (quasi?) L'ottimizzazione zero.

Se stai guardando Java, ad esempio, potrebbe essere più facile scrivere il codice, ma il livello di ottimizzazione non può essere controllato. Aggiungi garbage collection a caso, compilation JIT, ecc. E ti rendi conto che devi prestare molta attenzione quando interpreti le misure.

Se lo fai per motivi pratici, fallo sulla piattaforma che conta davvero. Non ha senso dimostrare che un algoritmo funziona in C ++ su una macchina Windows mentre la libreria JavaScript non funziona su un telefono cellulare con un browser specifico.