## digitalmars.D - Re: range chunks

bearophile <bearophileHUGS lycos.com> writes:
```Philippe Sigaud:
It's better to give it a default chunk size of 2.

Why?

I'm using partition() for years in various languages, and I've seen that the
chunks of size 2 are the most common.

And what should the default step be, according to you? If chose n (the chunk
size), because that's want the OP wanted.

No duplication across chunks, so on default it can split the natural numbers as:
[1, 2], [3, 4], [5, 6], etc.

Yeah, partition, chunk, segment, it a basic thing, worth including in
std.range.

The most common name is partition().

Bye,
bearophile
```
Aug 06 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 08/06/2010 06:52 PM, bearophile wrote:
Philippe Sigaud:
It's better to give it a default chunk size of 2.

Why?

I'm using partition() for years in various languages, and I've seen that the
chunks of size 2 are the most common.

And what should the default step be, according to you? If chose n (the chunk
size), because that's want the OP wanted.

No duplication across chunks, so on default it can split the natural numbers
as:
[1, 2], [3, 4], [5, 6], etc.

Yeah, partition, chunk, segment, it a basic thing, worth including in
std.range.

The most common name is partition().

When I see "partition" I think it's quicksort's partition algorithm...

Andrei
```
Aug 06 2010
Peter Alexander <peter.alexander.au gmail.com> writes:
```On 7/08/10 2:51 AM, Andrei Alexandrescu wrote:
On 08/06/2010 06:52 PM, bearophile wrote:
Philippe Sigaud:
Yeah, partition, chunk, segment, it a basic thing, worth including in
std.range.

The most common name is partition().

When I see "partition" I think it's quicksort's partition algorithm...

Andrei

Yeah, partition has always meant that to me as well.

I'd call that "chunking" algorithm "divide" because it is dividing the
range into equal parts.
```
Aug 06 2010
bearophile <bearophileHUGS lycos.com> writes:
```Peter Alexander:
Yeah, partition has always meant that to me as well.

Probably you come from a quite different part of computer science (The example
I have shown from Mathematica is not the only one).
What are the usages of that algorithm, beside being used in the QuickSort?

Bye,
bearophile
```
Aug 06 2010
Peter Alexander <peter.alexander.au gmail.com> writes:
```On 7/08/10 7:57 AM, bearophile wrote:
Peter Alexander:
Yeah, partition has always meant that to me as well.

Probably you come from a quite different part of computer science (The example
I have shown from Mathematica is not the only one).
What are the usages of that algorithm, beside being used in the QuickSort?

It's used a fair amount in geometry. I know the Kirkpatrick-Seidel
algorithm uses it and I've seen some Delaunay triangulation
implementations use it. I'm pretty sure there's other geometrical
applications for it as well.

Outside of specific algorithms, I think partition is quite a neglected
algorithm, because people typically just use sort, even when partition
would be more suitable. For example, consider some distribution service
that distributes some product to premium customers first, followed by
regular customers. Really, that's a job for partition, but in practice
your average Joe coder would just sort based on the same predicate,
wasting a factor of O(lg(n)). Either that or they'd just iterate over
the sequence twice: once for premium, and a second time for regular.

I think the main argument for calling it that is because it is called
that by almost all computer science literature. Do a Google search for
quick sort pseudocode. Almost invariably you'll find that they'll define
a helper function called partition, so programmers have come to learn
that that's what partition does.

(I just Googled for "quicksort pseudocode" and sure enough, all of the
top 10 entries that actually contained code defined a partition function
that does what std.algorithm.partition does).
```
Aug 07 2010
bearophile <bearophileHUGS lycos.com> writes:
```Peter Alexander:
It's used a fair amount in geometry. I know the Kirkpatrick-Seidel
algorithm uses it and I've seen some Delaunay triangulation
implementations use it. I'm pretty sure there's other geometrical
applications for it as well.

