Efficient Rank Ordering of Nested Lists

[Neil Cerutti]

On 2007-08-03, pablo.mitchell at gmail.com <pablo.mitchell 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