5
\$\begingroup\$

I have list of tuples like so:

lst = [(106, 210, 108, 134, 134),
       (106, 210, 108, 134, 210),
       (106, 210, 108, 168, 268),
       (106, 210, 108, 168, 671),
       ...]

I need to only keep the tuples that contain:

keep = (106, 210, 108, 168)

Which I am currently doing using this statement:

kept = [item for item in lst if set(keep) < set(item)]

This works but it is too slow for me since the actual list I am working with contains 2.6 million items. It takes about 1.5 seconds now. Is there a good way to significantly speed this up?

\$\endgroup\$
  • 2
    \$\begingroup\$ Why are you using set() ? You can remove it :). It has a complexity of O(len(item)) and doing that check 2.6 million times...well, it counts a bit I suppose \$\endgroup\$ – Grajdeanu Alex. Apr 29 '17 at 12:32
  • 1
    \$\begingroup\$ @MrGrj because keep is not always sorted. (106, 210, 168, 108)<(106, 210, 108, 168, 671) returns False. \$\endgroup\$ – user1286695 Apr 29 '17 at 12:46
  • 2
    \$\begingroup\$ Your code is not complete and possible to run, aka stub implementation. And you state that it returns False as if that is not the supposed action, indicating that your code doesn't work \$\endgroup\$ – holroy Apr 29 '17 at 12:49
  • 2
    \$\begingroup\$ ( 210, 106, 168, 108)<(106, 210, 108, 168, 671) returns False, but set(( 210, 106, 168, 108)) < set((106, 210, 108, 168, 671)) returns True, which is my desired result. Is my approach for this wrong? The items in lst and keep are not always neatly sorted, which is why I use set \$\endgroup\$ – user1286695 Apr 29 '17 at 12:53
  • 2
    \$\begingroup\$ @holroy: taking the example data sets (without the ellipses) should result in a full program. As for being broken, that was the suggested alternative that's broken, not the OP. \$\endgroup\$ – zondo Apr 29 '17 at 13:36
8
\$\begingroup\$

Your code as it stand is on the border of being off-topic as it is a stub, however since the following actually works and seems to do the job, I'm going to answer it:

lst = [(106, 210, 108, 134, 134),
       (106, 210, 108, 134, 210),
       (106, 210, 108, 168, 268),
       (106, 210, 108, 168, 671)]

keep = (106, 210, 108, 168)

kept = [item for item in lst if set(keep) < set(item)]
print kept

Firstly some comments on the code:

  • Please provide a fully working example – In general, if there in the question is not a fully working example code, it'll be shut down immediately. Please provide something like the above code segment.
  • Name and comment – Providing good names and comment to illustrate what the code does is vital. Using anonymous name like lst, item, and no comments, makes the code a lot harder to read.
  • Do you keep lst in memory? – In the text you state that lst has over 2.6 million entries, do you keep all of this in memory? That could possibly effect your running times severly depending on your hardware resources. You might want to look into some algorithm leaving it in file or in a database, or whatever suits your needs.

Alternate solution

You're asking for a faster solution, so let us analyze what is happening in your code currently:

  • You loop through the entire in-memory lst once, and create a new set for each item
  • This set(item) is then compared to repeatedly created set(keep) (could be optimised away by the compiler), to check which is lesser
  • If lesser, the list comprehension keeps the item

The operations in here is \$O(N)\$ where N is the number in the list, and that you can't beat. The cost for each element is the creation of one or two sets, and the comparison of those sets, which is dependent on the size of the sets \$O(M)\$. In general since the \$N << M\$, the loop over the elements should be prominent.

This means, without changing the data structures there is not a whole lot to be gained, as you do need to loop through all elements, and you need to verify membership agains the keep list. If any optimization is to be performed it needs to address the actual comparison somehow.

Another view on your solution is the readability of your code, and how to understand what is happening. The list comprehension is understandable, but the set comparison is not obvious to me, at least, and I would have liked a comment. Or a rewrite, so let us attempt an rewrite for readability and see how it performs. This rewrite is using a Python specific concept to avoid a flag variable:

keepers = []
for candidate in lst:
  for keeper in keep:
    if not keeper in candidate:
      break

  else:
    keepers.append(candidate)

This code expands the list comprehension into the double for loop which is hidden in the list comprehension. The inner for loop breaks up the keep list into each element, and tests for memberships. The criteria for the candidate to be kept is that all elements should be members, so if any member is not present, we break out and start checking the next candidate.

The trick to this solution is that if the inner for loop doesn't complete naturally (aka no breaks), the else part is not executed. Try the following and play with it, to understand this mechanism:

for i in range(5):
  if i == 3:
    break
else:
  print "This didn't end naturally"           # Not executed

for i in range(5):
  if i == 7:
    break
else:
  print "The loop finished without breaking"  # Executes

Whilst I was writing this answer, the answer with using the all concept came in, so I included that in some basic timeit tests to check for running times, and the result surprised me a little:

Original method: 2.62324810028
Using all():     3.84744811058
Double for loop: 1.84868502617

This was tested using the original lst duplicated a few times to get a slightly larger set, but it does show that using the double for loop like I did, is currently the faster solution, and it runs at about 33% faster than the original code, and the solution using all() is actually quite a bit slower.

\$\endgroup\$
3
\$\begingroup\$

One thing I notice is that you convert keep to a set once for each item in lst. If you just define it as a set in the first place, that should save on computation time. If you can, it would also be better if the items in lst were sets.

As chatton says, you would be better off using all():

kept = [item for item in lst if all(k in item for k in keep)]

all() is short-circuiting, which means it stops evaluating as soon as it knows the answer. You may be interested in How do Python's any and all functions work?

\$\endgroup\$

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.