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

Question

前提・実現したいこと

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

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

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

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

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

該当のソースコード

data = {
	'A':[1, 3, 5, 2, 1, 8, 9],
	'B':[9, 4, 3], 
	'C':[8, 5, 5, 6, 1]
}

output = {}

for alph, nums in data.items():
	avg = {}
	my_list = data[alph]
	for target_alph, target_nums in data.items():
		target_list = data[target_alph]
		if alph == target_alph:
			continue
		max_nums = []

		for i in my_list:
			max_num = 0
			for j in target_list:
				result = i * j
				if result is not None and result > max_num:
					max_num = result
			max_nums.append(max_num) 
		avg[target_alph] = sum(max_nums) / len(max_nums)
	output[alph] = avg
print(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を使用する必要があるため、関数を用いてもうまく効率化する術がわかりません。

#!/usr/bin/env python
# coding: utf-8

data = {
    'A':[1, 3, 5, 2, 1, 8, 9],
    'B':[9, 4, 3], 
    'C':[8, 5, 5, 6, 1]
}

output = {}

for alph, nums in data.items():
    avg = {}
    my_list = nums
    for target_alph, target_nums in data.items():
        target_list = target_nums
        """
        if alph == target_alph:
            continue
        max_nums = []

        for i in my_list:
            max_num = 0
            for j in target_list:
                result = i * j
                if result is not None and result > max_num:
                    max_num = result
            max_nums.append(max_num) 
        """
        avg[target_alph] = avg_of_max(my_list, target_list)
    output[alph] = avg
print(output)


def avg_of_max_nums(my_list, target_list):
    for alph, nums in data.items():
        for target_alph, target_nums in data.items():
            if alph == target_alph:
                continue
            max_nums = []

            for i in my_list:
                max_num = 0
                for j in target_list:
                    result = i * j
                    if result is not None and result > max_num:
                        max_num = result
                max_nums.append(max_num) 
             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

Comments

[hayataka2049]

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

[hayataka2049]

あと、if result is not None and resultは何か間違っているのでは（恐らく最大値更新のifだと思うが・・・）

[退会済みユーザー]

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

[hayataka2049]

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

[hayataka2049]

None判定必要ですか・・・？

[退会済みユーザー]

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

[hayataka2049]

負値はありえますか？

[退会済みユーザー]

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

Answer 1

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

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

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

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

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

import timeit
from itertools import permutations

import numpy as np

data1 = {
    'A':[1, 3, 5, 2, 1, 8, 9],
    'B':[9, 4, 3], 
    'C':[8, 5, 5, 6, 1]
}

data2 = {str(i):[np.random.randint(1000) for _ in range(50)]
         for i in range(50)}

data3 = {str(i):[np.random.randint(1000) for _ in range(500)]
         for i in range(500)}

def original(data):
    output = {}

    for alph, nums in data.items():
        avg = {}
        my_list = data[alph]
        for target_alph, target_nums in data.items():
            target_list = data[target_alph]
            if alph == target_alph:
                continue
            max_nums = []

            for i in my_list:
                max_num = 0
                for j in target_list:
                    result = i * j
                    if result is not None and result > max_num:
                        max_num = result
                max_nums.append(max_num) 
            avg[target_alph] = sum(max_nums) / len(max_nums)
        output[alph] = avg
    return output
    
def changed1(data):
    idx = list(data.keys())
    maxes = np.array([max(data[k]) for k in idx])
    means = np.array([sum(data[k])/len(data[k]) for k in idx])

    A = np.outer(means, maxes)
    idx_ij = {k:i for i,k in enumerate(idx)}
    d = {k:{} for k in idx}
    for k1,k2 in permutations(idx, 2):
        d[k1][k2] = A[idx_ij[k1]][idx_ij[k2]]
    return d

print(original(data1))
print(changed1(data1))
""" =>
{'B': {'A': 48.0, 'C': 42.666666666666664}, 'A': {'B': 37.285714285714285, 'C': 33.142857142857146}, 'C': {'B': 45.0, 'A': 45.0}}
{'B': {'A': 48.0, 'C': 42.666666666666664}, 'A': {'B': 37.28571428571429, 'C': 33.142857142857146}, 'C': {'B': 45.0, 'A': 45.0}}
"""

print(timeit.timeit(lambda : original(data1), number=10000))
print(timeit.timeit(lambda : changed1(data1), number=10000))
""" =>
0.2061475639929995
0.27564139396417886
"""

print(timeit.timeit(lambda : original(data2), number=10))
print(timeit.timeit(lambda : changed1(data2), number=10))
""" =>
4.815463805978652
0.01332262804498896
"""

print(timeit.timeit(lambda : changed1(data3), number=10))
""" =>
1.288064556021709
"""

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

Answer 2

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

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

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

これnums==my_listでは。

Comments

[退会済みユーザー]

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

[退会済みユーザー]

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

[退会済みユーザー]

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

[mkgrei]

変数名にこだわりがあるのであれば、
for alph, my_list in data.items():
にすれば済む話です。

これによって高速化することはありません。
ただ、コードに必要のない行が存在することで見通しを悪くしています。

今回の質問は並列化についてですが、並列化の検討以前にデータ構造とアルゴリズムについて検討する必要があります。
この検討の際にコードが簡潔で整理されている方が変更によってバグが生じにくく、かつ検討の時間短縮にもつながります。

[退会済みユーザー]

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

Answer 3

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

        max_nums = []

        for i in my_list:
            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) 
        avg[target_alph] = sum(max_nums) / len(max_nums)

def avg_of_max_nums(my_list, target_list):
    ...  # 以下のようにmax_numsの平均を計算して返す関数にする
    return sum(max_nums) / len(max_nums)

# avg[target_alph] = avg_of_max(my_list, target_list)
# の様に使う

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

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

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

Comments

[hayataka2049]

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]

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

[mkgrei]

for文で回しているとresultがNoneになることはなく、max_numが常に更新されているので、最後だけ計算すればよいことになります。

たぶん元のコードがバグっています。

[mkgrei]

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]

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

[hayataka2049]

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

[mkgrei]

確かにw

以前にlistを一度生成するかgeneratorかでlistを生成した方が速いことがあったので確かめていませんでした。

最初にdataについてmaxを取ればn^2から2nに落ちますね。
でもたすき掛けなので、たぶんやりたいことは別にあるのだと思っています。

[hayataka2049]

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

[退会済みユーザー]

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