[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: random predicate function
From: |
Pascal J. Bourguignon |
Subject: |
Re: random predicate function |
Date: |
Mon, 13 Dec 2010 19:38:19 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) |
Tyler Smith <tyler.smith@eku.edu> writes:
> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>
>>
>> You shoud not use sort to randomize, because it's suboptimal
>> [ O(n*log(n)) at best instead of O(n) ].
>>
>> And foremost, you should not use a predicate that is not a total order
>> because this usually gives invalid results.
>
> I don't know what a 'total order' means. Is the result of the predicate
> invalid or the actual sorting?
http://en.wikipedia.org/wiki/Total_order
Actually, it should even be a strict total order, that is, it must be a <
operator, not a <= operator.
If you have cycles such as: a < b < a
then some sort algorithms may not terminate.
When sorting lists, some algorithms could truncate the result.
--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
- Re: random predicate function, Pascal J. Bourguignon, 2010/12/13
- Re: random predicate function, Ted Zlatanov, 2010/12/13
- Re: random predicate function, Pascal J. Bourguignon, 2010/12/13
- Re: random predicate function, Ted Zlatanov, 2010/12/15
- Re: random predicate function, Pascal J. Bourguignon, 2010/12/15
- Re: random predicate function, Ted Zlatanov, 2010/12/15
- Re: random predicate function, Pascal J. Bourguignon, 2010/12/15
- Re: random predicate function, Ted Zlatanov, 2010/12/15
- RE: random predicate function, Drew Adams, 2010/12/15