efficient algorithm for list edits

Question

I have a 3D-point cloud, saved in two lists. Example with 5 points (x,y,z): (3,3,3), (1,1,1), (4,4,4), (2,2,2), (5,5,5) -> My lists looks like this:

z = [3, 1, 4, 2, 5] # the z values
pts = [(3,3), (1,1), (4,4), (2,2), (5,5)] # the x and y values

Now I want to eliminate all values where the z-value is higher than 3:

# what I want to receive:
z = [3, 1, 2]
pts = [(3,3), (1,1), (2,2)]

My algorithm is here:

k = -1
for i in range(len(z)):
    k += 1
    if z[k] > h:
        z.pop(k)
        pts.pop(k)
        k -= 1

This returns me exactly what I want - but it's very slow (for >100,000 values). I thought about first sorting my list via z.sort() and then do z = z[:index] - but when I do this for my z-list then my pts-list is still unsorted. And even if I could get both lists sorted, doesn't I also have to go through a long loop to find the index where my condition is true? Does anyone knows a more efficient solution?

thefourtheye · Accepted Answer · 2013-11-22 13:26:24Z

4

z, pts = zip(*[(z, pt) for z, pt in zip(z, pts) if z <= 3])
print z, pts

Output

(3, 1, 2) ((3, 3), (1, 1), (2, 2))

answered Nov 22, 2013 at 13:26

thefourtheye

241k53 gold badges466 silver badges505 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Munchkin Over a year ago

thank you, I tested all 3 answers and this one is the fastest (but only a little bit faster)

alko · Accepted Answer · 2013-11-22 13:28:01Z

4

With itertools:

from itertools import izip, ifilter

zip together

zipped_coords = izip(z, pts)

filter (in post you mention higher, but expeted results are in fact lower, choosed first one)

filtered_coords = ifilter(lambda x: x[0]>=3, zipped_coords )

unzip

znew, ptsnew = map(list, izip(*filtered_coords))

or all-in-one oneliner

>>> znew, ptsnew = map(list, izip(*ifilter(lambda x: x[0]>=3, izip(z, pts))))
>>> print znew, ptsnew
[3, 4, 5] [(3, 3), (4, 4), (5, 5)]

edited Nov 22, 2013 at 13:28

answered Nov 22, 2013 at 13:25

alko

48.7k12 gold badges99 silver badges105 bronze badges

2 Comments

José Tomás Tocino Over a year ago

Actually the filtering should be x[0]<=3 according to his expected output. Also you shouldn't need the last map, this works znew, ptsnew = izip(*ifilter(lambda x: x[0]>=3, izip(z, pts)))

alko Over a year ago

@JoséTomásTocino see comment in my code, OP's text contradicts with expected outout. as about map, he stated that he needs lists of coordinates, not tuples.

Tim · Accepted Answer · 2013-11-22 13:26:37Z

2

Because you are removing elements from the list as you iterate it is a O(N^2) algorithm. You can use a simple list comprehension along with zip to do this in linear time.

z = [3, 1, 4, 2, 5] # the z values
pts = [(3,3), (1,1), (4,4), (2,2), (5,5)] # the x and y values

merged = zip(z, pts)    
filtered = [x for x in merged if x[0] <= 3]
z, pts = zip(*filtered)

answered Nov 22, 2013 at 13:26

Tim

12.2k4 gold badges45 silver badges43 bronze badges

Collectives™ on Stack Overflow

efficient algorithm for list edits

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related