passing a list pointer to a function rather than the list

Question

Is it possible to pass a (moving) pointer to a list start into a function in Python?

I have a recursive function working on a section of a list. The list itself is not changed, only the pointer to a 'starting-point' into it. The problem I ran into was that long lists killed the code with memory overrun.

Here is the code:

def trim(l):
    print("list len= ", len(l))
    if len(l)!= 1:
        trim(l[1:])
    else:
        print("done")

The above example is contrived, my actual code does different stuff than just trimming the list, but it also has a moving start-pointer. A list of 1 million integers blew out of memory on a 10G RAM machine.

Any ideas are welcome.

Python doesn't have pointers. You can try passing around indices instead of a slice, which creates copies. You can also consider using `numpy` which provides object-oriented primitive arrays where slicing creates views, not copies. There is also the built-in `array` module, which provides space efficient primitive arrays of sized numerical types. Both of these array approaches should provide orders of magnitude space saving. A million 64bit ints is about 8 megabytes — juanpa.arrivillaga, Oct 12 '17 at 16:08
You may find the [`deque`](https://docs.python.org/3.6/library/collections.html#collections.deque) data structure useful. Instead of passing a slice (which is a shallow copy of all elements), you can use `l.popleft()` to remove an element from the head of the deque. This doesn't incur the copying cost of `l.pop(0)` when `l` is a list. — trent, Oct 12 '17 at 16:37

Joe · Answer 1 · 2017-10-12T16:14:53.903

If you're writing a non-tail-call recursive function to iterate over a list, your problem is more likely to be a stack overflow, or out-of-memory error related to the stack size.

I recommend re-writing this with an integer pointer and a for-loop, as it seems that Python doesn't have tail-call optimisation.

Here's a guess at what you might be wanting to do:

x = [0,0,0,0,0,1,2,3,4]

def trim_leading_zero(l):
  the_len = len(l)
  start_i = 0
  for i in xrange(the_len):
    if l[i] != 0:
      return l[i:]

>>> trim_leading_zero(x)
[1, 2, 3, 4]

It's not clear from your code what it's meant to actually do. If you're trying to actually return a sequence, then you may want to look at Generators, which don't require holding an entire sequence in memory.

score 2 · Accepted Answer · answered Oct 12 '17 at 16:09

Couldn't you just pass the index instead of passing the whole new list?

So you would call trim(l, 0) and then check the index against the length of the list, and then call trim(l, 1) if needed.

def trim(l, idx):
    print("list len = ", (len(l) - idx))
    if idx < (len(x) - 1):
        trim(l, idx + 1)
    else:
        print("done")

score 0 · Answer 3 · answered Oct 12 '17 at 16:44

When dealing with large data, use generators instead of regular iterators.

def trim(l):
    print("list len= ", len(l))
    pointer = 0
    if len(l)!= 1:
        yield l[pointer:]
        pointer += 1
    else:
        print("done")

x = [1, 2, 3, 4, 5, 6, 7, 8, 9]

for i in trim(x):
    print i

# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Generators will yield one item at a time and let you do whatever you need with it, avoiding create the whole list first before processing. If you want to get a list out of it, you can simply do list(trim(x)).

There are great explanations of yield and generators here - What does the yield keyword do

passing a list pointer to a function rather than the list

3 Answers3