title: Why is converting a list to a set faster than using just list to compute a list difference?
body: <p>Say, I wish to compute the difference of two lists <code>C = A - B</code>:</p>
  
  <pre><code>A = [1,2,3,4,5,6,7,8,9] 
  B = [1,3,5,8,9]
  C = [2,4,6,7]          #Result
  </code></pre>
  
  <p><code>A</code> and <code>B</code> are both sorted with unique integers <em>(not sure if there is a way to tell Python about this property of the list)</em>. I need to preserve the order of the elements. AFAIK there are two possible ways of doing it</p>
  
  <p><strong>Method 1</strong>: <em>Convert B into a set and use list comprehension to generate C:</em></p>
  
  <pre><code>s = set(B)
  C = [x for x in A if x not in s]
  </code></pre>
  
  <p><strong>Method 2</strong>: <em>Directly use list comprehension:</em></p>
  
  <pre><code>C = [x for x in A if x not in B]
  </code></pre>
  
  <p>Why is <code>#1</code> more efficient than <code>#2</code>? Isn't there an overhead to convert to a set? What am I missing here?</p>
  
  <p>Some performance benchmarks are given in <a href="https://stackoverflow.com/a/3462202/609074">this answer.</a></p>
  
  <p><strong>UPDATE:</strong> I'm aware that a set's average <code>O(1)</code> lookup time beats that of a list's <code>O(n)</code> but if the original list <code>A</code> contains about a million or so integers, wouldn't the set creation actually take longer?</p>