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

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

ただいまの
回答率

90.01%

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

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 625

tenjin

score 248

 前提・実現したいこと

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

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

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

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

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

 該当のソースコード

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • tenjin

    2018/08/07 09:48

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

    キャンセル

  • hayataka2049

    2018/08/07 10:41

    負値はありえますか?

    キャンセル

  • tenjin

    2018/08/07 10:44

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

    キャンセル

回答 3

checkベストアンサー

+2

アルゴリズムを改善して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桁強は改善しているようです。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

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

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

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

これnums==my_listでは。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/08/07 10:14

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

    キャンセル

  • 2018/08/07 10:25

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

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

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

    キャンセル

  • 2018/08/07 12:44

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

    キャンセル

+1

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

        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.ProcessPoolExecutormultiprocessing.pool.Poolを使うと良いと思います。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/08/03 19:15

    確かにw

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

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

    キャンセル

  • 2018/08/03 19:23 編集

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

    キャンセル

  • 2018/08/07 10:42

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

    キャンセル

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

  • ただいまの回答率 90.01%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる