Python: 並列処理

Question

任意の数までの中に存在する素数を表示するプログラムを書きました。
処理にかかった時間も表示するようにしてみました。

# coding=utf-8
from time import time

num = int(input('Enter the integer: '))
prime = []

if __name__ == '__main__':
    st = time()
    for i in range(2,num+1):
        isprime = True
        for j in prime:
            if i % j == 0:
                isprime = False
                break
        if isprime:
            prime.append(i)

    print(prime)
    print('{0} sec'.format(time() - st))

100を入力した場合の結果

c:\python>python prime.py
Enter the integer: 100
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
0.00200009346008 sec

PCの性能があまりよくないので1000000などの大きな数字を入力すると、処理にとても長い時間がかかってしまいます。
そこでPythonの並列処理のための外部モジュールであるjoblibを使用してより高速に処理しようと思いました。

# coding=utf-8

from sklearn.externals.joblib import Parallel, delayed
from time import time

num = int(raw_input('Enter the integer: '))
st = time()
array = []
prime = [2,]
def makeprime(num):
    isprime = True
    for j in prime:
        if num % j == 0:
            isprime = False
            break
        if isprime:
            prime.append(num)
    return num

if __name__ == ' __main__':
    array = Parallel(n_jobs=-1)( [delayed(makeprime)(i) for i in range(3,num)] )

print(array)
print('{0} sec'.format(time() - st))

すると結果は

c:\python>prime2.py
Enter the integer: 100
[]
0.000999927520752 sec

このようになってしまいました。
調べたり試行錯誤したり、僕にできることはすべてやったつもりなのですがうまくいきません。
よろしければ何が悪かったのかご教授していただきたいです。
こちらは私がjoblibについて質問させていただいたものです。

Answer 1

まず、コンピューターの性能問題に対する取り組み方について一言、言わせてください。性能を上げたい→並列計算すれば上がると言うのは、私の長い経験からすると、素人的な発想です。並列計算してもせいぜいCPU の個数倍にしかなりません。殆どの場合は、ソフトウェアに性能的なバグが有り、それを治すことが先決です（数十倍、場合によっては数万倍に性能が上がります）。この問題でいうと、

• （数学的）素数かどうか確かめるときに、小さい素数から順に確かめるのであれば、素数の2乗が対象の数を超えた時点で可能性はゼロなので途中で諦めることができます。プログラウで言うと、 j の2乗が iを超えた時点で break したほうが性能が上がるでしょう（この計算自信、毎回なので、この計算にコストはかかりますが、直感的には break したほうが安い）
• （プログラミング的） prime.append が遅そうです→一般的に大きな配列は append のコストは高いので、これを linked list とかにする必要があると考えます
• （プログラミング的） for i in range(N) では、サイズNの配列を生成するので、 Nが大きいとそれだけで性能が悪い→普通に i のインクリメントで実装されるべき

それで、バグとしては panda_bk さんが指摘している共有変数の問題がありますが、それ以前に前回の質問の解答で参考にされていたサイト によりますと、 Windows では、 if __name__ == ' __main__': の外側に実行コードを書いては行けないとのことですので、

print(array)
print('{0} sec'.format(time() - st))

が if 文の中に含まれてない（＝インデントされてない）のが問題だと思います。

また、結果として array を print していますが、素数の配列を印刷したいのであれば、 prime を印刷しなければなりません。

さらに、 prime を共有変数にしたとして、上記にも書いたように、ある数 N が素数であるかどうか確かめるためにはN の平方根までの素数がわかっている必要があり、並列実行において、それが保証されていないので、単に joblib で並列計算するのではだめだと思います→スケジューリングが必要です。

あと、 print(array) は Pararell の返却値を印刷します。素数の配列を印刷したいのであれば、 print(prime) でないとだめなのではないですか？

Comments

[i.natsuki]

コメントが大変遅れてしまってもうしわけありません。
大変わかりやすい説明ありがとうございます。

Answer 2

primeという変数がプロセス間で共有できる変数となっていませんね。
従って、プロセス間でprime変数を正常にやり取り出来ない為に起きている現象ではないでしょうか。

変数の定義を以下の様に書き換えてみるのは如何でしょう？

from multiprocessing import Manager
〜省略〜
manager = Manager()
prime = manager.list()

また、並列化した際、そのままだと結果値が順不同になります。
順序を気にされる場合は最後のprintの前にsortを入れてやると良いかも知れません。
(ただし、それをする場合は当然ですが実行速度に悪影響が出ます。)

prime.sort()
print(prime)

補足：
公式は推奨していない様ですが、multiprocessing.Arrayを使ったやり方でも同様に共有変数が定義できます。
参考ページ