• bearophile <bearophileHUGS lycos.com> Jun 09 2009
• Steve Schveighoffer <schveiguy yahoo.com> Jun 10 2009
• bearophile <bearophileHUGS lycos.com> Jun 11 2009
• Steven Schveighoffer <schveiguy yahoo.com> Jun 11 2009

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

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

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

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