首页 文章

混淆数组中每行的非零元素--Python / NumPy

提问于
浏览 次
34

我有一个相对稀疏的数组，我想遍历每一行并只调整非零元素 .

示例输入：

[2,3,1,0]
[0,0,2,1]

示例输出：

[2,1,3,0]
[0,0,1,2]

注意零如何改变位置 .

要对每行中的所有元素（包括零）进行洗牌，我可以这样做：

for i in range(len(X)):
    np.random.shuffle(X[i, :])

我试图做的是这样的：

for i in range(len(X)):
    np.random.shuffle(X[i, np.nonzero(X[i, :])])

但它没有效果 . 我注意到 X[i, np.nonzero(X[i, :])] 的返回类型与 X[i, :] 不同，这可能是原因 .

In[30]: X[i, np.nonzero(X[i, :])]
Out[30]: array([[23,  5, 29, 11, 17]])

In[31]: X[i, :]
Out[31]: array([23,  5, 29, 11, 17])
python numpy vectorization shuffle

7 回答

  • 7

    您可以将非就地numpy.random.permutation与显式非零索引一起使用：

    >>> X = np.array([[2,3,1,0], [0,0,2,1]])
>>> for i in range(len(X)):
...     idx = np.nonzero(X[i])
...     X[i][idx] = np.random.permutation(X[i][idx])
... 
>>> X
array([[3, 2, 1, 0],
       [0, 0, 2, 1]])
    回复于
  • 3

    我想我找到了三班轮？

    i, j = np.nonzero(a.astype(bool))
k = np.argsort(i + np.random.rand(i.size))
a[i,j] = a[i,j[k]]
    回复于
  • 8

    正如所承诺的那样，这是赏金期的第四天，这是我对矢量化解决方案的尝试 . 所涉及的步骤将在下面详细说明：

    • 为了便于参考，让我们将输入数组称为 a . 每行生成唯一的索引，涵盖行长度的范围 . 为此，我们可以简单地生成与输入数组相同形状的随机数，并沿每行获取 argsort 索引，这将是那些唯一索引 . 这个想法之前已在this post中进行了探讨 .

    • 将每个索引作为列索引放入输入数组的每一行 . 因此，我们需要advanced-indexing . 现在，这给了我们一个数组，每行都被洗牌 . 我们称之为 b .

    • 由于shuffling被限制为每行，如果我们只使用boolean-indexing： b[b!=0] ，我们将得到非零元素的混洗，并且还限制为每行的非零长度 . 这是因为NumPy数组中的元素以行主顺序存储，因此使用布尔索引时，它会在移动到下一行之前先在每行上选择混洗的非零元素 . 同样，如果我们使用类似于 a 的布尔索引，即 a[a!=0] ，我们在移动到下一行之前会先在每行上获得非零元素，这些元素将按原始顺序排列 . 所以，最后一步是 grab 蒙面元素 b[b!=0] 并分配到蒙版的地方 a[a!=0] .

    因此，涵盖上述三个步骤的实施将是 -

    m,n = a.shape
rand_idx = np.random.rand(m,n).argsort(axis=1) #step1
b = a[np.arange(m)[:,None], rand_idx]          #step2  
a[a!=0] = b[b!=0]                              #step3

    逐步运行示例可能会使事情变得更加清晰 -

    In [50]: a # Input array
Out[50]: 
array([[ 8,  5,  0, -4],
       [ 0,  6,  0,  3],
       [ 8,  5,  0, -4]])

In [51]: m,n = a.shape # Store shape information

# Unique indices per row that covers the range for row length
In [52]: rand_idx = np.random.rand(m,n).argsort(axis=1)

In [53]: rand_idx
Out[53]: 
array([[0, 2, 3, 1],
       [1, 0, 3, 2],
       [2, 3, 0, 1]])

# Get corresponding indexed array
In [54]: b = a[np.arange(m)[:,None], rand_idx]

# Do a check on the shuffling being restricted to per row
In [55]: a[a!=0]
Out[55]: array([ 8,  5, -4,  6,  3,  8,  5, -4])

In [56]: b[b!=0]
Out[56]: array([ 8, -4,  5,  6,  3, -4,  8,  5])

# Finally do the assignment based on masking on a and b
In [57]: a[a!=0] = b[b!=0]

