Инициализация вектора C ++ для случайных значений ... быстро

Question

Эй, я хотел бы сделать это как можно быстрее, потому что в программе, которую я пишу, он называется A LOT, поэтому есть ли более быстрый способ инициализации вектора C ++ случайными значениями, чем:

double range;//set to the range of a particular function i want to evaluate.
std::vector<double> x(30, 0.0);
for (int i=0;i<x.size();i++) {
    x.at(i) = (rand()/(double)RAND_MAX)*range;
}

РЕДАКТИРОВАТЬ: Исправлен инициализатор х.

Answer 1

Сейчас это должно быть действительно быстро, поскольку цикл не будет выполняться.

Лично я бы, наверное, использовал что-то вроде этого:

struct gen_rand { 
    double range;
public:
    gen_rand(double r=1.0) : range(r) {}
    double operator()() { 
        return (rand()/(double)RAND_MAX) * range;
    }
};

std::vector<double> x(num_items);
std::generate_n(x.begin(), num_items, gen_rand());

Редактировать: Это чисто микрооптимизация, которая может вообще ничего не менять, но вы можете подумать о перестановке вычислений, чтобы получить что-то вроде:

struct gen_rand { 
    double factor;
public:
    gen_rand(double r=1.0) : factor(range/RAND_MAX) {}
    double operator()() { 
        return rand() * factor;
    }
};

Конечно, есть действительно хороший шанс, что компилятор уже сделает это (или что-то подобное), но в любом случае это не помешает (хотя на самом деле это только поможет отключить оптимизацию).

Edit2: «sbi» (как обычно имеет место) правильно: вы могли бы немного выиграть, первоначально зарезервировав пространство, а затем используя итератор вставки, чтобы поместить данные на место:

std::vector<double> x;
x.reserve(num_items);
std::generate_n(std::back_inserter(x), num_items, gen_rand());

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

В конце, однако, почти единственная часть, которая на самом деле , вероятно, , может существенно изменить ситуацию, - это избавление от .at(i). Другие могут , но с включенными оптимизациями я бы не ожидал их.

Answer 2

В течение некоторого времени я использовал метод функтора Джерри Коффина, но с появлением C ++ 11 у нас появилось множество интересных функций для работы со случайными числами. Чтобы заполнить массив случайными float значениями, мы можем теперь сделать что-то вроде следующего. , ,

const size_t elements = 300;
std::vector<float> y(elements);    
std::uniform_real_distribution<float> distribution(0.0f, 2.0f); //Values between 0 and 2
std::mt19937 engine; // Mersenne twister MT19937
auto generator = std::bind(distribution, engine);
std::generate_n(y.begin(), elements, generator); 

См. Соответствующий раздел Википедия , чтобы узнать больше двигателей и дистрибутивов

Answer 3

Да, тогда как x.at (i) выполняет проверку границ, x [i] этого не делает. Кроме того, ваш код неверен, поскольку вы не указали размер x заранее. Вам нужно использовать std::vector<double> x(n), где n - количество элементов, которые вы хотите использовать; в противном случае ваш цикл там никогда не будет выполнен.

В качестве альтернативы, вы можете захотеть создать собственный итератор для генерации случайных значений и их заполнения с использованием итератора; потому что конструктор std :: vector будет инициализировать свои элементы, так или иначе, поэтому, если у вас есть собственный класс итератора, который генерирует случайные значения, вы можете исключить передачу элементов.

