Intersection of 2 lists which contain non-hashables
<p>What is the most efficient way to find the intersection of 2 lists when both lists contain non-hashables?</p>

<p>Basically, let's say I have the following lists (which I completely made up):</p>

<pre><code>A = [&lt;foo.bar object at 0x7f267c664080&gt;, &lt;foo.bar object at 0x7f267c664099&gt;]
B = [&lt;foo.bar object at 0x7f267c664080&gt;, &lt;foo.bar object at 0x123456789101&gt;]
</code></pre>

<p>We can see that the first element of <code>A</code> is the same as the first element of <code>B</code>. </p>

<p>I can do the simple thing by creating a for loop:</p>

<pre><code>intersection = []

for obj_a in A:
    for obj_b in B:
        if ( (obj_a == obj_b) and (obj_a not in intersection) ):
            intersection.extend(obj_a)
</code></pre>

<p>but I'm just wondering if there is a more efficient, cooler, or simpler way. For example, there is:</p>

<pre><code>C = [1, 2, 3]
D = [3, 4, 5]
set(C).intersection(set(D))
</code></pre>

<p>...but obviously I can't use <code>set</code> or <code>frozenset</code> for non-hashables because I get</p>

<pre><code>TypeError: unhashable type: foo.bar
</code></pre>

<p>Is there anything like this for non-hashables?</p>

<p>Hashing is what makes the <code>set</code> efficient. If you can't hash, then you can't take advantage of that efficiency - you have to compare every object with every other object and you get an O(nÂ²) algorithm instead of an amortized O(n) one.</p>

<p>However, if you care only about object <em>identity</em> and not equality, then you can make dicts mapping the object ids to the objects, and take the intersection of the ids:</p>

<pre><code>&gt;&gt;&gt; class foo(object): pass
...
&gt;&gt;&gt; f = foo()
&gt;&gt;&gt; A = [foo(), foo(), f]
&gt;&gt;&gt; B = [foo(), f, foo(), foo()]
&gt;&gt;&gt; [a for a in A if id(a) in (set(map(id, A)) &amp; set(map(id, B))]
[&lt;__main__.foo object at 0x100a7e9d0&gt;]
</code></pre>

<p>If you want a more code-efficient solution or you do care about object equality, then <a href="http://stackoverflow.com/a/39186008/15055">@Neil's answer</a> should suffice.</p>

python