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

I implemented a breadth-first search for a board game. Here I use a dict to reflect duplicate board configurations on each level. Currently, the overall search takes nearly all the RAM I have (16GB) for one start configuration, and I want to extend the program by checking intersections for different start configurations.

That's why I plan to convert the dict into a list with keys at [2n] and values at [2n 1] before going to the next level.

The problem is to find a fast conversion from {1: 2, 3: 4} to [1, 2, 3, 4] for dictwith more than 10**8 items.

I found sum(dict.items(), ()) from a comment by Natim to another question, which worked, but which is too slow (it seemingly stops working for dicts with more than 10**6 items). BTW, list and tuple would be equivalent in my context.

CodePudding user response：

Use itertools function chain and classmethod alternative constructor from_iterable:

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

Or with operator.iconcat and functools.reduce:

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

CodePudding user response：

You can try this:

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)

Output:

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

Check Runtime with dictionary that size is 50_000_000: (on 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()

Output:

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

CodePudding user response：

You can use a list comprehension over the items of the dict:

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

This outputs:

[1, 2, 3, 4]

CodePudding user response：

Appending and extending a list is quite efficient in python:

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

Therefore, the above apparently naive function beats the very compact and somehow also elegant expression list(sum(d.items(), ())) in terms of performance.