www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - QSort in D: is this best?

reply downs <default_357-line yahoo.de> writes:
Or are there any bugs/optimization opportunities I'm missing?

void qsort(T)(T[] array) {
  if (array.length < 2) return;
  static int i;
  auto pivot = array[i++%$];
  // from is base-0, to is base-1.
  int from = 0, to = array.length;
  while (from != to) {
    if (array[from] >= pivot && array[to-1] < pivot)
      swap(array[from], array[to-1]);
    if (array[from] < pivot)
      from ++;
    if (array[to-1] >= pivot)
      to --;
  }
  array[0 .. from].qsort();
  array[from .. $].qsort();
}
Dec 20 2009
next sibling parent reply downs <default_357-line yahoo.de> writes:
according to http://www.mail-archive.com/haskell-cafe%40haskell.org/msg63381.html

I'll let this speak for itself.

import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import Control.Monad.ST

myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi
    | lo < hi   = do
        let lscan p h i
                | i < h = do
                    v <- unsafeRead a i
                    if p < v then return i else lscan p h (i+1)
                | otherwise = return i
            rscan p l i
                | l < i = do
                    v <- unsafeRead a i
                    if v < p then return i else rscan p l (i-1)
                | otherwise = return i
            swap i j = do
                v <- unsafeRead a i
                unsafeRead a j >>= unsafeWrite a i
                unsafeWrite a j v
            sloop p l h
                | l < h = do
                    l1 <- lscan p h l
                    h1 <- rscan p l1 h
                    if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return
l1
                | otherwise = return l
        piv <- unsafeRead a hi
        i <- sloop piv lo hi
        swap i hi
        myqsort a lo (i-1)
        myqsort a (i+1) hi
    | otherwise = return ()
Dec 20 2009
next sibling parent reply Don <nospam nospam.com> writes:
downs wrote:
 according to http://www.mail-archive.com/haskell-cafe%40haskell.org/msg63381.html
 
 I'll let this speak for itself.
 
 import Data.Array.Base (unsafeRead, unsafeWrite)

Brilliant.
Dec 20 2009
parent reply Don <nospam nospam.com> writes:
retard wrote:
 Sun, 20 Dec 2009 16:44:03 +0100, Don wrote:
 
 downs wrote:
 according to
 http://www.mail-archive.com/haskell-cafe%40haskell.org/msg63381.html

 I'll let this speak for itself.

 import Data.Array.Base (unsafeRead, unsafeWrite)

Brilliant.

