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

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

新規登録して質問してみよう
ただいま回答率
85.51%
Python

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

Q&A

解決済

2回答

500閲覧

Python 3.x 辞書のキー値によって変換する場合の高速化

KK-31

総合スコア22

Python

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

0グッド

1クリップ

投稿2018/02/01 01:47

編集2018/02/01 05:26

Pythonにて、辞書(dict({key,value})を使って、list型の全要素をValue値に変換する際の、
高速化が可能かどうかをご教授いただきたいです。

python

1dict1 = {"a":"100","b":"200","c":"300"} #例です。 (大量に辞書リストくらいあることを想定 2target_list =["a","b","c","d"] #例です。 (大量にデータがある事を想定 3 4new_list = [] #list初期化 5new_list = [ list(map(dict(dict1).get, document)) for document in target_list] 6print(new_list) 7#[['100'], ['200'], ['300'], [None]] 8

上記コードのように、一応内包表記はしているのですが、速度改善のための方法を教えていただきたいです。

追記

デバッグ可能状態で実行したところ、26秒程度かかっておりましたが、
デバッグなしの状態では、全処理に3.515秒となりました。 
→アルゴリズム等の問題ではありませんでした。

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

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

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

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

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

quickquip

2018/02/01 02:35 編集

target_list の a と、dict1 の a は別物ですね? target_listの要素はリストやタプルなどで、その要素が dict1 のキーになっている? 最初の2行が例として相応しくない様に見えます。回答者がすぐに実行可能な形に修正した方がよいと思いました。
KK-31

2018/02/01 02:46

プログラムを修正しました。 ご回答のほどよろしくお願い致します。
quickquip

2018/02/01 03:27

結果がリストのリストなのは冗長で、実質can110さんの回答でいいのですね。諒解しました。
guest

回答2

0

気になって色々と試したけど、ピュアPythonのlist(map(dict1.get, target_list))が一番早いみたい。

ProcessPoolExecutorも試したけどオーバーヘッド(多分プロセス間のオブジェクト転送によるもの)で比較対照にはならず、元のPythonコードで最適化しているのでnumbacythonでも特に速くならず。

Cとか使ってPythonの外の世界で仕事をしないとこれ以上の高速化はできなさそうです。

コード

python

1from collections import defaultdict 2from functools import partial 3from random import random 4from timeit import timeit 5from uuid import uuid4 6 7 8import numba 9import cython 10 11 12def testdata(n_table, n_list): 13 return ( 14 {str(uuid4()):random() for _ in range(n_table)}, 15 [str(uuid4()) for _ in range(n_list)], 16 ) 17 18 19def pattern1(dict1, target_list): 20 return [*map(dict1.get, target_list)] 21 22 23def pattern2(dict1, target_list): 24 dict1 = defaultdict(lambda: None, dict1) 25 return [dict1[k] for k in target_list] 26 27 28def pattern3(dict1, target_list): 29 return [dict1.get(k) for k in target_list] 30 31 32def pattern4(dict1, target_list): 33 return list(map(dict1.get, target_list)) 34 35 36def pattern5(dict1, target_list): 37 def gen(T, L): 38 for i in L: 39 try: 40 yield T[i] 41 except KeyError: 42 yield None 43 return list(gen(dict1, target_list)) 44 45 46def pattern6(dict1, target_list): 47 def gen(T, L): 48 T_get = T.get 49 for i in L: 50 yield T_get(i) 51 return list(gen(dict1, target_list)) 52 53 54pattern7 = numba.jit(pattern4) 55 56 57def pattern8(dict1, target_list): 58 @numba.jit 59 def gen(T, L): 60 T_get = T.get 61 for i in L: 62 yield T_get(i) 63 return list(gen(dict1, target_list)) 64 65 66pattern9 = partial(cython.inline, "list(map(dict1.get, target_list))") 67pattern9(dict1={}, target_list=[]) 68 69 70if __name__ == "__main__": 71 T, L = testdata(100000, 1000000) 72 73 for i in range(9): 74 func = "pattern%d" % (i + 1) 75 elapsed = timeit(func + "(dict1=T, target_list=L)", 76 number=10, globals=globals()) / 10 77 print("%s: %.3f sec" % (func, elapsed)) 78

実行結果

pattern1: 0.212 sec pattern2: 0.576 sec pattern3: 0.277 sec pattern4: 0.199 sec pattern5: 0.502 sec pattern6: 0.302 sec pattern7: 0.214 sec pattern8: 2.336 sec pattern9: 0.220 sec

環境

C:\Users\sakurai>python -VV Python 3.6.1 (v3.6.1:69c0db5, Mar 21 2017, 18:41:36) [MSC v.1900 64 bit (AMD64)]

投稿2018/02/01 10:53

YouheiSakurai

総合スコア6142

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

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

YouheiSakurai

2018/02/01 11:08

追伸:データの桁をtestdata(1000000, 10000000)というふうに上げたら、pure python > numba > cythonとcythonが一番速くなった。
KK-31

2018/02/01 23:23

ありがとうございます。 大変参考になりました。
guest

0

ベストアンサー

欲しいリストを誤解しているかもしれませんがnew_list = [ dict1.get(document) for document in target_list]なのでは?

Python

1def func(N): 2 # とりあえずキーは文字列とする 3 dict1 = {('%06d'%i):i for i in range(N)} 4 print(dict1) 5 # {'000000': 0, '000001': 1} 6 7 target_list = [('%06d'%(i%N)) for i in range(3*N)] 8 print(target_list) 9 # ['000000', '000001', '000000', '000001', '000000', '000001'] 10 11 new_list = [ list(map(dict(dict1).get, document)) for document in target_list] 12 print(new_list) # これが求めたいリスト? 13 # [[None, None, None, None, None, None], [None, None, None, None, None, None], [None, None, None, None, None, None], [None, None, None, None, None, None], [None, None, None, None, None, None], [None, None, None, None, None, None]] 14 15 new_list = [ dict1.get(document) for document in target_list] 16 print(new_list) # こちらでは? 17 # [0, 1, 0, 1, 0, 1] 18 19func(2)

辞書100万、元リスト300万要素での実行結果
i7-3770, 16GB, Win10, Anaconda(x64), python=3.5.x

Python

1def printTime( prev): 2 cur = time.time() 3 print ("elapsed[%.3f][sec]"%(cur - prev)) 4 return cur 5 6def func(N): 7 prev = time.time() 8 dict1 = {('key%06d'%i):('val%06d'%i) for i in range(N)} 9 prev = printTime(prev) 10 target_list = [('key%06d'%(i%N)) for i in range(3*N)] 11 prev = printTime(prev) 12 new_list = [ [dict1.get(document)] for document in target_list] 13 prev = printTime(prev) 14func(1000000) 15""" 16elapsed[0.794][sec] 17elapsed[1.138][sec] 18elapsed[2.558][sec] 19"""

投稿2018/02/01 02:41

編集2018/02/01 05:20
can110

総合スコア38230

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

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

KK-31

2018/02/01 02:59

[ dict1.get(document) for document in target_list] このような形が欲しい値と一致しています。 これ以上に高速化する場合は、並列処理させるなどの手法しかないでしょうか?
can110

2018/02/01 04:03

アルゴリズム上は高速化する余地はほぼないと思います。 辞書100万、元リスト300万要素で当方環境では1秒程度でしたので 個人的には満足なのですが、並列化などすれば多少はスピードアップするかもしれません。
KK-31

2018/02/01 04:22

ありがとうございました。 差し支えなければ、実行環境のについて可能な範囲で教えていただけませんでしょうか。 CPU: pythonバージョン: 実行方法など こちらの環境では、同条件で、26秒かかりました。
KK-31

2018/02/01 04:26

(こちらの環境はAzure のNC6インスタンスになります)
mkgrei

2018/02/01 04:28

N個の内容が欲しくて、O(N)なので、これ以上は高速化できないと思われますね。 データがたくさんあるのなら、データベースに突っ込んだほうが速くなるかもしれません。 pandasやsqliteを使うことによって実行時間を減らせるかもしれません。 データがたくさんあるのならメモリに載せた後どうするかによって方法を選択するのがよいと思われます。
KK-31

2018/02/01 04:38

mkgrei様 アドバイスありがとうございます。 辞書サイズは、10万ペアで置換対象データは、100万データです。 こちらをデータベースに書き出すI/Oのほうが時間がかかりそうな気がします。 やりたい事は、listの中身を辞書dict型のValue値に置換する処理です。 何か具体的に方策はありますでしょうか。
can110

2018/02/01 04:48 編集

i7-3770, 16GB, Win10, Anaconda(x64), python=3.5.xです。 マシンスペックはこちらのほうが低そうですね。 回答で示したコードで「new_list = [ list(map(dict~」部分はコメントアウトし、func(1000000)呼出で26秒だとするとデータに差異はないので、ちょっと違いすぎる気もします。
KK-31

2018/02/01 04:50

can110様、mkgrei様、 環境などについて見直しを行ってみます。 func(1000000)にて行いましたので、同条件になっております。 ご回答・ご教授ありがとうございました。 大変助かりました。またよろしくお願い致します。
can110

2018/02/01 04:53

あ。 「new_list = [ dict1.get(document) for document in target_list]」の1行の処理のみで1秒です。 その前後の処理は計測に含めていませんので、念のため。
mkgrei

2018/02/01 05:01

取り出しは速いのですが、データ生成に時間がかかりますね。 数十秒ほど。
can110

2018/02/01 05:21

もうちょいちゃんと測ってみたら実際には3秒近くかかってました。 まあでも、こんなもんかなという気がします。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.51%

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

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

質問する

関連した質問