www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Re: range chunks

reply 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
next sibling parent reply 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
parent reply 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
parent reply 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
next sibling parent reply 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
parent reply 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.



Thank you for your explanations.



 (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
parent reply 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.



Hmm, how about kPartitions?

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



 Hmm, how about kPartitions?
 
 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.




how about

std.range.tochunks([1,2,3,4,5,6],3) == [[1,2,3],[4,5,6]]
Aug 18 2010
prev sibling parent 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
prev sibling parent reply 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
parent reply 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
parent 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