Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > sort array, apply rearrangement to second

Reply
Thread Tools

sort array, apply rearrangement to second

 
 
Victor Eijkhout
Guest
Posts: n/a
 
      03-30-2010
I have two arrays, made with numpy. The first one has values that I want
to use as sorting keys; the second one needs to be sorted by those keys.
Obviously I could turn them into a dictionary of pairs and sort by the
first member, but I think that's not very efficient, at least in space,
and this needs to be done as efficiently as possible.

I could use a hand.

Victor.
--
Victor Eijkhout -- eijkhout at tacc utexas edu
 
Reply With Quote
 
 
 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      03-30-2010
* Victor Eijkhout:
> I have two arrays, made with numpy. The first one has values that I want
> to use as sorting keys; the second one needs to be sorted by those keys.
> Obviously I could turn them into a dictionary of pairs and sort by the
> first member, but I think that's not very efficient, at least in space,
> and this needs to be done as efficiently as possible.
>
> I could use a hand.


Just do the pairing, but in a 'list', not a dictionary (a dictionary is
unordered and can't be sorted). You need to keep track of which keys belong to
which values anyway. And anything in Python is a reference: you're not copying
the data by creating the pairs. That is, the space overhead is proportional to
the number of items but is independent of the data size of each item.


Cheers & hth.,

- Alf
 
Reply With Quote
 
 
 
 
Steve Holden
Guest
Posts: n/a
 
      03-30-2010
Victor Eijkhout wrote:
> I have two arrays, made with numpy. The first one has values that I want
> to use as sorting keys; the second one needs to be sorted by those keys.
> Obviously I could turn them into a dictionary of pairs and sort by the
> first member, but I think that's not very efficient, at least in space,
> and this needs to be done as efficiently as possible.
>
> I could use a hand.
>

Well, my first approach would be to do it as inefficiently as I can ( or
at least no more efficiently than I can with a simple-minded approach)
and then take it from there.

If I believe this is not a premature optimization (a question about
which I am currently skeptical) I'd suggest conversion to a list of
pairs rather than a dict.

Can you use zip() on numpy arrays? That would be the easiest way to
create the list of pairs.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
See PyCon Talks from Atlanta 2010 http://pycon.blip.tv/
Holden Web LLC http://www.holdenweb.com/
UPCOMING EVENTS: http://holdenweb.eventbrite.com/

 
Reply With Quote
 
MRAB
Guest
Posts: n/a
 
      03-31-2010
Victor Eijkhout wrote:
> I have two arrays, made with numpy. The first one has values that I want
> to use as sorting keys; the second one needs to be sorted by those keys.
> Obviously I could turn them into a dictionary of pairs and sort by the
> first member, but I think that's not very efficient, at least in space,
> and this needs to be done as efficiently as possible.
>
> I could use a hand.
>

You could sort a list of the indices, using the first array to provide
the keys.
 
Reply With Quote
 
Robert Kern
Guest
Posts: n/a
 
      03-31-2010
On 2010-03-30 18:25 , Victor Eijkhout wrote:
> I have two arrays, made with numpy. The first one has values that I want
> to use as sorting keys; the second one needs to be sorted by those keys.
> Obviously I could turn them into a dictionary of pairs and sort by the
> first member, but I think that's not very efficient, at least in space,
> and this needs to be done as efficiently as possible.


second[first.argsort()]

Ask numpy questions on the numpy mailing list.

http://www.scipy.org/Mailing_Lists

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

 
Reply With Quote
 
Victor Eijkhout
Guest
Posts: n/a
 
      03-31-2010
Robert Kern <(E-Mail Removed)> wrote:

> second[first.argsort()]


Really cool. Thanks.

> Ask numpy questions on the numpy mailing list.


I will. I thought that this question would have an answer in a generic
python idiom.

Victor.
--
Victor Eijkhout -- eijkhout at tacc utexas edu
 
Reply With Quote
 
Robert Kern
Guest
Posts: n/a
 
      03-31-2010
On 2010-03-31 13:58 PM, Victor Eijkhout wrote:
> Robert Kern<(E-Mail Removed)> wrote:
>
>> second[first.argsort()]

>
> Really cool. Thanks.
>
>> Ask numpy questions on the numpy mailing list.

>
> I will. I thought that this question would have an answer in a generic
> python idiom.


When dealing with numpy arrays, the generic Python idiom is often much slower.

--
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
that is made terrible by our own mad attempt to interpret it as though it had
an underlying truth."
-- Umberto Eco

 
Reply With Quote
 
Steve Holden
Guest
Posts: n/a
 
      03-31-2010
Victor Eijkhout wrote:
> Robert Kern <(E-Mail Removed)> wrote:
>
>> second[first.argsort()]

>
> Really cool. Thanks.
>
>> Ask numpy questions on the numpy mailing list.

>
> I will. I thought that this question would have an answer in a generic
> python idiom.
>
> Victor.


Not an unreasonable assumption, but it turns out that for most Python
users (estimate PFTA: 97%) numpy/scipt is esoteric knowledge.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
See PyCon Talks from Atlanta 2010 http://pycon.blip.tv/
Holden Web LLC http://www.holdenweb.com/
UPCOMING EVENTS: http://holdenweb.eventbrite.com/

 
Reply With Quote
 
Raymond Hettinger
Guest
Posts: n/a
 
      03-31-2010
On Mar 30, 4:25*pm, (E-Mail Removed) (Victor Eijkhout) wrote:
> I have two arrays, made with numpy. The first one has values that I want
> to use as sorting keys; the second one needs to be sorted by those keys.
> Obviously I could turn them into a dictionary *of pairs and sort by the
> first member, but I think that's not very efficient, at least in space,
> and this needs to be done as efficiently as possible.


Alf's recommendation is clean and correct. Just make a list of
tuples.

FWIW, here's a little hack that does the work for you:

>>> values = ['A', 'B', 'C', 'D', 'E']
>>> keys = [50, 20, 40, 10, 30]
>>> keyiter = iter(keys)
>>> sorted(values, key=lambda k: next(keyiter))

['D', 'B', 'E', 'C', 'A']


Raymond
 
Reply With Quote
 
Steve Howell
Guest
Posts: n/a
 
      04-01-2010
On Mar 31, 1:09*pm, Raymond Hettinger <(E-Mail Removed)> wrote:
> On Mar 30, 4:25*pm, (E-Mail Removed) (Victor Eijkhout) wrote:
>
> > I have two arrays, made with numpy. The first one has values that I want
> > to use as sorting keys; the second one needs to be sorted by those keys..
> > Obviously I could turn them into a dictionary *of pairs and sort by the
> > first member, but I think that's not very efficient, at least in space,
> > and this needs to be done as efficiently as possible.

>
> Alf's recommendation is clean and correct. *Just make a list of
> tuples.
>
> FWIW, here's a little hack that does the work for you:
>
> >>> values = ['A', 'B', 'C', 'D', 'E']
> >>> keys = [50, 20, 40, 10, 30]
> >>> keyiter = iter(keys)
> >>> sorted(values, key=lambda k: next(keyiter))

>
> ['D', 'B', 'E', 'C', 'A']
>


Another option:

[values[i] for i in sorted(range(len(keys)), key=lambda i: keys[i])]

Sort the indexes according to keys values, then use indexes to get the
values.

It might read more clearly when broken out into two lines:

>>> sorted_indexes = sorted(range(len(keys)), key = lambda i: keys[i])
>>> sorted_indexes

[3, 1, 4, 2, 0]
>>> [values[i] for i in sorted_indexes]

['D', 'B', 'E', 'C', 'A']

The advantage of Raymond's solution is that he only creates one new
Python list, whereas my solutions create an intermediate Python list
of integers. I don't think my solution really is that space-wasteful,
though, since by the time the second list gets created, any internal
intermediate lists from CPython's sorted() implementation will
probably have been cleaned up.



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
strip all but second second line from bottom and then strip that!!!! yelipolok Perl Misc 4 01-27-2010 08:14 AM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM
Can I get a second pair of eyes on this sort ... MW Perl Misc 14 08-29-2003 09:50 PM
Datalist selects Item after first click, but does apply the SelectedItemTemplate after the second click only Dirk Meusel ASP .Net 1 08-19-2003 09:56 AM
[XSLT] could not apply "apply-templates" Stefan Siegl XML 1 07-18-2003 09:43 AM



Advertisments