Efficient Rank Ordering of Nested Lists

[pablo.mitchell at gmail.com]

On Aug 3, 5:53 am, Neil Cerutti <horp... at yahoo.com> wrote:
> On 2007-08-03, pablo.mitch... at gmail.com <pablo.mitch... at gmail.com> wrote:
>
>
>
> > A naive approach to rank ordering (handling ties as well) of nested
> > lists may be accomplished via:
>
> >    def rankLists(nestedList):
> >       def rankList(singleList):
> >           sortedList = list(singleList)
> >           sortedList.sort()
> >           return map(sortedList.index, singleList)
> >       return map(rankList, nestedList)
>
> >    >>> unranked = [ [ 1, 2, 3, 4, 5 ], [ 3, 1, 5, 2, 4 ], [ -1.1, 2.2,
> > 0, -1.1, 13 ] ]
> >    >>> print rankLists(unranked)
>
> >    [[0, 1, 2, 3, 4], [2, 0, 4, 1, 3], [0, 3, 2, 0, 4]]
>
> > This works nicely when the dimensions of the nested list are
> > small. It is slow when they are big.  Can someone suggest a
> > clever way to speed it up?
>
> Use binary search instead of linear.
>
>  import bisect
>  import functools
>
>  def rankLists(nestedList):
>    def rankList(singleList):
>      sortedList = list(sorted(singleList))
>      return map(functools.partial(bisect.bisect_left, sortedList), singleList)
>    return map(rankList, nestedList)
>
> --
> Neil Cerutti
> Facts are stupid things. --Ronald Reagan

Very clean and precisely what I was looking for.  Thanks for expanding
my knowledge of the language.