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
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
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
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
C & C++
DMDScript
Steven Schveighoffer <schveiguy yahoo.com>