Come si chiama quando si modifica il tempo di esecuzione Big O di una funzione [chiuso]

In genere viene chiamato "ottimizzazione del rendimento" , ma non lo chiamerei "refactoring", poiché questo termine si riferisce in genere a modifiche nel codice che non modificano il suo comportamento visibile . E un cambiamento nel Big-O è sicuramente qualcosa che definirei un cambiamento visibile.

in doing so I will change the fundamental way the operation runs

In questo caso, l'ottimizzazione è una riscrittura di quella funzione. Non tutte le ottimizzazioni, anche se cambiano "Big-O", sono necessariamente una riscrittura, a volte sono necessari solo piccoli cambiamenti per ottenere un tale miglioramento, ma anche in questo caso, sono riluttante a usare il termine "refactoring" per questo, perché tende a dare un'impressione sbagliata sulla natura del cambiamento.

EDIT: ho controllato l'elenco di refactoring di Fowler , e tra questi ~ 100 refactoring nominati, l'ultimo è chiamato "Algoritmo sostitutivo" . Quindi, se prendiamo questo come riferimento canonico, c'è una piccola area grigia in cui l'ottimizzazione della forma descritta potrebbe essere chiamata un tipo speciale di refactoring (ma IMHO non è una tipica). Si noti inoltre che l'obiettivo di Fowler con tutti i refactoring era sempre quello di migliorare il design con attenzione alla manutenibilità e all'evoluibilità del codice esistente senza riscriverlo, e chiaramente non all'ottimizzazione delle prestazioni.

Non penso che ci sia un termine standard, comunemente usato ottimizzazione sebbene miglioramento o accelerazione sarebbe anche corretto chiarendo che si sta parlando di modifiche al codice e non di modifiche all'hardware.

Come altri hanno già detto, "ottimizzare" è il termine generale per migliorare le prestazioni di un algoritmo. Tuttavia, l'ottimizzazione spesso significa migliorare i fattori costanti. Se volessi esprimere in modo conciso ma chiaramente che ho ridotto la complessità asintotica (tempo), direi che ho "migliorato le prestazioni asintotiche". A volte le persone descrivono questo come "migliorare il ridimensionamento" ma questo è particolarmente ambiguo al giorno d'oggi.

Avviso : la riduzione della complessità temporale asintotica non è necessariamente la stessa cosa dell'ottimizzazione in un contesto pratico . Spesso gli algoritmi asintoticamente non ottimali sono usati perché sulla gamma di ingressi il programma è effettivamente esposto agli algoritmi meno ottimali che danno risultati migliori.

Sarà dipendente dal contesto.

"Risolvere un bug di prestazioni di runtime quadratico" è in genere ciò che vedo. Tuttavia, se ciò merita di essere risolto (una modifica del codice) dipende dal contesto.

Tieni presente che i database offrono molti strumenti per migliorare la complessità del tempo. Ad esempio, per ottenere i primi risultati N da un database, basta dirlo. Quando si converte un kludge inefficiente in una chiamata ottimizzata integrata, la spiegazione sembra superflua.

Il motivo per cui considero un algoritmo con tempo di esecuzione quadratica per meritare una revisione del codice (discussione) non è tanto perché è lento (slow è relativo; quadratica è veloce rispetto al esponenziale), ma perché l'intuizione umana (come il tuo i clienti, o colleghi programmatori) sono innatamente a disagio con una funzionalità software che devia troppo dal tempo di esecuzione lineare, a causa del mescolamento delle aspettative dalla vita quotidiana.

Molti reclami dei clienti relativi alle prestazioni del software rientrano in queste due categorie:

• L'intero sistema (software e hardware) è stato specificato in base all'utilizzo stimato. La scorsa settimana, tutto funziona bene, una certa funzionalità ha richiesto meno di 5 secondi. Questa settimana, dopo aver installato un aggiornamento, la stessa funzionalità impiega più di 1 minuto.

  • Questo è un confronto con una prestazione precedentemente valutata. Il cliente tiene le prestazioni future a un metro assoluto di una scala temporale umana (dai secondi ai minuti).

• Ho inviato 100 lavori al sistema. Perché impiega 400 volte il tempo di elaborazione, rispetto al tempo necessario per un singolo lavoro?

  • Il cliente si aspetta che i tempi di elaborazione siano lineari. Infatti, il cliente non può capire o accettare che esistano attività più lente di quelle lineari.

Per questo motivo, un cliente considererà il bug di esecuzione un errore se entrambi sono veri:

• Più lento di lineare
• Notevole (cioè rientra nell'intervallo di tempo umano (più lungo di secondi o minuti) in base alle dimensioni tipiche dell'attività)

Argomenti legittimi che spiegano che un algoritmo di runtime quadratico non pone problemi (cioè non merita un cambio di codice):

• La dimensione dell'attività generalmente gestita da questa funzione di runtime quadratica è in qualche modo limitata
• Data l'intervallo di dimensioni tipico, il tempo di esecuzione effettivo (assoluto) è ancora abbastanza piccolo da essere eliminato
• Se un utente tenta effettivamente di inviare un'attività sufficientemente ampia da essere visibile, l'utente riceverà un messaggio di avviso relativo al lungo tempo di esecuzione
• Gli utenti del sistema sono tutti esperti, quindi sanno cosa stanno facendo. Ad esempio, gli utenti di un'API dovrebbero aver letto la stampa fine sulla documentazione dell'API.

Un sacco di algoritmi utili per lo sviluppo di applicazioni tipiche sono infatti più lento di quello lineare (per lo più O (N log N), come in l'ordinamento), quindi il software su larga scala sarà infatti cercare di soluzione che, da solo l'ordinamento relativo parte dei dati, o utilizzare tecniche di filtraggio degli istogrammi (statistiche) che raggiungono un effetto simile.

Questo vale per i clienti del software, ma se consideri che gli utenti di una libreria software o di una funzione API siano anche "clienti", la risposta verrebbe comunque applicata.

Se l'algoritmo originale è stato implementato correttamente (o eventuali bug dove irrilevante) quindi "modifica dell'algoritmo" o "sostituzione dell'algoritmo" , poiché tali cambiamenti significano che stai facendo precisamente quello; sostituendo un algoritmo con una complessità temporale diversa per quella precedentemente utilizzata.

Se la complessità del tempo precedente era dovuta a un bug nell'implementazione (ad esempio, si stava reimpostando accidentalmente il punto iniziale di un loop interno su una sequenza in modo che quello che avrebbe dovuto essere O (n) diventasse O (n ² )) quindi "risoluzione di un errore di costo quadratico" o simile.

C'è una sovrapposizione, in quanto in questo caso l'effetto sul codice è lo stesso se si sa fin dall'inizio che il lavoro può essere svolto in tempo O (n) e l'O (n ² ) time era un errore, o se prima l'hai implementato deliberatamente nel tempo O (n ² ) e poi realizzato funzionava ancora correttamente senza reimpostare il punto di partenza, e quindi ha sostituito un O (n ) algoritmo per uno O (n ² ).

Ottimizzazione della velocità di un ordine / ordini di grandezza. Sebbene si tratti di linguaggio matematicamente scorretto, trasmette al meglio l'idea che l'Ordine sia cambiato.

Miglioramento della scalabilità. ascoltato anche.