I'm not asking for an answer to the question, but rather how I, on my own, could have gotten the answer.

Original Question:

Does the following code cause Python to make a new list of size (len(nums) - 1) in memory that then gets iterated over?

for item in nums[1:]:
   # do stuff with item

Original Answer

A similarish question is asked here and there is a subcomment by Srinivas Reddy Thatiparthy saying that a new sublist is created. But, there is no detail given about how he arrived at this answer, which I think makes it very different from what I'm looking for.

Question:

How could I have figured out on my own what the answer to my question is?

I've had similar questions before. For instance, I learned that if I do my_function(nums[1:]), I don't pass in a "slice" but rather a completely new, different sublist! I found this out by just testing whether the original list passed into my_function was modified post-function (it wasn't). But I don't see an immediate way to figure out if Python is making a new sublist for the for loop example. Please help me to know how to do this.

side note

By the way, this is the current solution I'm using from the original stackoverflow post solutions:

for indx, item in enumerate(nums):
    if indx == 0:
       continue 
    # do stuff w items 

CodePudding user response：

In general, the easy way to learn if you have a new chunk of data or just a new reference to an existing chunk of data is to modify the data through one reference, and then see if it is also modified through the other. (It sounds like that's "the hard way" you did, but I would recommend it as a general technique.) Some psuedocode would look like:

function areSameRef(thing1, thing2){
    thing1.modify()
    return thing1.equals(thing2) //make sure this is not just a referential equality check
}

It is very rare that this will fail, and essentially requires behind-the-scenes optimizations where data isn't cloned immediately but only when modified. In this case the fact that the underlying data is the same is being hidden from you, and in most cases, you should just trust that whoever did the hiding knows what they're doing. Exceptions are if they did it wrong, or if you have some complex performance issues. For that you may need to turn to more language-specific debugging or profiling tools. (See below for more)

Do also be careful about cases where part of the data may be shared - for instance, look up cons lists and tail sharing. In those cases if you do something like:

function foo(list1, list2){
   list1.append(someElement)
   return list1.length == list2.length
}

will return false - the element is only added to the first list, but something like

function bar(list1, list2){
    list1.set(someIndex, someElement)
    return list1.get(someIndex)==list2.get(someIndex)
}

will return true (though in practice, lists created that way usually don't have an interface that allows mutability.)

I don't see a question in part 2, but yes, your conclusion looks valid to me.

EDIT: More on actual memory usage

As you pointed out, there are situations where that sort of test won't work because you don't actually have two references, as in the for i in [nums 1:] case. In that case I would say turn to a profiler, but you couldn't really trust the results.

The reason for that comes down to how compilers/interpreters work, and the contract they fulfill in the language specification. The general rule is that the interpreter is allowed to re-arrange and modify the execution of your code in any way that does not change the results, but may change the memory or time performance. So, if the state of your code and all the I/O are the same, it should not be possible for foo(5) to return 6 in one interpreter implementation/execution and 7 in another, but it is valid for them to take very different amounts of time and memory.

This matters because a lot of what interpreters and compilers do is behind-the-scenes optimizations; they will try to make your code run as fast as possible and with as small a memory footprint as possible, so long as the results are the same. However, it can only do so when it can prove that the changes will not modify the results.

This means that if you write a simple test case, the interpreter may optimize it behind the scenes to minimize the memory usage and give you one result - "no new list is created." But, if you try to trust that result in real code, the real code may be too complex for the compiler to tell if the optimization is safe, and it may fail. It can also depend upon the specific interpreter version, environmental variables or available hardware resources.

Here's an example:

def foo(x : int):
    l = range(9999)
    return 5

def bar(x:int):
    l = range(9999)
    if (x   1 != (x*2 2)/2):
      return l[x]
    else:
      return 5

I can't promise this for any particular language, but I would usually expect foo and bar to have much different memory usages. In foo, any moderately-well-created interpreter should be able to tell that l is never referenced before it goes out of scope, and thus can freely skip actually allocating any memory at all as a safe operation. In bar (unless I failed at arithmetic), l will never be used either - but knowing that requires some reasoning about the condition of the if statement. It takes a much smarter interpreter to recognize that, so even though these two code snippets might look the same logically, they can have very different behind-the-scenes performances.

EDIT: As has been pointed out to my, Python specifically may not be able to optimize either of these, given the dynamic nature of the language; the range function and the list type may both have been re-assigned or altered from elsewhere in the code. Without specific expertise in the python optimization world I can't say what they do or don't do. Anyway I'm leaving this here for edification on the general concept of optimizations, but take my error as a case lesson in "reasoning about optimization is hard".

All of that being said: FWIW, I strongly suspect that the python interpreter is smart enough to recognize that for i in nums[1:] should not actually allocate new memory, but just iterate over a slice. That looks to my eyes to be a relatively simple, safe and valuable transformation on a very common use case, so I would expect the (highly optimized) python interpreter to handle it.

EDIT2: As a final (opinionated) note, I'm less confident about that in Python than I am in almost any other language, because Python syntax is so flexible and allows so many strange things. This makes it much more difficult for the python interpreter (or a human, for that matter) to say anything with confidence, because the space of "legal python code" is so large. This is a big part of why I prefer much stricter languages like Rust, which force the programmer to color inside the lines but result in much more predictable behaviors.

EDIT3: As a post-final note, usually for things like this it's best to trust that the execution environment is handling these sorts of low-level optimizations. Nine times out of ten, don't try to solve this kind of performance problem until something actually breaks.

CodePudding user response：

As for knowing how list slice works, from the language reference Sequence Types — list, tuple, range, we know that

s[i:j] - The slice of s from i to j is defined as the sequence of items with index k such that i <= k < j.

So, the slice creates a new sequence but we don't know whether that sequence is a list or whether there is some clever way that the same list object somehow represents both of these sequences. That's not too surprising with the python language spec where lists are described as part of the general discussion of sequences and the spec never really tries to cover all of the details for object implementation.

That's because in the end, something like nums[1:] is really just syntactic sugar for nums.__getitem__(slice(1, None)), meaning that lists get to decide for themselves what slicing means. And you need to go to the source for the implementation. See the list_subscript function in listobject.c.

But we can experiment. Looking at the doucmentation for The for statement,

for_stmt ::= "for" target_list "in" starred_list ":" suite ["else" ":" suite] The starred_list expression is evaluated once; it should yield an iterable object.

So, nums[1:] is an expression that must yield an iterable object and we can assign that object to an intermediate variable.

nums = [1 ,2, 3]
tmp = nums[1:]
for item in tmp:
    pass

tmp[0] = "new stuff"

assert id(nums) != id(tmp), "List slice creates a new object"
assert type(tmp) == type(nums), "List slice creates a new list"
assert 999 not in nums, "List slice doesn't affect original"

Run that, and if neither assertion error is raised, you know that a new list was created.

Other sequence-like objects may work radically different. In a numpy array, for instance, two array objects may indeed reference the same memory. In this example, that final assert will be raised because the slice is another view into the same array. Yes, this can keep you up all night.

import numpy as np

nums = np.array([1,2,3])
tmp = nums[1:]
for item in tmp:
    pass

tmp[0] = 999

assert id(nums) != id(tmp), "array slice creates a new object"
assert type(tmp) == type(nums), "array slice creates a new list"
assert 999 not in nums, "array slice doesn't affect original"

CodePudding user response：

You can use the new Walrus operator := to capture the temporary object created by Python for the slice. A little investigation demonstrates that they aren't the same object.

import sys
print(sys.version)

a = list(range(1000))
for i in (b := a[1:]):
    b[0] = 906
print(b is a)
print(a[:10])
print(b[:10])
print(sys.getsizeof(a))
print(sys.getsizeof(b))

Generates the following output:

3.11.0 (main, Nov  4 2022, 00:14:47) [GCC 7.5.0]
False
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[906, 2, 3, 4, 5, 6, 7, 8, 9, 10]
8056
8048

See for yourself on the Godbolt Compiler Explorer where you can also see the compiler generated code.