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
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)


[snip]

Brilliant.
Dec 20 2009
parent reply 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)


 [snip]
 
 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
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)


 [snip]

 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)


 [snip]

 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)


 [snip]

 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)


 [snip]

 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)


 [snip]

 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.


 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.


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.


 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.


 
 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 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
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 parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
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
Dec 22 2009
next sibling parent reply 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


 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



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
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
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
Dec 23 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:

                yield v


        except StopIteration:

        except IndexError:
            return


Bye,
bearophile
Dec 22 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