будет накапливаться в той же позиции в плоской версии. Таким образом, с этим смещением мы сохраняем одни и те же числа в разных строках как отдельные для работы с bincount. Вот и вся идея.

я есть массив NumPy с целочисленными значениями. Значения матрицы варьируются от 0 до максимального элемента в матрице (другими словами, все числа от 0 до максимального элемента данных представлены в нем). Мне нужно построить эффективно (эффективное средство быстрое полностью векторизованное решение) для поиска количества элементов в каждой строке и их кодирования в соответствии со значениями матрицы.

Я не мог найти подобный вопрос или вопрос, который каким-то образом помог решить эту проблему.

Так что, если у меня есть этоdata на входе:

# shape is (N0=4, m0=4) 
1   1   0   4
2   4   2   1
1   2   3   5
4   4   4   1

желаемый результат:

# shape(N=N0, m=data.max()+1):
1   2   0   0   1   0
0   1   2   0   1   0
0   1   1   1   0   1
0   1   0   0   3   0

Я знаю, как решить эту проблему, просто посчитав уникальные значения в каждой строкеdata повторяя одну за другой, а затем объединяя результаты с учетом всех возможных значений вdata массив.

При использовании NumPy для векторизации этого ключевая проблема заключается в том, что поиск каждого числа один за другим идет медленно и при условии, что представлено много уникальных чисел, это не может быть эффективным решением. Как правило, обаN и количество уникальных номеров довольно велико (кстати,N кажется, больше, чем количество уникальных чисел).

У кого-нибудь есть отличные идеи?)

Ответы на вопрос(1)

Решение Вопроса

np.bincount делает с1D массивы. Но нам нужно использовать его в каждой строке итеративно (просто подумав об этом). Чтобы сделать его векторизованным, мы могли бы сместить каждую строку на это максимальное число. Идея состоит в том, чтобы иметь разные ячейки для каждой строки, чтобы на них не влияли другие элементы строки с одинаковыми номерами.

Следовательно, реализация будет -

# Vectorized solution
def bincount2D_vectorized(a):    
    N = a.max()+1
    a_offs = a + np.arange(a.shape[0])[:,None]*N
    return np.bincount(a_offs.ravel(), minlength=a.shape[0]*N).reshape(-1,N)

Пробный прогон -

In [189]: a
Out[189]: 
array([[1, 1, 0, 4],
       [2, 4, 2, 1],
       [1, 2, 3, 5],
       [4, 4, 4, 1]])

In [190]: bincount2D_vectorized(a)
Out[190]: 
array([[1, 2, 0, 0, 1, 0],
       [0, 1, 2, 0, 1, 0],
       [0, 1, 1, 1, 0, 1],
       [0, 1, 0, 0, 3, 0]])

Numba Tweaks

Мы можем принести вnumba для дальнейших ускорений. В настоящее время,numba позволяет несколько настроек.

Во-первых, это позволяет JIT-компиляцию.

Кроме того, недавно они представили экспериментальныеparallel это автоматически распараллеливает операции в функции, известной как имеющей параллельную семантику.

Окончательный твик будет использоватьprange в качестве замены дляrange, Документы утверждают, что это запускает циклы параллельно, аналогично OpenMP для циклов параллельно и prange Cython.prange хорошо работает с большими наборами данных, что, вероятно, связано с накладными расходами, необходимыми для настройки параллельной работы.

Итак, с этими двумя новыми настройками вместе сnjit для режима без Python у нас было бы три варианта -

# Numba solutions
def bincount2D_numba(a, use_parallel=False, use_prange=False):
    N = a.max()+1
    m,n = a.shape
    out = np.zeros((m,N),dtype=int)

    # Choose fucntion based on args
    func = bincount2D_numba_func0
    if use_parallel:
        if use_prange:
            func = bincount2D_numba_func2
        else:
            func = bincount2D_numba_func1
    # Run chosen function on input data and output
    func(a, out, m, n)
    return out

@njit
def bincount2D_numba_func0(a, out, m, n):
    for i in range(m):
        for j in range(n):
            out[i,a[i,j]] += 1

@njit(parallel=True)
def bincount2D_numba_func1(a, out, m, n):
    for i in range(m):
        for j in range(n):
            out[i,a[i,j]] += 1

@njit(parallel=True)
def bincount2D_numba_func2(a, out, m, n):
    for i in prange(m):
        for j in prange(n):
            out[i,a[i,j]] += 1

Для полноты и тестирования позже, петлевая версия будет:

# Loopy solution
def bincount2D_loopy(a):
    N = a.max()+1
    m,n = a.shape
    out = np.zeros((m,N),dtype=int)
    for i in range(m):
        out[i] = np.bincount(a[i], minlength=N)
    return out 

Испытание во время выполнения

Дело 1 :

In [312]: a = np.random.randint(0,100,(100,100))

In [313]: %timeit bincount2D_loopy(a)
     ...: %timeit bincount2D_vectorized(a)
     ...: %timeit bincount2D_numba(a, use_parallel=False, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=True)
10000 loops, best of 3: 115 µs per loop
10000 loops, best of 3: 36.7 µs per loop
10000 loops, best of 3: 22.6 µs per loop
10000 loops, best of 3: 22.7 µs per loop
10000 loops, best of 3: 39.9 µs per loop

Дело № 2:

In [316]: a = np.random.randint(0,100,(1000,1000))

In [317]: %timeit bincount2D_loopy(a)
     ...: %timeit bincount2D_vectorized(a)
     ...: %timeit bincount2D_numba(a, use_parallel=False, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=True)
100 loops, best of 3: 2.97 ms per loop
100 loops, best of 3: 3.54 ms per loop
1000 loops, best of 3: 1.83 ms per loop
100 loops, best of 3: 1.78 ms per loop
1000 loops, best of 3: 1.4 ms per loop

Дело № 3:

In [318]: a = np.random.randint(0,1000,(1000,1000))

In [319]: %timeit bincount2D_loopy(a)
     ...: %timeit bincount2D_vectorized(a)
     ...: %timeit bincount2D_numba(a, use_parallel=False, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=False)
     ...: %timeit bincount2D_numba(a, use_parallel=True, use_prange=True)
100 loops, best of 3: 4.01 ms per loop
100 loops, best of 3: 4.86 ms per loop
100 loops, best of 3: 3.21 ms per loop
100 loops, best of 3: 3.18 ms per loop
100 loops, best of 3: 2.45 ms per loop

Похоже наnumba варианты работают очень хорошо. Выбор одного из трех вариантов будет зависеть от параметров формы входного массива и в некоторой степени от количества уникальных элементов в нем.

 Grigory16 сент. 2017 г., 19:29
О, я понял: вы смещаете значения в каждой строке, чтобы сделать их уникальными.
 Grigory16 сент. 2017 г., 19:11
Замечательно. Работает именно так, как нужно. Огромное спасибо.
 Divakar16 сент. 2017 г., 19:32
@Grigoriy Точно, потому что те же числа, когда кормятbincount будет накапливаться в той же позиции в плоской версии. Таким образом, с этим смещением мы сохраняем одни и те же числа в разных строках как отдельные для работы с bincount. Вот и вся идея.
 Grigory16 сент. 2017 г., 19:17
a + np.arange(a.shape[0])[:,None]*N сейчас выглядит как волшебство. Можете ли вы дать объяснение идеи «смещения» значений, пожалуйста?

Ваш ответ на вопрос