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

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

ただいまの
回答率

91.37%

  • Python

    3802questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    2398questions

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

pythonの高速化について

解決済

回答 3

投稿 2017/12/07 16:47

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

guinn4192

score 2

前提・実現したいこと

pythonで組んだプログラムを高速化したいと考えています。大学の研究で配送計画問題という問題を解くプログラムを組み、解を導出するところまで実装したのですが、いざ実行すると非常に遅く、研究するにあたって非効率的です。for文の中でTWと名付けた関数を回し、そのTW関数内で更にfor文を回していることが低速である原因だと考えているのですが、うまくfor文を回避して書く方法や他に高速化する方法が有りましたらご教授頂きたいです。

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

上記のように、プログラムが低速である

該当のソースコード

import tkinter as tk
import tkinter.filedialog as fd
import numpy as np
import math
import matplotlib.pyplot as plt
import itertools

root=tk.Tk()
root.withdraw()

def TW():
    global early 
    global late 
    global route_list
    global cap
    global cap_over
    global route_sum
    global n_vhicle
    early = 0
    late = 0
    route_list = []
    cap_over = 0
    route_sum = 0
    for k in range(1,len(buff)):#時間枠の計算
        j = 0
        x = 0
        y = []
        cap = 0
        t = 0
        if path_list[0][k] == 1:#デポ->顧客kに経路があるなら
            x += distance_customer[0][k]#距離を足し合わせて
            cap += buff[k][2]
            if x < buff[k][3]:
                early += (buff[k][3] - x)#早ければearly
            elif x > buff[k][4]:
                late += (x-buff[k][4])#遅ければlateにどれだけずれたかを入れる
            y.append(0)
            y.append(k)
            i = k

            while True:
               if path_list[i][j] == 1:#上とおんなじ
                   #print(distance_customer[i][j])
                   cap += buff[j][2]
                   x += distance_customer[i][j]
                   if x < buff[j][3]:
                       early += (buff[j][3] - x)
                   elif x > buff[j][4]:
                       late += (x-buff[j][4])    
                   y.append(j)

                   if j ==0:
                       if cap > vehicle_capacity:
                           cap_over = cap - vehicle_capacity
                       #print(f"経路:{y},経路の移動コスト:{x},早着時間:{early},遅刻時間:{late},積載量超過:{cap_over}")
                       #print("")
                       route_list.append(y)

                       break
                   else:
                       i = j
                       j = 0

               else:
                   j += 1
    n_vhicle = len(route_list)
    for i,value in np.ndenumerate(path_list):#総走行距離の計算
        if path_list[i[0]][i[1]] == 1:
            route_sum += distance_customer[i[0]][i[1]]

    #print(f"総走行距離:{route_sum}")

def EF(Evaluationf):
    global best_path_list
    global best_route_list
    new_Evaluationf = route_sum + 0.1*early + 100*late + cap_over +100*n_vhicle
    if Evaluationf > new_Evaluationf:
        Evaluationf = new_Evaluationf
        best_path_list = path_list.copy()
        best_route_list = route_list
        print(route_list)
    return Evaluationf
######################################


TW()#TW関数で時間枠の計算
#print(order_list)
#print(demand_list)

#print(f"早着時間:{early}")
#print(f"遅刻時間:{late}")
#print(f"ルート:{route_list}")
#print(f"長さ:{length_list}")
Evaluationf = 1000000
Evaluationf = EF(Evaluationf)#評価関数
#print(f"トラックの数:{len(route_list)}")#トラックの数


while True:
    tmp_path_list = path_list.copy()
    tmp_route_list = route_list
    tmp_Evaluationf = Evaluationf
    for i,j in itertools.combinations(range(len(tmp_route_list)),2):
        for k,l in itertools.product(
                itertools.combinations_with_replacement(
                range(len(tmp_route_list[i][:-1])),2),
                itertools.combinations_with_replacement(
                range(len(tmp_route_list[j][:-1])),2)):
            path_list = tmp_path_list.copy()
            I = tmp_route_list[i][k[0]]
            K = tmp_route_list[i][k[1]]
            J = tmp_route_list[j][l[0]]
            L = tmp_route_list[j][l[1]]
            Id = tmp_route_list[i][k[0]+1]
            Kd = tmp_route_list[i][k[1]+1]
            Jd = tmp_route_list[j][l[0]+1]
            Ld = tmp_route_list[j][l[1]+1]
            path_list[I][Id] = 0
            path_list[K][Kd] = 0
            path_list[J][Jd] = 0
            path_list[L][Ld] = 0
            if ((I != K) and (J != L)) or ((I == K) and (J == L)):                
                path_list[I][Jd] = 1
                path_list[K][Ld] = 1
                path_list[J][Id] = 1
                path_list[L][Kd] = 1
            elif (I != K) and (J == L):
                path_list[I][Kd] = 1
                path_list[J][Id] = 1
                path_list[K][Jd] = 1
            elif (I == K) and (J != L):
                path_list[J][Ld] = 1
                path_list[I][Jd] = 1
                path_list[L][Id] = 1

            TW()


            Evaluationf = EF(Evaluationf)
    if Evaluationf  == tmp_Evaluationf:
        break
    else:
        print("No")
    tmp_Evaluationf = Evaluationf
    path_list = best_path_list.copy()                                                                        
    route_list = best_route_list
