Быстрый 2-мерный массив (матрица) в Python без расширений C - PullRequest
Новая
       14

Быстрый 2-мерный массив (матрица) в Python без расширений C

4 голосов
/ 29 февраля 2012

Мне нужно написать плагин для приложения, которое можно расширять с помощью Python 2.7. Он должен выполнять довольно сложный динамический алгоритм, который работает с матрицей целых чисел.

Установка Python по умолчанию, поставляемая с этим приложением, не включает в себя числовую библиотеку, такую ​​как numpy, поэтому, к сожалению, я должен реализовать это, используя только Python stdlib.

Я попробовал несколько разных подходов для представления матрицы в памяти: 

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

Диктовый подход существует только для полноты, на самом деле он не очень полезен, потому что к каждому элементу обращаются.

Судя по моим измерениям, последний из них кажется самым быстрым для сборки и доступа. Тем не менее, я удивлен, что нет встроенной функциональности матрицы. Из того, что я узнал о Python до сих пор, если вы не найдете какой-либо очевидной функциональности в stdlib, наиболее вероятной причиной является то, что вы не выглядели достаточно усердно.

Так что мне интересно, можно ли еще оптимизировать это, например, с помощью модуля array или какой-либо другой функции, о которой я не знаю.

Ответы [ 2 ]

2 голосов
/ 29 февраля 2012

Модуль array может быть быстрее, когда матрица становится большой, потому что она может упаковать значения более компактно;может использоваться с соглашением values[j*width + i].Но нет, в стандартной библиотеке Python нет многомерного массива, возможно потому, что (a) Numpy уже эффективно заполняет эту нишу и (b) вы всегда можете составить список списков, если производительность не имеет первостепенного значения.

Самый быстрыйВариант действительно зависит от алгоритма.Подход, основанный на dict, может быть самым быстрым, когда матрицы, с которыми вы работаете, очень редки (чего в алгоритмах DP обычно нет, по крайней мере, в тех, которые я видел).

0 голосов
/ 29 февраля 2012

Вы можете использовать словарь по умолчанию и использовать 2-кортежи в качестве индексов, либо реализовать собственный класс и реализовать методы __getitem__ и __setitem__ для работы с 2-кортежами в качестве индексов и сохранения результата в Python. массив: 

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

Или, используя defaultdict, вы можете получить лучшую производительность: 

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