Il collo di bottiglia qui è in realtà il ciclo for
. I loop Python for
sono relativamente lenti, quindi se hai bisogno di iterare oltre un milione di elementi, puoi guadagnare molta velocità evitandoli del tutto. In questo caso, è abbastanza facile. Invece di questo:
for item in range(n):
if ((s1[item])**2 + (s2[item])**2) < 1:
ii = ii + 1
fare questo:
ii = ((s1 ** 2 + s2 ** 2) < 1).sum()
Questo funziona perché numpy
ha supporto incorporato per le operazioni di matrice ottimizzate. Il ciclo si verifica in c
anziché in python, quindi è molto più veloce. Ho fatto un test rapido in modo da poter vedere la differenza:
>>> def estimate_pi_loop(x, y):
... total = 0
... for i in xrange(len(x)):
... if x[i] ** 2 + y[i] ** 2 < 1:
... total += 1
... return total * 4.0/len(x)
...
>>> def estimate_pi_numpy(x, y):
... return ((x ** 2 + y ** 2) < 1).sum()
...
>>> %timeit estimate_pi_loop(x, y)
1 loops, best of 3: 3.33 s per loop
>>> %timeit estimate_pi_numpy(x, y)
100 loops, best of 3: 10.4 ms per loop
Ecco alcuni esempi dei tipi di operazioni che sono possibili, solo così si ha un senso di come funziona.
quadratura una matrice:
>>> a = numpy.arange(5)
>>> a ** 2
array([ 0, 1, 4, 9, 16])
array Aggiunta:
>>> a + a
array([0, 2, 4, 6, 8])
array confronto:
>>> a > 2
array([False, False, False, True, True], dtype=bool)
sommatori valori:
>>> (a > 2).sum()
2
Come probabilmente ti rendi conto, ci sono modi più veloci per stimare Pi, ma ammetterò che ho sempre ammirato la semplicità e l'efficacia di questo metodo.
Qualsiasi motivo per cui è necessario calcolare questo? Questo è già stato fatto migliaia di volte (ad esempio, leggilo dal file o hardcode). – Caramiriel
La lentezza è solo inerente all'algoritmo: ogni volta che si desidera una cifra in più di precisione, il tempo di esecuzione aumenta di 10 volte. Dai un'occhiata a [Pi - modern quest for more digit] (https://en.wikipedia.org/wiki/Pi#Modern_quest_for_more_digits) per approcci più rapidi. – Kevin
C'è qualche ragione per costruire due array in anticipo? Perché non prendi due 'random.random()' numeri * dentro * il ciclo? Tuttavia, come sottolinea @Kevin, questo algoritmo è fondamentalmente 'O (n)', quindi per grandi 'n' eventuali modifiche all'implementazione precisa comporteranno solo differenze minime rispetto al runtime complessivo. – jonrsharpe