chainer의 매뉴얼에 「chainer.utils.WalkerAlias는 np.choice보다 빠르다」라고 쓰여 있었으므로, 속도를 비교해 보았다. 그러나 CPU 전용.

chainer.utils.WalkerAlias

Alias ​​method on Wikipedia

코드

난수 생성

import numpy as np
import chainer
from time import time
import matplotlib.pyplot as plt
%matplotlib inline

loops = 10  # for taking average
verc_size = 10 ** np.arange(1, 7)  # i
n_samples = 10 ** np.arange(1, 7)  # j

t_choice = np.zeros((len(verc_size), len(n_samples)))
t_alias  = np.zeros((len(verc_size), len(n_samples)))
t_aliasv = np.zeros((len(verc_size), len(n_samples)))



for i in range(len(verc_size)):

    p = np.random.randint(100, size=verc_size[i])
    p = p / p.sum()
    # p = p.astype(np.float32)  # for gpu?
    c = np.random.randint(100, size=verc_size[i])

    start_time = time()
    for loop in range(loops):
        sampler = chainer.utils.WalkerAlias(p)
    end_time = time()
    e_time = end_time - start_time
    t_aliasv[i, :] = e_time / loops


    for j in range(len(n_samples)):

        # numpy choice
        start_time = time()
        for loop in range(loops):
            res = np.random.choice(c, size=n_samples[j], p=p)
        end_time = time()
        e_time = end_time - start_time
        print('choice', e_time, n_samples[j], verc_size[i])
        t_choice[i, j] = e_time / loops

        # chainer alisas
        start_time = time()
        for loop in range(loops):
            res = sampler.sample(n_samples[j])
            res = c[res]
        end_time = time()
        e_time = end_time - start_time
        print('alias ', e_time, n_samples[j], verc_size[i])
        t_alias[i, j] = e_time / loopsimport numpy as np

플롯

플롯

fig, ax = plt.subplots(nrows=1, ncols=3, figsize=(15, 5))

def myax(ax, title):
    ax.set_yscale('log')
    ax.set_xscale('log')
    ax.set_ylim(1e-4, 1e2)
    ax.set_title(title)
    ax.set_xlabel('# samples')
    ax.set_ylabel('time [s]')

for i in range(len(verc_size)):
    ax[0].plot(n_samples, t_choice[i], label=verc_size[i])
myax(ax[0], 'np.choice')
ax[0].legend(loc='best')

ax[1].plot(n_samples, t_alias)
myax(ax[1], 'chainer.alias sampling only')

ax[2].plot(n_samples, t_alias + t_aliasv)
myax(ax[2], 'chainer.alias init + sampling')

결과

alias method는 확실히 O(1)이라는 것을 알 수 있다(sampling only의 경우. 계산 시간은 샘플수에 의존하지 않는다).

alias method는 초기화에 방대한 시간이 걸리므로 초기화 시간을 포함하면 확실히 np.choice 쪽이 빠르다.

초기화를 제외하면, 「1만개 중에서 1개 선택한다」를 1만회 반복할 때에는, alias method 쪽이 빨라 보인다.

GPU에서 alias method가 얼마나 빠르는지는 검증되지 않았다 (chainer.utils.WalkerAlias에는 to_gpu ()가 있다).