Creating a Nested List in Python

Question

I'm trying to make a nested list in Python to contain information about points in a video, and I'm having a lot of trouble creating an array for the results to be saved in to. The structure of the list is simple: the top level is a reference to the frame, the next level is a reference to a marker, and the last level is the point of the marker. So for example, the list is setup as such:

markerList # a long list of every marker in every frame markerList[0] # every marker in the first frame markerList[0][0] # the first marker of the first frame markerList[0][0][0] # the x value of the first marker of the first frame

Calling markerList[0] looks like this:

 array([[  922.04443359,   903.        ],
   [  987.83850098,   891.38830566],
   [  843.27374268,   891.70471191],
   [  936.38446045,   873.34661865],
   [  965.52880859,   840.44445801],
   [  822.19567871,   834.06298828],
   [  903.48956299,   830.62268066],
   [  938.70031738,   825.71557617],
   [  853.09545898,   824.47247314],
   [  817.84277344,   816.05029297],
   [ 1057.91186523,   815.52935791],
   [  833.23632812,   787.48504639],
   [  924.24224854,   755.53997803],
   [  836.07800293,   720.02764893],
   [  937.83880615,   714.11199951],
   [  813.3493042 ,   720.30566406],
   [  797.09521484,   705.72729492],
   [  964.31713867,   703.246521  ],
   [  934.9864502 ,   697.27099609],
   [  815.1550293 ,   688.91473389],
   [  954.94085693,   685.88171387],
   [  797.70239258,   672.35119629],
   [  877.05749512,   659.94250488],
   [  962.24786377,   659.26495361],
   [  843.66131592,   618.83868408],
   [  901.50476074,   585.42541504],
   [  863.41851807,   584.4977417 ]], dtype=float32)

The problem is that every frame contains a different number of markers. I want to create an empty array the same length as markerList (i.e., the same number of frames) in which every element is the same size as the largest frame in markerList. Some important caveats: first,I want to save the results into a .mat file where the final array (which I'll call finalStack) is a cell of cells. Second, I need to be able to reference and assign to any specific part of finalStack. So if I want to move a point to finalStack[0][22], I need to be able to do so without conflict. This basically just means I can't use append methods anywhere, but it's also unearthed my first problem - finding a way to create finalStack that doesn't cause every new assignment to be duplicated throughout the entire parent list. I've tried to do this a few different ways, and none work correctly.

Attempts at a solution:

Following another SO question, I attempted to create finalStack iteratively, but to no avail. I created the following function:

def createFinalStack(numMarkers, numPoints, frames):
    step = [[0]*numPoints for x in xrange(numMarkers)]
    finalStack = [step]*frames
    return finalStack

However, this causes all assignments to be copied across the parent list, such that assigning finalStack[0][12] leads to finalStack[2][12] == finalStack[20][12] == finalStack[0][12]. In this example, numMarkers= 40, numPoints = 2 (just x & y), and frames= 200. (So the final array should be 200 x 40 x 2.)

That said, this seems like the most straightforward way to do what I want, I just can't get past the copy error (I know it's a reference issue, I just don't know how to avoid it in this context).

Another seemingly simple solution would be to copy markerList using copy.deepcopy(markerList), and pad any frames with less than 40 markers to get them to numMarkers = 40, and zero out anything else. But I can't come up with a good way to cycle through all of the frames, add points in the correct format, and then empty out everything else.

If this isn't enough information to work with, I can try to provide greater context and some other not-good-methods that didn't work at all. I've been stuck on this long enough that I'm convinced the solution is horribly simple, and I'm just missing the obvious. I hope you can prove me right!

Thanks!

Answer 1

This illustrates what is going on:

In [1334]: step=[[0]*3 for x in range(3)]
In [1335]: step
Out[1335]: [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
In [1336]: stack=[step]*4
In [1337]: stack
Out[1337]: 
[[[0, 0, 0], [0, 0, 0], [0, 0, 0]],
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]]]
In [1338]: stack[0]
Out[1338]: [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
In [1339]: stack[0][2]=3
In [1340]: stack
Out[1340]: 
[[[0, 0, 0], [0, 0, 0], 3],
 [[0, 0, 0], [0, 0, 0], 3],
 [[0, 0, 0], [0, 0, 0], 3],
 [[0, 0, 0], [0, 0, 0], 3]]
In [1341]: step
Out[1341]: [[0, 0, 0], [0, 0, 0], 3]

When you use alist*n to create new list, the new list contains multiple pointers to the same underlying object. As a general rule, using *n to replicate a list is dangerous if you plan on changing values later on.

If instead I make an array of the right dimensions I don't have this problem:

In [1342]: np.zeros((4,3,3),int)
Out[1342]: 
array([[[0, 0, 0],
        [0, 0, 0],
        [0, 0, 0]],

         ...
        [0, 0, 0]]])

Or in list form:

In [1343]: np.zeros((4,3,3),int).tolist()
Out[1343]: 
[[[0, 0, 0], [0, 0, 0], [0, 0, 0]],
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]]]

If I assign a value in this list, I only change one item:

In [1344]: stack=np.zeros((4,3,3),int).tolist()
In [1345]: stack[0][2]=3
In [1346]: stack
Out[1346]: 
[[[0, 0, 0], [0, 0, 0], 3],
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]],
 [[0, 0, 0], [0, 0, 0], [0, 0, 0]]]

I really should have used stack[0][2][1]=3, but you get the idea. If I make the same assignment in the array form I end up changing a whole row

In [1347]: stack=np.zeros((4,3,3),int)
In [1348]: stack[0][2]=3
In [1349]: stack
Out[1349]: 
array([[[0, 0, 0],
        [0, 0, 0],
        [3, 3, 3]],

       [[0, 0, 0],
         ...
        [0, 0, 0]]])

I should have used an expression like stack[0,2,:]=4.

It's probably possible to construct a triply next list like this where all initial values are independent. But this array approach is simpler.