Блог

Главная - Вопросы по программированию - Более быстрая прокрутка случайных гауссовых векторов

Более быстрая прокрутка случайных гауссовых векторов

#python #c #optimization #numpy #random

#python #c #оптимизация #numpy #Случайный

Вопрос:

Для моделирования, подобного методу Монте-Карло, мне нужно случайным образом выбрать тысячи случайных гауссовых векторов (то есть векторов, имеющих независимо нормально распределенные записи). Каждый такой вектор имеет фиксированную длину (около 100).

У NumPy есть способ добиться этого:

 import numpy.random
vectors = [numpy.random.normal(size=100) for _ in xrange(10000)]

random.normal Функция NumPy имеет линейную сложность, с накладными расходами для значений малого размера. Однако, похоже, что накладные расходы незначительны для size=100 (возможно, около 30%, проверено эмпирически; сравните с накладными расходами для size=1 , которые составляют около 2300%). Возможно, я смогу сэкономить часть этих накладных расходов, выполнив один раз прокрутку, а затем разделив массив (еще не пробовал).

Тем не менее, это все еще слишком медленно для моих нужд. Возможно, я здесь слишком жадный; Я знаю, что функции рандомизации NumPy написаны c с учетом оптимизации; тем не менее,

 timeit numpy.random.normal(size=100)
# 100000 loops, best of 3: 5.8 us per loop

(протестировано внутри IPython, используя его магию %timeit )

Это составляет ~ 0,06 секунды для 10 тыс. векторов. Мне было интересно, существует ли гораздо более быстрый метод, который позволит мне свернуть 10 тыс. векторов размером 100 (скажем) менее чем за 0,6 мс, то есть в 100 раз быстрее. Решение может включать c расширения или все, что необходимо.

Обновить

Очень простой c код, основанный на примере из cppreference , показывает гораздо лучшую производительность:

 #include <iostream>
#include <random>

int main()
{
    float x;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::normal_distribution <> d(0,1);

    for(int i=0; i < 100000; i  )
    {
      x = d(gen);
    }
    std::cout << x << 'n';

    return 0;
}

и время показывает:

 real    0m0.028s
user    0m0.020s
sys     0m0.004s

что примерно в 20 раз быстрее, чем дает NumPy. Тем не менее, я не уверен в накладных расходах c-расширений для python, и у меня нет интуиции относительно того, может ли это стать функцией python, которая быстрее, чем numpy.random.normal .

Комментарии:

1. np.random.randn(100, 10000)

2. @behzad.nouri: спасибо за ваш ответ! Однако это только улучшило мои 0,06 секунды примерно до 0,04 секунды, что все еще далеко от того, что я надеялся найти.

3. с помощью numpy> = 1.9 вы можете использовать потоки для ускорения процесса, но он не может быть быстрее, чем при использовании numpy. numpy использует метод box muller, вы можете получить лучшую производительность при расширении с использованием метода ziggurat.

4. @jtaylor — спасибо; Я считаю, что это будет далеко за пределами моих c навыков. Тем не менее, это, вероятно, хорошее направление для рассмотрения.

5. Насколько нормальными должны быть ваши случайные числа, т. Е. Сколько ошибок в распределении вы можете иметь. Это просто «примерно нормально»? Тогда могут быть способы ускорить процесс.

Метки: