CODEWITHSUNDEEP
pythonlistslice
i_am_finally_learning_python
i_am_finally_learning_python

Reputation: 187

Python list slicing efficiency

In the following code:

def listSum(alist):
    """Get sum of numbers in a list recursively."""
    sum = 0
    if len(alist) == 1:
        return alist[0]
    else:
        return alist[0] + listSum(alist[1:])
    return sum

is a new list created every time when I do listSum(alist[1:])?

If yes, is this the recommended way or can I do something more efficient? (Not for the specific function -this serves as an example-, but rather when I want to process a specific part of a list in general.)

Edit:

Sorry if I confused anyone, I am not interested in an efficient sum implementation, this served as an example to use slicing this way.

Upvotes: 16

Views: 18073

Answers (3)

marcadian
marcadian

Reputation: 2618

I can think of some options:

  1. use builtin function sum for this particular case
  2. If you really need recursion (for some reason), pass in the same list to the function call and also index of current element, so you don't need to slice the list (which creates new list)

option 2 works like this:

def f_sum(alist, idx=0):
    if idx >= len(alist):
        return 0
    return alist[idx] + f_sum(alist, idx + 1)


f_sum([1, 2, 3, 4])
a = range(5)
f_sum(a)

Upvotes: 4

Joohwan
Joohwan

Reputation: 2512

This is another way if you must use recursion (tail-recursive). In many other languages this is more efficient than regular recursions in terms of space complexity. Unfortunately this isn't the case in python because it does not have a built-in support for optimizing tail calls. It's a good practice to take note of if you are learning recursion nonetheless. 

def helper(l, s, i):
    if len(l) == 0:
        return 0
    elif i < len(l) - 1:
        return helper(l, s + l[i], i + 1) 
    else:
        return s + l[i]


def listSum(l):
    return helper(l, 0, 0)

Upvotes: -1

user395760
user395760

Reputation:

Yes, it creates a new list every time. If you can get away with using an iterable, you can use itertools.islice, or juggle iter(list) (if you only need to skip some items at the start). But this gets messy when you need to determine if the argument is empty or only has one element - you have to use try and catch StopIteration. Edit: You could also add an extra argument that determines where to start. Unlike @marcadian's version, you should make it a default argument to not burden the caller with that and avoid bugs from the wrong index being passed in from the outside.

It's often better to not get in that sort of situation - either write your code such that you can let for deal with iteration (read: don't use recursion like that). Alternatively, if the slice is reasonably small (possibly because the list as a whole is small), bite the bullet and slice anyway - it's easier, and while slicing is linear time, the constant factor is really tiny.

Upvotes: 12

Related Questions