for i in range(len(path_list)):
    for j in range(len(path_list)):
        if path_list[i][j] == 1:
            print(f"({i},{j})経路有り")
np.set_printoptions(threshold=np.inf,linewidth=np.inf)#numpyの配列を省略せず全表示するオプション
print(f"トラックの数:{len(route_list)}")#トラックの数
print(route_list)
#print(path_list)
for i in range(len(buff)):
    for j in range(len(buff)):
        if path_list[i][j] == 1:
            x = [buff[i][0],buff[j][0]]
            y = [buff[i][1],buff[j][1]]
            plt.plot(x,y,lw=0.5,alpha = 0.5)
plt.scatter(buff[:,0],buff[:,1],s = 2)
plt.show()

試したこと

nambaというコンパイラを試してみたのですが、どの関数に対しても以下のようなエラーで使用できませんでした。未実装によるエラーとのことですが、調べてもわからず、numbaは使えずにいます。
関数内にリストを初期化したり,print(f"hoge")など書くとエラーを吐くようですが、これらを除いても駄目でした。
NotImplementedError: Failed at object (analyzing bytecode)
Use of unknown opcode STORE_GLOBAL

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

言語:python3.6.1
OS:windows8.1pro
プロセッサ:Intel(R)Core(TM) i5-4460 CPU @ 3.20GHz
メモリ:16GB

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 3

+2

そのTW関数内で更にfor文を回していることが低速である原因だと考えている

といった推測を正に検証する為のツールがプロファイラです。   

Pythonプロファイリング基礎 で紹介されているline_profilerだと、スクリプト中の各行がどれだけ時間を食っているのか網羅的に調査できます。特に足をひっぱっている部分をこれによって特定し、集中的にリファインしていくとよいでしょう。 

投稿 2017/12/07 17:46

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/12/07 18:12

    言われてみると、実際にどこがボトルネックなのか調べてから質問するべきでした。一度プロファイルしてみます。ありがとうございます。

    キャンセル

checkベストアンサー

+1

Cythonというものがあります。
PythonとC/C++言語でPythonを高速化出来るみたいです。
以下の記事が詳しく説明されていたので載せておきます。
深入りしないCython入門 - Qiita

投稿 2017/12/07 16:50

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/12/07 17:24

    cythonはCの知識が必要だと聞いていたのですが、jupyter上でなら比較的容易に使用できるのですね。試してみます。ありがとうございます。

    キャンセル

+1

global変数への代入が実装されていないようです。
頑張って各変数を引数で渡すように修正すれば動作するかもしれません。

import numpy as np
from numba.decorators import jit,autojit

x = 0

@jit
def pairwise_numba(X, D):
    global x
    x = 0 # Use of unknown opcode STORE_GLOBAL at line 10 of ~hoge.py
    M = X.shape[0]
    N = X.shape[1]
    for i in range(M):
        for j in range(M):
            d = 0.0
            for k in range(N):
                tmp = X[i, k] - X[j, k]
                d += tmp * tmp
            D[i, j] = np.sqrt(d)

X = np.random.random((1000, 3))
D = np.empty((1000, 1000))

pairwise_numba(X, D)


numba知らなかったですが、簡単に使えそうですね。

投稿 2017/12/07 17:37

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/12/07 18:10

    今自分でも確認したところ、確かにglobalに代入するとエラーになりました。numbaを使用するならソースコードを整理する必要があるのですね。参考になりました。ありがとうございます。

    キャンセル

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

ただいまの回答率

91.37%

関連した質問

同じタグがついた質問を見る

  • Python

    3802questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    2398questions

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