seemingly simple list indexing problem

[iu2]

On Jul 29, 2:26 am, John Krukoff <jkruk... at ltgc.com> wrote:
> On Mon, 2008-07-28 at 16:00 -0700, iu2 wrote:
> > On Jul 29, 12:10 am, John Krukoff <jkruk... at ltgc.com> wrote:
> > > On Mon, 2008-07-28 at 16:24 -0500, Ervan Ensis wrote:
> > > > My programming skills are pretty rusty and I'm just learning Python so
> > > > this problem is giving me trouble.
>
> > > > I have a list like [108, 58, 68].  I want to return the sorted indices
> > > > of these items in the same order as the original list.  So I should
> > > > return [2, 0, 1]
>
> > > > For a list that's already in order, I'll just return the indices, i.e.
> > > > [56, 66, 76] should return [0, 1, 2]
>
> > > > Any help would be appreciated.
>
> > > > --
> > > >http://mail.python.org/mailman/listinfo/python-list
>
> > > If your lists aren't so large that memory is an issue, this might be a
> > > good place for a variation of decorate, sort, undecorate.
>
> > > >>> listToSort = [ 108, 58, 68 ]
> > > >>> decorated = [ ( data, index ) for index, data in
>
> > > enumerate( listToSort ) ]>>> decorated
>
> > > [(108, 0), (58, 1), (68, 2)]>>> result = [ None, ] * len( listToSort )
> > > >>> for sortedIndex, ( ignoredValue, originalIndex ) in
>
> > > enumerate( sorted( decorated ) ):
> > > ...     result[ originalIndex ] = sortedIndex
> > > ...>>> result
>
> > > [2, 0, 1]
>
> > > --
> > > John Krukoff <jkruk... at ltgc.com>
> > > Land Title Guarantee Company
>
> > Inspired by your idea and the above one, here is another try:
>
> > >>> a0 = [108, 58, 68, 108, 58]
> > >>> a1 = [(x, y) for x, y in enumerate(a0)]
>
> You know this line is a no-op, right?
>
> > >>> a1
> > [(0, 108), (1, 58), (2, 68), (3, 108), (4, 58)]
> > >>> a2 = sorted(a1, lambda x, y: cmp(x[1], y[1]))
>
> If you're going to do the unpacking here for the sort, just use
> enumerate directly. Since this is a simple case, should use the key
> parameter instead of the cmp parameter for speed. Can also use the
> operator module to avoid a bit of lambda overhead:
>
> >>> import operator
> >>> a2 = sorted( enumerate( a0 ), key = operator.itemgetter( 1 ) )
> > >>> a2
> > [(1, 58), (4, 58), (2, 68), (0, 108), (3, 108)]
> > >>> a3 = [a2.index(x) for x in a1]
> > >>> a3
> > [3, 0, 2, 4, 1]
>
> > The idea is to make each item unique (by making it a tuple), and then
> > apply the naive solution.
>
> > --
> >http://mail.python.org/mailman/listinfo/python-list
>
> Using index is still kinda evil, due to the exponential time required
> since you're rescanning half the list (on average) to find each index
> value.
>
> --
> John Krukoff <jkruk... at ltgc.com>
> Land Title Guarantee Company- Hide quoted text -
>
> - Show quoted text -

Well, a dictionary can replace the index search

helper_dict = dict(zip(a2, xrange(len(a2))))
>>> helper_dict
{(1, 58): 0, (4, 58): 1, (3, 108): 4, (2, 68): 2, (0, 108): 3}

a3 = [helper_dict[x] for x in a1]
>>> a3
[3, 0, 2, 4, 1]

The performance now should be n*log(n)