how to intersect a list and set in python and preserve the order of the list?

Question

How can I intersect a list and a set to preserve the order of the list? Simple example:

k=[1,2,3,4]
d={3,2}
d.intersection(k)
[2,3]#this is the ideal result

edit: speed is the most important factor here

Are the elements of `k` unique? – donkopotamus Nov 29 '16 at 22:16 — donkopotamus, Nov 29 '16 at 22:16
no, but they are in ascending order. – mikeLundquist Nov 29 '16 at 22:19 — mikeLundquist, Nov 29 '16 at 22:19

score 7 · Accepted Answer · edited May 23 '17 at 12:09

You'll have to use a list comprehension, which lets you keep the order by filtering:

[i for i in k if i in d]

Demo:

>>> k = [1, 2, 3, 4]
>>> d = {2, 3}
>>> [i for i in k if i in d]
[2, 3]

For Python 3, this is the fastest option available; you could use list(filter(d.__contains__, l)) but this is slower on this trivially small example:

>>> from timeit import timeit
>>> def listcomp(k, d):
...     return [i for i in k if i in d]
...
>>> def filtered(k, d):
...     return list(filter(d.__contains__, k))
...
>>> timeit('listcomp(k, d)', 'from __main__ import listcomp, k, d')
0.49590064199946937
>>> timeit('filtered(k, d)', 'from __main__ import filtered, k, d')
0.6533352420010488

and timings worsen when the data sets grow in size:

>>> import random
>>> k = sorted([random.randrange(1000) for _ in range(1000)])
>>> d = {random.randrange(1000) for _ in range(100)}
>>> timeit('listcomp(k, d)', 'from __main__ import listcomp, k, d', number=10000)
0.30027976899873465
>>> timeit('filtered(k, d)', 'from __main__ import filtered, k, d', number=10000)
0.4524774450001132

In Python 2, filter() is the faster option, given large enough inputs:

>>> from timeit import timeit
>>> import random
>>> def listcomp(k, d):
...     return [i for i in k if i in d]
...
>>> def filtered(k, d):
...     return filter(d.__contains__, k)
...
>>> k = [1, 2, 3, 4]
>>> d = {2, 3}
>>> timeit('listcomp(k, d)', 'from __main__ import listcomp, k, d')
0.4015800952911377
>>> timeit('filtered(k, d)', 'from __main__ import filtered, k, d')
0.4407978057861328
>>> k = sorted([random.randrange(1000) for _ in range(1000)])
>>> d = {random.randrange(1000) for _ in range(100)}
>>> timeit('listcomp(k, d)', 'from __main__ import listcomp, k, d', number=10000)
0.4594550132751465
>>> timeit('filtered(k, d)', 'from __main__ import filtered, k, d', number=10000)
0.28088998794555664

I'm not aware of any faster options; the available ordered set implementations are all Pure-python solutions, and slower still.

@user4757074: it would have been helpful if you mentioned this in your question. — Martijn Pieters, Nov 29 '16 at 22:12
@user4757074: there are no other standard-library options that I know of. There are ordered-set implementations on PyPI but these are pure-Python implementations and likely slower still. — Martijn Pieters, Nov 29 '16 at 22:12
I don't think you can do better than one 'in' comparison for each item in the list- — Paul Becotte, Nov 29 '16 at 22:17
i don’t think the ascending order of the list is very helpful here in terms of performance — taylor swift, Nov 29 '16 at 22:31
@taylorswift: the order doesn't make any difference; I only added the `sorted()` call to match the OP data set. — Martijn Pieters, Nov 29 '16 at 22:36
i was speaking to the OP when he/she says that this answer is too slow. I don’t think you can get much better than this in pure python — taylor swift, Nov 29 '16 at 22:37

how to intersect a list and set in python and preserve the order of the list?

1 Answers1