Перестановка матрицы на месте в NumPy

27

Я хочу изменить плотную квадратную матрицу перехода на месте, изменив порядок нескольких ее строк и столбцов, используя библиотеку NumPy Python. Математически это соответствует предварительному умножению матрицы на матрицу перестановок P и последующему умножению ее на P ^ -1 = P ^ T, но это не является разумным в вычислительном отношении решением.

Прямо сейчас я меняю строки и столбцы вручную, но я ожидал, что у numpy будет хорошая функция f (M, v), где M имеет n строк и столбцов, а v имеет n записей, так что f (M, v) обновляет M в соответствии с перестановкой индекса v. Может быть, я просто не могу найти в Интернете.

Нечто подобное может быть возможно с «продвинутой индексацией» numpy, но, насколько я понимаю, такого решения не будет. Также для некоторых простых ситуаций может быть достаточно просто отдельно отслеживать перестановку индекса, но это не удобно в моем случае.

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

Добавлено:
Матрица достаточно мала, чтобы поместиться в оперативной памяти, но достаточно большой, чтобы я не хотел копировать ее бездумно. На самом деле я хотел бы использовать матрицы как можно большего размера, но я не хочу иметь дело с неудобством невозможности удерживать их в ОЗУ, и я выполняю O (N ^ 3) операций LAPACK над матрицей, что также ограничить практический размер матрицы. В настоящее время я копирую такие большие матрицы без необходимости, но я надеюсь, что этого легко избежать при перестановке.

никто
источник
3
Было бы хорошо, если бы вы могли обновить вопрос, чтобы указать размер ваших матриц. «Гигантский» не означает одно и то же для всех людей.
Билл Барт,
2
Вы правы, что расширенная (или так называемая причудливая) индексация создает копию. Но если вы согласны жить с этим фактом, тогда ваш код просто M[v]переставляет строки.
Даниэль Велков
@daniel: И это будет M [v,:] [:, v], чтобы сделать всю перестановку? Это был бы лучший способ получить перестановку, используя причудливую индексацию? И будет ли он использовать 3х матричную память, включая размер исходной матрицы, матрицу перестановок строки + столбца и матрицу перестановки временной строки?
нет
Это верно, у вас будет оригинальная матрица и 2 копии. Кстати, зачем вам нужно переставлять строки и столбцы одновременно?
Даниэль Велков
4
Что вы собираетесь делать с переставленной матрицей? Может быть лучше просто переставить вектор при применении оператора.
Джед Браун

Ответы:

9

Согласно документации, в numpy нет метода перестановки на месте, что-то вроде ndarray.sort .

Таким образом, ваши варианты (при условии, что Mэто матрица и вектор перестановки)N×Np

  1. реализовать свой собственный алгоритм в C как модуль расширения (но алгоритмы на месте трудны, по крайней мере для меня!)
  2. накладных расходов памятиN

    for i in range(N):
        M[:,i] = M[p,i]
    for i in range(N):
        M[i,:] = M[i,p]
  3. накладные расходы памятиN2

    M[:,:] = M[p,:]
    M[:,:] = M[:,p]

Надеюсь, что эти неоптимальные хаки полезны.

Стефано М
источник
@ нет, это взлом 2. что вы называете «ручная замена строк и столбцов»?
Стефано М
1
Я хотел бы объединить варианты 1 и 2: написать код C, который использует буфер порядка N для записи каждого переставленного столбца, а затем записывает его туда, откуда он пришел; затем сделайте то же самое для строк. Как пишет @Stefano, для этого требуется только дополнительной памяти, которую вы уже тратите, чтобы сохранить перестановку p в первую очередь. O(N)п
Эрик П.
О(N)О(N)
2
Это действительно хороший вариант для функции Cython. Не должно быть более 10 строк. , , хотите, чтобы я дал ему трещину?
Meawoppl
Смешно. Я начал это на Cython, затем нашел правильный ответ в функции, которую я использую все время. Doh. Смотрите мой опубликованный ответ.
meawoppl
6

Предупреждение: приведенный ниже пример работает правильно, но использование полного набора параметров, предложенных в конце статьи, приводит к ошибке или, по крайней мере, «недокументированной возможности» в функции numpy.take (). Смотрите комментарии ниже для деталей. Отчет об ошибке подан .

