多維數組就地混洗

Question

我想在Cython中實現一個NaN安全的混洗過程，該過程可以沿任意維度的多維矩陣的多個軸進行混洗。

在一維矩陣的簡單情況，可以簡單地打亂了非NaN的所有指數值使用費雪耶茨算法：

def shuffle1D(np.ndarray[double, ndim=1] x): 
    cdef np.ndarray[long, ndim=1] idx = np.where(~np.isnan(x))[0] 
    cdef unsigned int i,j,n,m 

    randint = np.random.randint 
    for i in xrange(len(idx)-1, 0, -1): 
     j = randint(i+1) 
     n,m = idx[i], idx[j] 
     x[n], x[m] = x[m], x[n] 

我想延長這種算法來處理大型多維沒有重塑的數組（這觸發了更復雜的情況下副本，這裏不考慮）。爲此，我需要擺脫固定的輸入維度，這在Cython中似乎既不可能用numpy數組也不可能。有沒有解決方法？

非常感謝提前！

Answer 1

由於@Veedrac的這個回答使用了更多的用Cython能力的意見。

• 一個指針數組存儲的值的沿着axis
• 你的算法被用於具有修飾that checks for nan values，防止被分類
• 它不會爲C有序陣列創建一個副本它們的存儲器地址。在Fortran有序陣列的情況下，ravel()命令將返回副本。這可以通過建立雙指針的另一個數組攜帶的x值，可能與一些cache代價得到改善...

此代碼是幅度至少一個數量級比基於切片的其他快。

from libc.stdlib cimport malloc, free 

cimport numpy as np 
import numpy as np 
from numpy.random import randint 

cdef extern from "numpy/npy_math.h": 
    bint npy_isnan(double x) 

def shuffleND(x, int axis=-1): 
    cdef np.ndarray[double, ndim=1] v # view of x 
    cdef np.ndarray[int, ndim=1] strides 
    cdef int i, j 
    cdef int num_axis, pos, stride 
    cdef double tmp 
    cdef double **v_axis 

    if axis==-1: 
     axis = x.ndim-1 

    shape = list(x.shape) 
    num_axis = shape.pop(axis) 

    v_axis = <double **>malloc(num_axis*sizeof(double *)) 
    for i in range(num_axis): 
     v_axis[i] = <double *>malloc(1*sizeof(double)) 

    try: 
     tmp_strides = [s//x.itemsize for s in x.strides] 
     stride = tmp_strides.pop(axis) 
     strides = np.array(tmp_strides, dtype=np.int32) 
     v = x.ravel() 
     for indices in np.ndindex(*shape): 
      pos = (strides*indices).sum() 
      for i in range(num_axis): 
       v_axis[i] = &v[pos + i*stride] 
      for i in range(num_axis-1, 0, -1): 
       j = randint(i+1) 
       if npy_isnan(v_axis[i][0]) or npy_isnan(v_axis[j][0]): 
        continue 
       tmp = v_axis[i][0] 
       v_axis[i][0] = v_axis[j][0] 
       v_axis[j][0] = tmp 
    finally: 
     free(v_axis) 

    return x 

Answer 2

以下算法基於切片，不進行任何複製，它應該適用於任何np.ndarray。其主要步驟是：

• np.ndindex()用於throught不同的多維指數運行，排除了一個屬於你想洗牌
• 已經按您的1-d的情況下制定的洗牌軸應用。

代碼：

def shuffleND(np.ndarray x, axis=-1): 
    cdef np.ndarray[long long, ndim=1] idx 
    cdef unsigned int i, j, n, m 
    if axis==-1: 
     axis = x.ndim-1 
    all_shape = list(np.shape(x)) 
    shape = all_shape[:] 
    shape.pop(axis) 
    for slices in np.ndindex(*shape): 
     slices = list(slices) 
     axis_slice = slices[:] 
     axis_slice.insert(axis, slice(None)) 
     idx = np.where(~np.isnan(x[tuple(axis_slice)]))[0] 
     for i in range(idx.shape[0]-1, 0, -1): 
      j = randint(i+1) 
      n, m = idx[i], idx[j] 
      slice1 = slices[:] 
      slice1.insert(axis, n) 
      slice2 = slices[:] 
      slice2.insert(axis, m) 
      slice1 = tuple(slice1) 
      slice2 = tuple(slice2) 
      x[slice1], x[slice2] = x[slice2], x[slice1] 
    return x