np.choice와 chainer.utils.WalkerAlias의 속도 대결

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 ()가 있다).

  • 좋은 웹페이지 즐겨찾기