Remove items from two lists if they meet a criteria

Question

I have two lists in python, they contain points, and I want to remove from BOTH lists any permutation that exists in both lists.

I tried writing the followiing code that fails:

  for indexA, pointA in enumerate(listA):
    for indexB, pointB in enumerate(listB):
       if isPermutation(listA[indexA],listB[indexB]):
            del listA[indexA]
            del listB[indexB]

This of course would not work because the del command creates a new list and the for loop will loose the reference to both lists (not to mention it takes O(n) to remove from a list in python). There are various ways to do this when you have one list which are mentioned here. But they don't seem to be helpful when working with two lists with the dependency above.

Could anyone supply code/a way to do this?
I care about speed. Note: Building the list using .append() is really slow due to the fact its amortized.

Do you need the keep the order? If you don't, you should use sets instead of lists, compute the intersection and subtract from both. — Pedro Werneck, Jul 28 '13 at 21:38
I don't mind changing the current order, but I need the final order preserved. That is, you can sort it, but you must keep it sorted in the same way. — GuySoft, Jul 28 '13 at 21:56
Can you just avoid this problem completely by *not* inserting items into listA if they are already in listB (and delete from listB at the same time), and vice-versa? And if you actually need to maintain a list of duplicate items then have a 3rd list (ListAB) containing each item that would otherwise be in *both* listA and listB. — jarmod, Jul 28 '13 at 22:39
@jarmod No I can't. I am not the one inserting them. They are actually parsed from a different part of the program. I will note they are parsed FAST. Really fast, I am not sure how to be honest. [Its part of the blender source code](https://svn.blender.org/svnroot/bf-extensions/trunk/py/scripts/addons/io_mesh_stl/stl_utils.py), so its not magic. — GuySoft, Jul 28 '13 at 23:10

score 1 · Accepted Answer · answered Jul 28 '13 at 20:51

1

I would suggest first to create another list containing the elements to be deleted from the initial lists, say listC and then use list comprehension to modify both listA and listB. For instance, after having obtained listC:

listA = [a for a in listA if a not in listC]
listB = [a for a in listB if a not in listC]

answered Jul 28 '13 at 20:51

papafe

2,959
4
41
72

Is there a way to do this without using `.append()`? – GuySoft Jul 28 '13 at 22:05
@GuySoft, to which `.append()` are you referring to? – papafe Jul 28 '13 at 22:11
in order to create the list containing the elements to be deleted from both listA and listB you need to build the list somehow. [Here is my current code](http://pastebin.com/6tGrJSuj). . It works, but would prefer to make it faster by dropping the `.append()` on lines 13 and 14: – GuySoft Jul 28 '13 at 22:17
@GuySoft, I see. If you prefer, you could use list comprehension to create those list too. For instance, using the same code you used in the question, you could do something like `removeA = [a for a in listA for b in listB if isPermutation(a,b)]` – papafe Jul 28 '13 at 22:27
Thanks! Will try that and update, running out of input files to test it. – GuySoft Jul 28 '13 at 23:11
@GuySoft. You can speed up the process if your initial lists do not contain duplicate elements. In this case you can create the final list as following: `listA = [a for a in listA for b in listB if not isPermutation(a,b)]`. In this case you will have duplicate elements, but you can delete the duplicates transforming the list in a set (and then transforming to a list again if you really need lists): `listA = set(listA)` – papafe Jul 29 '13 at 07:52

freeforall tousez · Answer 2 · 2013-07-29T00:32:21.510

0

instead of doing it the way markusian say, you could make new listA and listB directly instead of making a listC to compare and there isn't really a need for enumerate is there?

removing the enumerate cause it isn't really needed cause it in a loop will speed it up a little.

listC = []
listD = []
for pointA in listA:
  for pointB in listB:
     if not isPermutation(pointA,pointB):
       listC.append(pointA)
       listD.append(pointB)
     else:
       # fix B to look like A in new listA (listC) and listB (listD)
       listC.append(pointB)
       listD.append(pointB)

then if you want, you could just replace the old list with the new

listA = listC
listB = listD

edit1: if you really must avoid append, you could do it this way, although, it slower on small list, not so sure about big list:

listC = []
listD = []
for pointA in listA:
  for pointB in listB:
     if not isPermutation(pointA,pointB):
       # a += b is like a = a + b
       listC += [pointA]
       listD += [pointB]
     else:
       # fix B to look like A in new listA (listC) and listB (listD)
       listC += [pointB]
       listD += [pointB]

edited Jul 29 '13 at 00:32

answered Jul 28 '13 at 22:14

freeforall tousez

836
10
26

I am trying to avoid `.append` because use its [amortized](http://wiki.python.org/moin/TimeComplexity). – GuySoft Jul 28 '13 at 23:06
if you must avoid .append, you could turn the point into a list and join it together with the list, but it slower than .append... – freeforall tousez Jul 29 '13 at 00:29
No point of using something slower. The point is finding something that is faster. I thought that was obvious :-/ – GuySoft Jul 29 '13 at 07:58
I am trying to avoid .append because use its amortized. – GuySoft 10 hours ago, so i give you something other than append lol – freeforall tousez Jul 29 '13 at 09:06

Remove items from two lists if they meet a criteria

2 Answers2