In [58]: a # Final verification on desired result
Out[58]: 
array([[ 8, -4,  0,  5],
       [ 0,  6,  0,  3],
       [-4,  8,  0,  5]])
    回复于
  • 3

    矢量化解决方案的基准测试

    我们期待在这篇文章中对矢量化解决方案进行基准测试现在，向量化试图避免循环，我们将循环遍历每一行并进行重排 . 因此，输入数组的设置涉及更多行 .

    方法 -

    def app1(a): # @Daniel F's soln
    i, j = np.nonzero(a.astype(bool))
    k = np.argsort(i + np.random.rand(i.size))
    a[i,j] = a[i,j[k]]
    return a

def app2(x): # @kazemakase's soln
    r, c = np.where(x != 0)
    n = c.size
    perm = np.random.permutation(n)
    i = np.argsort(perm + r * n)
    x[r, c] = x[r, c[i]]
    return x

def app3(a): # @Divakar's soln
    m,n = a.shape
    rand_idx = np.random.rand(m,n).argsort(axis=1)
    b = a[np.arange(m)[:,None], rand_idx]
    a[a!=0] = b[b!=0]
    return a

from scipy.ndimage.measurements import labeled_comprehension
def app4(a): # @FabienP's soln
    def func(array, idx):
        r[idx] = np.random.permutation(array)
        return True
    labels, idx = nz = a.nonzero()
    r = a[nz]
    labeled_comprehension(a[nz], labels + 1, np.unique(labels + 1),\
                                func, int, 0, pass_positions=True)
    a[nz] = r
    return a

    Benchmarking procedure #1

    对于公平的基准测试，使用OP的示例似乎是合理的，只需将它们堆叠为更多行以获得更大的数据集 . 因此，通过该设置，我们可以创建两个包含200万和2000万行数据集的案例 .

    案例＃1：包含 2*1000,000 行的大型数据集

    In [174]: a = np.array([[2,3,1,0],[0,0,2,1]])

In [175]: a = np.vstack([a]*1000000)

In [176]: %timeit app1(a)
     ...: %timeit app2(a)
     ...: %timeit app3(a)
     ...: %timeit app4(a)
     ...: 
1 loop, best of 3: 264 ms per loop
1 loop, best of 3: 422 ms per loop
1 loop, best of 3: 254 ms per loop
1 loop, best of 3: 14.3 s per loop

    案例＃2：具有 2*10,000,000 行的较大数据集

    In [177]: a = np.array([[2,3,1,0],[0,0,2,1]])

In [178]: a = np.vstack([a]*10000000)

# app4 skipped here as it was slower on the previous smaller dataset
In [179]: %timeit app1(a)
     ...: %timeit app2(a)
     ...: %timeit app3(a)
     ...: 
1 loop, best of 3: 2.86 s per loop
1 loop, best of 3: 4.62 s per loop
1 loop, best of 3: 2.55 s per loop

    Benchmarking procedure #2 : Extensive one

    为了涵盖输入数组中不同百分比的非零的所有情况，我们将介绍一些广泛的基准测试场景 . 此外，由于 app4 似乎比其他人慢得多，为了进一步检查，我们正在跳过本节中的那个 .

    辅助函数来设置输入数组：

    def in_data(n_col, nnz_ratio):
    # max no. of elems that my system can handle, i.e. stretching it to limits.
    # The idea is to use this to decide the number of rows and always use
    # max. possible dataset size
    num_elem = 10000000

    n_row = num_elem//n_col
    a = np.zeros((n_row, n_col),dtype=int)
    L = int(round(a.size*nnz_ratio))
    a.ravel()[np.random.choice(a.size, L, replace=0)] = np.random.randint(1,6,L)
    return a

    主要时间和绘图脚本（使用IPython魔术功能 . 所以，需要运行opon复制并粘贴到IPython控制台上） -

    import matplotlib.pyplot as plt

# Setup input params
nnz_ratios = np.array([0.2, 0.4, 0.6, 0.8])
n_cols = np.array([4, 5, 8, 10, 15, 20, 25, 50])

init_arr1 = np.zeros((len(nnz_ratios), len(n_cols) ))
init_arr2 = np.zeros((len(nnz_ratios), len(n_cols) ))
init_arr3 = np.zeros((len(nnz_ratios), len(n_cols) ))

timings = {app1:init_arr1, app2:init_arr2, app3:init_arr3}
for i,nnz_ratio in enumerate(nnz_ratios):
    for j,n_col in enumerate(n_cols):
        a = in_data(n_col, nnz_ratio=nnz_ratio)
        for func in timings:
            res = %timeit -oq func(a)
            timings[func][i,j] = res.best
            print func.__name__, i, j, res.best