(I just Googled for "quicksort pseudocode" and sure enough, all of the
top 10 entries that actually contained code defined a partition function
that does what std.algorithm.partition does).

Yes, it's named partition in my implementations of Quicksort too :-) So it's
better to find a different name for the other one.

Bye,
bearophile
```
Aug 07 2010
Peter Alexander <peter.alexander.au gmail.com> writes:
```On 7/08/10 3:06 PM, bearophile wrote:
Peter Alexander:
(I just Googled for "quicksort pseudocode" and sure enough, all of the
top 10 entries that actually contained code defined a partition function
that does what std.algorithm.partition does).

Yes, it's named partition in my implementations of Quicksort too :-) So it's
better to find a different name for the other one.

e.g. kPartitions([1,2,3,4,5,6], 3) == [[1,2,3], [4,5,6]]

A k-partition is common terminology for partitioning a set into
k-element subsets, so that seems to fit, and isn't too verbose.
```
Aug 07 2010
Rory Mcguire <rjmcguire gm_no_ail.com> writes:
```Peter Alexander wrote:

On 7/08/10 3:06 PM, bearophile wrote:
Peter Alexander:
(I just Googled for "quicksort pseudocode" and sure enough, all of the
top 10 entries that actually contained code defined a partition function
that does what std.algorithm.partition does).

Yes, it's named partition in my implementations of Quicksort too :-) So
it's better to find a different name for the other one.

e.g. kPartitions([1,2,3,4,5,6], 3) == [[1,2,3], [4,5,6]]

A k-partition is common terminology for partitioning a set into
k-element subsets, so that seems to fit, and isn't too verbose.

std.range.tochunks([1,2,3,4,5,6],3) == [[1,2,3],[4,5,6]]
```
Aug 18 2010
Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
```On 08/07/2010 01:57 AM, bearophile wrote:
Peter Alexander:
Yeah, partition has always meant that to me as well.

Probably you come from a quite different part of computer science (The example
I have shown from Mathematica is not the only one).
What are the usages of that algorithm, beside being used in the QuickSort?

http://en.wikipedia.org/wiki/Selection_algorithm for example.

Andrei
```
Aug 07 2010
KennyTM~ <kennytm gmail.com> writes:
```On Aug 7, 10 07:52, bearophile wrote:
Philippe Sigaud:
It's better to give it a default chunk size of 2.

Why?

I'm using partition() for years in various languages, and I've seen that the
chunks of size 2 are the most common.

And what should the default step be, according to you? If chose n (the chunk
size), because that's want the OP wanted.

No duplication across chunks, so on default it can split the natural numbers
as:
[1, 2], [3, 4], [5, 6], etc.

Yeah, partition, chunk, segment, it a basic thing, worth including in
std.range.

The most common name is partition().

In D, 'partition' is already used for rearranging (splitting) a range
into two according to a predicate*. (It's the same in C++, Haskell and
Ruby.) Since the name is already taken, it's very bad to break the
compatibility to change what the function does even if the name were
more common.

Also, in Python this function called grouper() (in itertool's
"Recipes"), and in Ruby it's called each_slice. I've never seen it
called Partition[] besides Mathematica.

*: http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html#partition

Bye,
bearophile

```
Aug 07 2010
bearophile <bearophileHUGS lycos.com> writes:
```KennyTM~:
I've never seen it called Partition[] besides Mathematica.

As alternative do you like "chunker"?

Bye,
bearophile
```
Aug 07 2010
KennyTM~ <kennytm gmail.com> writes:
```On Aug 7, 10 20:11, bearophile wrote:
KennyTM~:
I've never seen it called Partition[] besides Mathematica.

As alternative do you like "chunker"?

Bye,
bearophile

I prefer 'chunks', but that conflicts with std.stdio.chunks. It can be
resolved by generalizing std.stdio.chunks to std.range.chunks and making
File a range that iterates ubyte, but this doesn't seem to be the
natural choice.
```
Aug 07 2010