Come progettare un confronto delle prestazioni tra due strutture di dati

Dipende molto da cosa pensi di fare con la struttura dei dati. Se finirai col riempirlo con un determinato input strutturato, dovresti anche testarlo in questo modo.

Se non sai nulla dei tuoi futuri input e vuoi misurare le prestazioni medie, ricorda che la teoria della complessità calcola le prestazioni medie basate su input randomizzati (usando una distribuzione normale). Quindi, il test delle prestazioni nel caso medio dovrebbe includere molte esecuzioni con input casuali diversi.

A seconda delle strutture dati stesse, potresti anche essere interessato a confrontare determinate strutture di input che sono note per essere molto buone / cattive per una delle strutture dati. Tuttavia, la tua futura applicazione della struttura dati potrebbe quasi mai creare tali input, nel qual caso potresti ben ignorare il confronto delle prestazioni di questi casi. (Esempio intuitivo: confrontando gli algoritmi di ordinamento in un contesto, in cui si tenta spesso di ordinare una sequenza già ordinata, è possibile che vengano lanciate molte implementazioni Quicksort.)

Per quanto riguarda il tuo punto di ottimizzazione, la risposta è di nuovo: dipende. Hai intenzione di utilizzare questa struttura dati esattamente in quel preciso progetto in questo momento? Quindi andrei per le versioni ottimizzate. Stai mirando a un confronto per avere un'idea generale su quale potrebbe essere più adatto per un progetto pianificato? Quindi prova a confrontare le implementazioni di riferimento, ma non perdere tempo a creare implementazioni super-efficienti. Naturalmente, il contesto in cui si eseguono i test deve essere comparabile, quindi non provare a f.ex. confrontare tra loro le implementazioni in diversi linguaggi di programmazione. Probabilmente ovvio, ma ho pensato di assicurarmi di menzionarlo.

Fai attenzione con la terminologia. Le strutture dati non hanno prestazioni; gli algoritmi. È vero che alcune strutture dati sono progettate specificamente per abilitare i loro algoritmi corrispondenti, ma è comunque una buona idea tenere a mente la distinzione.

Ad esempio, hai chiesto di confrontare l'AVL "ottimizzato" con l'RB "semplice". Se pensi in termini di algoritmi, allora stai solo confrontando un algoritmo con un altro. È possibile confrontare tutti i diversi tipi di algoritmi che eseguono lo stesso compito: inserimento AVL ottimizzato, inserimento AVL diretto, inserimento RB ottimizzato, inserimento RB semplice, inserimento heap, inserimento lista collegata, ecc. Raggiungono tutti obiettivi simili, quindi confrontarli è utile.

Un modo tipico per fare questo genere di cose è costruire un harness di test che esegua ciascun algoritmo allo stesso modo usando gli stessi dati lo stesso numero di volte. Ad esempio, potresti scrivere una funzione che accetta come parametri una funzione (l'algoritmo), un set di dati e un numero di ripetizioni. La funzione eseguirà quindi l'algoritmo utilizzando i dati per quel numero di ripetizioni e restituirà il tempo trascorso.

Gli algoritmi possono essere confrontati identificando alcune operazioni di base, come i confronti, e il loro conteggio, in funzione della quantità di dati di input.

I programmi sono molto più difficili da confrontare, perché non è possibile fare un confronto equo senza controllare tutti i tipi di variabili estranee. Oltre a ciò, se due programmatori scrivono programmi per fare la stessa cosa, uno prenderà più tempo dell'altro, a causa di sciocche decisioni di progettazione. Non ho mai visto un programma significativo che, come scritto per la prima volta, non avesse un lotto di spazio per l'accelerazione. È come immergere un asciugamano nell'acqua. Viene fuori bagnando fradicio. Se lo schiacci (sintonizzalo) puoi fare un sacco di acqua. Se lo stringi più strong, puoi ottenere più acqua fuori . Se lo stringi strong, puoi ottenere la maggior parte dell'acqua, ma sarà comunque umida. C'è un compromesso tra la velocità del programma e quanto tu cerchi di sintonizzarti, e questa è una variabile difficile da controllare tra i programmi.