深イイ意味など全くない並列処理 in Python

あるサイトに載っていたコードパズルを解く際に,全く解法が思いつかず,禁断の総当たりに手を染めることにした.

対象となる問題は,与えられた関数f,定数cに対してf(m) == cとなるmを見つけるというもの.

まずはシンプルに

ひとまず何も考えずに実装した結果が以下のコードになる.

solution1

import sys

def solve(m):
    # f, cは定義済みとする
    return f(m) == c

def solution1():
    limit = int(sys.argv[1])
    ans = [m for m in range(limit) if solve(m)]
    print ans

処理時間がどれくらいかかるかな,と思い,プロファイラを仕込んだ.

profile

import cProfile

if __name__ == '__main__':
    profiler = cProfile.Profile()
    profiler.runcall(solution1)
    profiler.print_stats()

で,実行.

solution1_profile_result

% python mp.py 100000000

(解は省略)

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}

煽り,並列,そして...

とりあえず答えは分かったかと一息ついていると,「なんとwww並列化しないでござるかwwwブフェフェwww」という声が横から聞こえてきた(注:発言は筆者の悪意により歪められています).

「そういえばPythonの並列処理は調べたことがないな」と思いつつ,並列化したバージョンを実装してみる.

solution2

import math
import sys
from multiprocessing import Process, Queue


def task(q, num_range):
    # キュー経由でデータをmain側に渡すことに,このプログラムでは本質的な意味はない.
    # ﾔﾘﾀｶｯﾀﾀﾞｹｰ
    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)))

    # 処理するリストを分割して,各プロセスに渡す.
    # 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()

で,実行. 処理時間は半分近くになっている.

solution2_profile_result

% python mp.py 100000000 4

(解は省略)

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__)
       (略)

進撃のメモリ

さきほどの実装は,リストの分割処理の際,range関数を使ってlistを生成している.
そのため,メモリ使用量がえらい事になる.

range関数ではなく,xrange関数を用いることで,この問題は解決できた.
xrange関数はリストではなくiteratorを返すため,メモリを一度に消費しない.

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()

で,実行 + その際のメモリ消費量. 実行時間は殆ど変わっていないが,劇的にメモリ消費量が減った

solution3_profile_result

% python mp.py 100000000 4

(解は省略)

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>)
       (略)

(補足)Python2/3でのrange関数の違い

Python3では,range関数はrangeクラスというイテレータを返すため,上記の対応は不要.
というより, xrange関数が廃止されている.

// 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'>
  >>>