Curva di prestazioni inattesa da un tipo di unione CPython

Question

Ho implementato un algoritmo di ordinamento di unione naive in Python. Algoritmo e il codice del test è inferiore:

import time 
import random 
import matplotlib.pyplot as plt 
import math 
from collections import deque 

def sort(unsorted): 
    if len(unsorted) <= 1: 
     return unsorted 
    to_merge = deque(deque([elem]) for elem in unsorted) 
    while len(to_merge) > 1: 
     left = to_merge.popleft() 
     right = to_merge.popleft() 
     to_merge.append(merge(left, right)) 
    return to_merge.pop() 

def merge(left, right): 
    result = deque() 
    while left or right: 
     if left and right: 
      elem = left.popleft() if left[0] > right[0] else right.popleft() 
     elif not left and right: 
      elem = right.popleft() 
     elif not right and left: 
      elem = left.popleft() 
     result.append(elem) 
    return result 

LOOP_COUNT = 100 
START_N = 1 
END_N = 1000 

def test(fun, test_data): 
    start = time.clock() 
    for _ in xrange(LOOP_COUNT): 
     fun(test_data) 
    return time.clock() - start 

def run_test(): 
    timings, elem_nums = [], [] 
    test_data = random.sample(xrange(100000), END_N) 
    for i in xrange(START_N, END_N): 
     loop_test_data = test_data[:i] 
     elapsed = test(sort, loop_test_data) 
     timings.append(elapsed) 
     elem_nums.append(len(loop_test_data)) 
     print "%f s --- %d elems" % (elapsed, len(loop_test_data)) 
    plt.plot(elem_nums, timings) 
    plt.show() 

run_test() 

Per quanto posso vedere tutto è OK e dovrei ottenere una curva log N N * bello come un risultato. Ma il quadro si differenzia un po ':

http://s8.postimage.org/o8ysrafat/deque_long_run_2.png

Le cose che ho cercato di esaminare la questione:

