Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Slicing a list in Python without generating a copy

Tags:

python

list

slice

I have the following problem.

Given a list of integers L, I need to generate all of the sublists L[k:] for k in [0, len(L) - 1], without generating copies.

How do I accomplish this in Python? With a buffer object somehow?

like image 308
Chris Avatar asked Feb 27 '11 04:02

Chris


People also ask

Does python list slicing create a copy?

No, slicing returns a list which is inside the original list. Not a copied list.

Does slicing a list create a copy?

Slicing lists does not generate copies of the objects in the list; it just copies the references to them. That is the answer to the question as asked.

Does slicing make deep copy?

slice() , Array. from() , Object. assign() , and Object. create() ) do not create deep copies (instead, they create shallow copies).

Does python list make a copy?

Copy a List. You cannot copy a list simply by typing list2 = list1 , because: list2 will only be a reference to list1 , and changes made in list1 will automatically also be made in list2 . There are ways to make a copy, one way is to use the built-in List method copy() .


2 Answers

The short answer

Slicing lists does not generate copies of the objects in the list; it just copies the references to them. That is the answer to the question as asked.

The long answer

Testing on mutable and immutable values

First, let's test the basic claim. We can show that even in the case of immutable objects like integers, only the reference is copied. Here are three different integer objects, each with the same value:

>>> a = [1000 + 1, 1000 + 1, 1000 + 1] 

They have the same value, but you can see they are three distinct objects because they have different ids:

>>> map(id, a) [140502922988976, 140502922988952, 140502922988928] 

When you slice them, the references remain the same. No new objects have been created:

>>> b = a[1:3] >>> map(id, b) [140502922988952, 140502922988928] 

Using different objects with the same value shows that the copy process doesn't bother with interning -- it just directly copies the references.

Testing with mutable values gives the same result:

>>> a = [{0: 'zero', 1: 'one'}, ['foo', 'bar']] >>> map(id, a) [4380777000, 4380712040] >>> map(id, a[1:] ... ) [4380712040] 

Examining remaining memory overhead

Of course the references themselves are copied. Each one costs 8 bytes on a 64-bit machine. And each list has its own memory overhead of 72 bytes:

>>> for i in range(len(a)): ...     x = a[:i] ...     print('len: {}'.format(len(x))) ...     print('size: {}'.format(sys.getsizeof(x))) ...  len: 0 size: 72 len: 1 size: 80 len: 2 size: 88 

As Joe Pinsonault reminds us, that overhead adds up. And integer objects themselves are not very large -- they are three times larger than references. So this saves you some memory in an absolute sense, but asymptotically, it might be nice to be able to have multiple lists that are "views" into the same memory.

Saving memory by using views

Unfortunately, Python provides no easy way to produce objects that are "views" into lists. Or perhaps I should say "fortunately"! It means you don't have to worry about where a slice comes from; changes to the original won't affect the slice. Overall, that makes reasoning about a program's behavior much easier.

If you really want to save memory by working with views, consider using numpy arrays. When you slice a numpy array, the memory is shared between the slice and the original:

>>> a = numpy.arange(3) >>> a array([0, 1, 2]) >>> b = a[1:3] >>> b array([1, 2]) 

What happens when we modify a and look again at b?

>>> a[2] = 1001 >>> b array([   1, 1001]) 

But this means you have to be sure that when you modify one object, you aren't inadvertently modifying another. That's the trade-off when you use numpy: less work for the computer, and more work for the programmer!

like image 96
senderle Avatar answered Oct 11 '22 07:10

senderle


Depending on what you're doing, you might be able to use islice.

Since it operates via iteration, it won't make new lists, but instead will simply create iterators that yield elements from the original list as requested for their ranges.

like image 26
Amber Avatar answered Oct 11 '22 07:10

Amber