Parallel processing with no deep meaning in Python
When solving a code puzzle on a site, I couldn't think of a solution at all, so I decided to brute force the forbidden.
The problem is to find m such that f (m) == c for the given function f and constant c.
First, simply
The result of implementing without thinking for the time being is the following code.
solution1
import sys
def solve(m):
# f,c is defined
return f(m) == c
def solution1():
limit = int(sys.argv[1])
ans = [m for m in range(limit) if solve(m)]
print ans
I wondered how long the processing time would take, so I prepared a profiler.
profile
import cProfile
if __name__ == '__main__':
profiler = cProfile.Profile()
profiler.runcall(solution1)
profiler.print_stats()
And run.
solution1_profile_result
% python mp.py 100000000
(The solution is omitted)
200000003 function calls in 333.009 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
100000000 78.739 0.000 299.934 0.000 mp.py:12(solve)
1 30.856 30.856 333.009 333.009 mp.py:31(solution1)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
100000000 221.195 0.000 221.195 0.000 {pow}
1 2.219 2.219 2.219 2.219 {range}
Fanned, parallel, and ...
When I was wondering if I knew the answer for the time being, I heard a voice from the side saying, "Why don't you parallelize www bufefe www" (Note: The remarks are distorted by my malicious intent). While thinking, "By the way, I haven't investigated the parallel processing of Python," I will implement a parallelized version.
solution2
import math
import sys
from multiprocessing import Process, Queue
def task(q, num_range):
#To pass data to the main side via a queue,There is no essential meaning in this program.
#Mirita Cutter Dagger
q.put([m for m in num_range if solve(m)])
def solution2():
queue = Queue()
limit = int(sys.argv[1])
worker_num = int(sys.argv[2])
task_size = int(math.ceil(float(limit) / float(worker_num)))
#Split the list to process,Pass to each process.
# ref. http://iogi.hatenablog.com/entry/split-list-into-sublist
num_ranges = izip_longest(*[iter(range(limit))]*task_size)
processes = [Process(group=None, target=task, args=(queue, num_range))
for num_range in num_ranges]
for process in processes:
process.start()
for process in processes:
print queue.get()
process.join()
And, the processing time is almost half.
solution2_profile_result
% python mp.py 100000000 4
(The solution is omitted)
1021 function calls (1018 primitive calls) in 182.498 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 __future__.py:48(<module>)
1 0.000 0.000 0.000 0.000 __future__.py:74(_Feature)
7 0.000 0.000 0.000 0.000 __future__.py:75(__init__)
1 0.005 0.005 0.042 0.042 __init__.py:102(Pipe)
1 0.004 0.004 0.084 0.084 __init__.py:213(Queue)
1 0.000 0.000 0.000 0.000 connection.py:117(Listener)
1 0.000 0.000 0.000 0.000 connection.py:183(Pipe)
1 0.000 0.000 0.000 0.000 connection.py:246(SocketListener)
1 0.013 0.013 0.037 0.037 connection.py:35(<module>)
1 0.000 0.000 0.000 0.000 connection.py:426(ConnectionWrapper)
1 0.000 0.000 0.000 0.000 connection.py:448(XmlListener)
1 0.000 0.000 0.000 0.000 forking.py:113(Popen)
4 0.000 0.000 0.027 0.007 forking.py:115(__init__)
(Abbreviation)
Attack on Titan memory
The previous implementation uses the range function to generate a list when splitting a list. Therefore, the memory usage is great.
This problem was solved by using the xrange function instead of the range function. The xrange function returns an iterator instead of a list, so it doesn't consume memory all at once.
solution3
import math
import sys
from multiprocessing import Process, Queue
def solution3():
queue = Queue()
limit = int(sys.argv[1])
worker_num = int(sys.argv[2])
task_size = int(math.ceil(float(limit) / float(worker_num)))
gen = xrange(limit)
processes = [Process(
group=None,
target=task,
args=(queue, islice(gen, task_size * i, task_size * (i + 1))))
for i in xrange(worker_num)]
for process in processes:
process.start()
for process in processes:
print queue.get()
process.join()
So, execution + memory consumption at that time. The execution time has hardly changed, but the memory consumption has decreased dramatically.
solution3_profile_result
% python mp.py 100000000 4
(The solution is omitted)
1019 function calls (1016 primitive calls) in 187.432 seconds
Ordered by: standard name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 __future__.py:48(<module>)
1 0.000 0.000 0.000 0.000 __future__.py:74(_Feature)
7 0.000 0.000 0.000 0.000 __future__.py:75(__init__)
1 0.006 0.006 0.047 0.047 __init__.py:102(Pipe)
1 0.005 0.005 0.082 0.082 __init__.py:213(Queue)
1 0.000 0.000 0.000 0.000 connection.py:117(Listener)
1 0.000 0.000 0.000 0.000 connection.py:183(Pipe)
1 0.000 0.000 0.000 0.000 connection.py:246(SocketListener)
1 0.015 0.015 0.041 0.041 connection.py:35(<module>)
1 0.000 0.000 0.000 0.000 connection.py:426(ConnectionWrapper)
1 0.000 0.000 0.000 0.000 connection.py:448(XmlListener)
1 0.000 0.000 0.000 0.000 forking.py:113(Popen)
4 0.000 0.000 0.001 0.000 forking.py:115(__init__)
10 0.000 0.000 0.000 0.000 forking.py:130(poll)
4 0.000 0.000 0.000 0.000 forking.py:146(wait)
1 0.014 0.014 0.019 0.019 forking.py:35(<module>)
(Abbreviation)
(Supplement) Difference of range function in Python2 / 3
In Python3, the range function returns an iterator called the range class, so the above correspondence is unnecessary. Rather, the xrange function is obsolete.
// Python3
% python3
Python 3.3.0 (default, Mar 2 2013, 11:44:00)
[GCC 4.2.1 Compatible Apple LLVM 4.2 (clang-425.0.24)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> a = range(5)
>>> a
range(0, 5)
>>> type(a)
<class 'range'>
>>>
>>> xrange(5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
NameError: name 'xrange' is not defined
// Python2
% python
Python 2.7.3 (default, May 14 2012, 22:41:33)
[GCC 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.1.00)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> a = range(5)
>>> a
[0, 1, 2, 3, 4]
>>> type(a)
<type 'list'>
>>>
Recommended Posts