Making A Program Multithreaded
Solution 1:
The most popular implementations of Python (CPython and PyPy) come with a Global Interpreter Lock ("GIL"). The purpose of this is basically to simplify memory management. The effect of it is that only one thread at a time can be executing Python bytecode. So for a program that does all its calculations in Python, threading won't make it faster.
Usually the best was to make a program faster is to find a better algorithm. Look e.g. at this:
defprime_list(num):
"""Returns a list of all prime numbers up to and including num.
:num: highest number to test
:returns: a list of primes up to num
"""if num < 3:
raise ValueError('this function only accepts arguments > 2')
candidates = range(3, num+1, 2) # (1)
L = [c for c in candidates ifall(c % p != 0for p inrange(3, c, 2))] #(2)return [2] + L # (3)
(1) Even numbers >2 can be divided by two, so they cannot be prime and need not be considered.
(2): For an odd number c
to be prime, one must ensure that c
modulo all previous odd numbers (p
) must be non-zero.
(3): 2 is also a prime number.
A small improvement is that p
only needs to go up to sqrt(c)
.
defprime_list2(num):
if num < 3:
raise ValueError('this function only accepts arguments > 2')
candidates = range(3, num+1, 2)
L = [c for c in candidates ifall(c % p != 0for p inrange(3, int(math.sqrt(c))+1, 2))]
return [2] + L
Note that I'm using list comprehensions instead of for-loops, because they are generally faster.
Finally, a kind of sieve as Adam Smith mentioned;
defprime_list3(num):
num += 1
candidates = range(3, num, 2)
results = [2]
whilelen(candidates):
t = candidates[0]
results.append(t)
candidates = [i for i in candidates ifnot i inrange(t, num, t)]
return results
To see which one is faster, we need to run tests;
First for num=100
.
In [8]:%timeitprime_list(100)1000 loops,best of 3:185µsperloopIn [9]:%timeitprime_list2(100)10000loops,best of 3:156µsperloopIn [10]:%timeitprime_list3(100)1000 loops,best of 3:313µsperloop
Then 1000:
In [11]: %timeit prime_list(1000)
100 loops, best of 3: 8.67 ms per loop
In [12]: %timeit prime_list2(1000)
1000 loops, best of 3: 1.94 ms per loop
In [13]: %timeit prime_list3(1000)
10 loops, best of 3: 21.6 ms per loop
Then 10000;
In [14]: %timeit prime_list(10000)
1 loops, best of 3: 680 ms per loop
In [15]: %timeit prime_list2(10000)
10 loops, best of 3: 25.7 ms per loop
In [16]: %timeit prime_list3(10000)
1 loops, best of 3: 1.99 s per loop
Of these algoriths, prime_list2
seems to hold up best.
Post a Comment for "Making A Program Multithreaded"