Prev: Tkinter library reference
Next: Help with Regexp, \b
From: Bryan on 29 May 2010 10:43
Mark Dickinson wrote:
> N.B.  I don't claim any originality for the algorithm; only for the
> implementation: the algorithm is based on an algorithm attributed to
> Robert Floyd, and appearing in Jon Bentley's 'Programming Pearls' book

Actually it is the sequel, /More Programming Pearls/.

> (though that algorithm produces a set, so doesn't worry about the
> ordering of the sample).

Bentley presents a version of the Floyd algorithm that provides random
order, but it requires a set data type with some idea of order, as in
"insert j in s after t". As Mark Dickinson's version uses a normal
dict(), which Bentley had already introduced under the name "associate
array", I'd say Mark's version is an improvement.


--
--Bryan
From: Mark Dickinson on 29 May 2010 13:06
On May 29, 3:43 pm, Bryan <bryanjugglercryptograp...(a)yahoo.com> wrote:
> Mark Dickinson wrote:
> > N.B.  I don't claim any originality for the algorithm; only for the
> > implementation: the algorithm is based on an algorithm attributed to
> > Robert Floyd, and appearing in Jon Bentley's 'Programming Pearls' book
>
> Actually it is the sequel, /More Programming Pearls/.

Thanks for the correction. I confess that I've yet to read either
book; I'll have to try to track them down.

> > (though that algorithm produces a set, so doesn't worry about the
> > ordering of the sample).
>
> Bentley presents a version of the Floyd algorithm that provides random
> order, but it requires a set data type with some idea of order, as in
> "insert j in s after t".

Ah, nice. The dict values, of course, exactly provide the necessary
idea of order, so I guess this amounts to pretty much the same thing.

--
Mark
 | 
Pages: 1
Prev: Tkinter library reference
Next: Help with Regexp, \b