digitalmars.D.learn - Circular Buffer
- Frustrated (7/7) Dec 20 2013 I'm in need of a circular buffer/array. I am using
- Orvid King (3/10) Dec 20 2013 There's actually already a circular buffer implemented in vibe.d, and
- Frustrated (1/1) Dec 20 2013 But does it rely on the GC?
- Orvid King (2/3) Dec 20 2013 Nope, the template you wanted is vibe.utils.array:FixedRingBuffer.
- bearophile (4/6) Dec 20 2013 Why do you need to avoid the GC?
- Timon Gehr (3/6) Dec 20 2013 What prevents you from implementing your buffer using an
- lomereiter (3/3) Dec 20 2013 Use std.range.cycle with std.container.Array (slice the array to
- Jonathan Dunlap (8/8) Feb 09 2014 (disclaimer: I'm new around here)
- Chris Cain (4/12) Feb 09 2014 Probably what you're looking for:
- Gary Willoughby (12/15) Feb 10 2014 import std.algorithm;
- Russel Winder (9/27) Feb 10 2014 This is why people should be using D instead of C++! This really needs
- bearophile (10/11) Feb 10 2014 retro+cycle is very simple code, you can also combine them:
- Russel Winder (12/24) Feb 12 2014 Tell me about it. I run training courses trying to get people to do this
- Frustrated (4/26) Feb 13 2014 how efficient is ufcs? It seems like it would be very slow in
- Artem Tarasov (6/9) Feb 13 2014 LDC and GDC are pretty darn good at inlining these UFCS chains,
- Jonathan Dunlap (14/20) Feb 10 2014 Wow! This is GREAT stuff. My use-case is slightly more complex,
- Martijn Pot (3/6) Feb 11 2014 It's not of immediate help, but it might trigger other answers.
- Andrea Fontana (5/27) Feb 11 2014 data.cycle.rotate(-2) == data.cycle(data.length + (-2 %
- Andrea Fontana (3/34) Feb 11 2014 I missed a .rotate after data.cycle, of course.
- Rene Zwanenburg (4/17) Feb 11 2014 Perhaps something like this?
- Rene Zwanenburg (5/24) Feb 11 2014 Wait, we can avoid creating that closure and eliminate the map.
- Andrea Fontana (4/29) Feb 11 2014 Why not drop and take?
- Jonathan Dunlap (4/6) Feb 11 2014 Ooo.. I like the drop and take approach! I wonder if this could
- Russel Winder (22/40) Feb 12 2014 As Gary is aware, I posted this problem to ACCU asking for a C++
- bearophile (4/12) Feb 13 2014 Take also a look at itertools.cycle.
- Russel Winder (10/11) Feb 13 2014 Indeed. I keep forgetting about itertools when rushed, which is a
- Russel Winder (22/23) Feb 13 2014 How about this:
- monarch_dodra (14/22) Feb 13 2014 We've had a discussion about this recently with Andrej Mitrovic.
- Tobias Pankrath (4/12) Feb 13 2014 I don't think it is currently possible, but it shouldn't be hard
- Tobias Pankrath (7/21) Feb 13 2014 Yep, I've missed three pages of this discussion.
- ponce (3/10) Dec 21 2013 http://p0nce.github.io/gfm/gfm.core.queue.html#RingBuffer < and
- simendsjo (7/14) Dec 21 2013 Writing your own should be quite simple. I see others have
I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? It looks like it is defined as templates so could I somehow hijack the code and modify only what is needed rather than duplicate a lot of stuff? (or maybe someone could just add it to the library... circular arrays are useful ya know ;)
Dec 20 2013
There's actually already a circular buffer implemented in vibe.d, and if I remember right it's not dependent on anything from vibe. On 12/20/13, Frustrated <c1514843 drdrb.com> wrote:I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? It looks like it is defined as templates so could I somehow hijack the code and modify only what is needed rather than duplicate a lot of stuff? (or maybe someone could just add it to the library... circular arrays are useful ya know ;)
Dec 20 2013
Orvid King <blah38621 gmail.com> On 12/20/13, Frustrated <c1514843 drdrb.com> wrote:But does it rely on the GC?Nope, the template you wanted is vibe.utils.array:FixedRingBuffer.
Dec 20 2013
Frustrated:I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC.Why do you need to avoid the GC? Bye, bearophile
Dec 20 2013
On 12/20/2013 04:45 PM, Frustrated wrote:I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? ...What prevents you from implementing your buffer using an std.container.Array as the backing store?
Dec 20 2013
Use std.range.cycle with std.container.Array (slice the array to get a range).
Dec 20 2013
(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal "takeBack" function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts?
Feb 09 2014
On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote:(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal "takeBack" function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts?Probably what you're looking for:
Feb 09 2014
On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote:(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach?import std.algorithm; import std.array; import std.range; import std.stdio; void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); }
Feb 10 2014
On Mon, 2014-02-10 at 09:16 +0000, Gary Willoughby wrote:On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote:This is why people should be using D instead of C++! This really needs to get onto the D website somewhere. -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach?import std.algorithm; import std.array; import std.range; import std.stdio; void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); }
Feb 10 2014
Russel Winder:This really needs to get onto the D website somewhere.retro+cycle is very simple code, you can also combine them: alias retroCycle = compose!(cycle, retro); Ranges and algorithms can be combined together in so many ways :-) For an imperative/OO programmer writing code based on lazy ranges and higher order functions is a new kind of programming that should be learnt patiently, but it's not hard and it doesn't contain many low-level pitfalls :-) Bye, bearophile
Feb 10 2014
On Mon, 2014-02-10 at 11:33 +0000, bearophile wrote:Russel Winder:point-free composition. We like this :-)This really needs to get onto the D website somewhere.retro+cycle is very simple code, you can also combine them: alias retroCycle = compose!(cycle, retro);Ranges and algorithms can be combined together in so many ways :-) For an imperative/OO programmer writing code based on lazy ranges and higher order functions is a new kind of programming that should be learnt patiently, but it's not hard and it doesn't contain many low-level pitfalls :-)Tell me about it. I run training courses trying to get people to do this higher-order stuff, and meta-object protocol stuff, in Python, Java and Groovy (with some Scala) and some get it and some don't. Rule 1: don't mention monads. -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Feb 12 2014
On Monday, 10 February 2014 at 10:41:06 UTC, Russel Winder wrote:On Mon, 2014-02-10 at 09:16 +0000, Gary Willoughby wrote:how efficient is ufcs? It seems like it would be very slow in general and way better to manually do the code. I wonder if anyone has done any tests?On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote:This is why people should be using D instead of C++! This really needs to get onto the D website somewhere.(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach?import std.algorithm; import std.array; import std.range; import std.stdio; void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); }
Feb 13 2014
On Thursday, 13 February 2014 at 20:56:32 UTC, Frustrated wrote:how efficient is ufcs? It seems like it would be very slow in general and way better to manually do the code. I wonder if anyone has done any tests?LDC and GDC are pretty darn good at inlining these UFCS chains, but the yielded machine code might be slightly suboptimal. In any case, you should use a profiler instead of making decisions based on some intuitive feelings which might easily be wrong. (don't underestimate the efforts put into GCC & LLVM backends!)
Feb 13 2014
Wow! This is GREAT stuff. My use-case is slightly more complex,
and I'm not sure how to best apply this knowledge. The retro
reverses the array which is problematic in itself as well as
losing the starting index location. I have an array that I'd like
to elegantly "rotate". Best way I can show this is by example of
an imaginary rotate function:
auto data = [1,2,3];
assert( data.cycle.rotate(2) == [3,1,2] );
assert( data.cycle.rotate(-2) == [2,3,1] );
Perhaps what I'm doing is too complex requires me making my own
iterator or something. In my quest of writing readable efficient
code, I'm wondering what's the best route here. Thanks :)
On Monday, 10 February 2014 at 09:16:31 UTC, Gary Willoughby
wrote:
void main(string[] args)
{
auto data = [1,2,3];
assert(data.cycle.take(5).array == [1,2,3,1,2]);
assert(data.retro.cycle.take(5).array == [3,2,1,3,2]);
}
Feb 10 2014
auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] );It's not of immediate help, but it might trigger other answers. Matlab offers this for multi-dimensional arrays: http://www.mathworks.nl/help/matlab/ref/circshift.html
Feb 11 2014
On Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote:Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly "rotate". Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :) On Monday, 10 February 2014 at 09:16:31 UTC, Gary Willoughby wrote:data.cycle.rotate(-2) == data.cycle(data.length + (-2 % data.length)) I guess you can implement your rotate function with this in mind.void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); }
Feb 11 2014
On Tuesday, 11 February 2014 at 09:10:16 UTC, Andrea Fontana wrote:On Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote:I missed a .rotate after data.cycle, of course.Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly "rotate". Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :) On Monday, 10 February 2014 at 09:16:31 UTC, Gary Willoughby wrote:data.cycle.rotate(-2) == data.cycle(data.length + (-2 % data.length)) I guess you can implement your rotate function with this in mind.void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); }
Feb 11 2014
On Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote:Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly "rotate". Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :)Perhaps something like this? http://dpaste.dzfl.pl/d4b82b0b5cba
Feb 11 2014
On Tuesday, 11 February 2014 at 16:26:06 UTC, Rene Zwanenburg wrote:On Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote:Wait, we can avoid creating that closure and eliminate the map. This should be a bit faster and not use the GC: http://dpaste.dzfl.pl/78c65eacfeb1Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly "rotate". Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :)Perhaps something like this? http://dpaste.dzfl.pl/d4b82b0b5cba
Feb 11 2014
On Tuesday, 11 February 2014 at 16:30:42 UTC, Rene Zwanenburg wrote:On Tuesday, 11 February 2014 at 16:26:06 UTC, Rene Zwanenburg wrote:Why not drop and take? http://dpaste.dzfl.pl/0649b809c81eOn Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote:Wait, we can avoid creating that closure and eliminate the map. This should be a bit faster and not use the GC: http://dpaste.dzfl.pl/78c65eacfeb1Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly "rotate". Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :)Perhaps something like this? http://dpaste.dzfl.pl/d4b82b0b5cba
Feb 11 2014
Ooo.. I like the drop and take approach! I wonder if this could be something that makes it into the standard library (std.range?). What would be the best way to approach in suggesting that?Why not drop and take? http://dpaste.dzfl.pl/0649b809c81e
Feb 11 2014
On Mon, 2014-02-10 at 09:16 +0000, Gary Willoughby wrote:On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote:As Gary is aware, I posted this problem to ACCU asking for a C++ version. I think Steve Love has had a go with an added range library not just pure C++14. I'll post when I have looked at his code, and ensured it works. He is using Catch for testing so I suspect it will. I had a quick go at doing a Python 3 version using PyTest: def provide(sourceSequence, resultLength): return (sourceSequence[i % len(sourceSequence)] for i in range(resultLength)) def provideReverse(sourceSequence, resultLength): sourceLength = len(sourceSequence) return (sourceSequence[sourceLength - 1 - i % sourceLength] for i in range(resultLength)) data = [1, 2, 3] def test_forward(): assert tuple(provide(data, 5)) == (1,2,3,1,2) def test_reverse(): assert tuple(provideReverse(data, 5)) == (3,2,1,3,2) -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach?import std.algorithm; import std.array; import std.range; import std.stdio; void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); }
Feb 12 2014
Russel Winder:
I had a quick go at doing a Python 3 version using PyTest:
def provide(sourceSequence, resultLength):
return (sourceSequence[i % len(sourceSequence)] for i in
range(resultLength))
def provideReverse(sourceSequence, resultLength):
sourceLength = len(sourceSequence)
return (sourceSequence[sourceLength - 1 - i % sourceLength]
for i in range(resultLength))
Take also a look at itertools.cycle.
Bye,
bearophile
Feb 13 2014
On Thu, 2014-02-13 at 18:03 +0000, bearophile wrote: […]Take also a look at itertools.cycle.Indeed. I keep forgetting about itertools when rushed, which is a definite error. -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Feb 13 2014
On Thu, 2014-02-13 at 18:03 +0000, bearophile wrote: […]Take also a look at itertools.cycle.How about this: from itertools import cycle, islice data = [1, 2, 3] def test_forward(): assert tuple(islice(cycle(data), 5)) == (1,2,3,1,2) def test_reverse(): assert tuple(islice(cycle(reversed(data)), 5)) == (3,2,1,3,2) -- Russel. ============================================================================= Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Feb 13 2014
On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote:(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal "takeBack" function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts?We've had a discussion about this recently with Andrej Mitrovic. The question was basically: Should Cycle (keeping in mind it is an infinite range) be bidirectional? And if yes, what should be the first last? There is fundamentally nothing preventing us from making Cycle bidirection (though maybe as opt-in CycleBidirectional, due to extra costs). We'd just need a use case, and specifications I guess. For example: auto s = cycle([1, 2, 3]); auto last = cycle.back; What's last's value? I think it should be 3. If we can agree and file an ER, it can be done.
Feb 13 2014
On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote:(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal "takeBack" function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts?I don't think it is currently possible, but it shouldn't be hard to make retro work with cycle.
Feb 13 2014
On Thursday, 13 February 2014 at 20:40:21 UTC, Tobias Pankrath wrote:On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote:Yep, I've missed three pages of this discussion. monarch_dodra I'd say a bidirectional cycle should be a consistent to the random access version, so popBack becomes essentially a index-- and back == front initially.(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal "takeBack" function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts?I don't think it is currently possible, but it shouldn't be hard to make retro work with cycle
Feb 13 2014
On Friday, 20 December 2013 at 15:45:04 UTC, Frustrated wrote:I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? It looks like it is defined as templates so could I somehow hijack the code and modify only what is needed rather than duplicate a lot of stuff? (or maybe someone could just add it to the library... circular arrays are useful ya know ;)http://p0nce.github.io/gfm/gfm.core.queue.html#RingBuffer < and use malloc instead of .length
Dec 21 2013
On Friday, 20 December 2013 at 15:45:04 UTC, Frustrated wrote:I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? It looks like it is defined as templates so could I somehow hijack the code and modify only what is needed rather than duplicate a lot of stuff? (or maybe someone could just add it to the library... circular arrays are useful ya know ;)Writing your own should be quite simple. I see others have already added some implementations, so I'll add mine too. Modifying it to use a static array shouldn't be too difficult, but you're probably better off using some of the others code as this is dynamic and haven't been used in production. https://gist.github.com/simendsjo/3b8a9c60bd92e16691d7
Dec 21 2013