[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: random predicate function
From: |
Tyler Smith |
Subject: |
Re: random predicate function |
Date: |
Mon, 13 Dec 2010 14:05:06 -0500 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) |
"Pascal J. Bourguignon" <pjb@informatimago.com> writes:
> 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.
Ah, thanks. Makes perfect sense now that I think about it.
Tyler
- 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