С точки зрения реализации собственного итератора , вот мой непроверенный код:

 class random_iterator
 {
     public:
         typedef std::input_iterator_tag iterator_category;
         typedef double value_type;
         typedef int difference_type;
         typedef double* pointer;
         typedef double& reference;

         random_iterator() : _range(1.0), _count(0) {}
         random_iterator(double range, int count) : 
                                         _range(range), _count(count) {}
         random_iterator(const random_iterator& o) : 
                                         _range(o._range), _count(o._count) {}
         ~random_iterator(){}

         double operator*()const{ return ((rand()/(double)RAND_MAX) * _range); }
         int operator-(const random_iterator& o)const{ return o._count-_count; }
         random_iterator& operator++(){ _count--; return *this; }
         random_iterator operator++(int){ random_iterator cpy(*this); _count--; return cpy; }
         bool operator==(const random_iterator& o)const{ return _count==o._count; }
         bool operator!=(const random_iterator& o)const{ return _count!=o._count; }

     private:
         double _range;
         int _count;
 };

С кодом выше, должно быть возможно использовать:

std::vector<double> x(random_iterator(range,number),random_iterator());

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

Answer 4

#include <iostream>
#include <vector>
#include <algorithm>

struct functor {
   functor(double v):val(v) {}
   double operator()() const {
      return (rand()/(double)RAND_MAX)*val;
   }
private:
   double val;
};

int main(int argc, const char** argv) {
   const int size = 10;
   const double range = 3.0f;

   std::vector<double> dvec;
   std::generate_n(std::back_inserter(dvec), size, functor(range));

   // print all
   std::copy(dvec.begin(), dvec.end(), (std::ostream_iterator<double>(std::cout, "\n")));

   return 0;
}

опоздал: (

Answer 5

Вы можете рассмотреть возможность использования генератора псевдослучайных чисел, который выдает выходные данные в виде последовательности. Так как большинство PRNG просто предоставляют последовательность в любом случае, это будет намного эффективнее, чем простой вызов rand () снова и снова.

Но тогда, я думаю, мне действительно нужно больше знать о вашей ситуации.

• Почему этот кусок кода выполняется так много? Можете ли вы реструктурировать свой код, чтобы избежать частой генерации случайных данных?
• Насколько велики ваши векторы?
• Насколько "хорош" должен быть ваш генератор случайных чисел? Качественные распределения, как правило, обходятся дороже.
• Если ваши векторы велики, вы повторно используете их буферное пространство или выбрасываете его и перераспределяете в другом месте? Создание новых векторов - это отличный способ уничтожить ваш кеш.

Answer 6

int main() {
  int size = 10;
  srand(time(NULL));
  std::vector<int> vec(size);
  std::generate(vec.begin(), vec.end(), rand);

  std::vector<int> vec_2(size);
  std::generate(vec_2.begin(), vec_2.end(), [](){ return rand() % 50;})
}

Вам нужно включить вектор, алгоритм, время, cstdlib.

Answer 7

@ Ответ Джерри Коффина выглядит очень хорошо. Впрочем, две другие мысли:

1. Inlining - Весь ваш векторный доступ будет очень быстрым, но если вызов rand () будет вне строки, издержки вызова функции могут доминировать. В этом случае вам может понадобиться запустить собственный генератор псевдослучайных чисел .

2. SIMD - Если вы собираетесь бросить свой собственный PRNG, вы можете также сделать так, чтобы он вычислял 2 удвоения (или 4 поплавка) одновременно. Это уменьшит количество преобразований типа int-to-float, а также умножения. Я никогда не пробовал, но, видимо, есть SIMD-версия Mersenne Twister, которая довольно хороша. Простой линейный конгруэнтный генератор тоже может быть достаточно хорош (и это, вероятно, то, что уже использует rand ()).

Answer 8

То, как я об этом думаю, - это подход «резиновая шина».
Другими словами, есть определенные минимальные вещи, которые должны произойти, не обходя их стороной, такие как:

• функция rand() должна вызываться N раз.

• результат rand() должен быть преобразован в double, а затем умножен на что-то.

• результирующие числа должны храниться в последовательных элементах массива.

Цель, как минимум, сделать все это.

Другие проблемы, такие как использование или отсутствие std::vector и итераторов, хороши, если они не добавляют дополнительных циклов. Самый простой способ узнать, добавляют ли они значительные дополнительные циклы, - это пошаговый код на уровне языка ассемблера.