Finding unique maximum values in a list using python

Question

Hi

I have a list of points as shown below

points=[ [x0,y0,v0],  [x1,y1,v1],  [x2,y2,v2].......... [xn,yn,vn]]

Some of the points have duplicate x,y values. What I want to do is to extract the unique maximum value x,y points

For example, if I have points [1,2,5] [1,1,3] [1,2,7] [1,7,3]

I would like to obtain the list [1,1,3] [1,2,7] [1,7,3]

How can I do this in python?

Thanks

Answer 1

For example:

import itertools

def getxy(point): return point[:2]

sortedpoints = sorted(points, key=getxy)

results = []

for xy, g in itertools.groupby(sortedpoints, key=getxy):
  results.append(max(g, key=operator.itemgetter(2)))

that is: sort and group the points by xy, for every group with fixed xy pick the point with the maximum z. Seems straightforward if you're comfortable with itertools (ahd you should be, it's really a very powerful and useful module!).

Alternatively you could build a dict with (x,y) tuples as keys and lists of z as values and do one last pass on that one to pick the max z for each (x, y), but I think the sort-and-group approach is preferable (unless you have many millions of points so that the big-O performance of sorting worries you for scalability purposes, I guess).

Answer 2

You can use dict achieve this, using the property that "If a given key is seen more than once, the last value associated with it is retained in the new dictionary." This code sorts the points to make sure that the highest values come later, creates a dictionary whose keys are a tuple of the first two values and whose value is the third coordinate, then translates that back into a list

points = [[1,2,5], [1,1,3], [1,2,7], [1,7,3]]
sp = sorted(points)
d = dict( ( (a,b), c) for (a,b,c) in sp)
results = [list(k) + [v] for (k,v) in d.iteritems()]

There may be a way to further improve that, but it satisfies all your requirements.

Answer 3

If I understand your question .. maybe use a dictionary to map (x,y) to the max z

something like this (not tested)

dict = {}
for x,y,z in list
    if dict.has_key((x,y)):
        dict[(x,y)] = max(dict[(x,y)], z)
    else:
        dict[(x,y)] = z

Though the ordering will be lost