6

Say that I have a list of strings and a set of the same strings:

l = [str1, str2, str3, str4, ...]
s = set([str1, str2, st3, str4, ...])

I need to run a string comparison with a phrase that I have: comparephrase

I need to iterate over all the elements in the list or the set and generate a ratio between the comparephrase and the compared string. I know that set() is faster when we are doing a membership test. However, I am not doing a membership test but comparing the phrase that I have and the strings in the list/set. Does set() still offer a faster speed? If so, why? It seems to me that this set is actually a set with a list inside. Wouldn't that take the long time since we're iterating over the list within the set?

qiaop
  • 129
  • 3
  • 7
  • 2
    It's orthogonal to your performance question, but: "It seems to me that this set is actually a set with a list inside." -- no, that's just how it displays. In Python 3, you see `{1, 2, 3}` instead of `set([1, 2, 3])`, but they're still the same objects underneath. – DSM Aug 12 '14 at 19:23
  • 4
    Why not `timeit`? I'd expect little difference, though. – jonrsharpe Aug 12 '14 at 19:24
  • 1
    sets are much more expensive to create and a little more expensive to iterate. The only advantage would be if there are a lot of duplicates in the list that would be removed in the set. – tdelaney Aug 12 '14 at 19:32

4 Answers4

10

Iterating over a List is much much faster than iterating over a set.

The currently accepted answer is using a very small set and list and hence, the difference is negligible there.

The following code explains it:

>>> import timeit
>>> l = [ x*x for x in range(1, 400)] 
>>> s = set(l)
>>> timeit.timeit("for i in s: pass", "from __main__ import s")
12.152284085999781
>>> timeit.timeit("for i in l: pass", "from __main__ import l")
5.460189446001095
>>> timeit.timeit("if 567 in l: pass", "from __main__ import l")
6.0497558240003855
>>> timeit.timeit("if 567 in s: pass", "from __main__ import s")
0.04609546199935721

I do not know what makes set iteration slow, but the fact is evident from the output above.

Aditya Shaw
  • 323
  • 4
  • 11
  • 1
    [Python sets use hashtables internally](https://stackoverflow.com/questions/3949310/how-is-set-implemented), which introduces plenty of overhead – adrian Nov 05 '21 at 18:39
4

A Python set is optimized for equality tests and duplicate removal, and thus implements a hash table underneath. I believe this would make it very slightly slower than a list, if you have to compare every element to comparephrase; lists are very good for iterating over every element one after the other. The difference is probably going to be negligible in almost any case, though.

TheSoundDefense
  • 6,753
  • 1
  • 30
  • 42
  • 1
    +1 for drawing attention to the different purposes of the different structures. Given that you could only iterate over a random subset of elements (including the subset 'all') of a set it would appear (though I hate to offer a hostage to fortune) that sets and iteration are not great bedfellows... – mike rodent Dec 29 '15 at 18:32
3

The test in the accepted answer is not really representative as Aditya Shaw stated.

Let me explain the technical differences between iterating lists and sets roughly in an easy way.

Iterating lists
Lists have their elements organized by an order and an index "by design", which can be iterated easily. Access by an index is fast because it bases on few cheap memory read operations.

Iterating sets
Sets iterate slower because their element access is done by hashes.
Imagine a big tree with many branches and each leaf is an element. A hash is being translated into "directions" to traverse all branches until reaching the leaf.
Finding a leaf or element is still fast but slower compared to a simple index access of a list.
Sets have no linked items so an iteration cannot jump to the "next" item easily like a list. It has to start from the root of the tree on each iteration.

Sets (and dicts) are contrary to lists.
Each kind has a primary use case. Lists and sets swap their advantages on finding elements directly.

Does a list contain an element?
The list has to iterate over all its elements until it finds a match. That depends heavily on the list size. If the element is near the beginning, it gets found quite fast even on large lists. If an element is not in the list or near the end, the list gets iterated completely or until a match near the end.

Does a set contain an element?
It just has to traverse let's say 5 branches to look if there's a leaf. Even on large sets, the number of branches to traverse is relative low.

Why not make and use a universal collection type?
If a set had an internal list index, the set's operations would be slower because the list had to be updated and/or checked.

If a list had an internal set to find items faster, list operations would be slower because the hashes had to be updated and/or checked.

Data found behind the hash and behind the index also may be inconsistent because of duplicate management. And that also increases memory usage at all.

sausix
  • 251
  • 2
  • 6
1

I've run some tests with timeit, and (while list performs slightly faster) there is no significant difference:

>>> import timeit
>>> # For the set
>>> timeit.timeit("for i in s: pass", "s = set([1,4,7,10,13])")
0.20565616500061878
>>> # For the list
>>> timeit.timeit("for i in l: pass", "l = [1,4,7,10,13]")
0.19532391999928223

These values stay very much the same (0.20 vs. 0.19) even when trying multiple times.

However, the overhead of creating the sets can be significant.

Community
  • 1
  • 1
hlt
  • 6,219
  • 3
  • 23
  • 43
  • Seems like you should `pass` in the for loop to remove the call to factorial from the timing ... – mgilson Aug 12 '14 at 19:31