Найти n случайный нулевой элемент в разреженном разреженном csr_matrix - PullRequest
Новая
       13

Найти n случайный нулевой элемент в разреженном разреженном csr_matrix

2 голосов
/ 16 марта 2019

Я хочу найти ноль элементов в разреженной матрице.Я пишу код ниже: 

counter = 0
while counter < n:
    r = randint(0, W.shape[0]-1)
    c = randint(0, W.shape[1]-1)
    if W[r,c] == 0:
        result.append([r,c])
        counter += 1

К сожалению, это очень медленно.Я хочу что-то более эффективное.Есть ли способ быстро получить доступ к нулевым элементам из скудной разреженной матрицы?

Ответы [ 3 ]

1 голос
/ 16 марта 2019

Во-первых, вот код для создания примера данных: 

import numpy as np
rows, cols = 10,20   # Shape of W
nonzeros = 7         # How many nonzeros exist in W
zeros = 70           # How many zeros we want to randomly select

W = np.zeros((rows,cols), dtype=int)
nonzero_rows = np.random.randint(0, rows, size=(nonzeros,))
nonzero_cols = np.random.randint(0, cols, size=(nonzeros,))
W[nonzero_rows, nonzero_cols] = 20

Приведенный выше код создал W в виде разреженного массива, имеющего форму (10,20) и содержащего только 7 ненулевых элементов (из элементов 200). Все ненулевые элементы имеют значение 20.

Вот решение для выбора zeros=70 нулевых элементов из этой разреженной матрицы: 

argwhere_res = np.argwhere(np.logical_not(W))
zero_count = len(argwhere_res)
ids = np.random.choice(range(zero_count), size=(zeros,))
res = argwhere_res[ids]

res теперь будет массивом (70,2) формы, дающим расположение элементов 70, которые мы случайно выбрали из W.

Обратите внимание, что это не связано с петлями.

1 голос
/ 16 марта 2019 
import numpy as np
import scipy.sparse as sparse
import random
randint = random.randint

def orig(W, n):
    result = list()
    while len(result) < n:
        r = randint(0, W.shape[0]-1)
        c = randint(0, W.shape[1]-1)
        if W[r,c] == 0:
            result.append((r,c))
    return result

def alt(W, n):
    nrows, ncols = W.shape
    density = n / (nrows*ncols - W.count_nonzero())
    W = W.copy()
    W.data[:] = 1
    W2 = sparse.csr_matrix((nrows, ncols))
    while W2.count_nonzero() < n:
        W2 += sparse.random(nrows, ncols, density=density, format='csr')
        # remove nonzero values from W2 where W is 1
        W2 -= W2.multiply(W)
    W2 = W2.tocoo()    
    r = W2.row[:n]
    c = W2.col[:n]
    result = list(zip(r, c))
    return result

def alt_with_dupes(W, n):
    nrows, ncols = W.shape
    density = n / (nrows*ncols - W.count_nonzero())
    W = W.copy()
    W.data[:] = 1
    W2 = sparse.csr_matrix((nrows, ncols))
    while W2.data.sum() < n:
        tmp = sparse.random(nrows, ncols, density=density, format='csr')
        tmp.data[:] = 1
        W2 += tmp
        # remove nonzero values from W2 where W is 1
        W2 -= W2.multiply(W)
    W2 = W2.tocoo()
    num_repeats = W2.data.astype('int')
    r = np.repeat(W2.row, num_repeats)
    c = np.repeat(W2.col, num_repeats)
    idx = np.random.choice(len(r), n)
    result = list(zip(r[idx], c[idx]))
    return result

Вот эталонный тест: 

W = sparse.random(1000, 50000, density=0.02, format='csr')
n = int((np.multiply(*W.shape) - W.nnz)*0.01)

In [194]: %timeit alt(W, n)
809 ms ± 261 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [195]: %timeit orig(W, n)
11.2 s ± 121 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [223]: %timeit alt_with_dupes(W, n)
986 ms ± 290 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Обратите внимание, что alt возвращает список без дубликатов.И orig, и alt_with_dupes могут возвращать дубликаты.

0 голосов
/ 16 марта 2019

Сначала составьте список всех 0: 

list_0s = [(j, i) for i in range(len(matrix[j])) for j in range len(matrix) if matrix[j,i] == 0]

Тогда получите случайный выбор: 

random_0s = random.choices(list_0s, k=n)

Тестирование с помощью: 

 matrix = np.random.randint(1000, size=(1000,1000))
 n = 100

Занимает 0,34 секунды.

...