Algorithmic complexity to convert a set to a list in python

user_1252386 0
Viewed 1142

In python, when I convert my set to a list, what is the algorithmic complexity of such a task? Is it merely type-casting the collection, or does it need to copy items into a different data structure? What's happening?

I'd love to learn that the complexity was constant, like so many things in Python.

python-collections time-complexity python-3.x python
3 Answers

You can easily see this with a simple benchmark:

import matplotlib.pyplot as plt


x = list(range(10, 20000, 20))
y = []
for n in x:
    s = set(range(n))
    res = %timeit -r2 -n2 -q -o list(s)
    y.append(res.best)


plt.plot(x, y)

plot

Which clearly shows a linear relationship -- modulo some noise.

(EDITED as the first version was benchmarking something different).

user_52183540

The time complexity in most cases will be O(n) where n is the size of the set, because:

  • The set is implemented as a hashtable whose underlying array size is bounded by a fixed multiple of the set's size. Iterating over the set is done by iterating over the underlying array, so it takes O(n) time.
  • Appending an item to a list takes O(1) amortized time, even if the list's underlying array is not originally allocated to be large enough for the whole set; so appending n items to an empty list takes O(n) time.

However, there is a caveat to this, which is that Python's sets have underlying array sizes based on the largest size the set object has had, not necessarily based on its current size; this is because the underlying array is not re-allocated to a smaller size when elements are removed from the set. If a set is small but used to be much larger, then iterating over it can be slower than O(n).

user_122990000

The complexity is linear because all references are copied to the new container. But only references and are and not objects - it can matter for big objects.

user_35452730
Related