Python Multidimensional Array as a single List

Question

Sure, you can have nested lists to represent multidimensional arrays, but that seems costly...

[[0, 1], [2, 3]]

Is there some way to "encode" and "decode" the coordinate into a single number, and use that number to lookup the corresponding element?

[0, 1, 2, 3]

This needs to work with n-dimensions, not just two, and the best I could come up with for encoding is:

def getcellindex(self, location):
  cindex = 0
  cdrop = self.gridsize # where self.gridsize is the number of cells
  for index in xrange(self.numdimensions): # where self.numdimensions is the number of dimensions
    # where self.dimensions is a tuple of the different sizes of the corresponding dimension
    cdrop /= self.dimensions[index]
    cindex += cdrop * location[index]
  return cindex

There're probably ways to optimize this, but more importantly, how do I reverse the process? And, does this function work?

I would use numpy, but I require it to work on 64-bit python, which doesn't seem to work for me. — skeggse, Jan 18 '11 at 22:17
Why does it seem costly? Have you tested and found it slow? A clever answer to this question might end up being slower than nested lists. — Brian Goldman, Jan 18 '11 at 22:35

Karmastan · Answer 1 · 2011-01-18T23:12:27.623

Are you avoiding the obvious answer (i.e. [[1, 2], [3, 4]]) because of concerns about its performance? If so and you're working with numberes, look at NumPy arrays. The best solution would be to not reinvent your own wheel.

Edit: If you do feel the need to do it your own way, you could follow a strided index scheme like NumPy, wihch might go something like this:

import operator
def product(lst):
    return reduce(operator.mul, lst, 1)

class MyArray(object):
    def __init__(self, shape, initval):
        self.shape = shape
        self.strides = [ product(shape[i+1:]) for i in xrange(len(shape)) ]
        self.data = [initval] * product(shape)

    def getindex(self, loc):
        return sum([ x*y for x, y in zip(self.strides, loc) ])

    def getloc(self, index):
        loc = tuple()
        for s in self.strides:
            i = index // s
            index = index % s
            loc += (i,)
        return loc

To be used as:

arr = MyArray((3, 2), 0)
arr.getindex((2, 1))
  -> 5
arr.getloc(5)
  -> (2, 1)

score 1 · Accepted Answer · answered Jan 18 '11 at 21:55

def getlocation(self, cellindex):
    res = []
    for size in reversed(self.dimensions):
        res.append(cellindex % size)
        cellindex /= size
    return res[::-1]

Or, for the full test case

class ndim:
    def __init__(self):
        self.dimensions=[8,9,10]
        self.numdimensions=3
        self.gridsize=8*9*10

    def getcellindex(self, location):
        cindex = 0
        cdrop = self.gridsize
        for index in xrange(self.numdimensions):
            cdrop /= self.dimensions[index]
            cindex += cdrop * location[index]
        return cindex

    def getlocation(self, cellindex):
        res = []
        for size in reversed(self.dimensions):
            res.append(cellindex % size)
            cellindex /= size
        return res[::-1]

n=ndim()
print n.getcellindex((0,0,0))
print n.getcellindex((0,0,1))
print n.getcellindex((0,1,0))
print n.getcellindex((1,0,0))

print n.getlocation(90)
print n.getlocation(10)
print n.getlocation(1)
print n.getlocation(0)

It appears that the "for size in reversed(self.dimensions):" should be "for size in self.dimensions" — skeggse, Jan 18 '11 at 22:20
@CMC: why that? I'm getting correct results with the code as it stands. You have to start the module operations with the least significant dimension. — Martin v. Löwis, Jan 18 '11 at 22:22
No wait...I'm wrong. Not quite sure how I though that, though. — skeggse, Jan 19 '11 at 17:00

score 0 · Answer 3 · answered Jan 18 '11 at 22:01

If you want fast arrays you may want to see numpy arrays which are pretty fast. Otherwise if you have dimensions n1, n2, n3, ...,nm, then you can encode a[i][j][k]...[r]: i * (product of (n2, n3...)) + j * (product of (n3, n4...)) + r. The reverse operation you have to get module of nm and that will be r, then you have to substract r and find module of nm*n(m-1) and so on.

primroot · Answer 4 · 2011-01-18T22:46:21.743

A well known bijection:


from itertools import tee

def _basis(dimensions):
    # compute products of subtuple entries
    return tuple(reduce(lambda x,y: x*y, dimensions[:i]) for i in xrange(1, len(dimensions)+1))

def coordinate(n, dimensions):
    basis = _basis(dimensions)
    residues = [n % b for b in basis]
    it2, it1 = tee(basis)
    for x in it2:
        break
    return (residues[0],) + tuple((m2-m1)/b in m2, m1, b in zip(it2, it1, basis))

def number(c, dimensions):
    basis = _basis(dimensions)
    return sum(x*b for x, b in zip(c, basis))

Python Multidimensional Array as a single List

4 Answers4