# Filtering a list of tuples

I have a list of tuples which may vary in size quite significantly. Typical number of tuples in the list would be somewhere around 100.000. I am trying to perform a down-selection on these tuples to end up with a more workable amount of them.

Each tuple contains (among other insignificant for this example data) an integer and 3 floats. These are of interest to me (shown bold below, positions 0, 2, 3, 4).

Example:

(100213, 'foo',-23.412, -277.11, 12.567, 12.24, 23.25, 150.14, 'bar', 'foobar')

And the criterion to implement is the following in pseudocode:

Assume tuples i and j:

if i[2] < j[2] and i[3] < j[3] and abs(i[4]) > abs(j[2]) then j leaves the list.

I wrote a couple algorithms for the task, timed them and improved them and finally I arrived here:

def clean3(lst):
lst = sorted(lst, key=lambda x: abs(x[4]), reverse=True)  # the abs comparison is taken care off.
remove = set()  # for quicker membership checks
for i, forces_i in enumerate(lst[:-1]):
if forces_i not in remove:  # the current entry might have already been removed
for forces_j in lst[i+1:]:  # forward check only - progressive gains
if forces_j not in remove: # the current entry might have already been removed
if all(forces_i[x] < forces_j[x] for x in range(2, 4)):  # check with all now possible
return list(set(lst) - remove)


To my eyes, this looks as streamlined as it could be, but:

1. Can it be further improved, and if yes, how?
2. Would an entirely different approach be better here?
• Could you give us some more background information about where these tuples come from and what they represent? It's a bit unusual to work with tuples of unknown size. Commented Dec 9, 2016 at 17:36
• the size of the tuples is known, their number is unkown (the size of the hosting list). The are simulation results originally stored in an sqlite database and feched with queries specifically for the task of filtering. I couldnt find a way to do this kind of filtering in the database directly
– Ma0
Commented Dec 9, 2016 at 17:40
• I'm certain that you would be better off devising an SQL query to do the job, and that solving this problem in Python is an XY problem. Commented Dec 9, 2016 at 17:42
• I tried but from what i understood, such a comparative filter cannot be written in SQL. There is the option of an external C# file implementing the fucntion that can be called by the query but....
– Ma0
Commented Dec 9, 2016 at 17:44
• Your description says you need to compare i[2] < j[2] and i[3] < j[3], but your code does all(forces_i[x] < forces_j[x] for x in range(2)). Please ensure that your question is consistent. Commented Dec 9, 2016 at 18:29

The pattern for i in range(n): for j in range(i+1, n): ... is better handled using itertools.combinations:

from itertools import combinations

def clean3(lst):
lst = sorted(lst, key=lambda x: abs(x[4]), reverse=True) # the abs comparison is taken care off.
remove = set() # for quicker membership checks
for forces_i, forces_j in combinations(lst, 2):
if forces_j not in remove: # the current entry might have already been removed
if all(forces_i[x] < forces_j[x] for x in range(2, 4)):

I also removed the test for forces_i in removed since I feel you could have cases where it would fail to remove some forces_j. But if I'm wrong it's very easy to put back on the same line than the test for forces_j.
• Thanks a lot for the feedback. The combinations usage is a nice addition. Regarding the forces_i in removed and unless i am missing something, if force_i would remove force_j but is already removed by let's say force_k then force_k also removes force_j, so..
• The problem with combinations though is that i cannot break the loop and go to the next forces_i if forces_i in remove`. I would still have to traverse the list in vain.