Infinite Loop and Program Freezing in Python

Question

I've come across an interesting scenario while working on a Python program that involves generating unique options for a game. In my implementation, I initially used a set to store the options and encountered an issue where the program would freeze, leading to an infinite loop. However, after making a slight modification by switching to a list, the freezing problem disappeared.

I'm curious to understand the underlying reasons behind this behavior and why the second implementation caused the program to freeze. I have my own thoughts on the matter, but I want to gather insights from you all to gain a deeper understanding.

Prerequisite code

MAX = 20
MIN = 1

ans = random.randint(MIN, MAX)
y = random.randint(MIN, ans)
x = ans - y

Here are the two implementations:

Implementation 1 (No freezing issue):

opts = [x]
while len(opts) < 4:

    opt = random.randint(MIN, MAX)

    if opt not in opts:
        opts.append(opt)

Implementation 2 (Caused program freezing):

opts = {x}
while len(opts) < 4:
    opts.add(random.randint(MIN, MAX))

Edit

Here is the full contents of the function (with implementation 1)

def question_generator():

MAX = 20
MIN = 1

ans = random.randint(MIN, MAX)
y = random.randint(MIN, ans)
x = ans - y

# Generate options list
opts = [x]
while len(opts) < 4:
    opt = random.randint(MIN, MAX)
    if opt not in opts:
        opts.append(opt)

random.shuffle(opts)

return (x, y, ans, opts)

Questions I have about this:

1. What exactly causes the freezing issue in the second implementation?

2. Why does the first implementation resolve the freezing problem?

3. Are there any underlying differences between sets and lists that contribute to this behavior?

I really can't seem to understand why there is such a drastic difference, thanks for any insight you may have.

Answer 1

In Python, when comparing the two data structures, “set” and “list”, one will immediately see significant differences and the best use cases for each.

Honestly looking at your use of both, I don’t think the program should freeze. But nevertheless, I’ll list some of the most common use cases so that you may profile your program and find the real problem.

1. Lists are indexed while sets aren’t so sets do not support indexing or slicing operations.
2. Although lists and sets are mutable, while elements of a lists are mutable, elements of sets are immutable. So an attempt to mutate an element of a set will not work.

Overall the add method of a set is efficient. And set is far faster, in general when testing for membership. In a list, this is O(n), linear in the size of the list. Adding to a set is O(1), independent of the number of the items in the set. stackoverflow answer

So the best way to tackle this would be profiling your program first to know if that is where the actual problem lies.