Remove elements from a big dict, in place

user_1422096 0
Viewed 57

I have a dict that has millions of elements, and can use hundreds of megabytes of memory.
I want to remove certain elements, based on a condition on the key:

d = {k: k for k in range(10_000_000)}        # simplified example

def mycondition(x):             
    return x % 10 != 0                       # simplified

  • This will work, but it will do a new copy of the dict, so I'd like to avoid it:

    d = {k: v for k, v in d.items() if mycondition(k)}

    because it would use the double of the RAM than needed compared to an "in place" solution

  • This fails:

    for k, v in d.items():
    if not mycondition(k):
        del d[k]

    because

    RuntimeError: dictionary changed size during iteration

How to solve this problem "in place", i.e. without using twice the size of d in RAM?

in-place dictionary python
3 Answers

I may have a simple solution - not a in place solution but it does not take double of the space.

d = {k: k for k in range(200)}

# List that stores the keys that should be removed
ids_to_remove = []

def mycondition(x):
    return x % 10 != 0

for k in d:
    if not mycondition(k):
        ids_to_remove.append(k)

for key in ids_to_remove:
    d.pop(key)
user_110058120

Dicts are iterable and iterables can be run through a filter to create another iterable. Since these are just pulling from the same source and iterating over them with next you shouldn't introduce any extra overhead when you finally use the iterable. Rather than modifying the dictionary in place, you can instead change the iterable and only evaluate it at the last possible moment when you absolutely have to. The best way to save on memory is if you can convert the generation of the dictionary itself into an iterable so it isn't even stored in memory before the filters. There is the OO way of making iterators but here is an more basic example:

d = map(lambda x: (x, x), range(10_000_000))
i = filter(lambda t: t[1] % 10 != 0, d)
i_2 = filter(lambda t: t[1] % 15 != 0, i)
# ... as many modifications as I want
output = json.dumps(dict(i_n))

Until we reach the output step, our iterators take up comparatively no space compared to having it all in memory. If you are loading this from a file, a similar approach could be used to iterate over each line.

user_48488010

Try this:

for k in list(d.keys()):
    if not mycondition(k):
        d.pop(k)
user_145119900
Related