www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - iterating through a range, operating on last few elements at a time

reply "Laeeth Isharc" <laeethnospam nospamlaeeth.com> writes:
I have a range that is an array of structs.  I would like to 
iterate through the range, calling a function with the prior k 
items in the range up to that point and storing the result of the 
function in a new range/array.

what's the best way to do this?  for low fixed k I could use zip 
with staggered slices (s[3..$],s[2..$-1],s[1..$-2],s[0..$-3]) and 
then map.  I can't think of how to do it elegantly.

any thoughts?
Aug 13 2015
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Fri, Aug 14, 2015 at 02:42:26AM +0000, Laeeth Isharc via Digitalmars-d-learn
wrote:

 I have a range that is an array of structs.  I would like to iterate
 through the range, calling a function with the prior k items in the
 range up to that point and storing the result of the function in a new
 range/array.
 
 what's the best way to do this?  for low fixed k I could use zip with
 staggered slices (s[3..$],s[2..$-1],s[1..$-2],s[0..$-3]) and then map.
 I can't think of how to do it elegantly.
 
 any thoughts?


Maybe something like this?

	import std.algorithm;
	import std.stdio;
	import std.range;
	
	auto slidingWindow(R)(R range, int k) {
		return iota(k).map!(i => range.save.drop(i))
			      .array
		              .transposed;
	}
	
	void main() {
		auto data = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
		writeln(data.slidingWindow(3));
	}

To apply the function to each slice, just write:

	data.slidingWindow(k).map!myFunc ...

I didn't figure out how to eliminate the short slices toward the end,
but all you need to do is to somehow drop the last (k-1) elements from
the range returned by slidingWindow.


T

-- 
Today's society is one of specialization: as you grow, you learn more and more
about less and less. Eventually, you know everything about nothing.
Aug 13 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/14/2015 05:12 AM, H. S. Teoh via Digitalmars-d-learn wrote:

 On Fri, Aug 14, 2015 at 02:42:26AM +0000, Laeeth Isharc via
Digitalmars-d-learn wrote:

 I have a range that is an array of structs.  I would like to iterate
 through the range, calling a function with the prior k items in the
 range up to that point and storing the result of the function in a new
 range/array.

 what's the best way to do this?  for low fixed k I could use zip with
 staggered slices (s[3..$],s[2..$-1],s[1..$-2],s[0..$-3]) and then map.
 I can't think of how to do it elegantly.

 any thoughts?


 Maybe something like this?

 	import std.algorithm;
 	import std.stdio;
 	import std.range;
 	
 	auto slidingWindow(R)(R range, int k) {
 		return iota(k).map!(i => range.save.drop(i))
 			      .array
 		              .transposed;
 	}
 	
 	void main() {
 		auto data = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
 		writeln(data.slidingWindow(3));
 	}

 To apply the function to each slice, just write:

 	data.slidingWindow(k).map!myFunc ...

 I didn't figure out how to eliminate the short slices toward the end,


import std.algorithm;
import std.stdio;
import std.range;

auto transp(RoR)(RoR ror){
     static struct Transp{
         typeof(transposed(ror)) orig;
         alias orig this;
          property bool empty(){
             return orig.tupleof[0].any!(a=>a.empty);
         }
     }
     return Transp(transposed(ror));
}

auto slidingWindow(R)(R range, int k) {
     return iota(k).map!(i => range.save.drop(i)).array.transp;
}

void main() {
     auto data = iota(1,11).array;
     writeln(data.slidingWindow(3));
}

:o)



 but all you need to do is to somehow drop the last (k-1) elements from
 the range returned by slidingWindow.
Aug 14 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 08/14/2015 03:26 PM, Timon Gehr wrote:

 On 08/14/2015 05:12 AM, H. S. Teoh via Digitalmars-d-learn wrote:

 ...

 I didn't figure out how to eliminate the short slices toward the end,


 ...

 :o)
 ...


Less hacky and less efficient:

auto slidingWindow(R)(R range, int k) {
     return iota(k).map!(i=>range.save.drop(i))
         .array.transposed.zip(range.save.drop(k-1)).map!(a=>a[0]);
}
Aug 14 2015
parent "Laeeth Isharc" <spamnolaeeth nospamlaeeth.com> writes:
On Friday, 14 August 2015 at 13:32:57 UTC, Timon Gehr wrote:

 On 08/14/2015 03:26 PM, Timon Gehr wrote:

 On 08/14/2015 05:12 AM, H. S. Teoh via Digitalmars-d-learn 
 wrote:

 ...

 I didn't figure out how to eliminate the short slices toward 
 the end,


 ...

 :o)
 ...


 Less hacky and less efficient:

 auto slidingWindow(R)(R range, int k) {
     return iota(k).map!(i=>range.save.drop(i))
         
 .array.transposed.zip(range.save.drop(k-1)).map!(a=>a[0]);
 }


Thanks v much HS and Timon.


Laeeth.
Aug 14 2015