1. PyPy. La curva è ok
2. Disabilitato il GC utilizzando il modulo gc. Ipotesi sbagliata L'output di debug ha mostrato che non funziona nemmeno fino alla fine del test.
3. Profili di memoria con melia - niente di speciale o sospetto. ` Ho avuto un'altra implementazione (una ricorsiva che utilizza la stessa funzione di unione), agisce in modo simile. Più cicli di test completi creo - più "salti" ci sono nella curva.

Quindi, come può essere spiegato questo comportamento e, si spera, risolto?

UPD: cambiato liste per collections.deque

UPD2: aggiunto il codice di prova completa

UPD3: io uso Python 2.7.1 su un sistema operativo Ubuntu 11.04, utilizzando un notebook 2Hz quad-core. Ho provato a cambiare la maggior parte degli altri processi: il numero di picchi è diminuito, ma almeno uno di essi era ancora lì.

Answer 1

Stai semplicemente rilevando l'impatto di altri processi sulla tua macchina.

Si esegue la funzione di ordinamento 100 volte per la dimensione di input 1 e si registra il tempo totale trascorso su questo. Quindi lo esegui 100 volte per la dimensione dell'ingresso 2 e registra il tempo totale trascorso. Si continueranno a farlo fino a raggiungere dimensioni di ingresso 1000.

Diciamo che di tanto in tanto il vostro sistema operativo (o voi stessi) iniziare a fare qualcosa CPU-intensive. Diciamo che questo "picco" dura fino a quando ti porta a eseguire la tua funzione di ordinamento 5000 volte. Ciò significa che i tempi di esecuzione sembrerebbero lenti per 5000/100 = 50 dimensioni di input consecutivi. Qualche istante dopo, si verifica un altro picco e un altro intervallo di dimensioni di input appare lento. Questo è esattamente ciò che vedi nel tuo grafico.

Posso pensare a un modo per evitare questo problema. Esegui la tua funzione di ordinamento una sola volta per ogni dimensione di input: 1, 2, 3, ..., 1000. Ripeti questa procedura 100 volte, usando gli stessi 1000 input (è importante, vedi spiegazione alla fine). Ora prendi lo minimo tempo impiegato per ogni dimensione di input come punto dati finale per il grafico.

In questo modo, i vostri punti dovrebbero interessare solo ogni formato di ingresso solo poche volte su 100 corse; e dal momento che stai prendendo il minimo, probabilmente non avranno alcun impatto sul grafico finale.

Se le punte sono molto molto lungo e frequente, è ovviamente potrebbe desiderare di aumentare il numero di ripetizioni oltre l'attuale 100 per dimensione di input.

Guardando le vostre punte, ho notato l'esecuzione rallenta esattamente 3 volte durante un picco.Suppongo che il sistema operativo dia al processo Python uno spazio su tre durante il carico elevato. Se la mia ipotesi è corretta o meno, l'approccio che consiglio dovrebbe risolvere il problema.

EDIT:

mi sono reso conto che non ho chiarire un punto nella mia soluzione proposta al vostro problema.

Si dovrebbe utilizzare lo stesso input in ciascuna delle 100 esecuzioni per la dimensione di input specificata? O dovrebbe usare 100 input diversi (casuali)?

Poiché ho consigliato di prendere il minimo dei tempi di esecuzione, gli input dovrebbero essere gli stessi (altrimenti otterrete output errato, poiché misurerete la complessità dell'algoritmo migliore invece della complessità media!) .

Ma quando si prendono gli stessi input, si crea un po 'di rumore nel grafico poiché alcuni input sono semplicemente più veloci di altri.

Quindi una soluzione migliore è quella di risolvere il problema del carico di sistema, senza creare il problema di un solo ingresso per ogni formato di input (questo è ovviamente pseudocodice):

seed = 'choose whatever you like' 
repeats = 4 
inputs_per_size = 25 
runtimes = defaultdict(lambda : float('inf')) 
for r in range(repeats): 
    random.seed(seed) 
    for i in range(inputs_per_size): 
    for n in range(1000): 
     input = generate_random_input(size = n) 
     execution_time = get_execution_time(input) 
     if runtimes[(n, i)] > execution_time: 
     runtimes[(n,i)] = execution_time 
for n in range(1000): 
    runtimes[n] = sum(runtimes[(n,i)] for i in range(inputs_per_size))/inputs_per_size 

Ora è possibile utilizzare tempi di esecuzione [n] per costruisci la tua trama.

Naturalmente, a seconda se il vostro sistema è super-rumorosa, si potrebbe cambiare (repeats, inputs_per_size) da (4,25) dire, (10,10), o addirittura (25,4).

Answer 2

posso riprodurre le punte utilizzando il codice:

Si consiglia di scegliere una funzione di temporizzazione appropriata (time.time() vs. time.clock()-from timeit import default_timer), il numero di ripetizioni in un test (per quanto tempo ogni test richiede) e il numero di test per scegliere il tempo minimo da. Ti dà una precisione migliore e meno influenza esterna sui risultati. Leggi la nota timeit.Timer.repeat() docs:

Si sarebbe tentati di calcolare la media e deviazione standard dal risultato vettoriale e segnalare questi. Tuttavia, questo non è molto utile. In un caso tipico , il valore più basso fornisce un limite inferiore per la velocità con cui la macchina può eseguire lo snippet di codice specificato; valori più alti nel risultato Il vettore in genere non è causato dalla variabilità della velocità di Python, ma dallo da altri processi che interferiscono con la precisione temporale. Quindi il il min() del risultato è probabilmente l'unico numero a cui dovresti essere interessato. Dopodiché, dovresti esaminare l'intero vettore e applicare il senso comune piuttosto che le statistiche.Modulo

timeit può scegliere parametri appropriati per voi:

$ python -mtimeit -s 'from m import testdata, sort; a = testdata[:500]' 'sort(a)' 

---

Ecco timeit curva di prestazioni basata su:

La figura mostra che sort() comportamento è coerente con.221.201.046,76321 milioni:

|------------------------------+-------------------| 
| Fitting polynom    | Function   | 
|------------------------------+-------------------| 
| 1.00 log2(N) + 1.25e-015 | N     | 
| 2.00 log2(N) + 5.31e-018 | N*N    | 
| 1.19 log2(N) +  1.116 | N*log2(N)   | 
| 1.37 log2(N) +  2.232 | N*log2(N)*log2(N) | 

Per generare la cifra che ho usato make-figures.py:

$ python make-figures.py --nsublists 1 --maxn=0x100000 -s vkazanov.msort -s vkazanov.msort_builtin 

dove:

# adapt sorting functions for make-figures.py 
def msort(lists): 
    assert len(lists) == 1 
    return sort(lists[0]) # `sort()` from the question 

def msort_builtin(lists): 
    assert len(lists) == 1 
    return sorted(lists[0]) # builtin 

liste di ingresso sono descritti here (nota: l'ingresso è ordinato in modo integrato sorted() la funzione mostra la prestazione O(N) prevista).