CODEWITHSUNDEEP
pythonlistrecursion
Gert Gottschalk
Gert Gottschalk

Reputation: 1716

passing a list pointer to a function rather than the list

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.

Upvotes: 0

Views: 423

Answers (3)

Chen A.
Chen A.

Reputation: 11328

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

Upvotes: 0

Joe
Joe

Reputation: 47659

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.

Upvotes: 2

wpercy
wpercy

Reputation: 10090

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")

Upvotes: 2

Related Questions