将字典转换为平面数据结构（列表或元组）的有效方法

Question

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

这就是为什么我计划将 dict 转换为平面数据结构（list 或 tuple），键位于 [2n] 位置，值位于 [=15] =] 在我评估下一个级别之前的位置。

问题是为 dict 找到一个从 {1: 2, 3: 4} 到 [1, 2, 3, 4] 的快速转换，项目超过 10**8 .

我从 a comment by Natim to another question 中找到了 sum(dict.items(), ())，它有效，但速度太慢（它似乎在 dict 秒内停止工作超过 10**6 个项目）。

Answer 1

附加和扩展 list 在 python 中非常有效：

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

因此，上述明显幼稚的函数在性能方面击败了非常紧凑且不知何故也很优雅的表达式 list(sum(d.items(), ()))。

Answer 2

您可以对字典的项目使用列表理解：

d = {1: 2, 3: 4}
print([i for t in d.items() for i in t])

这输出：

[1, 2, 3, 4]

Answer 3

使用itertools函数chain和classmethod替代构造函数from_iterable:

>>> from itertools import chain
>>> list(chain.from_iterable(dct.items()))
[1, 2, 3, 4]
>>>

或 operator.iconcat 和 functools.reduce:

>>> import operator, functools
>>> functools.reduce(operator.iconcat, dct.items(), [])
[1, 2, 3, 4]
>>>

Answer 4

你可以试试这个：

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]

使用 dictionary 检查运行时大小为 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

检查 dictionary 不同大小的运行时： （在 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()

将字典转换为平面数据结构（列表或元组）的有效方法

Efficient way to convert a dict into a flat data structure (list or tuple)

python

performance

dictionary

list

memory-efficient