What is so brilliant? Referential transparency is broken unless single- threadedness is forced through monadic computation or by some other means (uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort between D and Haskell.
Dec 20 2009
parent reply Tim Matthews <tim.matthews7 gmail.com> writes:
On 21/12/2009 8:57 p.m., Don wrote:
 retard wrote:
 Sun, 20 Dec 2009 16:44:03 +0100, Don wrote:

 downs wrote:
 according to
 http://www.mail-archive.com/haskell-cafe%40haskell.org/msg63381.html

 I'll let this speak for itself.

 import Data.Array.Base (unsafeRead, unsafeWrite)

Brilliant.

What is so brilliant? Referential transparency is broken unless single- threadedness is forced through monadic computation or by some other means (uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort between D and Haskell.

Quicksort can be expressed in haskell just like this: qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) It probably performs like a bitch but is a very beautiful way to express quicksort.
Dec 21 2009
next sibling parent reply "Nick Sabalausky" <a a.a> writes:
"Tim Matthews" <tim.matthews7 gmail.com> wrote in message 
news:hgp10e$2sj3$1 digitalmars.com...
 On 21/12/2009 8:57 p.m., Don wrote:
 retard wrote:
 Sun, 20 Dec 2009 16:44:03 +0100, Don wrote:

 downs wrote:
 according to
 http://www.mail-archive.com/haskell-cafe%40haskell.org/msg63381.html

 I'll let this speak for itself.

 import Data.Array.Base (unsafeRead, unsafeWrite)

Brilliant.

What is so brilliant? Referential transparency is broken unless single- threadedness is forced through monadic computation or by some other means (uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort between D and Haskell.

Quicksort can be expressed in haskell just like this: qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) It probably performs like a bitch but is a very beautiful way to express quicksort.

It's already been pointed out in a number of places that that's not quicksort. Quicksort is in-place and doesn't use the head as the pivot. Besides "It probably performs like a bitch" defeats the whole point of quicksort, doesn't it? And, going along with what Andrei pointed out in another thread, it's hard call a piece of code "beautiful" if it's either flat-out wrong or otherwise defeats its own point. This piece of PHP code is "beautiful" too: $result = doDBQuery("SELECT * FROM $_GET[table]") ...but it's still total shit and therefore worthless.
Dec 21 2009
next sibling parent reply =?UTF-8?B?UGVsbGUgTcOlbnNzb24=?= <pelle.mansson gmail.com> writes:
On 12/22/2009 01:16 AM, Nick Sabalausky wrote:
 It's already been pointed out in a number of places that that's not
 quicksort. Quicksort is in-place and doesn't use the head as the pivot.
 Besides "It probably performs like a bitch" defeats the whole point of
 quicksort, doesn't it? And, going along with what Andrei pointed out in
 another thread, it's hard call a piece of code "beautiful" if it's either
 flat-out wrong or otherwise defeats its own point.

It does however display the idea behind quicksort quite nicely: pivot, sort the larger and smaller portions of the array separately. The rest is just optimization.
Dec 21 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Pelle Månsson wrote:
 On 12/22/2009 01:16 AM, Nick Sabalausky wrote:
 It's already been pointed out in a number of places that that's not
 quicksort. Quicksort is in-place and doesn't use the head as the pivot.
 Besides "It probably performs like a bitch" defeats the whole point of
 quicksort, doesn't it? And, going along with what Andrei pointed out in
 another thread, it's hard call a piece of code "beautiful" if it's either
 flat-out wrong or otherwise defeats its own point.

It does however display the idea behind quicksort quite nicely: pivot, sort the larger and smaller portions of the array separately. The rest is just optimization.

I disagree. Partition is quintessential to quicksort. Andrei
Dec 21 2009
prev sibling parent Tim Matthews <tim.matthews7 gmail.com> writes:
On 22/12/2009 1:16 p.m., Nick Sabalausky wrote:
 "Tim Matthews"<tim.matthews7 gmail.com>  wrote in message
 news:hgp10e$2sj3$1 digitalmars.com...
 On 21/12/2009 8:57 p.m., Don wrote:
 retard wrote:
 Sun, 20 Dec 2009 16:44:03 +0100, Don wrote:

 downs wrote:
 according to
 http://www.mail-archive.com/haskell-cafe%40haskell.org/msg63381.html

 I'll let this speak for itself.

 import Data.Array.Base (unsafeRead, unsafeWrite)

Brilliant.

What is so brilliant? Referential transparency is broken unless single- threadedness is forced through monadic computation or by some other means (uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort between D and Haskell.

Quicksort can be expressed in haskell just like this: qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) It probably performs like a bitch but is a very beautiful way to express quicksort.

Quicksort is in-place and doesn't use the head as the pivot.

true
 Besides "It probably performs like a bitch" defeats the whole point of
 quicksort, doesn't it?

true
 And, going along with what Andrei pointed out in
 another thread, it's hard call a piece of code "beautiful" if it's either
 flat-out wrong or otherwise defeats its own point.

My stance on this is that the qsort code explains how you want the code to be sorted and a really good haskell compiler should optimize that out. Infact as haskell can't update in place anything without interfacing to c, I often blame the compiler but realistically most still have some way to go for that kind of optimizations. As for the qsort algorithm using the head as the pivot. Thanks for pointing that out. I didn't write it but I copy/pasted it from the official wiki http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell Another place that describe quicksort in haskell and also a wiki incase you want to edit it http://en.literateprograms.org/Quicksort_%28Haskell%29
Dec 21 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Tim Matthews wrote:
 On 21/12/2009 8:57 p.m., Don wrote:
 retard wrote:
 Sun, 20 Dec 2009 16:44:03 +0100, Don wrote:

 downs wrote:
 according to
 http://www.mail-archive.com/haskell-cafe%40haskell.org/msg63381.html

 I'll let this speak for itself.

 import Data.Array.Base (unsafeRead, unsafeWrite)

Brilliant.

What is so brilliant? Referential transparency is broken unless single- threadedness is forced through monadic computation or by some other means (uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort between D and Haskell.

Quicksort can be expressed in haskell just like this: qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) It probably performs like a bitch but is a very beautiful way to express quicksort.

That definition is what was discussed in this thread and alleged to be anything but beautiful. Andrei
Dec 21 2009
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 That definition is what was discussed in this thread and alleged to be 
 anything but beautiful.

I've been in museums in europe where they proudly display ornate swords and armor as "beautiful". I always kinda thought otherwise, because all that decoration and encrustation was not what the weapon was for. More interesting were the weapons with a single minded deadliness to them. I suppose it's the engineer in me <g>.
Dec 21 2009
next sibling parent reply Tim Matthews <tim.matthews7 gmail.com> writes:
On 22/12/2009 5:24 p.m., Walter Bright wrote:
 Andrei Alexandrescu wrote:
 That definition is what was discussed in this thread and alleged to be
 anything but beautiful.

I've been in museums in europe where they proudly display ornate swords and armor as "beautiful". I always kinda thought otherwise, because all that decoration and encrustation was not what the weapon was for. More interesting were the weapons with a single minded deadliness to them. I suppose it's the engineer in me <g>.

I guess it is true that "beauty is in the eye of the beholder" according to google this means: "people all have different ideas about what is beautiful"
Dec 21 2009
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Tim Matthews wrote:
 On 22/12/2009 5:24 p.m., Walter Bright wrote:
 Andrei Alexandrescu wrote:
 That definition is what was discussed in this thread and alleged to be
 anything but beautiful.

I've been in museums in europe where they proudly display ornate swords and armor as "beautiful". I always kinda thought otherwise, because all that decoration and encrustation was not what the weapon was for. More interesting were the weapons with a single minded deadliness to them. I suppose it's the engineer in me <g>.

I guess it is true that "beauty is in the eye of the beholder" according to google this means: "people all have different ideas about what is beautiful"

Sure. I see beauty in things that are perfectly suited to their task - nothing missing, and nothing extra. So ornate engravery leaves me cold, as does jewel encrustation.
Dec 22 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Tim Matthews wrote:
 On 22/12/2009 5:24 p.m., Walter Bright wrote:
 Andrei Alexandrescu wrote:
 That definition is what was discussed in this thread and alleged to be
 anything but beautiful.

I've been in museums in europe where they proudly display ornate swords and armor as "beautiful". I always kinda thought otherwise, because all that decoration and encrustation was not what the weapon was for. More interesting were the weapons with a single minded deadliness to them. I suppose it's the engineer in me <g>.

I guess it is true that "beauty is in the eye of the beholder" according to google this means: "people all have different ideas about what is beautiful"

Paul Graham argues that relativity of taste is just a fad: http://www.paulgraham.com/taste.html Andrei
Dec 22 2009
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 Paul Graham argues that relativity of taste is just a fad:
 
 http://www.paulgraham.com/taste.html

That essay is very applicable to programming language design.
Dec 22 2009
prev sibling parent reply Rainer Deyke <rainerd eldwood.com> writes:
Andrei Alexandrescu wrote:
 Paul Graham argues that relativity of taste is just a fad:
 
 http://www.paulgraham.com/taste.html

His entire argument seems to hinge on the idea that the difference between a good artist and a bad artist is that the better artist has better taste. Which is complete and utter bullshit. The good artist is good because he has the skill to better express his taste, not because his taste itself is superior. He can create things that are more beautiful (a technical skill), but only for his own sense of beauty. -- Rainer Deyke - rainerd eldwood.com
Dec 22 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Rainer Deyke wrote:
 Andrei Alexandrescu wrote:
 Paul Graham argues that relativity of taste is just a fad:

 http://www.paulgraham.com/taste.html

His entire argument seems to hinge on the idea that the difference between a good artist and a bad artist is that the better artist has better taste. Which is complete and utter bullshit. The good artist is good because he has the skill to better express his taste, not because his taste itself is superior. He can create things that are more beautiful (a technical skill), but only for his own sense of beauty.

I'm not sure. Actually to be frank I completely disagree. I'm trained in music and my father is an architect and painter; I see/hear plenty of work by artists that technically are very skilled but have poor taste. Besides, modern technology has democratized many aspects of creative work, but I'm almost afraid to factor that extra argument in because it might be attacked and evidence is powerful enough without it. Andrei
Dec 22 2009
parent reply Rainer Deyke <rainerd eldwood.com> writes:
Andrei Alexandrescu wrote:
 Rainer Deyke wrote:
 His entire argument seems to hinge on the idea that the difference
 between a good artist and a bad artist is that the better artist has
 better taste.  Which is complete and utter bullshit.  The good artist is
 good because he has the skill to better express his taste, not because
 his taste itself is superior.  He can create things that are more
 beautiful (a technical skill), but only for his own sense of beauty.

I'm not sure. Actually to be frank I completely disagree. I'm trained in music and my father is an architect and painter; I see/hear plenty of work by artists that technically are very skilled but have poor taste.

That statement pretty much presumes that you are qualified to judge other people's taste. In other words, if you don't like it, then it's objectively bad. Your own taste is objectively perfect, and the closer some other person's taste resembles your own, the better it is. Even if I did believe in an objective measure of taste, I wouldn't believe that your taste is the platonic ideal to which we should aspire. The ability to enjoy a work of art (i.e. "taste") is one thing, the ability to create a work of art that is enjoyed is another. The former is subjective, the latter presumes the former but is otherwise a technical skill. -- Rainer Deyke - rainerd eldwood.com
Dec 22 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Rainer Deyke wrote:
 Andrei Alexandrescu wrote:
 Rainer Deyke wrote:
 His entire argument seems to hinge on the idea that the difference
 between a good artist and a bad artist is that the better artist has
 better taste.  Which is complete and utter bullshit.  The good artist is
 good because he has the skill to better express his taste, not because
 his taste itself is superior.  He can create things that are more
 beautiful (a technical skill), but only for his own sense of beauty.

music and my father is an architect and painter; I see/hear plenty of work by artists that technically are very skilled but have poor taste.

That statement pretty much presumes that you are qualified to judge other people's taste. In other words, if you don't like it, then it's objectively bad. Your own taste is objectively perfect, and the closer some other person's taste resembles your own, the better it is.

Well it's exactly the point of the article that you oughtn't fall into the other extreme. If you did, Da Vinci would not be distinguishable from Ghirlandaio nor Porsche would be from Cadillac nor Bach would be from Boccherini.
 Even if I did believe in an objective measure of taste, I wouldn't
 believe that your taste is the platonic ideal to which we should aspire.

That doesn't mean you need to commit to relativism.
 The ability to enjoy a work of art (i.e. "taste") is one thing, the
 ability to create a work of art that is enjoyed is another.  The former
 is subjective, the latter presumes the former but is otherwise a
 technical skill.

That I agree with, but it doesn't add to your argument. In fact it adds to mine. Andrei
Dec 22 2009
parent Rainer Deyke <rainerd eldwood.com> writes:
Andrei Alexandrescu wrote:
 Rainer Deyke wrote:
 Andrei Alexandrescu wrote:
 Rainer Deyke wrote:
 His entire argument seems to hinge on the idea that the difference
 between a good artist and a bad artist is that the better artist has
 better taste.  Which is complete and utter bullshit.  The good
 artist is
 good because he has the skill to better express his taste, not because
 his taste itself is superior.  He can create things that are more
 beautiful (a technical skill), but only for his own sense of beauty.

music and my father is an architect and painter; I see/hear plenty of work by artists that technically are very skilled but have poor taste.

That statement pretty much presumes that you are qualified to judge other people's taste. In other words, if you don't like it, then it's objectively bad. Your own taste is objectively perfect, and the closer some other person's taste resembles your own, the better it is.

Well it's exactly the point of the article that you oughtn't fall into the other extreme. If you did, Da Vinci would not be distinguishable from Ghirlandaio nor Porsche would be from Cadillac nor Bach would be from Boccherini.

This "other extreme" is a ridiculous strawman that nobody, least of all myself, is advocating. An artist has many skills. One such skill is the low-level skill of placing brush strokes on a piece of paper. Another skill is the high level skill of making artistic choices that lead to something beautiful. I'm saying that these are both technical skills that can be objectively measured, and that they are both independent of the artist's (subjective) taste. It's an insult to artists everywhere to reduce the high level core of their work to mere taste. -- Rainer Deyke - rainerd eldwood.com
Dec 22 2009
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Rainer Deyke:
 The ability to enjoy a work of art (i.e. "taste") is one thing, the
 ability to create a work of art that is enjoyed is another.  The former
 is subjective, the latter presumes the former but is otherwise a
 technical skill.

Taste comes, mostly, from experience, training, work. So it's partially a technical skill :-) Bye, bearophile
Dec 23 2009
prev sibling next sibling parent "Nick Sabalausky" <a a.a> writes:
"Walter Bright" <newshound1 digitalmars.com> wrote in message 
news:hgphli$juf$1 digitalmars.com...
 Andrei Alexandrescu wrote:
 That definition is what was discussed in this thread and alleged to be 
 anything but beautiful.

I've been in museums in europe where they proudly display ornate swords and armor as "beautiful". I always kinda thought otherwise, because all that decoration and encrustation was not what the weapon was for. More interesting were the weapons with a single minded deadliness to them. I suppose it's the engineer in me <g>.

My take on that: "Beauty" usually refers to something being appealing to the senses, particularly sight. With something like code, though (as opposed to a physical object) it makes a little bit more sense than it normally would to use the term "beauty" metaphorically (ex: "functional qsort is/isn't beautiful"), because applying the traditional concept of "beauty" to code would amount to little more than an assessment of the formatting (font, spacing, etc.) and would not carry much, if any, relation to the actual content of the code. That content, of course, being the very thing that makes code code in the first place. I suppose a similar thing could be argued for swords (because one could define "sword" in terms of its intended function, just like "code"), but I think the argument there would be weaker because it's much easier to define something like "sword" in terms of its structure (shape, material, etc) than to define "code" in terms of its structure (one would probably have to start with a definition of certain glyphs and then find a structurally-oriented way to distinguish sequences of glyphs that do or don't qualify as "code"). So the criteria you're using to determine suitability of the label "beautiful sword/armor" is something I'd prefer to attach to a label more along the lines of "good sword/armor" or "well-designed/engineered sword/armor" (which, of course, IMO, is every bit as worthy of admiration as a pretty-looking one).
Dec 22 2009
prev sibling parent biozic <dransic free.fr> writes:
Le 22/12/09 05:24, Walter Bright a écrit :
 Andrei Alexandrescu wrote:
 That definition is what was discussed in this thread and alleged to be
 anything but beautiful.

