This is a mostly boring rant against the Go language:
http://monoc.mo.funpic.de/go-rant/
Near the end it contains an interesting bit:
>Too, why this divide, again, with reference types and value types? Did they
>not learn from the problems this caused in Java? While Java slowly struggles
bearophile Wrote:
> This is a mostly boring rant against the Go language:
> http://monoc.mo.funpic.de/go-rant/
>
> Near the end it contains an interesting bit:
> >Too, why this divide, again, with reference types and value types? Did they
> >not learn from the prob
There are things that I read often around in blogs and papers (and sometimes
even in books), but sometimes I keep not understanding them.
Sean Kelly:
> If I had to guess I'd say that he's referring to that fact that value types
> in Java are second-class citizens. The standard containers can on
bearophile Wrote:
> Sean Kelly:
> > If I had to guess I'd say that he's referring to that fact that value types
> > in Java are second-class citizens. The standard containers can only hold
> > objects, so boxing is necessary,<
>
> Reading that page I have thought he wants all data to be manage
Mon, 14 Dec 2009 19:51:10 -0500, Sean Kelly wrote:
> bearophile Wrote:
>
>> This is a mostly boring rant against the Go language:
>> http://monoc.mo.funpic.de/go-rant/
>>
>> Near the end it contains an interesting bit:
>> >Too, why this divide, again, wi
retard wrote in
news:hg8ppr$107...@digitalmars.com:
> That's not the only problem in JVM. Languages are
> getting more and more functional these days and many enterprise Java
> projects use ad-hoc single method interfaces to emulate lambdas.
I've been using Scala (http://www.scala-lang.org/) a
Thu, 17 Dec 2009 12:24:50 +, Peter C. Chapin wrote:
> retard wrote in
> news:hg8ppr$107...@digitalmars.com:
>
>> That's not the only problem in JVM. Languages are getting more and more
>> functional these days and many enterprise Java projects use ad-hoc
>> single method interfaces to emulat
On 2009-12-17 13:58:44 +0100, retard said:
Most likely they have will have to wrap lambdas inside some kind of
Function objects. I've read that even Scala would benefit from a more
functional friendly VM. But Sun's focus is on JavaFX and dynamic
languages now..
One of the first necessities for
Fri, 18 Dec 2009 16:43:35 +0100, Daniel de Kok wrote:
> On 2009-12-17 13:58:44 +0100, retard said:
>> Most likely they have will have to wrap lambdas inside some kind of
>> Function objects. I've read that even Scala would benefit from a more
>> functional friendly VM. But Sun's focus is on JavaF
retard wrote:
I've only seen how Scala solves problems elegantly. These are from some
biased blog posts etc. Can you show one example that looks uglier in
Scala, but looks decent in D or some other language?
Many languages offer "show" examples that look elegant. A classic
example is the one
== Quote from Walter Bright (newshou...@digitalmars.com)'s article
> qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
> prominently featured in Haskell's official introduction page:
> http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
> Ain't that cool? Bu
dsimcha wrote:
== Quote from Walter Bright (newshou...@digitalmars.com)'s article
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
prominently featured in Haskell's official introduction page:
http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
Ain't tha
dsimcha wrote:
== Quote from Walter Bright (newshou...@digitalmars.com)'s article
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
prominently featured in Haskell's official introduction page:
http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
Ain't tha
Walter Bright:
> Ain't that cool? But look closer. The advantage of quicksort is that it
> is an *in-place* sort. The Haskell one creates new arrays for every
> state in the sort. The other fundamental problem with the Haskell
> version is that it selects the first array element as the "pivot".
bearophile wrote:
Walter Bright:
Ain't that cool? But look closer. The advantage of quicksort is
that it is an *in-place* sort. The Haskell one creates new arrays
for every state in the sort. The other fundamental problem with the
Haskell version is that it selects the first array element as the
bearophile wrote:
Please ask if you have missed my two points, because they must be
understood if you want to design a modern language.
I believe I do get it. After all, look at D's support for functional
programming (immutable and pure).
I wrote the post in reply to "Can you show one example
Walter Bright wrote:
There is no
mention in the text of any of the egregious shortcomings of the example.
I take that back, later on it does mention the memory consumption problem:
http://www.haskell.org/haskellwiki/Introduction#When_C_is_better
Fri, 18 Dec 2009 16:42:27 -0800, Walter Bright wrote:
> bearophile wrote:
>> Please ask if you have missed my two points, because they must be
>> understood if you want to design a modern language.
>
> I believe I do get it. After all, look at D's support for functional
> programming (immutable a
Andrei Alexandrescu wrote:
bearophile wrote:
Walter Bright:
Ain't that cool? But look closer. The advantage of quicksort is
that it is an *in-place* sort. The Haskell one creates new arrays
for every state in the sort. The other fundamental problem with the
Haskell version is that it selects th
Walter Bright wrote:
The Haskell folks really need to find a better canonical example.
Add to that the Erlang folk, too. I'm reading the book on Erlang by
Armstrong. Here's the Quicksort section and example on page 52:
"Here's how to write a sort algorithm[footnote] using two list
comprehen
Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote:
> Walter Bright wrote:
>> The Haskell folks really need to find a better canonical example.
>
> Add to that the Erlang folk, too. I'm reading the book on Erlang by
> Armstrong. Here's the Quicksort section and example on page 52:
>
> "H
retard wrote:
> Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote:
>
>> Walter Bright wrote:
>>> The Haskell folks really need to find a better canonical example.
>> Add to that the Erlang folk, too. I'm reading the book on Erlang by
>> Armstrong. Here's the Quicksort section and example
retard wrote:
I'm 100% sure I can find a suboptimal programming example from some C/C++/
D book.
Andrei's book draft is out for review. If you wish to review it and make
suggestions for improvement, I'm sure Andrei can arrange that. Now's the
time to do that!
Just like an operating system i
== Quote from Andrei Alexandrescu (seewebsiteforem...@erdani.org)'s
> "This code is shown for its elegance rather than its efficiency. Using
> ++ in this way is not generally considered good programming practice."
> So if the code is inefficient and in poor programming practice, how in
> this bless
dsimcha wrote:
== Quote from Andrei Alexandrescu (seewebsiteforem...@erdani.org)'s
"This code is shown for its elegance rather than its efficiency. Using
++ in this way is not generally considered good programming practice."
So if the code is inefficient and in poor programming practice, how in
retard wrote:
Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote:
Walter Bright wrote:
The Haskell folks really need to find a better canonical example.
Add to that the Erlang folk, too. I'm reading the book on Erlang by
Armstrong. Here's the Quicksort section and example on page 52:
Sat, 19 Dec 2009 21:29:45 -0600, Andrei Alexandrescu wrote:
> dsimcha wrote:
>> == Quote from Andrei Alexandrescu (seewebsiteforem...@erdani.org)'s
>>> "This code is shown for its elegance rather than its efficiency. Using
>>> ++ in this way is not generally considered good programming practice."
On 2009-12-18 18:02:28 +0100, retard said:
I've only seen how Scala solves problems elegantly. These are from some
biased blog posts etc. Can you show one example that looks uglier in
Scala, but looks decent in D or some other language?
I can not paste any of this particular code ($WORK). From
On 2009-12-18 20:39:08 +0100, Walter Bright said:
Ain't that cool? But look closer. The advantage of quicksort is that it
is an *in-place* sort. The Haskell one creates new arrays for every
state in the sort.
But it does have one nice property: due to laziness, the n-th elements
of the sorte
On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu
said:
"This code is shown for its elegance rather than its efficiency. Using
++ in this way is not generally considered good programming practice."
So if the code is inefficient and in poor programming practice, how in
this blessed world could
Daniel de Kok wrote:
On 2009-12-18 20:39:08 +0100, Walter Bright
said:
Ain't that cool? But look closer. The advantage of quicksort is that
it is an *in-place* sort. The Haskell one creates new arrays for every
state in the sort.
But it does have one nice property: due to laziness, the n-th
Daniel de Kok wrote:
On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu
said:
"This code is shown for its elegance rather than its efficiency. Using
++ in this way is not generally considered good programming practice."
So if the code is inefficient and in poor programming practice, how in
th
Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote:
> On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu
> said:
>> "This code is shown for its elegance rather than its efficiency. Using
>> ++ in this way is not generally considered good programming practice."
>>
>> So if the code is inefficien
Mon, 21 Dec 2009 18:01:29 +0100, Daniel de Kok wrote:
> On 2009-12-18 18:02:28 +0100, retard said:
>> I've only seen how Scala solves problems elegantly. These are from some
>> biased blog posts etc. Can you show one example that looks uglier in
>> Scala, but looks decent in D or some other langu
retard wrote:
Agreed. Will be fixed later. Keep in mind that D is older language than
Scala - now tell me what mystruct.tupleof.stringof does - where's the
documentation? From the top of my head I can imagine at least 200
different cases where the D/Phobos's documentation sucks.
I would appre
retard wrote:
> Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote:
>
>> On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu
>> said:
>>> "This code is shown for its elegance rather than its efficiency. Using
>>> ++ in this way is not generally considered good programming practice."
>>>
>>> So
Mon, 21 Dec 2009 12:13:48 -0600, Andrei Alexandrescu wrote:
> Daniel de Kok wrote:
>> On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu
>> said:
>>> "This code is shown for its elegance rather than its efficiency. Using
>>> ++ in this way is not generally considered good programming practice."
>>
Mon, 21 Dec 2009 20:04:05 +0100, Lutger wrote:
> retard wrote:
>
>> Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote:
>>
>>> On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu
>>> said:
"This code is shown for its elegance rather than its efficiency.
Using ++ in this way is not gen
retard wrote:
I have several imperative language programming books and instead of qsort
they introduce the reader to the wonderful world of bubble sort!
Bubble sort should be part of an introductory programming course, if
only because:
1. it's an algorithm that gets reinvented if one is not
Walter Bright wrote:
retard wrote:
I have several imperative language programming books and instead of
qsort they introduce the reader to the wonderful world of bubble sort!
Bubble sort should be part of an introductory programming course, if
only because:
1. it's an algorithm that gets rei
retard wrote:
Mon, 21 Dec 2009 12:13:48 -0600, Andrei Alexandrescu wrote:
Daniel de Kok wrote:
On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu
said:
"This code is shown for its elegance rather than its efficiency. Using
++ in this way is not generally considered good programming practice."
== Quote from Andrei Alexandrescu (seewebsiteforem...@erdani.org)'s
> I fail to see how in D you'd be hard pressed to think in terms of lower
> level abstractions.
> Andrei
Devil's advocate since I mostly agree:
Conservative GC?
Andrei Alexandrescu wrote:
Walter Bright wrote:
retard wrote:
I have several imperative language programming books and instead of
qsort they introduce the reader to the wonderful world of bubble sort!
Bubble sort should be part of an introductory programming course, if
only because:
1. it'
On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger
wrote:
Andrei Alexandrescu wrote:
Walter Bright wrote:
retard wrote:
I have several imperative language programming books and instead of
qsort they introduce the reader to the wonderful world of bubble sort!
Bubble sort should be part
Walter Bright Wrote:
> dsimcha wrote:
> > == Quote from Walter Bright (newshou...@digitalmars.com)'s article
> >> qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
> >> prominently featured in Haskell's official introduction page:
> >> http://www.haskell.org/haskellwiki/Int
"Andrei Alexandrescu" wrote in message
news:4b2fcf53.9050...@erdani.org...
> Walter Bright wrote:
>> retard wrote:
>>> I have several imperative language programming books and instead of
>>> qsort they introduce the reader to the wonderful world of bubble sort!
>>
>> Bubble sort should be part o
On Mon, 21 Dec 2009 14:01:23 -0500, Walter Bright
wrote:
retard wrote:
Agreed. Will be fixed later. Keep in mind that D is older language than
Scala - now tell me what mystruct.tupleof.stringof does - where's the
documentation? From the top of my head I can imagine at least 200
differen
On 2009-12-21 19:13:48 +0100, Andrei Alexandrescu
said:
I disagree. We don't want to educate people to write patently
inefficient code and in poor programming practice.
I do not mind it, it's ok for explaining a concept clearly. Of course,
inadequacies should also be discussed. I'd argue that
Daniel de Kok wrote:
I do not mind it, it's ok for explaining a concept clearly. Of course,
inadequacies should also be discussed. I'd argue that these are also the
thinking steps normally involved in designing a solution to a problem:
first try to solve it in the obvious way to understand the
Tue, 22 Dec 2009 01:43:17 -0800, Walter Bright wrote:
> Daniel de Kok wrote:
>> I do not mind it, it's ok for explaining a concept clearly. Of course,
>> inadequacies should also be discussed. I'd argue that these are also
>> the thinking steps normally involved in designing a solution to a
>> pro
Tue, 22 Dec 2009 01:43:17 -0800, Walter Bright wrote:
> Daniel de Kok wrote:
>> I do not mind it, it's ok for explaining a concept clearly. Of course,
>> inadequacies should also be discussed. I'd argue that these are also
>> the thinking steps normally involved in designing a solution to a
>> pro
Andrei Alexandrescu Wrote:
> retard wrote:
> > Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote:
> >
> >> Walter Bright wrote:
> >>> The Haskell folks really need to find a better canonical example.
> >>
> >> The footnote says (how the hell did this make it through the editorial
> >> pa
Daniel de Kok wrote:
On 2009-12-21 19:13:48 +0100, Andrei Alexandrescu
said:
I disagree. We don't want to educate people to write patently
inefficient code and in poor programming practice.
I do not mind it, it's ok for explaining a concept clearly.
My point is that there is no "concept" be
Nick Sabalausky Wrote:
> It should be "should be", for the same reason and in the same way that the
> "waterfall" development model *should be* taught: Presenting it up front as
> conceptually-easy-but-generally-a-bad-thing-to-do will help people identify
> it and therefore avoid it. Not teachi
On 2009-12-22 10:43:17 +0100, Walter Bright said:
One of the big problems with the presentations of the functional qsort
is that it is presented as a shining success of FP, when it is anything
but.
There are better examples of 'shining succes' in FP. For example,
consider the very clear and
On 2009-12-22 14:24:41 +0100, Andrei Alexandrescu
said:
Daniel de Kok wrote:
...in pure FP. Of course, another problem is that some algorithms are
inherently imperative. For instance, I find calculating the edit
distance in a performant manner ugly in functional languages.
So then I guess I
retard wrote:
The discussion here mostly touts imperative languages with the same old
centuries old arguments like "omg functional languages can't do in-place
algorithms". "so you need hacks to implement in-place algorithms. that
must mean that the elegance of fpl is in fact something that cann
retard wrote:
Simon Peyton Jones had in his slides a nice graph of the reliability vs
performance issues. Functional languages were originally very slow, but
had the safety aspect. Imperative languages have always been fast, and
only gradually improved on the reliability front. Pure functional
Daniel de Kok wrote:
Of course, there are good counter-examples where purity helps. But it's
not a black-white world. Not that I really have to say that on a D list
;-).
Right, D is not a language implementing a religion!
Tue, 22 Dec 2009 10:27:39 -0800, Walter Bright wrote:
> For another example, around 1990 the programming world decided that OOP
> was the solution to all programming problems. One of the results of that
> thinking is Java. We've now suffered through the inevitable backlash,
> and a more reasoned c
retard wrote:
I use the Okasaki book as my bible when talking about purely functional
data structures.
It's an awesome book. It's also very frank and tells things as they are,
as opposed to others (*cough*) that patronize the reader by artificially
making it seem so easy, it's amazing how Sto
Andrei Alexandrescu wrote:
retard wrote:
I use the Okasaki book as my bible when talking about purely
functional data structures.
It's an awesome book. It's also very frank and tells things as they are,
as opposed to others (*cough*) that patronize the reader by artificially
making it seem s
Tue, 22 Dec 2009 14:51:55 -0600, Andrei Alexandrescu wrote:
> retard wrote:
>> I use the Okasaki book as my bible when talking about purely functional
>> data structures.
>
> It's an awesome book. It's also very frank and tells things as they are,
> as opposed to others (*cough*) that patronize t
retard wrote:
Tue, 22 Dec 2009 14:51:55 -0600, Andrei Alexandrescu wrote:
retard wrote:
I use the Okasaki book as my bible when talking about purely functional
data structures.
It's an awesome book. It's also very frank and tells things as they are,
as opposed to others (*cough*) that patroni
Andrei Alexandrescu wrote:
> Hm, I guess I should have been more explicit. The problem isn't defining
> a few more names, but that the explanation completely neglects any
> control flow issues (e.g. conditionals and loops). You can't define a
> new name for each instance of a loop, so everything is
Rainer Deyke wrote:
Andrei Alexandrescu wrote:
Hm, I guess I should have been more explicit. The problem isn't defining
a few more names, but that the explanation completely neglects any
control flow issues (e.g. conditionals and loops). You can't define a
new name for each instance of a loop, s
On Tue, Dec 22, 2009 at 21:51, Andrei Alexandrescu <
seewebsiteforem...@erdani.org> wrote:
> retard wrote:
>
>> I use the Okasaki book as my bible when talking about purely functional
>> data structures.
>>
>
> It's an awesome book. It's also very frank and tells things as they are, as
> opposed t
Philippe Sigaud wrote:
On Tue, Dec 22, 2009 at 21:51, Andrei Alexandrescu
mailto:seewebsiteforem...@erdani.org>>
wrote:
retard wrote:
I use the Okasaki book as my bible when talking about purely
functional data structures.
It's an awesome book. It's also very fran
Denis Koroskin wrote:
> On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger
> wrote:
>
>> Andrei Alexandrescu wrote:
>>> Walter Bright wrote:
retard wrote:
> I have several imperative language programming books and instead
of
> qsort they introduce the reader to the wonderful wor
Sat, 26 Dec 2009 09:21:55 -0800, Charles Hixson wrote:
> Denis Koroskin wrote:
>
>> On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger
>
>> wrote:
>>
>>> Andrei Alexandrescu wrote:
Walter Bright wrote:
> retard wrote:
>> I have several imperative language programming books and in
retard wrote:
Sat, 26 Dec 2009 09:21:55 -0800, Charles Hixson wrote:
Denis Koroskin wrote:
On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger
wrote:
Andrei Alexandrescu wrote:
Walter Bright wrote:
retard wrote:
I have several imperative language programming books and instead
of
qs
Don wrote:
I'd say it's easier. If you watch someone sorting some cards, they'll
use either insertion sort or selection sort. Nobody should have ever
heard of bubble sort, I'm pleased to hear some schools aren't mentioning
it. Such a foolish algorithm.
I suppose I'm alone in thinking that en
Don Wrote:
> retard wrote:
...
>
> I'd say it's easier. If you watch someone sorting some cards, they'll
> use either insertion sort or selection sort. Nobody should have ever
> heard of bubble sort, I'm pleased to hear some schools aren't mentioning
> it. Such a foolish algorithm.
>
> "the bu
Walter Bright:
> I suppose I'm alone in thinking that engineering school should also
> cover designs that don't work and explain why!
Knuth doesn't say it's uselsss to teach Bubble sort. Knowing bad algorithms is
useful if they are both obvious and slow, to know the basics and to avoid them.
And
== Quote from Don (nos...@nospam.com)'s article
> "the bubble sort seems to have nothing to recommend it, except a catchy
> name " - Knuth.
Well, the bubble sort distance is a pretty good metric of how similarly ordered
two lists are. It's useful, for example, in statistics such as Kendall's Tau.
== Quote from Walter Bright (newshou...@digitalmars.com)'s article
> Don wrote:
> > I'd say it's easier. If you watch someone sorting some cards, they'll
> > use either insertion sort or selection sort. Nobody should have ever
> > heard of bubble sort, I'm pleased to hear some schools aren't mentio
== Quote from Kevin Bealer (kevinbea...@gmail.com)'s article
> (Non-software) people doing routine tasks often come up with better algorithms
intuitively than my intuition expects them to.
> I think a lot of people would do even better than insertion with a deck of
> poker
cards -- they might grou
Walter Bright Wrote:
> Don wrote:
> > I'd say it's easier. If you watch someone sorting some cards, they'll
> > use either insertion sort or selection sort. Nobody should have ever
> > heard of bubble sort, I'm pleased to hear some schools aren't mentioning
> > it. Such a foolish algorithm.
>
Kevin Bealer wrote:
> I think a lot of people would do even better than insertion with a
> deck of poker cards -- they might group cards by either suit or rank
> (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and
> J-A"), then order the "buckets", then stick these ordered sets bac
Sean Kelly wrote:
Walter Bright Wrote:
I suppose I'm alone in thinking that engineering school should also
cover designs that don't work and explain why!
I'm sure every US-taught engineer has heard of the Tacoma Narrows
Bridge disaster. But it would be nice if there were a bit more time
spen
dsimcha wrote:
== Quote from Don (nos...@nospam.com)'s article
"the bubble sort seems to have nothing to recommend it, except a catchy
name " - Knuth.
Well, the bubble sort distance is a pretty good metric of how similarly ordered
two lists are. It's useful, for example, in statistics such as
dsimcha Wrote:
> == Quote from Kevin Bealer (kevinbea...@gmail.com)'s article
> > (Non-software) people doing routine tasks often come up with better
> > algorithms
> intuitively than my intuition expects them to.
> > I think a lot of people would do even better than insertion with a deck of
> >
Rainer Deyke Wrote:
> Kevin Bealer wrote:
> > I think a lot of people would do even better than insertion with a
> > deck of poker cards -- they might group cards by either suit or rank
> > (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and
> > J-A"), then order the "buckets", th
Kevin Bealer wrote:
I'm curious if the multi-pivot quicksort (I think everyone gets what I
mean by this? Divide by more than one pivot on each pass? I can give
details if you like ...) has been tried out much. It seems like it must
have been, but it also seems like something that would
Simen kjaeraas Wrote:
> Kevin Bealer wrote:
>
> > I'm curious if the multi-pivot quicksort (I think everyone gets what I
> > mean by this? Divide by more than one pivot on each pass? I can give
> > details if you like ...) has been tried out much. It seems like it must
> > have been, bu
Nekuromento Wrote:
> Simen kjaeraas Wrote:
>
> > Kevin Bealer wrote:
> >
> > > I'm curious if the multi-pivot quicksort (I think everyone gets what I
> > > mean by this? Divide by more than one pivot on each pass? I can give
> > > details if you like ...) has been tried out much. It seem
On Tue, 29 Dec 2009 21:36:25 +0300, justme wrote:
Nekuromento Wrote:
Simen kjaeraas Wrote:
> Kevin Bealer wrote:
>
> > I'm curious if the multi-pivot quicksort (I think everyone gets
what I
> > mean by this? Divide by more than one pivot on each pass? I can
give
> > details if you lik
Denis Koroskin Wrote:
> On Tue, 29 Dec 2009 21:36:25 +0300, justme wrote:
>
> > Nekuromento Wrote:
> >
> >> Simen kjaeraas Wrote:
> >>
> >> > Kevin Bealer wrote:
> >> >
> >> > > I'm curious if the multi-pivot quicksort (I think everyone gets
> >> what I
> >> > > mean by this? Divide by more
Denis Koroskin wrote:
On Tue, 29 Dec 2009 21:36:25 +0300, justme wrote:
Nekuromento Wrote:
Simen kjaeraas Wrote:
> Kevin Bealer wrote:
>
> > I'm curious if the multi-pivot quicksort (I think everyone gets
what I
> > mean by this? Divide by more than one pivot on each pass? I can
give
>
Don:
> Yeah, that's the obvious question -- what's the optimum number of
> pivots? It's a bit annoying that that paper doesn't mention it.
Two pivots help avoid a common bad corner case of the QuickSort (when there are
many equal items). Writing a good sorting routine is not easy, there's lot of
Wed, 30 Dec 2009 02:58:14 -0500, bearophile wrote:
> Don:
>> Yeah, that's the obvious question -- what's the optimum number of
>> pivots? It's a bit annoying that that paper doesn't mention it.
>
> Two pivots help avoid a common bad corner case of the QuickSort (when
> there are many equal items)
retard:
> So can you tell us then what is the optimal number of pivots?<
I can tell you that two pivot, used in the correct way, lead to a good
quicksort, as I've said.
>Can it be proven?
I don't know. It can be proven that two pivot are enough to avoid the problem
with the classic QuickSort.
bearophile wrote:
retard:
So can you tell us then what is the optimal number of pivots?<
I can tell you that two pivot, used in the correct way, lead to a good
quicksort, as I've said.
Can it be proven?
I don't know. It can be proven that two pivot are enough to avoid the problem
with t
Don:
> It'd be interesting to know how the two-pivot quicksort compares to timsort.
Timsort is probably a bit slower, but they can't be compared, because Timsort
is a stable sort, while normal quicksorts aren't.
> I suspect there's a median-of-five-killer worst case for this quicksort,
> just
Don wrote:
> dsimcha wrote:
>> == Quote from Don (nos...@nospam.com)'s article
>>> "the bubble sort seems to have nothing to recommend it, except a
catchy
>>> name " - Knuth.
>>
>> Well, the bubble sort distance is a pretty good metric of how
similarly
>> ordered
>> two lists are. It's useful,
95 matches
Mail list logo