質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
並列処理

複数の計算が同時に実行される手法

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

3回答

2084閲覧

並列処理を行う際のコード変更について

退会済みユーザー

退会済みユーザー

総合スコア0

並列処理

複数の計算が同時に実行される手法

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

1クリップ

投稿2018/08/03 06:24

編集2018/08/07 01:40

前提・実現したいこと

データセットがキーのアルファベット記号と要素の数字からなる辞書型で与えられており、
数字はリストに格納されています。リストの長さはキーによって様々です。
各キーの要素の数字間でそれぞれ、たすき掛けで掛け算し、最も大きいものを採用した上で、
配列の長さで割った値を2つのキー間の値として出力します。

これを大規模なデータセットで実行することを実現したいです。

発生している問題・エラーメッセージ

小規模なデータセットでは問題なく実行できますが、
このコードで、データセットのキーの数が大規模(例えば3万など)な場合、
1つのキーに対してたすき掛けの計算で比較する対象も膨大になるため、
現行のコードのまま実行すると膨大な時間がかかってしまいます。

そこで、並列処理を行いたいのですが、どのようにコードを改変すればいいかわからず、
アドバイスをいただきたいです。

該当のソースコード

python

1 2data = { 3 'A':[1, 3, 5, 2, 1, 8, 9], 4 'B':[9, 4, 3], 5 'C':[8, 5, 5, 6, 1] 6} 7 8output = {} 9 10for alph, nums in data.items(): 11 avg = {} 12 my_list = data[alph] 13 for target_alph, target_nums in data.items(): 14 target_list = data[target_alph] 15 if alph == target_alph: 16 continue 17 max_nums = [] 18 19 for i in my_list: 20 max_num = 0 21 for j in target_list: 22 result = i * j 23 if result is not None and result > max_num: 24 max_num = result 25 max_nums.append(max_num) 26 avg[target_alph] = sum(max_nums) / len(max_nums) 27 output[alph] = avg 28print(output)

出力(一行だと長いため、改行してあります)

{ {'A': {'B': 37.285714285714285, 'C': 33.142857142857146}, 'B': {'A': 48.0, 'C': 42.666666666666664}, 'C': {'A': 45.0, 'B': 45.0}} }

ご回答を受けて試したこと

関数に切り出してみたのですが、うまく切り出すことができず、
エラーが出てしまいました。関数内でも、alphとtarget_alphを使用する必要があるため、関数を用いてもうまく効率化する術がわかりません。

python

1#!/usr/bin/env python 2# coding: utf-8 3 4data = { 5 'A':[1, 3, 5, 2, 1, 8, 9], 6 'B':[9, 4, 3], 7 'C':[8, 5, 5, 6, 1] 8} 9 10output = {} 11 12for alph, nums in data.items(): 13 avg = {} 14 my_list = nums 15 for target_alph, target_nums in data.items(): 16 target_list = target_nums 17 """ 18 if alph == target_alph: 19 continue 20 max_nums = [] 21 22 for i in my_list: 23 max_num = 0 24 for j in target_list: 25 result = i * j 26 if result is not None and result > max_num: 27 max_num = result 28 max_nums.append(max_num) 29 """ 30 avg[target_alph] = avg_of_max(my_list, target_list) 31 output[alph] = avg 32print(output) 33 34 35def avg_of_max_nums(my_list, target_list): 36 for alph, nums in data.items(): 37 for target_alph, target_nums in data.items(): 38 if alph == target_alph: 39 continue 40 max_nums = [] 41 42 for i in my_list: 43 max_num = 0 44 for j in target_list: 45 result = i * j 46 if result is not None and result > max_num: 47 max_num = result 48 max_nums.append(max_num) 49 return sum(max_nums) / len(max_nums)

エラー文

$ python sample.py File "sample.py", line 49 return sum(max_nums) / len(max_nums) ^ IndentationError: unindent does not match any outer indentation level

補足情報(FW/ツールのバージョンなど)

python3.6

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

hayataka2049

2018/08/03 08:26 編集

首尾よく並列化できたとして、オクタコアのryzenでも膨大な時間/8程度の時間で処理できるようになるだけで、まだまだ膨大です。まずはロジックの改善でがんばりましょう。質問文とコードがわかりづらいので、実例を交えてわかりやすく説明してみてください
hayataka2049

2018/08/03 08:53

あと、if result is not None and resultは何か間違っているのでは(恐らく最大値更新のifだと思うが・・・)
退会済みユーザー

退会済みユーザー

2018/08/03 13:23

ご指摘いただきましてありがとうございます。if文が間違えていました。
hayataka2049

