Python Multidimensional Array as a single List

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 loo开发者_如何学Ckup 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?

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)

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)

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.

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))