www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Arrays vs slices

reply bearophile <bearophileHUGS lycos.com> writes:
Once the language tells apart arrays and slices, the arrays may have a third
field that represents the capacity, and the slices may have a third field that
represents the stride (that defaults to 1).
Python slices with strides specified:

 a = range(10)
 a



 a[:]



 a[::]



 a[::1]



 a[::2]



 a[::3]



 a[::-1]



 a[::-2]



 a[::2] = [10, 20, 30, 40, 50]
 a



A simple example of stride usage, a true FFT (cmath contains functions that work on complex numbers): from cmath import exp, pi def fft(x): N = len(x) if N <= 1: return x e = fft(x[0 : : 2]) o = fft(x[1 : : 2]) return [e[k] + exp(-2j * pi / N * k) * o[k] for k in xrange(N // 2)] + \ [e[k] - exp(-2j * pi / N * k) * o[k] for k in xrange(N // 2)] t = fft([1.0] * 4 + [0.0] * 4) print t[len(t)//2 :], "\n", t[: len(t)//2] The output: [0j, (0.99999999999999989+0.41421356237309492j), 0j, (0.99999999999999967+2.4142135623730949j)] [(4+0j), (1-2.4142135623730949j), 0j, (1-0.41421356237309492j)] Bye, bearophile
Jun 09 2009
parent reply Steve Schveighoffer <schveiguy yahoo.com> writes:
On Tue, 09 Jun 2009 16:22:39 -0400, bearophile wrote:

 Once the language tells apart arrays and slices, the arrays may have a
 third field that represents the capacity, and the slices may have a
 third field that represents the stride (that defaults to 1).

No, please no! Do I really need to carry around an integer that is going to be unused 99.9% of the time (In my case, probably 100%)? I'd rather have a special type that has a stride. But, the capacity field is good. I would imagine that is a must for appendable arrays. Would be nice to specify an allocation strategy for arrays too, so we can avoid some of the issues being discussed about the GC allocating gigabytes for a 40MB array. -Steve
Jun 10 2009
parent reply bearophile <bearophileHUGS lycos.com> writes:
Steve Schveighoffer:
 No, please no!  Do I really need to carry around an integer that is going 
 to be unused 99.9% of the time (In my case, probably 100%)?  I'd rather 
 have a special type that has a stride.

Strides aren't essential, but once in a while they are useful, I use them now and then in Python. How can you tell that you don't need them so strongly? But I agree that passing 3-structs is slower than 2-structs (having a "slice with stride" type in some standard library can be enough).
 Would be nice to specify an allocation strategy for 
 arrays too, so we can avoid some of the issues being discussed about the 
 GC allocating gigabytes for a 40MB array.

Just fixing the bug and putting there a sensible default seems more than enough to me. Variable allocation strategies are fine for library-defined arrays, but built-ins are better kept simple and flexible and efficient. Bye, bearophile
Jun 11 2009
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
bearophile Wrote:

 Steve Schveighoffer:
 No, please no!  Do I really need to carry around an integer that is going 
 to be unused 99.9% of the time (In my case, probably 100%)?  I'd rather 
 have a special type that has a stride.

Strides aren't essential, but once in a while they are useful, I use them now and then in Python. How can you tell that you don't need them so strongly?

The only time I use a "stride" is when I know I need a stride. That is, carrying the stride around with the slice is only useful if the code using it doesn't know it needs to be strided, and just lets the object tell it what values it needs. But if you know you want every other element, it's not that hard to construct a for-loop that does what you want. That method seems far more appealing to me and probably performs better. Especially in the 99% of cases you want to use a stride of 1, there is no runtime check. The cases where I want to use a function that operates on an array but stride the input (the only use case I see for stride to be builtin to an array) are non-existent in my code. -Steve
Jun 11 2009