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

Question

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

pythonlistperformancedictionarymemory-efficient

3

我为一个棋盘游戏实现了广度优先搜索。在这里，我使用dict来反映每个级别上的重复棋盘配置。目前，对于一个起始配置，整体搜索几乎占用了我所有的RAM（16GB）。我计划为不同的起始配置集成交集检查。因此，我需要读取我找到的配置，并且如果级别完成，则该级别的dict将不会更改。

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

问题在于：如何从{1: 2, 3: 4}快速转换为[1, 2, 3, 4]以处理包含超过10**8项的dict？

我从Natim的评论到另一个问题找到了sum（dict.items（），（）），它可以工作，但速度太慢了（对于具有超过10 ** 6个项的dict似乎停止工作）。

- Wolf

4个回答

0

在Python中，向list追加和扩展元素非常高效：

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

因此，从性能的角度来看，上述表面上看起来很朴素的函数胜过了非常紧凑且优雅的表达式list(sum(d.items(), ()))。

- Wolf

2

list(chain.from_iterable(a.items())) - jizhihaoSAMA

有点遗憾的是，这个第一反应并没有开始回答。我认为我更可能会将“从可迭代对象中获取链”这个口号记在心里，而不是使用稍微快一些但需要更多步骤的函数式方案。 - Wolf

0

你可以使用字典项的列表推导式：

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

这将输出：

[1, 2, 3, 4]

- blhsing

和“朴素函数”基本一样的速度。 - Wolf

0

使用 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]
>>>

- U13-Forward

让我们在聊天中继续这个讨论。 - Wolf

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- I'mahdi · Accepted Answer

您可以尝试这个方法：

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

检查使用不同尺寸的字典的运行时：（在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()