Pythonで辞書型データから高速に検索したい

以下の辞書型のデータ構造で，valueから検索したいケースが生じてしまい，良い検索手段を検討しております。
高速な方法があればご教授いただきたいです。

以下のような文字列をkeyとし，文字列が格納されたリストがvalueになった辞書型のデータ構造で，数万レコードあります。

なお，リスト[0]がkeyと同値になっています。

python
1test_dict =
2{"A":["A","B","C"],
3 "B":["B","C","D"],
4 :
5 "X":["X","Y","Z"]}

これまではこの辞書型データに対して，keyを利用した検索を行っておりました。

python
1>print(test_dict["A"])
2["A","B","C"]

しかし，リスト[1]が"B"のリストを取得したいという事態となりました。

これを純粋にやると以下のようになり性能懸念があり，改善策を検討しております。

python
1index = 1     # 取得したい値のインデックス
2target = "B"  # 取得したい値
3
4for key, value in test_dict.items():
5    if target == value[index]:
6        print(value) # ["A","B","C"]

良い方法があればご教授ください。

行動規範の内容に同意します

回答3件

ベストアンサー

検索回数によってやるべきことが変わります。

一度しか検索しないのであればO(N)を我慢するしかありません。

何度も検索するのであれば、最初にそのための辞書を作ってからの方が速くなります。

衝突回避版。

python
1test_dict = {
2    "A":["A","B","C"],
3    "B":["B","C","D"],
4    "X":["X","Y","Z"],
5}
6
7test_dict_1 = {}
8for k, v in test_dict.items():
9    if v[1] in test_dict_1:
10        test_dict_1[v[1]].append(k)
11    else:
12        test_dict_1[v[1]] = [k]
13
14print([test_dict[k] for k in test_dict_1['B']])

投稿2018/02/21 11:30

編集2018/02/21 14:28

mkgrei

総合スコア8562

こうやってあらかじめデータ構造を変更してみればいかがでしょうか？

python
1test_dict = {
2    "A":["A","B","C"],
3    "B":["B","C","D"],
4    "X":["X","Y","Z"],
5}
6 
7test_dict_1 = {v[1]: v for v in test_dict.values()}
8print(test_dict_1)

投稿2018/02/21 11:30

YouheiSakurai

総合スコア6149

mkgrei

2018/02/21 11:31

keyが複数存在した場合が少し面倒ですね。

YouheiSakurai

2018/02/21 11:34

そうですね。前提のデータによってはそのコーナーケースに殺される可能性はありますね。

badtz

2018/02/21 12:04

ご回答ありがとうございます。 print(test_dict_1["B"])と理解しました。 test_dictのkeyはユニークで，リストの要素数はすべて同じになっています。何度も検索するのですが，毎回検索したいインデックスと値が異なるので一度切りです。 list[1]の”B"，list[2]の”Z"，list[1]の”C"と検索したい時に， list[1]の”B"，list[1]の”C"，list[2]の”Z"の順番に変更する(インデックス毎に分ける)と，上記の方法で早くなりそうです。

行動規範の内容に同意します

Pythonの機能だけだと改善のしようがないので、pandasのDataFrameを使った方法で回答します。

Python
1import pandas as pd
2test_dict = {
3     "A":["A","B","C"],
4     "B":["B","C","D"],
5     "X":["X","Y","Z"]
6}
7df = pd.DataFrame.from_dict(test_dict, orient="index")
8print(df)
9
10#    0  1  2
11# A  A  B  C
12# B  B  C  D
13# X  X  Y  Z

これで今までのデータをDataFrameに移行しました。
ここから、

Python
1index = 1     # 取得したい値のインデックス
2target = "B"  # 取得したい値
3
4result = df[df[index] == target]
5result = result.values.tolist()  # コメントアウトしても動きます
6print(result)
7# [['A', 'B', 'C']]

などと出来ます。結果が配列の配列になっているのは、該当するレコードが２個以上になる場合もあるためです。
ただ、kyeアクセスには少しだけ手間が増えますので、場合によってはリファクタリング箇所が増えてしまう恐れがあります。

Python
1key = "X"
2value = df.loc[key].tolist()
3print(value)
4# ['X', 'Y', 'Z']

ご参考までに。

追記
速度を測ってみました。結論から言うと、1回の検索ですらpandasのほうが平均して遅いという結果になりました。

適当にデータを作成

Python
1import pandas as pd
2from itertools import product
3temp = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
4test_dict = {s+t+u: [s+t+u+"0", s+t+u+"1", s+t+u+"2"] for s, t, u in product(temp, repeat=3)}
5df = pd.DataFrame.from_dict(test_dict, orient="index")
6print("head")
7print(df.head())
8print("tail")
9print(df.tail())
10print("レコード数", len(df))
11
12# head
13#         0     1     2
14# aaa  aaa0  aaa1  aaa2
15# aab  aab0  aab1  aab2
16# aac  aac0  aac1  aac2
17# aad  aad0  aad1  aad2
18# aae  aae0  aae1  aae2
19# tail
20#         0     1     2
21# ZZV  ZZV0  ZZV1  ZZV2
22# ZZW  ZZW0  ZZW1  ZZW2
23# ZZX  ZZX0  ZZX1  ZZX2
24# ZZY  ZZY0  ZZY1  ZZY2
25# ZZZ  ZZZ0  ZZZ1  ZZZ2
26# レコード数 140608

これに対して元の方法とpandasを比較します。

Python
1def get_value0(index, target):
2    # 元の方法
3    for key, value in test_dict.items():
4        if target == value[index]:
5            return value
6
7def get_value1(index, target):
8    # pandas使った方法
9    return df[df[index] == target].values.tolist()[0]
10
11# 探したいデータ        
12index = 2     # 取得したい値のインデックス
13target = "Gcw2"  # 取得したい値
14
15# 同じ結果になるか確認
16assert get_value0(index, target) == get_value1(index, target)
17
18# 元の方法
19%timeit get_value0(index, target)
20# 7.78 ms ± 131 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
21
22# pandasを使った方法
23%timeit get_value1(index, target)
24# 11.7 ms ± 231 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)