[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: comic-book-insult

From: Yuri Khan
Subject: Re: comic-book-insult
Date: Mon, 9 Sep 2019 12:09:08 +0700

On Mon, 9 Sep 2019 at 02:05, Emanuel Berg via Users list for the GNU
Emacs text editor <> wrote:

>         (rand-chars (sort chars (lambda (_ __) (zerop (random 2)))))

If you were to pull off this kind of thing in C or C++, that would be
classified as undefined behavior and possibly cause demons to fly out
your nose. The comparison predicate used in sorting algorithms must be
a strict weak ordering, i.e.:

* irreflexive — (not (p x x)) for each x;
* antisymmetric — if (p x y), then (not (p y x));
* transitive — if (p x y) and (p y z), then (p x z);
* the equivalence induced by it must also be transitive — if (not (or
(p x y) (p y x))) and (not (or (p y z) (p z y))), then (not (or (p x
z) (p z x))).

A predicate that returns a random boolean on each invocation will
easily violate any or all of the above.

The canonical lazy coder way to random-shuffle a collection is to
first associate a random value with each element, then sort by that:

 (seq-map #'car
          (seq-sort-by #'cdr #'<
                       (seq-map (lambda (x) (cons x (random)))
                                (string-to-vector "@#$%&")))))

(This whole sorting approach is criticized because it is O(n log n) in
the number of elements while there exist random shuffle algorithms
that are linear, i.e. O(n). See [1].)


reply via email to

[Prev in Thread] Current Thread [Next in Thread]