I've been in museums in europe where they proudly display ornate swords and armor as "beautiful". I always kinda thought otherwise, because all that decoration and encrustation was not what the weapon was for. More interesting were the weapons with a single minded deadliness to them. I suppose it's the engineer in me <g>.

Maybe it's just that these museums don't give the complete argument: there were times when a "beautiful" jewel-encrusted sword was more powerful a weapon than a sharp-designed one. Showing off wealth and influential social position could avoid a physical fight... :)
Dec 23 2009
prev sibling parent retard <re tard.com.invalid> writes:
Sun, 20 Dec 2009 16:44:03 +0100, Don wrote:

 downs wrote:
 according to
 http://www.mail-archive.com/haskell-cafe%40haskell.org/msg63381.html
 
 I'll let this speak for itself.
 
 import Data.Array.Base (unsafeRead, unsafeWrite)

Brilliant.

What is so brilliant? Referential transparency is broken unless single- threadedness is forced through monadic computation or by some other means (uniqueness types comes to mind).
Dec 20 2009
prev sibling next sibling parent reply Lutger <lutger.blijdestijn gmail.com> writes:
downs wrote:

 Or are there any bugs/optimization opportunities I'm missing?
 
 void qsort(T)(T[] array) {
   if (array.length < 2) return;
   static int i;
   auto pivot = array[i++%$];
   // from is base-0, to is base-1.
   int from = 0, to = array.length;
   while (from != to) {
     if (array[from] >= pivot && array[to-1] < pivot)
       swap(array[from], array[to-1]);
     if (array[from] < pivot)
       from ++;
     if (array[to-1] >= pivot)
       to --;
   }
   array[0 .. from].qsort();
   array[from .. $].qsort();
 }

