www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - range chunks

reply Adrian Matoga <epi atari8.info> writes:
Hi,

Is there any off the shelf solution for iterating over a range by 
chunks? Example:

int[] arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
int i;
foreach (chunk; chunks(arr, 3))
{
	assert(chunk == arr[i * 3 .. min(i * 3 + 3, arr.length)]);
}

(should substitute [1, 2, 3], [4, 5, 6], [7, 8, 9], [10] for chunk in 
subsequent iterations)

Regards,
Adrian Matoga
Aug 05 2010
next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
2010/8/6 Adrian Matoga <epi atari8.info>

 Hi,

 Is there any off the shelf solution for iterating over a range by chunks?
None that I know of. (should substitute [1, 2, 3], [4, 5, 6], [7, 8, 9], [10] for chunk in
 subsequent iterations)
As a data point, why do you think it should produce [10] and not stop at [7,8,9]? Here is what I cooked, it's still a bit rough around the edges. It has an optional step argument, to see how many elements to jump. import std.range; struct Chunks(R) if (isInputRange!R) { R range; size_t n; // chunk size size_t step; // how many elements to jump bool empty() property { return range.empty;} ElementType!R[] front() property { return array(take(range, n));} // inefficient if you call front() many times in a row void popFront() property { popFrontN(range, step);} static if (hasLength!R) size_t length() property { return (range.length+step-1)/step;} } Chunks!R chunks(R)(R range, size_t n) if (isInputRange!R) { return Chunks!R(range, n, n); // default is step == n } Chunks!R chunks(R)(R range, size_t n, size_t step) if (isInputRange!R) { return Chunks!R(range, n, step); } Philippe
Aug 06 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Philippe Sigaud:
 Here is what I cooked, it's still a bit rough around the edges. It has an
 optional step argument, to see how many elements to jump.
It's better to give it a default chunk size of 2. If I have understood this well, then this is the partition() function: http://reference.wolfram.com/mathematica/ref/Partition.html If you want to be more complete you can add two more features: to start counting items from the end (but they are given from the start) and give a "duplication window", so for example the natural numbers with a window of 2 and a duplication of 1 are [1, 2], [2, 3], [3, 4]. But adding too many features risks to produce functions like the Mathematica ones, that sometimes are hard to use because they have tons of complex arguments.) Bye, bearophile
Aug 06 2010
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Aug 6, 2010 at 19:41, bearophile <bearophileHUGS lycos.com> wrote:

 Philippe Sigaud:
 Here is what I cooked, it's still a bit rough around the edges. It has an
 optional step argument, to see how many elements to jump.
It's better to give it a default chunk size of 2.
Why? And what should the default step be, according to you? If chose n (the chunk size), because that's want the OP wanted. If I have understood this well, then this is the partition() function:
 http://reference.wolfram.com/mathematica/ref/Partition.html
Yeah, partition, chunk, segment, it a basic thing, worth including in std.range. Very useful in conjunction with mapping: calculating the moving average, for example.
 If you want to be more complete you can add two more features: to start
 counting items from the end (but they are given from the start) and give a
 "duplication window", so for example the natural numbers with a window of 2
 and a duplication of 1 are [1, 2], [2, 3], [3, 4].
This simple code does this already: chunks(range, 2, 1).
Aug 06 2010
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 06 Aug 2010 13:33:09 -0400, Philippe Sigaud  
<philippe.sigaud gmail.com> wrote:

 Here is what I cooked, it's still a bit rough around the edges. It has an
 optional step argument, to see how many elements to jump.
[snip]
     ElementType!R[] front()  property { return array(take(range, n));} //
efficient D code, avoid the heap when you can :) -Steve
Aug 06 2010
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Aug 6, 2010 at 19:48, Steven Schveighoffer <schveiguy yahoo.com>wrote:

 On Fri, 06 Aug 2010 13:33:09 -0400, Philippe Sigaud <
 philippe.sigaud gmail.com> wrote:

  Here is what I cooked, it's still a bit rough around the edges. It has an
 optional step argument, to see how many elements to jump.
[snip] ElementType!R[] front() property { return array(take(range, n));} //


 efficient D code, avoid the heap when you can :)
