What is the fastest way to access elements in a nested list?

Question

I have a list which is made up out of three layers, looking something like this for illustrative purposes:

a = [[['1'],['2'],['3'],['']],[['5'],['21','33']]]

Thus I have a top list which contains several other lists each of which again contains lists.

The first layer will contain in the tens of lists. The next layer could contain possibly millions of lists and the bottom layer will contain either an empty string, a single string, or a handful of values (each a string).

I now need to access the values in the bottom-most layer and store them in a new list in a particular order which is done inside a loop. What is the fastest way of accessing these values? The amount of memory used is not of primary concern to me (though I obviously don't want to squander it either).

I can think of two ways:

1. I access list a directly to retrieve the desired value, e.g. a[1][1][0] would return '21'.
2. I create a copy of the elements of a and then access these to flatten the list a bit more. In this case thus, e.g.: b=a[0], c=a[1] so instead of accessing a[1][1][0] I would now access b[1][0] to retrieve '21'.

Is there any performance penalty involved in accessing nested lists? Thus, is there any benefit to be gained in splitting list a it into separate lists or am I merely incurring a RAM penalty in doing so?

Answer 1

Accessing elements via their index (ie: a[1][1][0]) is a O(1) operation: source. You won't get much quicker than that.

Now, assignment is also a O(1) operation, so there's no difference between the two methods you've described as far as speed goes. The second one actually doesn't incur in any memory problems because assignments to lists are by reference, not by copy (except you explicitly tell it to do it otherwise).