13

I am working in Python (2.7.9) and am trying to filter a list of tuples by a list of elements of those tuples. In particular, my objects have the following form:

tuples = [('a', ['a1', 'a2']), ('b',['b1', 'b2']), ('c',['c1', 'c2'])]
filter = ['a', 'c']

I am new to Python and the easiest way to filter the tuples that I could discover was with the following list comprehension:

tuples_filtered = [(x,y) for (x,y) in tuples if x in filter]

The resulting filtered list looks like:

tuples_filtered = [('a', ['a1', 'a2']), ('c',['c1', 'c2'])]

Unfortunately, this list comprehension seems to be very inefficient. I suspect this is because my list of tuples is much larger than my filter, the list of strings. In particular, the filter list contains 30,000 words and the list of tuples contains about 134,000 2-tuples.

The first elements of the 2-tuples are largely distinct, but there are a few instances of duplicate first elements (not sure how many, actually, but by comparison to the cardinality of the list it's not many).

My question: Is there a more efficient way to filter a list of tuples by a list of elements of those tuples?

(Apologies if this is off-topic or a dupe.)

Related question (which does not mention efficiency):

Filter a list of lists of tuples

8
  • 1
    So how large is your real filter list? Why do you feel this is inefficient, do you have profiling information for your real situation?
    – Martijn Pieters
    Nov 16, 2016 at 18:50
  • The filter list contains 30,000 words and the list of tuples contains about 134,000 2-tuples.
    – DyingIsFun
    Nov 16, 2016 at 18:52
  • If list comprehension doesn't work for you, you should think of a module like numpy which has been implemented in C. But note that in that case you should have a large list, otherwise the cost of converting your python list to a numpy array would be more than the performance you gain from numpy.
    – Mazdak
    Nov 16, 2016 at 18:52
  • @Silenus: there's your problem then, the filter list.
    – Martijn Pieters
    Nov 16, 2016 at 18:52
  • 1
    Try turning your list of tuples into a dict and iterating over your filter getting the (key, values) pairs. I won't post this as an answer since I can't test its efficiency now but it may be worth a try. Nov 16, 2016 at 18:56

1 Answer 1

14

In a comment you write:

The filter list contains 30,000 words and the list of tuples contains about 134,000 2-tuples.

in containment tests against a list takes O(N) linear time, which is slow when you do this 134k times. Each time you have to iterate over all those elements to find a match. Given that you are filtering, not all those first elements are going to be present in the 30k list, so you are executing up to 30k * 134k == 4 billion comparisons.

Use a set instead:

filter_set = set(filter)

Set containment tests are O(1) constant time; now you reduced your problem to 134k tests.

A much smaller component of time you can avoid spending is the tuple assignment; use indexing to extract just the one element you are testing with:

tuples_filtered = [tup for tup in tuples if tup[0] in filter_set]
10
  • As the size of the filter list is much less than the size of the 2-tuples list, how about converting the 2-tuples list into a dictionary (using zip perhaps) and iterating over the filter list instead. I am not sure if this would be efficient. Will the list in the value field of the dictionary be a copy or a reference? If it is will be a reference, then this approach should be more efficient. Nov 16, 2016 at 18:57
  • 1
    Reduces the O(n*m) of OPs answer to O(n) Nov 16, 2016 at 18:58
  • @agamagarwal No need for zip to turn it into a dict, doing mydict = dict(tuples) is enough. Nov 16, 2016 at 18:59
  • @agamagarwal: that would require those first elements to be unique.
    – Martijn Pieters
    Nov 16, 2016 at 19:04
  • @lucasnadalutti Oh yeah! Thanks. Anyway, I just checked. When converting the tuples list into a dictionary, the list (['a1', 'a2']) is assigned to the value as a reference. So the iterating over the filter list instead of the tuples should be faster than this answer's approach. Nov 16, 2016 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.