Как ускорить один код горячего кодера

Question

Я сделал простую функцию, которая вернет выходную горячую кодированную матрицу при задании в качестве входного одного вектора.

import numpy as np 

def ohc(x): 
    u = list(set(x)) 
    c = len(u) 
    X = np.zeros((len(x), c)) 
    for idx, val in enumerate(x): 
     for i in range(c): 
      if val == u[i]: 
       X[idx, i] = 1 
    return X 

inputx = np.random.randint(1, 4, 1000000) 
ohc(inputx) 
Out[2]: 
array([[ 0., 1., 0.], 
     [ 0., 1., 0.], 
     [ 0., 1., 0.], 
     ..., 
     [ 0., 0., 1.], 
     [ 0., 1., 0.], 
     [ 0., 1., 0.]]) 

, но мне интересно, если из-за этих двух циклов есть какой-либо способ ускорить его?

 1000006 function calls in 1.102 seconds 

    Ordered by: standard name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
    1 0.930 0.930 1.102 1.102 <ipython-input-32-fcf6d323f906>:1(ohc) 
    1 0.000 0.000 1.102 1.102 <string>:1(<module>) 
    2 0.000 0.000 0.000 0.000 {len} 
    1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
    1 0.000 0.000 0.000 0.000 {numpy.core.multiarray.zeros} 
    1000000 0.172 0.000 0.172 0.000 {range} 

Answer 1

выглядит как работа для np.unique

uniq, inv = np.unique(x, return_inverse=True) 
result = np.zeros((len(x), len(uniq)), dtype=int) 
result[np.arange(len(x)), inv] = 1 

В ответ на тесты Дивакара: вот более информативное сравнение, подтверждающее небольшое преимущество в скорости для dv при небольших алфавитах, которое пересекает около K=20 и меняет значение в несколько раз на pp по адресу K=1000. Это ожидается, так как pp использует разреженность одноразового использования. Ниже, K - размер алфавита, N длина образца.

import numpy as np 
from timeit import timeit 

def pp(x): 
    uniq, inv = np.unique(x, return_inverse=True) 
    result = np.zeros((len(x), len(uniq)), dtype=int) 
    result[np.arange(len(x)), inv] = 1 

def dv(x): 
    (x[:,None] == np.unique(x)).astype(int) 


for K in (4, 10, 20, 40, 100, 200, 1000): 
    tpp, tdv = [], [] 
    print('@ K =', K) 
    for N in (1000, 10000, 100000): 
     data = np.random.choice(np.random.random(K), N, replace=True) 
     tdv.append(timeit('f(a)', number=100, globals={'f': dv, 'a': data})) 
     tpp.append(timeit('f(a)', number=100, globals={'f': pp, 'a': data})) 
    print('dv:', '{:.6f}, {:.6f}, {:.6f}'.format(*tdv), 'secs for 100 trials @ N = 1000, 10000, 100000') 
    print('pp:', '{:.6f}, {:.6f}, {:.6f}'.format(*tpp), 'secs for 100 trials @ N = 1000, 10000, 100000') 

Печать:

@ K = 4 
dv: 0.003458, 0.038176, 0.421894 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.004856, 0.052298, 0.603758 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 10 
dv: 0.005136, 0.056491, 0.663157 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.005955, 0.054069, 0.719152 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 20 
dv: 0.007201, 0.084867, 0.988886 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.007638, 0.084580, 0.891122 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 40 
dv: 0.010748, 0.130974, 1.498022 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.009321, 0.103912, 1.080271 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 100 
dv: 0.025357, 0.292930, 2.946326 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.011916, 0.147117, 1.641588 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 200 
dv: 0.033651, 0.560753, 6.042001 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.022971, 0.221142, 3.580255 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 1000 
dv: 0.156715, 2.655647, 37.112166 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.055516, 0.920938, 10.358050 secs for 100 trials @ N = 1000, 10000, 100000 

Использование uint8 и позволяет @ метод Divakar, чтобы использовать более дешевый вид литье:

