spiegazione dell'ottimizzazione dello snippet python

Question

spiegazione dell'ottimizzazione dello snippet python

#1 da (1 voti)

0

Sto tentando di ottimizzare e capire perché per l'input n una funzione che ho scritto f (n) sembra non terminare mai l'esecuzione quando n > 26.

TL; DR Ho bisogno di capire come trovare la complessità delle varie istruzioni Python che implicano la concatenazione di una stringa vuota e ricerche nel dizionario tutte all'interno di un ciclo while. Il resto appare come O (1) o trascurabile. Leggi di seguito per provare che ho RTFM ampiamente e ho bisogno di aiuto per afferrare questo

f (n) restituisce una stringa alfabetica casuale di lunghezza n:

def func(n, prefix=None):
    if prefix is None:
        empty = ""
    else:
        empty = prefix
    while (len(empty) < n):
        c = padder[random.randint(0,len(padder) -1)]
        if empty.find(c) == -1:
            str = empty+c
            empty = str
    return empty

Disassembro il bytecode Python

>>>dis.dis(func(8))
        0 BREAK_LOOP
        1 POP_BLOCK
        2 PRINT_NEWLINE
        3 INPLACE_POWER
        4 RETURN_VALUE
        5 PRINT_ITEM
        6 <69>
        7 IMPORT_STAR

Tuttavia, quando n > 26 si blocca. Perché il seguente è più veloce? (nota: sostituisci x con la lunghezza desiderata della stringa)

print(''.join(random.choice(string.ascii_uppercase) for i in range(x)))

Quando lo disassembro come sopra, sembra eseguito in O (n).

Finora, sono giunto alla conclusione che dovrei abbattere ogni operazione, trovare le loro complessità e questo determinerebbe il motivo per cui si blocca su n > 26. Ho trovato un cheatsheet per la complessità temporale delle comuni operazioni python

Tuttavia, non copre SETUP_LOOP, LOAD_CONST vs LOAD_FAST, ecc. e altre istruzioni python

Qualcuno può spiegare perché il mio primo script è più lento del secondo e almeno mi indica un buon materiale di riferimento? I google dork'd

intext:"python" intext:"time complexity" intext:"instruction"

Che era chiaro su un cheatsheet. Ho trovato una buona spiegazione ma è stato un po 'difficile da seguire

python complexity optimization

posta grepNstepN 18.03.2016 - 17:34

fonte

1 risposta

Leggi altre domande sui tag python complexity optimization

Come modellare una proprietà con due formati e intervalli diversi Guesstimating multiple Epics

score 1 · Accepted Answer

C'è una differenza significativa nei due frammenti di codice che li inducono a esibirsi in modo diverso.

La tua prima versione crea una stringa contenente lettere uniche casuali dal set sorgente. La tua seconda versione crea semplicemente una stringa contenente lettere casuali dal set. Quindi "AABDEEE" verrebbe generato per il secondo, ma non per il primo.

Quindi l'algoritmo della seconda versione è:

while number of letters less than goal
    select a letter at random
    add it to the result

Il tuo secondo è:

while number of letters less than goal
    do    
        select a letter at random
    while letter is already in goal
    add it to the result

Pensa a cosa succede mentre selezioni le lettere, supponendo che il set sorgente sia di 26 lettere.

Prima scelta, ne otterrai sempre una che funzioni. Seconda scelta, c'è una possibilità 1/26 che devi selezionare. Terza scelta, c'è una possibilità 2/26 che devi scegliere. . . La venticinquesima scelta, c'è una possibilità 24/26 che devi selezionare.

Quindi se chiedi una stringa lunga 25 caratteri, con 26 scelte, allora ci vorranno 13 scelte per trovarne una che funzioni. Se fai i conti, significa che deve fare 71 chiamate a random.randint per riempire una stringa di 25 caratteri. Al contrario, la seconda versione richiede solo 25 chiamate a random.choice per generare una stringa di 25 caratteri (con duplicati).

Se l'unicità è un requisito, allora quello che vuoi veramente è un algoritmo che usi una sorta di shuffle. In effetti, il modulo python random ha qualcosa che fa esattamente quello che penso tu stia cercando di fare:

 ''.join(random.sample(string.ascii_uppercase, 25))

Se vuoi farlo a mano, probabilmente l'algoritmo è simile a:

 s = ascii letters
 result = ""
 for i in 1 to 25
     i = random int
     c = s[i]
     result += c
     delete s[i]

(Traduzione di python lasciato come esercizio per il lettore.)