[Tutor] lazily decorated sort

Chris Smith smichr at gmail.com
Tue Sep 11 13:44:04 CEST 2012

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
  while time()-t<1:
  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)
        d = defaultdict(list)
        f = keys.pop(0)
        for a in seq:
        seq = []
        for k in sorted(d.keys()):
          if len(d[k]) > 1 and keys:
              seq.extend(lazyDSU(d[k], keys=keys[1:]))
    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.


More information about the Tutor mailing list