Dictionary infinite loop is exiting unexpectedly

Question

I was experimenting with various ways of creating an infinite loop in Python (other than the usual while True), and came up with this idea:

x = {0: None}

for i in x:
    del x[i]
    x[i+1] = None  # Value doesn't matter, so I set it to None
    print(i)

On paper, I traced out the way this would infinitely loop:

1. I loop through the key's value in the dictionary
2. I delete that entry.
3. The current counter position in the loop + 1 will be the new key with value None which updates the dictionary.
4. I output the current counter.

This, in my head, should output the natural numbers in a sort of infinite loop fashion:

0
1
2
3
4
5
.
.
.

I thought this idea was clever, however when I run it on Python 3.6, it outputs:

0
1
2
3
4

Yes, it somehow stopped after 5 iterations. Clearly, there is no base condition or sentinel value in the code block of the loop, so why is Python only running this code 5 times?

Answer 1

There is no guarantee that you will iterate over all your dict entries if you mutate it in your loop. From the docs:

Iterating views while adding or deleting entries in the dictionary may raise a RuntimeError or fail to iterate over all entries.

You could create an "enumerated" infinite loop similar to your initial attempt using itertools.count(). For example:

from itertools import count

for i in count():
    print(i)
    # don't run this without some mechanism to break the loop, i.e.
    # if i == 10:
    #     break

# OUTPUT
# 0
# 1
# 2
# ...and so on

Answer 2

In this case, like @benvc wrote, this is not guaranteed to work. But in case you wonder why does it work in C-Python:

The C-Python implementation destroys the dict object after some inserts and copies it to a new space in memory. It does not care about deletions. So when this happens, the loop notices it and breaking with an exception.

Check out this link if you want to read more about this, and many other interesting python internals here.

https://github.com/satwikkansal/wtfpython#-modifying-a-dictionary-while-iterating-over-it

Answer 3

I just tested your code in python2 and python3

python3 output
0,1,2,3,4
python2
0,1,2,3,4,5,6,7

One thing comes to mind that could be going on. Either there is only a certain amount of memory being allocated in your dictionary when you create the first key value and when you delete the key value we do not allocate any memory or deallocate the memory you are just removing the value. Once all the allocated memory is used it exits. Because if you run without that del you will get this error

RuntimeError: dictionary changed size during iteration

So python creates enough memory for that key value and a few more and once it is used up theres no more memory allocated for your dictionary.

Answer 4

As many pointed out, modifying a datastructure during iteration with a for loop is not a good idea. The while loop though does allow that as it re-evaluates its loop condition at each iteration (I'm impressed nobody suggested that as alternative yet). One just has to find the right loop condition. Your script would have to become:

x = {0: None}
while x:
    i, _ = x.popitem()
    print(i)
    # to avoid infinite loop while testing
    # if i == 10:
    #     break
    x[i+1] = None

In Python, a dictionary is falsy when it is empty (see docs), so the loop will only stop if at the beginning of an iteration x is empty. Since the dictionary only has one key-value pair, popitem() should be enough to get that pair and remove it from the dictionary. As the next integer is added right after the dictionary is emptied, the loop condition will never be false when evaluated thereby resulting in an infinite loop.