[Tutor] lazily decorated sort

[Chris Smith]

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