2018/08/03 14:56

ちなみに、その出力が本当に意図した処理の結果なのかどうか、手計算で検算してみましたか?
hayataka2049

2018/08/03 15:59 編集

None判定必要ですか・・・?
退会済みユーザー

退会済みユーザー

2018/08/07 00:48

コメントいただきましてありがとうございます。手計算で検算して、意図した処理の結果であることが明白になりました。None判定は、大規模なデータセットの中に数字ではないものが紛れてい流可能性があるので、念のため、設定しております。
退会済みユーザー

退会済みユーザー

2018/08/07 01:44

ご質問いただきましてありがとうございます。負値はありえません。
guest

回答3

0

ベストアンサー

アルゴリズムを改善してnumpyで実装することで、ある程度大きいデータに対してなら数桁は速くなります。

  • どうせ最大のものだけ取るので、ほかは計算する必要はない

max([x*y for y in lst])x*max(lst)ですね(x,y,lstは適当なデータです。数値がすべて非負の場合)

  • 配列の長さで割った値はただの平均ですね

結論だけ端的にいうと、各データの最大値と平均を計算し、直積を求めれば良いです。これはnumpyで高速に書けます。

python

1import timeit 2from itertools import permutations 3 4import numpy as np 5 6data1 = { 7 'A':[1, 3, 5, 2, 1, 8, 9], 8 'B':[9, 4, 3], 9 'C':[8, 5, 5, 6, 1] 10} 11 12data2 = {str(i):[np.random.randint(1000) for _ in range(50)] 13 for i in range(50)} 14 15data3 = {str(i):[np.random.randint(1000) for _ in range(500)] 16 for i in range(500)} 17 18def original(data): 19 output = {} 20 21 for alph, nums in data.items(): 22 avg = {} 23 my_list = data[alph] 24 for target_alph, target_nums in data.items(): 25 target_list = data[target_alph] 26 if alph == target_alph: 27 continue 28 max_nums = [] 29 30 for i in my_list: 31 max_num = 0 32 for j in target_list: 33 result = i * j 34 if result is not None and result > max_num: 35 max_num = result 36 max_nums.append(max_num) 37 avg[target_alph] = sum(max_nums) / len(max_nums) 38 output[alph] = avg 39 return output 40 41def changed1(data): 42 idx = list(data.keys()) 43 maxes = np.array([max(data[k]) for k in idx]) 44 means = np.array([sum(data[k])/len(data[k]) for k in idx]) 45 46 A = np.outer(means, maxes) 47 idx_ij = {k:i for i,k in enumerate(idx)} 48 d = {k:{} for k in idx} 49 for k1,k2 in permutations(idx, 2): 50 d[k1][k2] = A[idx_ij[k1]][idx_ij[k2]] 51 return d 52 53print(original(data1)) 54print(changed1(data1)) 55""" => 56{'B': {'A': 48.0, 'C': 42.666666666666664}, 'A': {'B': 37.285714285714285, 'C': 33.142857142857146}, 'C': {'B': 45.0, 'A': 45.0}} 57{'B': {'A': 48.0, 'C': 42.666666666666664}, 'A': {'B': 37.28571428571429, 'C': 33.142857142857146}, 'C': {'B': 45.0, 'A': 45.0}} 58""" 59 60print(timeit.timeit(lambda : original(data1), number=10000)) 61print(timeit.timeit(lambda : changed1(data1), number=10000)) 62""" => 630.2061475639929995 640.27564139396417886 65""" 66 67print(timeit.timeit(lambda : original(data2), number=10)) 68print(timeit.timeit(lambda : changed1(data2), number=10)) 69""" => 704.815463805978652 710.01332262804498896 72""" 73 74print(timeit.timeit(lambda : changed1(data3), number=10)) 75""" => 761.288064556021709 77""" 78

そこまでスマートなコードではありませんが、とりあえず2桁強は改善しているようです。

投稿2018/08/07 07:18

編集2018/08/07 07:19
hayataka2049

総合スコア30933

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

※直接の回答ではないです。

並列化の検討や、アルゴリズムの無駄以前にコードが無駄なく書かれていますか?

python

1for alph, nums in data.items(): 2 avg = {} 3 my_list = data[alph]

これnums==my_listでは。

投稿2018/08/03 08:49

編集2018/08/03 10:09
mkgrei

総合スコア8560

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2018/08/07 00:55

ご回答いただきましてありがとうございます。 ご指摘の通り、nums==my_listです。 my_list = data[alph] とするよりも my_list = nums とした方が効率がいいのでしょうか。
退会済みユーザー

退会済みユーザー

2018/08/07 00:56