@ K = 4 
dv: 0.003092, 0.038149, 0.386140 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.004392, 0.043327, 0.554253 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 10 
dv: 0.004604, 0.054215, 0.501708 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.004930, 0.051555, 0.607239 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 20 
dv: 0.006421, 0.067397, 0.665465 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.006616, 0.054055, 0.703260 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 40 
dv: 0.008857, 0.087155, 0.862316 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.006945, 0.060408, 0.733966 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 100 
dv: 0.015660, 0.142464, 1.426929 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.008063, 0.070860, 0.908615 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 200 
dv: 0.025631, 0.235712, 2.401750 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.008805, 0.101772, 1.111652 secs for 100 trials @ N = 1000, 10000, 100000 
@ K = 1000 
dv: 0.069953, 1.024585, 11.313402 secs for 100 trials @ N = 1000, 10000, 100000 
pp: 0.011558, 0.182684, 2.201837 secs for 100 trials @ N = 1000, 10000, 100000 

Answer 2

Ваш код работает в O (п [из множества()] + пс [из-за для петель]). В большинстве практических приложений вы все равно получите O (nc) *, потому что вам нужно выделить пространство для массива. Однако есть несколько трюков, чтобы сделать его более эффективным:

1. Использование dict. Дикты реализуются с использованием хеширования, которое должно в среднем принимать постоянное время.
2. Не перебирайте с помощью возможных функций на каждом шагу, но запоминайте индекс для каждой функции.

Вот моя реализация:

import numpy as np 

def ohc(x): 
    elem_to_idx = {} 
    for e in x: 
     if e not in elem_to_idx: 
      elem_to_idx[e] = len(elem_to_idx) 
    c = len(elem_to_idx) 
    X = np.zeros((len(x), c)) 
    for idx, val in enumerate(x): 
     X[idx, elem_to_idx[val]] = 1 
    return X 

* в зависимости от того, что вы собираетесь делать с матрицей X, вы можете захотеть использовать numpy.sparse матрицу, которая не выделяет, что много памяти и в очередь может сделать ваш код, выполняемый в O (N) вместо O (НЗ)

Answer 3

Вот Векторизованный подход, использующий только уникальные значения из np.unique для сравнение с исходным массивом для доступа к массиву с одним горячим кодированием -

(inputx[:,None] == np.unique(inputx)).astype(float) 

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

Другие подходы -

# Original soln 
def ohc(x): 
    u = list(set(x)) 
    c = len(u) 
    X = np.zeros((len(x), c)) 
    for idx, val in enumerate(x): 
     for i in range(c): 
      if val == u[i]: 
       X[idx, i] = 1 
    return X 

# @Tommalla's soln 
def ohc_dict(x): 
    elem_to_idx = {} 
    for e in x: 
     if e not in elem_to_idx: 
      elem_to_idx[e] = len(elem_to_idx) 
    c = len(elem_to_idx) 
    X = np.zeros((len(x), c)) 
    for idx, val in enumerate(x): 
     X[idx, elem_to_idx[val]] = 1 
    return X 

# @Paul Panzer's soln 
def unique_inverse(x): 
    uniq, inv = np.unique(x, return_inverse=True) 
    result = np.zeros((len(x), len(uniq)), dtype=int) 
    result[np.arange(len(x)), inv] = 1 
    return result 

тайминги -

In [42]: inputx = np.random.randint(1, 4, 1000000) 

In [43]: %timeit ohc(inputx) 
1 loops, best of 3: 526 ms per loop 

In [44]: %timeit ohc_dict(inputx) 
1 loops, best of 3: 256 ms per loop 

In [45]: %timeit unique_inverse(inputx) 
10 loops, best of 3: 48.6 ms per loop 

In [46]: %timeit (inputx[:,None] == np.unique(inputx)).astype(float) 
10 loops, best of 3: 34.4 ms per loop 

Дальнейшее выступление boost-

Использование np.int8 в качестве выходного DTYPE для дальнейшего увеличения производительности с предлагаемым способом -

In [58]: %timeit (inputx[:,None] == np.unique(inputx)).astype(np.int8) 
10 loops, best of 3: 27.7 ms per loop 

Как было предложено @Paul Panzer, мы можем также использовать view вместо типа литья для некоторого дальнейшего повышения на массивах с более уникальными номерами -

In [23]: inputx = np.random.randint(1, 40, 1000000) 

In [24]: %timeit (inputx[:,None] == np.unique(inputx)).astype(np.int8) 
10 loops, best of 3: 98.4 ms per loop 

In [25]: %timeit (inputx[:,None] == np.unique(inputx)).view(np.int8) 
10 loops, best of 3: 92.5 ms per loop