Hmm, good idea. And that way, if n is big, you get a lazy range. But you lose the random access and such. I guess the user will call map!array() if she wants to get arrays? Intially, I had a cache, but I ran into problems to initiate it correctly and told myself "Hey, it's a 10' function, don't sweat it, post it already, if that may help." Maybe the type produced could be decided by a policy: lazy, dynamic array... In a version I use, the n arg is a template arg and the range returns tuples. If found that easier to deal with: from a tuple, you can easily create and array (static, or dynamic), if you want to. And I can easily use it as a function argument list... Philippe
Aug 06 2010
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 06 Aug 2010 14:59:17 -0400, Philippe Sigaud  
<philippe.sigaud gmail.com> wrote:

 On Fri, Aug 6, 2010 at 19:48, Steven Schveighoffer  
 <schveiguy yahoo.com>wrote:

 On Fri, 06 Aug 2010 13:33:09 -0400, Philippe Sigaud <
 philippe.sigaud gmail.com> wrote:

  Here is what I cooked, it's still a bit rough around the edges. It has  
 an
 optional step argument, to see how many elements to jump.
[snip] ElementType!R[] front() property { return array(take(range, n));} //


 efficient D code, avoid the heap when you can :)
Hmm, good idea. And that way, if n is big, you get a lazy range. But you lose the random access and such. I guess the user will call map!array() if she wants to get arrays?
Doesn't take return a random-access range if the original is a random access range? I would actually expect take(range, n) to return range[0..n] if range supports that. -Steve
Aug 06 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Steven Schveighoffer wrote:
 On Fri, 06 Aug 2010 14:59:17 -0400, Philippe Sigaud 
 <philippe.sigaud gmail.com> wrote:
 
 On Fri, Aug 6, 2010 at 19:48, Steven Schveighoffer 
 <schveiguy yahoo.com>wrote:

 On Fri, 06 Aug 2010 13:33:09 -0400, Philippe Sigaud <
 philippe.sigaud gmail.com> wrote:

  Here is what I cooked, it's still a bit rough around the edges. It 
 has an
 optional step argument, to see how many elements to jump.
[snip] ElementType!R[] front() property { return array(take(range, n));} //


 efficient D code, avoid the heap when you can :)
Hmm, good idea. And that way, if n is big, you get a lazy range. But you lose the random access and such. I guess the user will call map!array() if she wants to get arrays?
Doesn't take return a random-access range if the original is a random access range? I would actually expect take(range, n) to return range[0..n] if range supports that.
It does since recently. Andrei
Aug 06 2010
parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Aug 6, 2010 at 22:11, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 Steven Schveighoffer wrote:

 Doesn't take return a random-access range if the original is a random
 access range?

 I would actually expect take(range, n) to return range[0..n] if range
 supports that.
It does since recently.
Damn. Uh, I mean, cool! I did not integrate this. Then everything is for the best. Philippe
Aug 06 2010
prev sibling parent Adrian Matoga <epi atari8.info> writes:
On 2010-08-06 19:33, Philippe Sigaud wrote:
 2010/8/6 Adrian Matoga <epi atari8.info <mailto:epi atari8.info>>
 
     Hi,
 
     Is there any off the shelf solution for iterating over a range by
     chunks?
 
 
 None that I know of.
 
     (should substitute [1, 2, 3], [4, 5, 6], [7, 8, 9], [10] for chunk
     in subsequent iterations)
 
 
 As a data point, why do you think it should produce [10] and not stop at 
 [7,8,9]?
By an analogy to taking a file by chunks. The other case also occured to me but I simply thought I could imagine more situations in which I need the whole input range to be exhausted, including remainder.
 Here is what I cooked, it's still a bit rough around the edges. It has 
 an optional step argument, to see how many elements to jump.
 
 import std.range;
 struct Chunks(R) if (isInputRange!R)
 {
     R range;
     size_t n; // chunk size
     size_t step; // how many elements to jump
 
     bool empty()  property { return range.empty;}
     ElementType!R[] front()  property { return array(take(range, n));} 
 // inefficient if you call front() many times in a row
     void popFront()  property { popFrontN(range, step);}
 
     static if (hasLength!R)
         size_t length()  property { return (range.length+step-1)/step;}
 }
 
 Chunks!R chunks(R)(R range, size_t n) if (isInputRange!R)
 {
     return Chunks!R(range, n, n); // default is step == n
 }
 
 Chunks!R chunks(R)(R range, size_t n, size_t step) if (isInputRange!R)
 {
     return Chunks!R(range, n, step);
 }
  
 
Thank you very much! And yes, I also think it should be included in std.range (actually before posting the question I was almost sure I could find it there ;)). Adrian
Aug 06 2010
prev sibling parent 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