Сортировать пустой массив на месте, используя порядок из второго массива - PullRequest
Новая
       7

Сортировать пустой массив на месте, используя порядок из второго массива

0 голосов
/ 21 октября 2018

Пусть два ndarrays: A формы (n, *m) и B формы (n, ).Есть ли способ сортировки A на месте с использованием порядка сортировки B?

Сортировка A с B проста с использованием np.argsort, но это не делается на месте: 

A = A[np.argsort(B)]

Комментарии:

  • A и Bимеют разные dtypes, и A может иметь более двух измерений.Следовательно, их нельзя штабелировать для использования ndarray.sort().
  • A занимает много места, поэтому его нужно отсортировать на месте.Следовательно, любое решение, требующее вдвое больше места, занимаемого A, может нанести ущерб этой цели.
  • Название этого вопроса « Переупорядочение массива numpy на месте » может показаться связанным, но вопросСам не очень понятно, и ответы не соответствуют моему вопросу.

Ответы [ 2 ]

0 голосов
/ 21 октября 2018

Вот решение, которое работает, следуя циклам в массиве индекса.При желании его можно скомпилировать, используя pythran, что дает значительное ускорение, если строки маленькие (80x для 10 элементов), и небольшое ускорение, если строки большие (30% для 1000 элементов).

Чтобы обеспечить его совместимость с pythran, у меня былонемного упростить его, поэтому он принимает только двумерные массивы и сортирует только по оси 0.

Код: 

import numpy as np

#pythran export take_inplace(float[:, :] or int[:, :], int[:])

def take_inplace(a, idx):
    n, m = a.shape
    been_there = np.zeros(n, bool)
    keep = np.empty(m, a.dtype)
    for i in range(n):
        if been_there[i]:
            continue
        keep[:] = a[i]
        been_there[i] = True
        j = i
        k = idx[i]
        while not been_there[k]:
            a[j] = a[k]
            been_there[k] = True
            j = k
            k = idx[k]
        a[j] = keep

Пример запуска с использованием скомпилированной версии.Как указано выше, компиляция требуется только для небольших строк, для больших строк чистый python должен быть достаточно быстрым. 

>>> from timeit import timeit
>>> import numpy as np
>>> import take_inplace
>>> 
>>> a = np.random.random((1000, 10))
>>> idx = a[:, 4].argsort()
>>>
>>> take_inplace.take_inplace(a, idx)
>>>
# correct
>>> np.all(np.arange(1000) == a[:, 4].argsort())
True
>>>
# speed
>>> timeit(lambda: take_inplace.take_inplace(a, idx), number=1000)
0.011950935004279017
>>>
# for comparison
>>> timeit(lambda: a[idx], number=1000)
0.02985276997787878
0 голосов
/ 21 октября 2018

Если вы можете заранее установить A в виде структурированного массива , тип данных которого состоит из подмассива формы (m, ) и скаляра того же типа (например, np.int32), то выможно отсортировать на месте относительно B.Например: 

import numpy as np

B = np.array([3, 1, 2])
A = np.array([[10, 11], [20, 21], [30, 31]])

(n, m) = A.shape

dt = np.dtype([('a', np.int32, (m, )), ('b', int)])
A2 = np.array([(a, b) for a, b in zip(A, B)], dtype=dt)

A2.sort(order='b')
print A2
...