[racket] Looking for feedback on code style

From: Phil Bewig (pbewig at gmail.com)
Date: Thu Sep 9 12:09:40 EDT 2010

I did treaps, too: http://programmingpraxis.com/2009/06/26/treaps/.  And I
use them all the time, including where most people probably use hash tables,
because so often you need the keys in order somewhere in your program.

On Thu, Sep 9, 2010 at 11:03 AM, Prabhakar Ragde <plragde at uwaterloo.ca>wrote:

> On 9/9/10 11:33 AM, Phil Bewig wrote:
>> http://programmingpraxis.com/2009/12/11/selection/
> This method takes O(n) time with high probability if the partitioning
> element is chosen deterministically and the data is randomly permuted (with
> all permutations equally likely) or if the partitioning element is chosen
> uniformly at random. Its deterministic worst-case cost is O(n^2). However,
> for a site called "Programming Praxis", it's definitely the right choice.
> Our attitude towards randomness in computer science is a bit strange. I'm
> convinced most of our students graduate thinking that Quicksort is an O(n
> log n) algorithm, but this is only true in a probabilistic model. On the
> other hand, the shortest, cleanest, and most elegant method I know of to
> balance binary search trees (which underlies non-hash efficient set and map
> implementations) uses randomness, but no one talks about it or knows it.
> --PR
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20100909/53b518e1/attachment.html>

Posted on the users mailing list.