[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: avoid narrow-to-region (was: Re: replace-regexp)
From: |
Yuri Khan |
Subject: |
Re: avoid narrow-to-region (was: Re: replace-regexp) |
Date: |
Sun, 9 May 2021 12:48:29 +0700 |
On Sun, 9 May 2021 at 06:00, Emanuel Berg via Users list for the GNU
Emacs text editor <help-gnu-emacs@gnu.org> wrote:
> (sort-subr nil
> #'forward-line
> #'end-of-line
> nil nil
> (lambda (_ __) (zerop (random 2)) )))))
Note that this is not a suitable sorting predicate. It violates all
axioms of a strict weak ordering:
* Consistency: If (f a b) returns t once, it must return t when called
again with the same arguments.
* Irreflexivity: (f a a) must return nil. Your predicate returns nil
or t randomly.
* Antisymmetry: of (f a b) and (f b a), no more than one may return t.
In your case, both can return t.
* Transitivity: If (f a b) and (f b c) both return t, (f a c) must
also return t.
* Transitivity of equivalence: if (f a b), (f b a), (f b c), (f c b)
all return nil, then (f a c) and (f c a) must also return nil.
Generic sorting algorithms typically require the predicate to conform
to all of the above; otherwise, they may signal an error or enter an
endless loop.
I have not analyzed whether ‘sort-subr’ has any issues with
inconsistent orderings, and its docstring does not mention these
requirements, but it would be a good idea to avoid that anyway.
Also, using a sorting algorithm to randomize an ordered sequence is a
bit of an overkill. Sorting has an asymptotic complexity of O(n log
n), but the Fisher–Yates–Durstenfeld shuffle algorithm is O(n).
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- Re: replace-regexp, (continued)
- Re: replace-regexp, Emanuel Berg, 2021/05/08
- Re: replace-regexp, Emanuel Berg, 2021/05/08
- Re: replace-regexp, Stefan Monnier, 2021/05/08
- Re: replace-regexp, Emanuel Berg, 2021/05/08
- Re: replace-regexp, Stefan Monnier, 2021/05/08
- Re: replace-regexp, Emanuel Berg, 2021/05/08
- Re: replace-regexp, Stefan Monnier, 2021/05/08
- Re: replace-regexp, Emanuel Berg, 2021/05/08
- Re: replace-regexp, Emanuel Berg, 2021/05/09
- avoid narrow-to-region (was: Re: replace-regexp), Emanuel Berg, 2021/05/08
- Re: avoid narrow-to-region (was: Re: replace-regexp),
Yuri Khan <=
- Re: avoid narrow-to-region (was: Re: replace-regexp), Emanuel Berg, 2021/05/09
- Re: avoid narrow-to-region (was: Re: replace-regexp), Yuri Khan, 2021/05/09
- Re: avoid narrow-to-region (was: Re: replace-regexp), Emanuel Berg, 2021/05/09
- Re: avoid narrow-to-region (was: Re: replace-regexp), Jean Louis, 2021/05/09
- Re: avoid narrow-to-region (was: Re: replace-regexp), Emanuel Berg, 2021/05/09
- Re: avoid narrow-to-region (was: Re: replace-regexp), Yuri Khan, 2021/05/09
- Re: avoid narrow-to-region (was: Re: replace-regexp), Emanuel Berg, 2021/05/09
- Re: avoid narrow-to-region (was: Re: replace-regexp), Yuri Khan, 2021/05/09
- Re: avoid narrow-to-region (was: Re: replace-regexp), Emanuel Berg, 2021/05/09
- Re: avoid narrow-to-region (was: Re: replace-regexp), Emanuel Berg, 2021/05/09