Why use a set for list comparisons?
python
Solution
Just from an algorithmic perspective, it takes `O(n)` to construct the set and `O(n)` to do the list comprehension (since testing if an element is contained in a set is `O(1)`). However in the second example, it would take `O(n^2)` to loop through both lists. So regardless of the programming language, the first approach is superior.
Also, list comprehensions in python are inherently faster than a for loop. This reduces the constant factor even more (and significantly so too). The reason why can be summarized in this post which I quote here:
The fact that list comprehensions can only be comprised of expressions, not statements, is a considerable factor, as much less work is required behind the scenes for each iteration. Another factor is that the underlying iteration mechanism for list comprehensions is much closer to a C loop than execution of a for loop.
Problem
I just read another users question while looking for a way to compute the differences in two lists. Python, compute list difference My question is why would I do ``` def diff(a,b): b = set(b) return [aa for aa in a if aa not in b] ``` rather than doing ``` def diff(a,b): tmp = [] for i in a: if(i not in b): tmp.append(i) return tmp ``` edit: just noticed the second diff function actually returned the similarities. It should be correct now.