fig = plt.figure(1)
colors = ['b','k','r']
for i in range(len(nnz_ratios)):
    ax = plt.subplot(2,2,i+1)
    for f,func in enumerate(timings):
        ax.plot(n_cols, 
                [time for time in timings[func][i]], 
                label=str(func.__name__), color=colors[f])
    ax.set_xlabel('No. of cols')
    ax.set_ylabel('time [seconds]')
    ax.grid(which='both')
    ax.legend()
    plt.tight_layout()
    plt.title('Percentage non-zeros : '+str(int(100*nnz_ratios[i])) + '%')
plt.subplots_adjust(wspace=0.2, hspace=0.2)

    时间输出 -

    enter image description here

    Observations :

    • 方法＃1，＃2对整个输入数组中的非零元素执行 argsort . 因此，它使用较少的非零值来表现更好 .

    • 方法＃3创建与输入数组相同形状的随机数，然后每行得到 argsort 个索引 . 因此，对于输入中给定数量的非零，其时序比前两种方法更陡峭 .

    Conclusion :

    方法＃1似乎做得很好，直到60％非零标记 . 对于更多的非零值，如果行长度很小，方法＃3似乎表现得不错 .

    回复于
  • 15

    我想到了：

    nz = a.nonzero()                      # Get nonzero indexes
a[nz] = np.random.permutation(a[nz])  # Shuffle nonzero values with mask

    哪个看起来比其他提议的解决方案更简单（并且更快一点？） .

    EDIT: new version that does not mix rows

    labels, *idx = nz = a.nonzero()                                    # get masks
 a[nz] = np.concatenate([np.random.permutation(a[nz][labels == i])  # permute values
                         for i in np.unique(labels)])               # for each label

    其中第一个 a.nonzero() 数组（axis0中非零值的索引）用作标签 . 这是不混合行的技巧 .

    然后应用 np.random.permutation a[a.nonzero()] 为每个"label"独立 .

    据说scipy.ndimage.measurements.labeled_comprehension可以在这里使用，因为它似乎失败了 np.random.permutation .

    我终于看到它看起来很像@randomir提出的那样 . 无论如何，这只是为了让它发挥作用的挑战 .

    EDIT2:

    终于让它与 scipy.ndimage.measurements.labeled_comprehension 一起工作了

    def shuffle_rows(a):
    def func(array, idx):
        r[idx] = np.random.permutation(array)
        return True
    labels, *idx = nz = a.nonzero()
    r = a[nz]
    labeled_comprehension(a[nz], labels + 1, np.unique(labels + 1), func, int, 0, pass_positions=True)
    a[nz] = r
    return a

    哪里：

    • func() 将非零值混洗

    • labeled_comprehension 适用于 func() 标签

    这将取代之前的for循环，并且在具有许多行的数组上会更快 .

    回复于
  • 8

    这是矢量化解决方案的一种可能性：

    r, c = np.where(x > 0)
n = c.size

perm = np.random.permutation(n)
i = np.argsort(perm + r * n)

x[r, c] = x[r, c[i]]

    向量化这个问题的挑战是 np.random.permutation 只给出平面索引，它会跨行对数组元素进行混洗 . 使用添加的偏移量对置换值进行排序可确保不会跨行进行混洗 .

    回复于
  • 4

    这是你的两个衬垫，无需安装numpy .

    from random import random

def shuffle_nonzeros(input_list):
    ''' returns a list with the non-zero values shuffled '''
    shuffled_nonzero = iter(sorted((i for i in input_list if i!=0), key=lambda k: random()))
    print([i for i in (i if i==0 else next(shuffled_nonzero) for i in input_list)])

    如果你不喜欢一个衬垫，你可以用它做一个发电机

    def shuffle_nonzeros(input_list):
    ''' generator that yields a list with the non-zero values shuffled '''
    random_nonzero_values = iter(sorted((i for i in input_list if i!=0), key=lambda k: random()))
    for i in iterable:
        if i==0:
            yield i
        else:
            yield next(random_nonzero_values)

    或者如果你想要一个列表作为输出，并且不喜欢一行理解

    def shuffle_nonzeros(input_list):
    ''' returns a list with the non-zero values shuffled '''
    out = []
    random_nonzero_values = iter(sorted((i for i in input_list if i!=0), key=lambda k: random()))
    for i in iterable:
        if i==0:
            out.append(i)
        else:
            out.append(next(random_nonzero_values))
    return out
    回复于

相关问题