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

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

ただいまの
回答率

90.42%

  • Python

    9718questions

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

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

解決済

回答 2

投稿 編集

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

KK-31

score 13

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

dict1 = {"a":"100","b":"200","c":"300"} #例です。 (大量に辞書リストくらいあることを想定
target_list =["a","b","c","d"] #例です。 (大量にデータがある事を想定

new_list = [] #list初期化
new_list = [ list(map(dict(dict1).get, document)) for document in target_list]
print(new_list)
#[['100'], ['200'], ['300'], [None]]


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

追記

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

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

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

  • quiqui

    2018/02/01 11:33 編集

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

    キャンセル

  • KK-31

    2018/02/01 11:46

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

    キャンセル

  • quiqui

    2018/02/01 12:27

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

    キャンセル

回答 2

+3

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

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

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

 コード

from collections import defaultdict
from functools import partial
from random import random
from timeit import timeit
from uuid import uuid4


import numba
import cython


def testdata(n_table, n_list):
    return (
        {str(uuid4()):random() for _ in range(n_table)},
        [str(uuid4()) for _ in range(n_list)],
    )


def pattern1(dict1, target_list):
    return [*map(dict1.get, target_list)]


def pattern2(dict1, target_list):
    dict1 = defaultdict(lambda: None, dict1)
    return [dict1[k] for k in target_list]


def pattern3(dict1, target_list):
    return [dict1.get(k) for k in target_list]


def pattern4(dict1, target_list):
    return list(map(dict1.get, target_list))


def pattern5(dict1, target_list):
    def gen(T, L):
        for i in L:
            try:
                yield T[i]
            except KeyError:
                yield None
    return list(gen(dict1, target_list))


def pattern6(dict1, target_list):
    def gen(T, L):
        T_get = T.get
        for i in L:
            yield T_get(i)
    return list(gen(dict1, target_list))


pattern7 = numba.jit(pattern4)


def pattern8(dict1, target_list):
    @numba.jit
    def gen(T, L):
        T_get = T.get
        for i in L:
            yield T_get(i)
    return list(gen(dict1, target_list))


pattern9 = partial(cython.inline, "list(map(dict1.get, target_list))")
pattern9(dict1={}, target_list=[])


if __name__ == "__main__":
    T, L = testdata(100000, 1000000)

    for i in range(9):
        func = "pattern%d" % (i + 1)
        elapsed = timeit(func + "(dict1=T, target_list=L)",
                         number=10, globals=globals()) / 10
        print("%s: %.3f sec" % (func, elapsed))

 実行結果

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 20:08

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

    キャンセル

  • 2018/02/02 08:23

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

    キャンセル

checkベストアンサー

+1

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

def func(N):
    # とりあえずキーは文字列とする
    dict1 = {('%06d'%i):i for i in range(N)}
    print(dict1)
    # {'000000': 0, '000001': 1}

    target_list = [('%06d'%(i%N)) for i in range(3*N)]
    print(target_list)
    # ['000000', '000001', '000000', '000001', '000000', '000001']

    new_list = [ list(map(dict(dict1).get, document)) for document in target_list]
    print(new_list) # これが求めたいリスト?
    # [[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]]

    new_list = [ dict1.get(document) for document in target_list]
    print(new_list) # こちらでは?
    # [0, 1, 0, 1, 0, 1]

func(2)

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

def printTime( prev):
    cur = time.time()
    print ("elapsed[%.3f][sec]"%(cur - prev))
    return cur

def func(N):
    prev = time.time()
    dict1 = {('key%06d'%i):('val%06d'%i) for i in range(N)}
    prev = printTime(prev)
    target_list = [('key%06d'%(i%N)) for i in range(3*N)]
    prev = printTime(prev)
    new_list = [ [dict1.get(document)] for document in target_list]
    prev = printTime(prev)
func(1000000)
"""
elapsed[0.794][sec]
elapsed[1.138][sec]
elapsed[2.558][sec]
"""

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/02/01 11:59

    [ dict1.get(document) for document in target_list]

    このような形が欲しい値と一致しています。
    これ以上に高速化する場合は、並列処理させるなどの手法しかないでしょうか?

    キャンセル

  • 2018/02/01 13:03

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

    キャンセル

  • 2018/02/01 13:22

    ありがとうございました。
    差し支えなければ、実行環境のについて可能な範囲で教えていただけませんでしょうか。

    CPU:
    pythonバージョン:
    実行方法など

    こちらの環境では、同条件で、26秒かかりました。

    キャンセル

  • 2018/02/01 13:26

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

    キャンセル

  • 2018/02/01 13:28

    N個の内容が欲しくて、O(N)なので、これ以上は高速化できないと思われますね。

    データがたくさんあるのなら、データベースに突っ込んだほうが速くなるかもしれません。
    pandasやsqliteを使うことによって実行時間を減らせるかもしれません。

    データがたくさんあるのならメモリに載せた後どうするかによって方法を選択するのがよいと思われます。

    キャンセル

  • 2018/02/01 13:38

    mkgrei様

    アドバイスありがとうございます。
    辞書サイズは、10万ペアで置換対象データは、100万データです。
    こちらをデータベースに書き出すI/Oのほうが時間がかかりそうな気がします。

    やりたい事は、listの中身を辞書dict型のValue値に置換する処理です。
    何か具体的に方策はありますでしょうか。

    キャンセル

  • 2018/02/01 13:45 編集

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

    キャンセル

  • 2018/02/01 13:50

    can110様、mkgrei様、

    環境などについて見直しを行ってみます。
    func(1000000)にて行いましたので、同条件になっております。

    ご回答・ご教授ありがとうございました。
    大変助かりました。またよろしくお願い致します。

    キャンセル

  • 2018/02/01 13:53

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

    キャンセル

  • 2018/02/01 14:01

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

    キャンセル

  • 2018/02/01 14:21

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

    キャンセル

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

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

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

  • Python

    9718questions

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