target_list = data[target_alph] で比較対象のリストを読み込んでいるので、わかりやすさを重視して、 my_list = data[alph] としました。
退会済みユーザー

退会済みユーザー

2018/08/07 01:14

my_list = numsとtarget_list = target_numsに変更したところ、同じ出力が得られましたが、これは処理の高速化に繋がるのでしょうか。
mkgrei

2018/08/07 01:25

変数名にこだわりがあるのであれば、 for alph, my_list in data.items(): にすれば済む話です。 これによって高速化することはありません。 ただ、コードに必要のない行が存在することで見通しを悪くしています。 今回の質問は並列化についてですが、並列化の検討以前にデータ構造とアルゴリズムについて検討する必要があります。 この検討の際にコードが簡潔で整理されている方が変更によってバグが生じにくく、かつ検討の時間短縮にもつながります。
退会済みユーザー

退会済みユーザー

2018/08/07 03:44

お返事いただきましてありがとうございます。
guest

0

まずはこの部分だけ以下のような関数に切り出すと並列化しやすくなりますよ。

python

1 max_nums = [] 2 3 for i in my_list: 4 max_num = 0 5 for j in target_list: 6 result = i * j 7 if result is not None and result: 8 max_num = result 9 max_nums.append(max_num) 10 avg[target_alph] = sum(max_nums) / len(max_nums)

python

1def avg_of_max_nums(my_list, target_list): 2 ... # 以下のようにmax_numsの平均を計算して返す関数にする 3 return sum(max_nums) / len(max_nums) 4 5# avg[target_alph] = avg_of_max(my_list, target_list) 6# の様に使う

あとは小手先の高速化を2点。

  1. if result is not None and result:は常に真になるので不要では?
  2. 平均の計算は多分statistics.meanを使ったほうが速いと思う。

最後に並列化はconcurrent.futures.ProcessPoolExecutormultiprocessing.pool.Poolを使うと良いと思います。

投稿2018/08/03 08:34

編集2018/08/03 09:15
YouheiSakurai

総合スコア6142

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

hayataka2049

2018/08/03 08:46 編集

statistics.meanはびっくりするくらい遅かったです。というか、sumが速いというべきか >>> import statistics >>> import timeit >>> lst = list(range(1000)) >>> timeit.timeit(lambda :sum(lst)/len(lst), number=1000) 0.012537279006210156 >>> timeit.timeit(lambda :statistics.mean(lst), number=1000) 0.5525303650065325
YouheiSakurai

2018/08/03 09:13

ほんとですね。statistics.meanの中身を確認してみたら、CではなくPythonで色々と余計な処理をしていたので、そら遅いわって思いました。
mkgrei

2018/08/03 09:48

for文で回しているとresultがNoneになることはなく、max_numが常に更新されているので、最後だけ計算すればよいことになります。 たぶん元のコードがバグっています。
mkgrei

2018/08/03 09:55

max_num = 0 for j in target_list: ..result = i * j ..if result is not None and result: ....max_num = result max_nums.append(max_num) 少なくとも、上のは max_num = max([i*j for j in target_list]) max_nums.append(max_num) のような。 変数名を信じるのであればですが。 内包表記になってたぶん10倍はやくなりましたね(憶測)
YouheiSakurai

2018/08/03 09:58

ほんとですね。どの単位で並列化するのが効率良さそうかという点しか考えてませんでした。
hayataka2049

2018/08/03 10:05 編集

>mkgreiさん 私もちょっとあれこれ試しましたが、その内包表記はlistインスタンス生成のオーバーヘッド分(だけかどうかはちょっとよくわかりませんが)遅いです target_listの最大値とiをかけてあげてください(もしiが負数なら最小値か)
mkgrei

2018/08/03 10:15

確かにw 以前にlistを一度生成するかgeneratorかでlistを生成した方が速いことがあったので確かめていませんでした。 最初にdataについてmaxを取ればn^2から2nに落ちますね。 でもたすき掛けなので、たぶんやりたいことは別にあるのだと思っています。
hayataka2049

2018/08/03 10:27 編集

掲載されているコードを合理的に解釈すると、maxとmeanの外積(outer)っぽいのですが、断定はできないので 質問が修正されてから「numpyで多少工夫して書けば数桁は速くなるけど、並列化しますか?」という回答を書くつもりでいます
退会済みユーザー

退会済みユーザー

2018/08/07 01:42

YouheiSakuraiさま、 ご回答いただきましてありがとうございます。関数切り出しに関しまして、質問文中のご回答を受けて試したことに追記させていただきました。お手数おかけしますが、ご確認いただけますと幸いです。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問