python - 将字典转换为平面数据结构(列表或元组)的有效方法

Question

我实现了一个 breadth-first search对于棋盘游戏。在这里我使用 dict以反射(reflect)每个级别的重复电路板配置。目前，整体搜索几乎占用了我所有的 RAM (16GB) 用于一次启动配置。我计划为不同的启动配置集成交叉检查。所以我需要对我找到的配置的读取权限，并且如果该级别完成，则该级别的字典不会更改。

这就是我计划转换 dict 的原因进入平面数据结构( list 或 tuple )，键为 [2n] [2n+1] 的位置和值在我评估下一个级别之前的位置。

问题是从 {1: 2, 3: 4} 中找到一个快速 转换至 [1, 2, 3, 4]对于 dict超过10**8项目。

我找到了 sum(dict.items(), ())来自 a comment by Natim至 another question ，它有效，但速度太慢(它似乎停止工作 dict 超过 10**6 个项目)。

Answer 1

你可以试试这个:

dct = {1:2, 3:4, 5:6, 7:8}

out = [None] * 2*len(dct)

for idx, (out[2*idx],out[2*idx+1]) in enumerate(dct.items()):
    pass

print(out)

输出:

[1, 2, 3, 4, 5, 6, 7, 8]

使用大小为 50_000_000 的字典检查运行时: (在 colab 上)

from timeit import timeit
import operator, functools
from itertools import chain

def approach1(dct):
    li = []
    for k, v in dct.items():
        li.extend([k,v])
    return li

def approach2(dct):
    out = [None] * 2*len(dct)
    for idx, (out[2*idx],out[2*idx+1]) in enumerate(dct.items()):
        pass
    return (out)

def approach3(dct):
    return functools.reduce(operator.iconcat, dct.items(), [])

def approach4(dct):
    return list(chain.from_iterable(dct.items()))

def approach5(dct):
    return [i for t in dct.items() for i in t]
    
funcs = approach1, approach2, approach3, approach4, approach5
dct = {i:i for i in range(50_000_000)}

for _ in range(3):
    for func in funcs:
        t = timeit(lambda: func(dct), number=1)
        print('%.3f s ' % t, func.__name__)
    print()

输出:

8.825 s  approach1
13.243 s  approach2
4.506 s  approach3
3.809 s  approach4
7.881 s  approach5

8.391 s  approach1
13.159 s  approach2
4.487 s  approach3
3.854 s  approach4
7.946 s  approach5

8.391 s  approach1
13.197 s  approach2
4.448 s  approach3
3.681 s  approach4
7.904 s  approach5

使用不同大小的字典检查运行时: (在 colab 上)

from timeit import timeit
import operator, functools
from itertools import chain
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
def app_extend(dct):
    li = []
    for k, v in dct.items():
        li.extend([k,v])
    return li
def app_enumerate(dct):
    out = [None] * 2*len(dct)
    for idx, (out[2*idx],out[2*idx+1]) in enumerate(dct.items()):
        pass
    return (out)
def app_functools(dct):
    return functools.reduce(operator.iconcat, dct.items(), [])
def app_chain(dct):
    return list(chain.from_iterable(dct.items()))
def app_for(dct):
    return [i for t in dct.items() for i in t]
funcs = app_extend, app_enumerate, app_functools, app_chain, app_for
dct_rslt = {}
for dct_size in [100_000, 250_000, 500_000, 1_000_000, 2_500_000, 5_000_000, 10_000_000, 25_000_000, 50_000_000]:
    dct = {i:i for i in range(dct_size)}
    dct_rslt[str(dct_size)] = {func.__name__ : timeit(lambda: func(dct), number=1) for func in funcs}
df = pd.DataFrame(dct_rslt).T
fig, ax = plt.subplots()
fig.set_size_inches(12, 9)
sns.lineplot(data=df)
plt.xlabel('Dictionary Size')
plt.ylabel('Time(sec)')
plt.show()