Intersecting lists in python won't work

Question

I've been having trouble in performing an algorythm to intersect two lists in my code. I took this discussion (link below) as a reference and nothing seems to be working the way i expected. Find intersection of two lists?

I have this json file and am writing a code which will allow to perform search on its thousands items according to different (and simultaneous) criteria. At some point of the code, a list that contains all items of the json file that have already been found (according to the first criteria) must be intersected to the list generated from a second search (so that the resulting list will contain the items that satisfy BOTH criteria)

I used different algorythms to perform the intersection.

def intersect(a, b):
    for k in a:
        print "for k in a"
        if k not in b:
            print "if k not b"
            a.remove(k)
    return a

a = intersect(a, b)

i also tried both that are mentioned in the link above, not to mention others i made.

The result is that i don't get the intersected list as a result. sometimes it doesn't intersect at all, sometimes i don't know what goes wrong. With the algorythm above, the remove() function simply didn't remove anything.

I wonder if there's a problem with modifying a list that you're in the middle of iterating. — Mark Ransom, Jan 28 '16 at 17:28
Even if this worked, the performance is O(n\*\*2). It can be done in O(n). — Tom Karzes, Jan 28 '16 at 17:38
Is it possible to use `set` instead? Then, you could use the built-in intersection method. — Jared Goguen, Jan 28 '16 at 17:55

Alex Alifimoff · Accepted Answer · 2016-01-28T17:57:21.357

3

What about

def intersect(a, b): return [x for x in a if x in b]

if a and b are both lists, this should work fine.

As Tom rightly points out in the comments, this is a slow algorithm.

def intersect(a, b):
    sb = set(b)
    return [x for x in a if x in sb]

should be faster.

If you're interested in a rough comparison of these two algorithms, check out this blog post

edited Jan 28 '16 at 17:57

answered Jan 28 '16 at 17:28

Alex Alifimoff

1,850
2
17
34

2

This is an O(n\*\*2) algorithm, only suited to small lists. If the lists are large, it would make much more sense to create a set for `b` and then use set membership instead of list membership. That would reduce the runtime to O(n). – Tom Karzes Jan 28 '16 at 17:36
2

Your second solution will change the order of the list. A better way would be as @TomKarzes suggests and only turn `b` into a set, leave `a` as a list and use the list comprehension as you did in the first answer. – Mark Ransom Jan 28 '16 at 17:51

Intersecting lists in python won't work

1 Answers1