It's not reentrant but perhaps you don't care? I think these two optimizations matter the most: - improve selection of pivot (median of 3 for example) - switch to insertion sort or shellsort when array is below a certain length (somewhere between 50 and 150 I think is ok). A further optimization can be to implement a custom stack, but it's not as much bang-for-buck as switching to a different sort.
Dec 20 2009
parent reply downs <default_357-line yahoo.de> writes:
Lutger wrote:
 downs wrote:
 
 Or are there any bugs/optimization opportunities I'm missing?

 void qsort(T)(T[] array) {
   if (array.length < 2) return;
   static int i;
   auto pivot = array[i++%$];
   // from is base-0, to is base-1.
   int from = 0, to = array.length;
   while (from != to) {
     if (array[from] >= pivot && array[to-1] < pivot)
       swap(array[from], array[to-1]);
     if (array[from] < pivot)
       from ++;
     if (array[to-1] >= pivot)
       to --;
   }
   array[0 .. from].qsort();
   array[from .. $].qsort();
 }

It's not reentrant but perhaps you don't care?

Given that i is used as semi-random state, cross-thread bugs would help rather than hurt it, by making it more unpredictable.
 I think these two optimizations matter the most:
 - improve selection of pivot (median of 3 for example)
 - switch to insertion sort or shellsort when array is below a certain length 
 (somewhere between 50 and 150 I think is ok). 
 
 A further optimization can be to implement a custom stack, but it's not as 
 much bang-for-buck as switching to a different sort.
 
 

