more useful options | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
The warm-up problem isn't so trivial. Two possible solutions are decribed in Cormen – Leiserson – Rivest – Stein: Introduction to Algorithms. One of these is randomized and runs in expected O(n) time. (Update: the other one runs in guaranteed O(n) time, as Perl Mouse has noted in his reply. I'm sorry this wasn't clear from my original post.) I've recently implemented this randomized algorithm for perl, although my implementation is not a very efficent one, as it would be possible to do all its operations in place (with only O(n) extra memory and more importantly less time). The rest of this post shows my implementation. Here's the code although it might not make much sense without context. The quantile function is passed a positive ordinal $r and a list of numbers @a. It returns the $r-th least number from the list if it would be sorted, with $r = 1 meaning to return the minimum of the list. If you want a median, pass $r = int((@a + 1)/2)
In reply to Re: Puzzle: The Ham Cheese Sandwich cut.
by ambrus
|
|