Вы можете сделать это на месте с помощью функции take () numpy , но это требует небольшого количества прыжков.

Вот пример выполнения случайной перестановки строк единичной матрицы:

import numpy as np
i = np.identity(10)
rr = range(10)
np.random.shuffle(rr)
np.take(i, rr, axis=0)
array([[ 0.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  0.,  0.],
       [ 1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.]])

Чтобы сделать это на месте, все, что вам нужно сделать, это указать параметр "out", который будет таким же, как входной массив, и вы должны установить mode = "clip" или mode = "wrap". Если вы не установите режим, он сделает копию для восстановления состояния массива в исключении Python (см. Здесь) .

В заключение отметим, что take является методом массива, поэтому вместо

np.take(i, rr, axis=0)

ты можешь позвонить

i.take(rr, axis=0)

если это больше на ваш вкус. Таким образом, в целом ваш звонок должен выглядеть примерно так:

#Inplace Rearrange
arr = makeMyBixMatrix()
pVec0, pVec1 = calcMyPermutationVectors()
arr.take(pVec0, axis=0, out=arr, mode="clip")
arr.take(pVec1, axis=1, out=arr, mode="clip")

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

meawoppl
источник
Как сказано, алгоритмы на месте сложны. Ваше решение не работает с NumPy 1.6.2. и 1.7.1 (повторяющиеся строки / столбцы). У меня не было времени проверить, исправляет ли 1.8.x эту проблему
Stefano M
Хммм. Можете ли вы опубликовать тестовый код где-нибудь? В моей голове я чувствую, что должна быть операция сортировки по индексам, которая происходит сначала перед выщипыванием. Я буду исследовать больше этого ПМ.
meawoppl
1
Когда я запускаю этот код я получаю 1.6.2, test take, not overwriting: True, test not-in-place take: True, test in-place take: False, rr [3, 7, 8, 1, 4, 5, 9, 0, 2, 6], arr [30 70 80 70 40 50 90 30 80 90], ref [30 70 80 10 40 50 90 0 20 60]. Так что, np.takeпо крайней мере, для numpy 1.6.2 не известно о необходимости перестановки на месте и все портится.
Стефано М
Yeouch. Хорошо продемонстрировано. Это, вероятно, квалифицируется как ошибка ИМХО. По крайней мере, в документах должно быть сказано, что вход и выход не могут быть одним и тем же массивом, возможно, проверьте, чтобы увидеть, и если это не так.
Meawoppl
Договорились об ошибке: возможно, вам следует добавить примечание к вашему сообщению, чтобы предупредить читателей о том, что ваше решение может дать неправильные результаты.
Стефано М
2

Если у вас есть разреженная матрица, сохраненная в COOформате, может быть полезно следующее

    A.row = perm[A.row];
    A.col = perm[A.col];

ACOOpermnumpy.arraymm

Винсент Трааг
источник
но каковы накладные расходы памяти для хранения полной плотной матрицы в качестве разреженной C00матрицы в первую очередь?
Федерико Полони
intfloatfloatn2numpy.ndarray
1

У меня недостаточно репутации, чтобы комментировать, но я думаю, что следующий вопрос SO может быть полезным: /programming/4370745/view-onto-a-numpy-array

Основные моменты , которые вы можете использовать основные нарезки и создадут представление о к массиву без копирования, но если вы делаете передовые нарезки / индексацию , то это будет создавать копию.

hadsed
источник
OP запрашивает перестановку, а это невозможно при базовом разрезании.
Стефано М
Вы правы конечно. Я подумал, что для ОП было бы полезно понять, что происходит с нарезкой (в случае, если они не знали), так как они были обеспокоены тем, когда будут происходить копии. Если бы он использовал что-то из вашего ответа, я думаю, это было бы полезно узнать, поскольку вы используете их внутри своих циклов.
пропал
-1

Как насчет

my_array [:, [0, 1]] = my_array [:, [1, 0]]

johnsankey
источник
1
Это создает временный, который именно то, что он хочет избежать.
Майкл Грант