Well yeah, it's not the best sorting algorithm all things considered. I intended it mostly as a response to the much-vaunted Haskell qsort example.
Dec 20 2009
parent Lutger <lutger.blijdestijn gmail.com> writes:
downs wrote:

 Lutger wrote:
 downs wrote:
 
 Or are there any bugs/optimization opportunities I'm missing?

 void qsort(T)(T[] array) {
   if (array.length < 2) return;
   static int i;
   auto pivot = array[i++%$];
   // from is base-0, to is base-1.
   int from = 0, to = array.length;
   while (from != to) {
     if (array[from] >= pivot && array[to-1] < pivot)
       swap(array[from], array[to-1]);
     if (array[from] < pivot)
       from ++;
     if (array[to-1] >= pivot)
       to --;
   }
   array[0 .. from].qsort();
   array[from .. $].qsort();
 }

It's not reentrant but perhaps you don't care?

Given that i is used as semi-random state, cross-thread bugs would help rather than hurt it, by making it more unpredictable.

I see, that's clever.
 
 I think these two optimizations matter the most:
 - improve selection of pivot (median of 3 for example)
 - switch to insertion sort or shellsort when array is below a certain
 length (somewhere between 50 and 150 I think is ok).
 
 A further optimization can be to implement a custom stack, but it's not
 as much bang-for-buck as switching to a different sort.
 
 

Well yeah, it's not the best sorting algorithm all things considered. I intended it mostly as a response to the much-vaunted Haskell qsort example.

I didn't see you second post. But this is quite funny, you could write the same page the haskell intro does but swap the roles of haskell and C (or D) :)
Dec 20 2009
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
You can try translating this in efficient, readable and short D2 code using
Phobos2 (the purpose is to find spots where Phobos2 may need improvements):
http://rosettacode.org/wiki/Hamming_numbers#Haskell

