[Tutor] lazily decorated sort

[Mark Lawrence]

On 11/09/2012 12:44, Chris Smith wrote:
> Hi all,
>
> I'm wondering if anyone has seen or knows of a good way to do a lazily
> decorated sort. I was reading about how good the DSU (decorate, sort,
> undecorate) approach is but the problem that we are running into in
> SymPy is that we want to get by with a fast hash sort if possible, and
> only decorate to break ties *if necessary*. It's a pity to decorate
> with an expensive function if you don't need it but I don't know how
> to only decorate when there are ties. Do you have any ideas how to do
> the following better:
>
>
> def f():
>    """delay for 2 seconds"""
>    from time import time
>    from random import random
>    t=time()
>    while time()-t<1:
>      pass
>    return random
>
> class foo(object):
>    """an object that calls the delay function when comparing"""
>    def __eq__(self, other):
>      return f() == f()
>    def __lt__(self, other):
>      return f() < f()
>
> def lazyDSU(seq, keys=[]):
>      """Return sorted seq, breaking ties by lazily applying keys successively
>      as needed from the list of provided keys."""
>      if not keys:
>          seq = sorted(seq)
>      else:
>          d = defaultdict(list)
>          f = keys.pop(0)
>          for a in seq:
>              d[f(a)].append(a)
>          seq = []
>          for k in sorted(d.keys()):
>            if len(d[k]) > 1 and keys:
>                seq.extend(lazyDSU(d[k], keys=keys[1:]))
>            else:
>                seq.extend(d[k])
>      return tuple(seq)
>
>>>> lazyDSU(range(5)) # fast
> (0, 1, 2, 3, 4)
>>>> [i[0] for i in lazyDSU(zip(range(5), [foo()]*5))] # fast, no ties
> [0, 1, 2, 3, 4]
>>>> [i[0] for i in lazyDSU([(0, foo())] + list(zip(range(5), [foo()]*5)))] # slower
> [0, 0, 1, 2, 3, 4]
>
> The last run takes 4 seconds (but not 12 seconds) because only two had
> to have ties broken.
>
> In the examples, no keys were passed but the discretionary decoration
> was demonstrated.
>
> /Chris
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
>

It's my understanding that DSU is unneccessary in modern versions of 
Python so I suggest you read  http://docs.python.org/howto/sorting.html 
http://wiki.python.org/moin/PythonSpeed/PerformanceTips#Sorting these 
before you go any further, if you haven't already done so already that is.

-- 
Cheers.

Mark Lawrence.