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

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
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.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
if p < v then return i else lscan p h (i+1)
| otherwise = return i
rscan p l i
| l < i = do
if v < p then return i else rscan p l (i-1)
| otherwise = return i
swap i j = do
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
i <- sloop piv lo hi
swap i hi
myqsort a lo (i-1)
myqsort a (i+1) hi
| otherwise = return ()
```
Dec 20 2009
Don <nospam nospam.com> writes:
```downs wrote:

I'll let this speak for itself.

Brilliant.
```
Dec 20 2009
Don <nospam nospam.com> writes:
```retard wrote:
Sun, 20 Dec 2009 16:44:03 +0100, Don wrote:

downs wrote:
according to

I'll let this speak for itself.

Brilliant.

What is so brilliant? Referential transparency is broken unless single-
(uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort
```
Dec 20 2009
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

I'll let this speak for itself.

Brilliant.

What is so brilliant? Referential transparency is broken unless single-
means (uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort

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

I'll let this speak for itself.

Brilliant.

What is so brilliant? Referential transparency is broken unless single-
means (uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort

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
=?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
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
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

I'll let this speak for itself.

Brilliant.

What is so brilliant? Referential transparency is broken unless single-
means (uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort

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

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

I'll let this speak for itself.

Brilliant.

What is so brilliant? Referential transparency is broken unless single-
means (uniqueness types comes to mind).

The brilliant bit is the idea of doing a fairer comparison of quicksort

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

to mine.

Andrei
```
Dec 22 2009
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
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

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
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
"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
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
retard <re tard.com.invalid> writes:
```Sun, 20 Dec 2009 16:44:03 +0100, Don wrote:

downs wrote:
according to

I'll let this speak for itself.

Brilliant.

What is so brilliant? Referential transparency is broken unless single-
(uniqueness types comes to mind).
```
Dec 20 2009
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
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
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
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):

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

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

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