Haskell version:

hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*) hamming
     where merge (x:xs) (y:ys)
            | x < y = x : xs `merge` (y:ys)
            | x > y = y : (x:xs) `merge` ys
            | otherwise = x : xs `merge` ys
 
main = do
    print $ take 20 hamming
    print $ hamming !! 1690
    print $ hamming !! 1000000

(There's also a good enough Python version in that page).

Bye,
bearophile
Dec 20 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
This is a great example that I don't have the time to look into now. In 
essence the task is to generate all numbers of the form 2^^a*3^^b*5^^c 
where a, b, and c are natural numbers.

Currently Phobos doesn't have the means to compute the cross-product of 
ranges. I encourage people to think about implementing that.

Andrei

bearophile wrote:
 You can try translating this in efficient, readable and short D2 code using
Phobos2 (the purpose is to find spots where Phobos2 may need improvements):
 http://rosettacode.org/wiki/Hamming_numbers#Haskell
 
 Haskell version:
 
 hamming = 1 : map (2*) hamming `merge` map (3*) hamming `merge` map (5*)
hamming
      where merge (x:xs) (y:ys)
             | x < y = x : xs `merge` (y:ys)
             | x > y = y : (x:xs) `merge` ys
             | otherwise = x : xs `merge` ys
  
 main = do
     print $ take 20 hamming
     print $ hamming !! 1690
     print $ hamming !! 1000000
 
 (There's also a good enough Python version in that page).
 
 Bye,
 bearophile

Dec 21 2009
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:
 This is a great example that I don't have the time to look into now.

It's a nice example, and I know you don't have a lot of time to implement it now.
 Currently Phobos doesn't have the means to compute the cross-product of 
 ranges.

The idea is to have standard means in Phobos to implement that kind delayed access to the lazily generated sequence. I have already shown this topic here: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=103682 Partially related: in the meantime someone has implemented my idea of vectorized lazyness, it's called "Chunked Sequences" in Clojure 1.1: http://www.infoq.com/news/2009/12/clojure-11-rc1-transients More (don't save this, click on it): http://clojure.googlegroups.com/web/chunks.pdf Despite your good intelligence Phobos2 will need some tuning and refinement, they are far from being battle-tested :-) "Small" examples like those two ones may help. Bye, bearophile
Dec 21 2009
prev sibling next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Philippe Sigaud (philippe.sigaud gmail.com)'s article
 --0016e6db29968796e0047b5716c2
 Content-Type: text/plain; charset=ISO-8859-1
 On Mon, Dec 21, 2009 at 23:44, Andrei Alexandrescu <
 SeeWebsiteForEmail erdani.org> wrote:
 This is a great example that I don't have the time to look into now. In
 essence the task is to generate all numbers of the form 2^^a*3^^b*5^^c where
 a, b, and c are natural numbers.

 Currently Phobos doesn't have the means to compute the cross-product of
 ranges. I encourage people to think about implementing that.

 Andrei

http://www.dsource.org/projects/dranges If some people are interested, I'd be delighted to have some feedback. The docs for the algorithm module is here: http://svn.dsource.org/projects/dranges/trunk/docs/algorithm2.html There is a cross-product for ranges (returning tuples), called combinations. As in, auto c = combinations(r1, r2, r3, r4); // Takes a variadic number of ranges. I put a Hamming numbers example in the docs, for the merge function.
From the docs :

// see http://en.wikipedia.org/wiki/Regular_number // Dijkstra's algorithm heavily uses merge. T[] hamming(T)(T[] r) { return 1 ~ *merge2*(map!"2*a"(r),*merge2*(map!"3*a"(r),map!"5*a"(r))); } auto hammingNumbers = iterate!hamming([1UL][]); // develops the Hamming sequence at each iteration. // 1,2,3,4,5,6,8,9,10,12,... // For the i-th iteration, the sequence is complete up to 2^i, // but has much more numbers already calculated. So I kind of cheat there: it's not Haskell's elegant self-recursive definition, but it's very near Dijkstra's algorithm and can be made a one-liner, if that's really a criteria... At each front call, iterate extends the sequence. merge2 is greedy and works only for two ranges (hence it's name), but I have a templated, predicate-aliased, lazy, n-ranges version called merge in the module. Philippe

The work you've done looks excellent and will probably get noticed a lot more in a few months when development of Phobos gets put back on the front burner. I apologize for the relative silence on what looks to be lots of very useful, well-documented code, but the core D people are currently in a mad dash to tie up all the loose ends of the core language ahead of Andrei's book. Phobos and libraries in general haven't been on the front burner since last spring.
Dec 22 2009
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Philippe Sigaud:
 merge2 is greedy and works only for two ranges (hence it's name), but I have
 a templated, predicate-aliased, lazy, n-ranges version called merge in the
 module.

This is how merge is implemented in the heapq module of the Python standard lib: def merge(*iterables): h = [] for itnum, it in enumerate(map(iter, iterables)): try: next = it.next h.append([next(), itnum, next]) except StopIteration: pass heapify(h) while True: try: while True: v, itnum, next = s = h[0] # raises IndexError when h is empty yield v s[0] = next() # raises StopIteration when exhausted heapreplace(h, s) # restore heap condition except StopIteration: heappop(h) # remove empty iterator except IndexError: return Bye, bearophile
Dec 22 2009
prev sibling next sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e6db29968796e0047b5716c2
Content-Type: text/plain; charset=ISO-8859-1

On Mon, Dec 21, 2009 at 23:44, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 This is a great example that I don't have the time to look into now. In
 essence the task is to generate all numbers of the form 2^^a*3^^b*5^^c where
 a, b, and c are natural numbers.

 Currently Phobos doesn't have the means to compute the cross-product of
 ranges. I encourage people to think about implementing that.

 Andrei

I posted yesterday on D.announce that I have some code related to that: http://www.dsource.org/projects/dranges If some people are interested, I'd be delighted to have some feedback. The docs for the algorithm module is here: http://svn.dsource.org/projects/dranges/trunk/docs/algorithm2.html There is a cross-product for ranges (returning tuples), called combinations. As in, auto c = combinations(r1, r2, r3, r4); // Takes a variadic number of ranges. I put a Hamming numbers example in the docs, for the merge function.
From the docs :

// Calculating Hamming numbers, numbers of the form 2^i * 3^j * 5^k // see http://en.wikipedia.org/wiki/Regular_number // Dijkstra's algorithm heavily uses merge. T[] hamming(T)(T[] r) { return 1 ~ *merge2*(map!"2*a"(r),*merge2*(map!"3*a"(r),map!"5*a"(r))); } auto hammingNumbers = iterate!hamming([1UL][]); // develops the Hamming sequence at each iteration. // 1,2,3,4,5,6,8,9,10,12,... // For the i-th iteration, the sequence is complete up to 2^i, // but has much more numbers already calculated. So I kind of cheat there: it's not Haskell's elegant self-recursive definition, but it's very near Dijkstra's algorithm and can be made a one-liner, if that's really a criteria... At each front call, iterate extends the sequence. merge2 is greedy and works only for two ranges (hence it's name), but I have a templated, predicate-aliased, lazy, n-ranges version called merge in the module. Philippe --0016e6db29968796e0047b5716c2 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br><div class=3D"gmail_quote">On Mon, Dec 21, 2009 at 23:44, Andrei Al= exandrescu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdan= i.org">SeeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote c= lass=3D"gmail_quote" style=3D"border-left: 1px solid rgb(204, 204, 204); ma= rgin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> This is a great example that I don&#39;t have the time to look into now. In= essence the task is to generate all numbers of the form 2^^a*3^^b*5^^c whe= re a, b, and c are natural numbers.<br> <br> Currently Phobos doesn&#39;t have the means to compute the cross-product of= ranges. I encourage people to think about implementing that.<br><font colo= r=3D"#888888"> <br> Andrei</font></blockquote><div><br>I posted yesterday on D.announce that I = have some code related to that:<br><br><a href=3D"http://www.dsource.org/pr= ojects/dranges">http://www.dsource.org/projects/dranges</a><br><br>If some = people are interested, I&#39;d be delighted to have some feedback. The docs= for the algorithm module is here:<br> <br><a href=3D"http://svn.dsource.org/projects/dranges/trunk/docs/algorithm= 2.html">http://svn.dsource.org/projects/dranges/trunk/docs/algorithm2.html<= /a><br><br>There is a cross-product for ranges (returning tuples), called c= ombinations. As in, <br> <br>auto c =3D combinations(r1, r2, r3, r4); // Takes a variadic number of = ranges. <br><br><br>I put a Hamming numbers example in the docs, for the me= rge function.<br>From the docs :<br><br><pre class=3D"d_code"><font color= =3D"green">// Calculating Hamming numbers, numbers of the form 2^i * 3^j * = 5^k<br> </font><font color=3D"green">// see <a href=3D"http://en.wikipedia.org/wiki= /Regular_number">http://en.wikipedia.org/wiki/Regular_number</a><br></font>= <font color=3D"green">// Dijkstra&#39;s algorithm heavily uses merge.<br></= font>T[] hamming(T)(T[] r)<br> {<br> <font color=3D"blue">return</font> 1 ~ <u>merge2</u>(map!<font col= or=3D"red">&quot;2*a&quot;</font>(r),<u>merge2</u>(map!<font color=3D"red">= &quot;3*a&quot;</font>(r),map!<font color=3D"red">&quot;5*a&quot;</font>(r)= ));<br> }<br><br><font color=3D"blue">auto</font> hammingNumbers =3D iterate!hammi= ng([1UL][]); <font color=3D"green">// develops the Hamming sequence at each= iteration.</font><br><font color=3D"green">// 1,2,3,4,5,6,8,9,10,12,...<br=
</font><font color=3D"green">// For the i-th iteration, the sequence is co=

</font><font color=3D"green">// but has much more numbers already calculate= d.<br><br></font></pre>So I kind of cheat there: it&#39;s not Haskell&#39;s= elegant self-recursive definition, but it&#39;s very near Dijkstra&#39;s a= lgorithm and can be made a one-liner, if that&#39;s really a criteria... At= each front call, iterate extends the sequence.<br> <br>merge2 is greedy and works only for two ranges (hence it&#39;s name), b= ut I have a templated, predicate-aliased, lazy, n-ranges version called mer= ge in the module.<br><br>=A0=A0 Philippe<br><br></div></div> --0016e6db29968796e0047b5716c2--
Dec 22 2009
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e6d99acec45c6c047b65976e
Content-Type: text/plain; charset=ISO-8859-1

On Tue, Dec 22, 2009 at 23:25, dsimcha <dsimcha yahoo.com> wrote:

The work you've done looks excellent and will probably get noticed a lot
 more in a
 few months when development of Phobos gets put back on the front burner.  I
 apologize for the relative silence on what looks to be lots of very useful,
 well-documented code, but the core D people are currently in a mad dash to
 tie up
 all the loose ends of the core language ahead of Andrei's book.  Phobos and
 libraries in general haven't been on the front burner since last spring.

Uh, David, no need for any apologies! And thanks for the kind words. I very well know that now is a hectic and wonderful time for D. Kudos to all of you for the wonderful work! It's just that now that I've understood how to put things on dsource (my difficulties, not dsource), I can talk about it on the NG... I'll stop now, for fear of derailing the thread. Philippe --0016e6d99acec45c6c047b65976e Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <br><br> <div class=3D"gmail_quote">On Tue, Dec 22, 2009 at 23:25, dsimcha <span dir= =3D"ltr">&lt;<a href=3D"mailto:dsimcha yahoo.com">dsimcha yahoo.com</a>&gt;= </span> wrote:<br><br> <blockquote style=3D"BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex= ; PADDING-LEFT: 1ex" class=3D"gmail_quote">The work you&#39;ve done looks e= xcellent and will probably get noticed a lot more in a<br>few months when d= evelopment of Phobos gets put back on the front burner. =A0I<br> apologize for the relative silence on what looks to be lots of very useful,= <br>well-documented code, but the core D people are currently in a mad dash= to tie up<br>all the loose ends of the core language ahead of Andrei&#39;s= book. =A0Phobos and<br> libraries in general haven&#39;t been on the front burner since last spring= .</blockquote> <div>=A0</div> <div>Uh, David, no need for any apologies! And thanks for the kind words. I= very well know that now is a hectic and wonderful time for D. Kudos to all= of you for the wonderful work! </div> <div>It&#39;s just that now that I&#39;ve understood how to put things on d= source (my difficulties, not dsource), I can talk about it on the NG...</di= v> <div>=A0</div> <div>I&#39;ll stop now, for fear of derailing the thread.</div> <div>=A0</div> <div>=A0Philippe</div> <div>=A0</div></div><br> --0016e6d99acec45c6c047b65976e--
Dec 23 2009
prev sibling next sibling parent Sean Kelly <sean invisibleduck.org> writes:
downs Wrote:

 Or are there any bugs/optimization opportunities I'm missing?
 
 void qsort(T)(T[] array) {
   if (array.length < 2) return;
   static int i;
   auto pivot = array[i++%$];
   // from is base-0, to is base-1.
   int from = 0, to = array.length;
   while (from != to) {
     if (array[from] >= pivot && array[to-1] < pivot)
       swap(array[from], array[to-1]);
     if (array[from] < pivot)
       from ++;
     if (array[to-1] >= pivot)
       to --;
   }
   array[0 .. from].qsort();
   array[from .. $].qsort();
 }

It could be better. I have a quicksort implementation that could probably beat it, but I haven't compared the two yet. The existing one is a lot simpler though.
Dec 20 2009
prev sibling parent BCS <none anon.com> writes:
Hello downs,

 Or are there any bugs/optimization opportunities I'm missing?
 
 void qsort(T)(T[] array) {
 if (array.length < 2) return;
 static int i;
 auto pivot = array[i++%$];
 // from is base-0, to is base-1.
 int from = 0, to = array.length;
 while (from != to) {
 if (array[from] >= pivot && array[to-1] < pivot)
 swap(array[from], array[to-1]);
 if (array[from] < pivot)
 from ++;
 if (array[to-1] >= pivot)
 to --;
 }
 array[0 .. from].qsort();
 array[from .. $].qsort();
 }

The last 2 ifs get repeated for every loop even when you can know they don't need to be. It would take more code but you could get around that.
Dec 20 2009