2
\$\begingroup\$

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
                        remove.add(forces_j)
    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?
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – 200_success Dec 9 '16 at 17:36
  • \$\begingroup\$ 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 \$\endgroup\$ – Ev. Kounis Dec 9 '16 at 17:40
  • \$\begingroup\$ 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. \$\endgroup\$ – 200_success Dec 9 '16 at 17:42
  • \$\begingroup\$ 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.... \$\endgroup\$ – Ev. Kounis Dec 9 '16 at 17:44
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – 200_success Dec 9 '16 at 18:29
2
\$\begingroup\$

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)):
                remove.add(forces_j)
    return list(set(lst) - remove)

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.

\$\endgroup\$
  • \$\begingroup\$ 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.. \$\endgroup\$ – Ev. Kounis Dec 13 '16 at 9:25
  • \$\begingroup\$ 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. \$\endgroup\$ – Ev. Kounis Dec 13 '16 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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