<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, Oct 27, 2013 at 12:28 PM, Freddie Witherden <span dir="ltr"><<a href="mailto:freddie@witherden.org" target="_blank">freddie@witherden.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi all,<br>
<br>
This is a question which has been bugging me for a while.  I have an (N,<br>
3) array where N ~ 16 of points.  These points are all unique and<br>
separated by a reasonable distance.<br>
<br>
I wish to sort these points into a canonical order in a fashion which is<br>
robust against small perturbations.  In other words changing any<br>
component of any of the points by an epsilon ~ 1e-12 should not affect<br>
the resulting sorted order.<br>
<br>
Considering a direct application of np.lexsort:<br>
<br>
  In [6]: my_array = np.array([[-0.5, 0, 2**0.5],<br>
                               [0.5, 0, 2**0.5 - 1e-15]])<br>
<br>
  In [7]: my_array[np.lexsort(my_array.T)]<br>
  Out[7]:  array([[ 0.5       ,  0.        ,  1.41421356],<br>
                  [-0.5       ,  0.        ,  1.41421356]])<br>
<br>
however, if the small 1e-15 perturbation is removed the order changes to<br>
the 'natural' ordering.  Hence, np.lexsort is out.<br>
<br>
Rounding the array before sorting is not suitable either; just because<br>
(a - b) < epsilon does not mean that np.around(a, decimals=x) ==<br>
np.around(b, decimals=b).<br>
<br>
I am therefore looking for an efficient (= within a factor of 10 of<br>
np.lexsort) solution to the problem.  I've looked at writing my own<br>
comparison function cmp(x, y) which looks at the next dimension if<br>
abs(x[i] - y[i]) < epsilon however using this with sorted is thousands<br>
of times slower.  Given that I have well over 100,000 of these arrays<br>
this is nuisance.<br>
<br>
My other idea is to therefore find a means of quickly replacing all<br>
numbers within 10*epsilon of a given number in an array with that<br>
number.  This should permit the application of np.lexsort in order to<br>
obtain the desired ordering (which is what I'm interesting in).<br>
However, I am yet to figure out how to do this efficiently.<br>
<br>
Before I throw in the towel and drop down to C are there any other neat<br>
tricks I am missing?<br>
<br></blockquote><div><br></div><div>Sort them as strings? <br><br>In [17]: a = np.random.random((5,3))<br><br>In [18]: a<br>Out[18]: <br>array([[ 0.64734085,  0.71582772,  0.82743219],<br>       [ 0.92769057,  0.46880266,  0.73836167],<br>
       [ 0.11904745,  0.56834934,  0.16144849],<br>       [ 0.59186013,  0.90698496,  0.56950572],<br>       [ 0.7317681 ,  0.93495724,  0.19217244]])<br><br>In [19]: a.view('S24').sort(0)<br><br>In [20]: a<br>Out[20]: <br>
array([[ 0.7317681 ,  0.93495724,  0.19217244],<br>       [ 0.64734085,  0.71582772,  0.82743219],<br>       [ 0.59186013,  0.90698496,  0.56950572],<br>       [ 0.92769057,  0.46880266,  0.73836167],<br>       [ 0.11904745,  0.56834934,  0.16144849]])<br>
<br></div><div>Chuck<br></div></div></div></div>