How to iterate an array in Python pointer-likely and efficiently?

Question

I am quite new in Python, I would like to iterate an array to calculate the next element based on the previous elements. I can just think of this in C++ manner but how to achieve this in Python using Numpy or Pandas? I know that the similar method is using shifting but that way seems not really efficient.

The following is a simple Fibonacci example:

int arr[10];
arr[0] = 1;
arr[1] = 1;

int* pt = &arr[2];         <--get a iterator like a moving pointer
int count = 8;
while (count > 0)
{
    *pt = pt[-1] + pt[-2]; <--access previous k element based on current index
    count--;
    pt++;                  <--point to next element
}
for (int i = 0; i < 10; i++)
    cout << arr[i] << endl;

List:

L = [1, 1]
while len(L) != 10:
    L.append(L[-1] + L[-2]) <--But I have to append element every time
print L

Do you know how to create a list in Python? You can append to it using its `append` method and get the last two elements as `l[-1]` and `l[-2]`. — Ry-, Jul 18 '15 at 02:59
Do you need fast insertion? That is, do you specifically need a linked list structure? Or is a dynamic array (contiguous memory) acceptable? If you are primarily iterating rather than inserting (or all your insertions are at the end), then Python's builtin list object would be the way to go. — Michael Aaron Safyan, Jul 18 '15 at 03:03
You can preallocate the underlying array: `L = 10 * [0]; L[0] = L[1] = 1` — michaelmeyer, Jul 18 '15 at 03:06
Lots of Python options in this SO, including your list based one. None use pointers though: http://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence-in-python — hpaulj, Jul 18 '15 at 04:18

hpaulj · Accepted Answer · 2015-07-18T05:10:27.483

The direct numpy immitation of your C++ is

arr=np.ones((10,))
for i in range(2,arr.shape[0]):
     arr[i]=arr[i-1]+arr[i-2]

producing:

array([  1.,   1.,   2.,   3.,   5.,   8.,  13.,  21.,  34.,  55.])

This probably isn't the most efficient way of doing this in numpy, but it's discussion start.

Most fast numpy operations use compiled c code, and the results are buffered, so it is tricky to perform fast sequential operations. It is best to think of numpy operations acting in parallel, on all terms of an array at once (without preference for any order). Exceptions are ufunc cumsum and cumprod - cumulative processes, and an unbuffered ufunc called at. I'd have to play around to see if there's a way of calculating this series with one of these tools.

Another option is to implement the calculation in C or C++ and link it. cython is the most convenient tool for doing this.

http://wiki.scipy.org/Cookbook/Ctypes#head-6a582bd7b101bca0df6e5631a06e2d1d76e35a95 is an example of using ctypes and c code with numpy to calculate Fibonachi.

http://numpy-discussion.10968.n7.nabble.com/vectorizing-recursive-sequences-td35532.html describes a cleaver way of calculating this series. It depends on the ufunc taking an out array. The author admits that it also depends on implementation details, especially that the calculation is not buffered.

arr=np.ones((10,))
np.add(arr[:-2], arr[1:-1], out=arr[2:])

The elements of the 1st 2 arguments are added, element by element, and stored in the out array.

arr[2:] = arr[:-2]+arr[1:-1]

does not work because of buffering

http://docs.cython.org/src/tutorial/cython_tutorial.html#fibonacci-fun

is a Cython example of fibonacci. It should be fast, but it just prints the results, as opposed to accumulating them in an array. Still it shouldn't be hard to do Cython/c version that stores the results in a cython array or memoryview.

Here's a cython script, that can be saved as a pyx, compiled and imported. It could be refined to usefulness and speed, but it's enough to test the concept:

import numpy as np
narr = np.ones((10,), dtype=np.dtype("i"))
cdef int [:] narr_view = narr

cpdef void fib(int[:] arr):
    I = arr.shape[0]
    for i in range(2,I):
        arr[i] = arr[i-2]+arr[i-1]
fib(narr_view)
print 'fib arr:', narr

Thank you very much! That's exactly what I want to know. – James Jul 18 '15 at 03:40 — James, Jul 18 '15 at 03:40

How to iterate an array in Python pointer-likely and efficiently?

1 Answers1