Fast two-dimensional array (matrix) in Python without C extensions

Question

I need to write a plugin for an application that expands with Python 2.7. It should execute a rather complicated dynamic algorithm that works on a rectangular matrix of integers.

The default Python installation that comes with this application does not include a number library such as numpy , so unfortunately I have to implement this using only Python stdlib .

I tried several different approaches for representing a matrix in memory:

 values = defaultdict(int) values = [[0 for _ in range(width)] for _ in range(height)] values = [0] * (width * height) # access like values[j*width + i] later values = [[0] * width for _ in range(height)] 

The dictation approach is used only for completeness, in fact it is not very effective, because each element is accessed.

Judging by my measurements, the last one seems to be the fastest to create and access. However, I am surprised that there is no built-in matrix functionality. From what I have learned about Python so far, if you do not find any obvious functionality in stdlib , the most likely reason is that you did not look hard enough.

So I wonder if this can be optimized even further. For example, using the array module or another function that I do not know about.

Answer 1

The array module can be faster when the matrix becomes large, because it can pack values ​​more compactly; it can be used with the values[j*width + i] convention. But no, there is no multidimensional array in the Python standard library, perhaps because (a) Numpy already fills this niche efficiently and (b) you can always make a list of lists if performance is not of primary importance.

The fastest option really depends on the algorithm. The dict based approach may be the fastest when the matrices you process are very scarce (that they are usually absent in DP algorithms, at least not in the ones I saw).

Answer 2

You can use the default dictionary and use 2-tuples as indices or implement your own class and implement the __getitem__ and __setitem__ methods to process 2 tuples as indices and save the result in a Python array:

 from array import array class Array2D(object): def __init__(self, w, h): self.data = array("f", [0] * w * h) self.width = w def __getitem__(self, index): return self.data[index[1] * self.width + index[0]] def __setitem__(self, index, value): self.data[index[1] * self.width + index[0]] = value 

Or, using the defaultdict parameter, you can get better performance:

 >>> from collections import defaultdict >>> d = defaultdict(lambda : 0) >>> d[0,0] 0 >>> d[0,0] = 2.5 >>> d[0,0] 2.5 >>> 

Answer 3

Maybe this can help:

 arr=[*map(lambda a: [a]*cols,[0]*rows)] 

this will create a 2D (row x column) matrix of zeros

[[0, 0, 0], [0, 0, 0]]