hen Bloch
> Sent: 13 September 2010 21:44
> To: users@racket-lang.org
> Subject: Re: [racket] Looking for feedback on code style
>
>
> On Sep 13, 2010, at 3:07 PM, David Van Horn wrote:
>
> >> In fact, ANY method to do this (even with a vector) takes
> Omega(n
> -Original Message-
> From: robby.find...@gmail.com
> [mailto:robby.find...@gmail.com] On Behalf Of Robby Findler
> Sent: 14 September 2010 17:16
> To: Stephen Bloch
> Cc: Jos Koot; users@racket-lang.org
> Subject: Re: [racket] Looking for feedback on code st
On Sep 14, 2010, at 10:37 AM, Jos Koot wrote:
> The following measurement shows O(n).
> But O(n) = O(C+n) where C may be a big number.
More relevantly, O(n) is hard to distinguish experimentally from O(n log n).
In particular, all the sizes you seem to tried are well within a machine word,
so
I think that racket guarantees that no vector has more elements than
the size of the largest fixnum (to support optimizations).
Also, Jos: you might want to use time-apply.
Robby
On Tue, Sep 14, 2010 at 9:56 AM, Stephen Bloch wrote:
>
> On Sep 14, 2010, at 10:37 AM, Jos Koot wrote:
>
>> The fol
))
(gc (begin (read) (read) (read
(values cpu (- cpu gc)
(timer 10 10 100 100)
> -Original Message-
> From: users-boun...@racket-lang.org
> [mailto:users-boun...@racket-lang.org] On Behalf Of Stephen Bloch
> Sent: 13 Sept
On Sep 13, 2010, at 3:07 PM, David Van Horn wrote:
>> In fact, ANY method to do this (even with a vector) takes Omega(n log n)
>> time. It needs to be able to produce any of n! different answers, so it
>> needs to make at least log(n!) decisions, which is Theta(n log n).
>> Otherwise there wouldn
On 9/13/10 1:34 PM, Phil Bewig wrote:
Fixed. See the comment at
http://programmingpraxis.com/2009/12/11/selection/.
Prabhakar: You are correct that shuffling once at the beginning is
sufficient. But I am interested in your critique of shuffling. Do you
know a better way to shuffle a list tha
s, one being empty, the
> other one containing all numbers left so far, resulting in an infinite
> loop.
> Jos
>
> > -Original Message-
> > From: Prabhakar Ragde [mailto:plra...@uwaterloo.ca]
> > Sent: 10 September 2010 23:38
> > To: Jos Koot
> > Su
containing all numbers left so far, resulting in an infinite loop.
Jos
> -Original Message-
> From: Prabhakar Ragde [mailto:plra...@uwaterloo.ca]
> Sent: 10 September 2010 23:38
> To: Jos Koot
> Subject: Re: [racket] Looking for feedback on code style
>
> On 9/10/10 5:
ing list of numbers for each next partition.
Jos
_
From: users-boun...@racket-lang.org [mailto:users-boun...@racket-lang.org]
On Behalf Of Phil Bewig
Sent: 09 September 2010 17:34
To: David Van Horn
Cc: users@racket-lang.org; Prabhakar Ragde
Subject: Re: [racket] Looking for feedback on code s
This format is a pretty good idea. I like how HTDP pushes it from the
beginning. But is something like this a good idea?
Welcome to DrRacket, version 5.0 [3m].
Language: racket; memory limit: 1024 MB.
> (require user/help)
> (help foo)
No help available.
> (help help)
help
(or (name -> void) (void
On Thu, Sep 9, 2010 at 5:03 PM, Prabhakar Ragde wrote:
> 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.
"What is the average a
On Sep 9, David Van Horn wrote:
> On 9/9/10 11:26 AM, Eli Barzilay wrote:
> > On Sep 9, David Van Horn wrote:
> >>
> >> [...] As for the structure of the code as given, I would use helper
> >> functions in place of the `let'. The resulting code will be easier
> >> to read and the helper function
[...] As for the structure of the code as given, I would use helper
functions in place of the `let'. The resulting code will be easier
to read and the helper functions can be tested independently, [...]
Sounds like an overkill in this case, and for most values of
"idiomatic" I'd say that
On 9/9/10 11:26 AM, Eli Barzilay wrote:
On Sep 9, David Van Horn wrote:
[...] As for the structure of the code as given, I would use helper
functions in place of the `let'. The resulting code will be easier
to read and the helper functions can be tested independently, making
it easier to main
On 9/9/10 1:27 PM, Will M. Farr wrote:
Nevertheless, it sure feels like it's O(N) (I've experimented quite a
bit with timing tests, and the simple argument about averages I gave
before "feels right").
Your intuition is correct; it's a bit tricky, but not too tricky, to
show that the algorithm
On Sep 9, 2010, at 11:37 AM, Prabhakar Ragde wrote:
> And then what? Are we justified in saying T(N) = T(3N/4) + O(N)? Really, we
> have T(N) = T(X) + O(N), where X is a random variable uniformly distributed
> over [0..N-1]. With a suitable induction hypothesis, we can dig ourselves out
> of th
On 9/9/10 12:09 PM, Phil Bewig wrote:
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.
I'm sorry, I shouldn't have said "
Will M. Farr wrote:
Looks like Phil beat me to it, but here's some code that finds the
n-th element of a list in O(N) time. The algorithm is similar to
quicksort, but you don't sort both the sub-lists: partition the list
into elements less than and greater or equal to a pivot. By counting
the
I should note that the code I posted also used randomness to select the pivot
element, so the statements below apply to it, too. It's on average O(N) (where
average can mean either "run many times on the same input" or "run on many
inputs of length N").
Will
On Sep 9, 2010, at 11:03 AM, Prabh
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 wrote:
> On 9/9/10 11:33
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 el
On 9/9/10 11:52 AM, Prabhakar Ragde wrote:
Selection can be done in O(n) time regardless of the value of k.
Ah, that's where I went wrong. I think I was confused by the Wikipedia
text on introselect, where k is a constant (unrelated the kth smallest
element).
The idea is to split the n el
On 9/9/10 11:26 AM, David Van Horn wrote:
The original post got me interested in median algorithms and I started
to read up on the selection problem. Wikipedia (I know, I know) says the
same thing as you: medians can be computed in O(n) time and points to
selection as the way to do it. But I don
David,
Looks like Phil beat me to it, but here's some code that finds the n-th element
of a list in O(N) time. The algorithm is similar to quicksort, but you don't
sort both the sub-lists: partition the list into elements less than and greater
or equal to a pivot. By counting the number of el
http://programmingpraxis.com/2009/12/11/selection/
On Thu, Sep 9, 2010 at 10:26 AM, David Van Horn wrote:
> On 9/9/10 10:04 AM, Prabhakar Ragde wrote:
>
>> I don't think vectors help very much in this case (median-finding). For
>> the given code, the O(n) access to the middle of the list is domin
On 9/9/10 10:04 AM, Prabhakar Ragde wrote:
I don't think vectors help very much in this case (median-finding). For
the given code, the O(n) access to the middle of the list is dominated
by the cost of the sorting, which is at least O(n log n) [*].
It is theoretically possible to compute the medi
On Sep 9, David Van Horn wrote:
>
> [...] As for the structure of the code as given, I would use helper
> functions in place of the `let'. The resulting code will be easier
> to read and the helper functions can be tested independently, making
> it easier to maintain and improve the likelihood t
On 9/9/10 9:24 AM, Noel Welsh wrote:
On Thu, Sep 9, 2010 at 1:09 PM, David Van Horn wrote:
What!?
What can I say -- I have low standards.
Without a purpose statement, contract, or examples, it's difficult to know
what this code is supposed to do, much less say if it is doing whatever it
is
Noel Welsh wrote:
I think this is great code -- very clear. For production use you have
the wrong data structure (Lists are O(n) random access and length; you
want O(1) vectors), but that doesn't matter for your use.
I don't think vectors help very much in this case (median-finding). For
the
On Thu, Sep 9, 2010 at 1:09 PM, David Van Horn wrote:
> What!?
What can I say -- I have low standards.
> Without a purpose statement, contract, or examples, it's difficult to know
> what this code is supposed to do, much less say if it is doing whatever it
> is supposed to do correctly.
'round
On 9/9/10 3:51 AM, Noel Welsh wrote:
On Thu, Sep 9, 2010 at 4:35 AM, Scott Hickey wrote:
I was helping my son with his math homework tonight, working with
medians and wrote the following below. As I was looking at it, I was
wondering:
...
I think this is great code -- very clear.
What!?
Wi
On Thu, Sep 9, 2010 at 4:35 AM, Scott Hickey wrote:
> I was helping my son with his math homework tonight, working with
> medians and wrote the following below. As I was looking at it, I was
> wondering:
...
I think this is great code -- very clear. For production use you have
the wrong data stru
BTW, for anyone new to this email list, the HtDP textbook, which will
indoctrinate you in the prevailing methodology and mindset, is available
for free at: http://htdp.org/
--
http://www.neilvandyke.org/
_
For list-related administrative tasks:
: Neil Van Dyke
Sender: users-boun...@racket-lang.org
Date: Thu, 09 Sep 2010 00:21:39
To: Scott Hickey
Cc:
Subject: Re: [racket] Looking for feedback on code style
Scott, your formatting of the code and naming of variables is perfectly
fine and idiomatic, but don't worry about that right no
Scott, your formatting of the code and naming of variables is perfectly
fine and idiomatic, but don't worry about that right now.
I recommend focusing on the things David mentions, and then on making
sure that your approach and code is correct.
Afterwards, people might also have comments on s
On 9/8/10 11:35 PM, Scott Hickey wrote:
I just like to see my coding style mature from
beginner to advanced beginner :)
Purpose statement? Contract? Examples?
David
_
For list-related administrative tasks:
http://lists.racket-lang.org/listinf
I was helping my son with his math homework tonight, working with
medians and wrote the following below. As I was looking at it, I was
wondering:
1) Is this an idiomatic use for let - is there too much code for
middle-position in the let?
2) Should 2 be on its own line at the end of my function re
38 matches
Mail list logo
