Ci dovrebbe essere un test per la complessità algoritmica? Se é cosi, come?

La complessità algoritmica è un costrutto teorico e come tale è meglio "testata" con carta e penna. Non può essere utilmente testato meccanicamente.

Le prestazioni assolute possono essere testate meccanicamente e possono rendere utili test unitari. Se le prestazioni sono importanti, puoi specificare una soglia: "questa query non dovrebbe richiedere più di 50ms per essere eseguita su 10 ⁶ numeri e non più di 60ms su 10 ⁷ numeri ". Che puoi costruire un test unitario per.

L'utente finale non si cura se il tuo algoritmo è lineare o logaritmico; si preoccupano che la loro interfaccia utente risponda ancora istantaneamente anche quando hanno un anno di dati in app.

Anche se non sono sicuro che questo strumento sarà particolarmente utile per i test unitari, il documento "Empirical Computational Complexity" di Goldsmith, Aiken e Wilkerson descrive un metodo per strumentare il codice e osservare il suo comportamento dinamico su un insieme di vari input per ricavarne empiricamente la complessità asintotica. Il programma descritto nel documento è open-source ed è disponibile qui .

Spero che questo aiuti!

La cosa principale è provarlo con i big data e vedere se ci vuole troppo tempo.

Nell'esperienza di ottimizzazione delle prestazioni, come in questo esempio , ciò che accade è che se un algoritmo è (per esempio) O (n ^ 2) potrebbe andare bene fino a quando la percentuale di tempo che impiega non arriva mai al radar.

Tuttavia, quando viene fornito un set di dati di una dimensione che potrebbe non essere visto ma una volta all'anno, la frazione del tempo totale risucchiata da quell'algoritmo potrebbe diventare catastroficamente dominante.

Se riesci a farlo durante i test, è un'ottima cosa, perché è estremamente facile trovare il problema, proprio come se si trattasse di un loop infinito reale.

Non penso che quello che vuoi fare sia Unit Testing.

AFAIK, il test delle unità è solo per assicurarsi che il codice faccia ciò che dovrebbe fare e non si concentri sulle prestazioni.

From Wikipedia: Testing cannot be expected to catch every error in the program: it is impossible to evaluate every execution path in all but the most trivial programs. The same is true for unit testing. Additionally, unit testing by definition only tests the functionality of the units themselves. Therefore, it will not catch integration errors or broader system-level errors (such as functions performed across multiple units, or non-functional test areas such as performance). Unit testing should be done in conjunction with other software testing activities. Like all forms of software testing, unit tests can only show the presence of errors; they cannot show the absence of errors.

Esistono altri tipi di strumenti e modelli per misurare le prestazioni. Uno di quelli che posso ricordare ora è Test di accettazione incentrati sui requisiti non funzionali.

Ce ne sono altri come test delle prestazioni (che utilizza test di stress, test di carico, ecc.)

Potresti anche usare alcuni strumenti di stress insieme a uno strumento di compilazione (formica, studio di build automatizzato) come parte dei tuoi passi di distribuzione (questo è ciò che faccio).

Quindi la risposta breve è no, non dovresti preoccuparti di ciò quando l'unità testa un codice.

Il passaggio al comparatore e il fatto di tenere traccia del numero di volte in cui viene chiamato funzionerà per scopi semplici, ad esempio controllando che il numero di confronti durante la ricerca in un input fisso (ad esempio new int[] { 1,2,3, ... , 1024 } ) rimanga inferiore a 10 Ciò chiarirà almeno le tue intenzioni su come dovrebbe comportarsi l'algoritmo.

Non penso che i test unitari siano il modo giusto per verificare che il tuo algoritmo sia O (log n); ciò richiederebbe un sacco di generazione casuale dei dati, alcune curve di adattamento e probabilmente delle statistiche grossolane per determinare se un gruppo di punti dati si adatta al runtime previsto. (Per questo algoritmo è probabilmente fattibile, ma se inizi a ottenere l'ordinamento, ecc diventerà difficile colpire ripetutamente gli scenari peggiori).