Analisi runtime di funzioni che chiamano altre funzioni

Question

Analisi runtime di funzioni che chiamano altre funzioni

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

1

Se hai una funzione chiamata in un'altra funzione, indovina il runtime per essere chiamato e poi "aggiungi" per funzionare per il quale desideri analizzare il runtime?

Funzione da analizzare:

for (i = 0, i > n, ++i)
{
    if (function.call() > 0)
    {
        \something
    }
}

Funzione chiamata:

Call
{
   for (i = 0, i > n, ++i)
    {
        \return something
    }
}

runtime

posta RandomPleb 14.09.2014 - 20:12

fonte

2 risposte

Leggi altre domande sui tag runtime

Applicazioni SPA: AJAX per scaricare modelli o creare da stringhe Estrarre efficacemente i dati da pdf con un sistema di template?

score 1 · Answer 1

Consideralo come una sorta di contabilità.

Il tempo di inclusione di una funzione è:

Il tempo trascorso tra l'ingresso e l'uscita di questa funzione,
MINUS overhead puro (se noto, zero se trascurabile o indeterminato)
PLUS tempo trascorso totale trascorso su altri core della CPU o thread del sistema operativo a causa di qualsiasi lavoro delegato da questa funzione. (In altre parole, il lavoro esterno che è "fatturabile" a questa funzione.)

Il tempo esclusivo di una funzione è:

Il tempo inclusivo della funzione,
MENO il tempo totale inclusivo di tutti i bambini di quella funzione.
- La definizione di "bambini" spetta al progettista del profiler.
- Ad esempio, le funzioni figlio che sono state completamente integrate nella funzione padre di solito non sono più considerate come un elemento separato e quindi non verranno sottratte.
- D'altra parte, qualsiasi utilizzo di framework per i profiler "source-based" impedirà l'ottimizzazione inlining da parte del compilatore, al punto che tutte le funzioni contrassegnate per la strumentazione non saranno mai inline comunque.

score 0 · Answer 2

@Rufflewind aveva ragione nei commenti, devi sostituire la chiamata alla funzione - pensa più da vicino per copiare / incollare la sottofunzione nella funzione principale. Questo può diventare un po 'fastidioso quando hai chiamate ricorsive, come puoi immaginare.

Una cosa importante da tenere a mente è il "cosa" della tua analisi. Solitamente l'analisi runtime di stile big-O preleva un certo numero di operazioni da misurare: swap, aggiunte, moltiplicazioni, ecc. Potresti avere casi in cui la sottofunzione funziona, ma nessuna delle operazioni viene misurata, nel qual caso dovrebbe abbandonare analisi.

Quindi nel tuo esempio sembra che il ciclo esterno sia O (N) se la sottofunzione non ha funzionato, ma quando lo sostituisci, ti ritroverai con un tipo O (N ^ 2) di operazione.