Заполнить динамический вектор размера рекурсивно

Question

Может быть, позвольте мне изложить мою ситуацию в псевдо-C ++ - сначала код:

std:vector<double> sample(someFunctor f, double lower, double upper) {
    double t = (lower + upper)/2;
    double newval = f(t);

    if (f(upper) - newval > epsilon)
        subsample1 = sample(f, t, upper);
    if (newval - f(lower) > epsilon)
        subsample2 = sample(f, lower, t);

    return concat(subsample2, newval, subsample1);
}

, где concat просто, ну, в общем, объединяет возвращаемые векторы.По сути, я выполняю выборку функции таким образом, чтобы между двумя сохраненными значениями функции была лишь небольшая разница.

Я не доволен изложенным выше способом, поскольку кажется, что на каждом рекурсивном шаге выделяется немного памяти (выделяйте два подвектора, затем объединяйте эти и другой элемент).Этот фрагмент кода должен работать в той части моего алгоритма, которая критична для производительности.Если upper - lower довольно мало, оценка f не займет много времени.

Итак, мои вопросы:

• Видите ли вы умный способ использовать одну и ту же структуру данных во всех рекурсивных вызовах и просто заполнить текущие части этого вектора?(Помните, что количество необходимых оценок функций не известно заранее).Мысли об этом:

  • Использование списка вместо вектора.Но я чувствую, что перестройка памяти не подходит для простого хранения двойных чисел.
  • Сохраняйте дыры в векторе и поддерживайте другой вектор, говоря, какие записи заполнены.В конце рекурсивного вызова сдвиньте записи так, чтобы между subsample s и newval не было дыр.Но теперь я переключаю копирование, переключаясь с дополнительной работой на второй вектор - возможно, это плохая идея.

• Вы видите способ полностью избавиться от рекурсии?Однако для правильности важно, чтобы я использовал шаблон «разделяй и властвуй», изложенный выше.Функция f интенсивно использует верхнюю и нижнюю границы и благодаря этому значительно повышает производительность.

Спасибо за ваши мысли.

---

В соответствии с запросом Space_C0wb0y позвольте мне попытаться перефразировать мою проблему.Возможно, первое объяснение было не очень ясным.

У меня есть некоторая функция (в математическом смысле), которую я хочу отобрать (например, оценить в определенных точках) в заданном интервале.

Предположим, что интервал равен [0,100].Я знаю значения функций в 0 и в 100. Может быть, это f(0)=0 и f(100) = 40.Теперь я оцениваю функцию в средней точке интервала, которая равна 50. Скажем, моя функция возвращает f(50)=10.Поскольку f(0)-f(50) <= 10, мне не нужны дополнительные выборки в интервале [0,50].Однако мне нужны дальнейшие вычисления для интервала [50,100].Таким образом, на следующем (рекурсивном) шаге я оцениваю f(75).Теперь повторите рекурсивную логику.

В конце я хотел бы (два) вектора, дающие мне значения функции с соответствующими параметрами, подобными этим:

parameter  = vector(0, 50, 56.25, 62.5, 75, 100)
value      = vector(0, 10, 17.21, 25    34,  40)

Я ищу лучшее (как наиболее эффективно)подход к построению этих векторов рекурсивно.

Надеюсь, это прояснит ситуацию.

Answer 1

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

1.Используйте копирование по ссылке вместо копирования по (возвращаемому) значению.

2.Не нужно указывать функтор, поскольку он постоянен.

3.Это могло бы быть быстрее, если бы low и high были целыми числами.Это зависит от требований.

    // Thanks to Space_C0wb0y, here we avoid using a global vector
    // by passing the vector as reference. It's efficient as there
    // is no copy overhead as well.        
    void sample(vector<double>& samples, double low, double high)
    {
       // You can use shift operator if they're integers.
       double mid = (low + high)/2;

       // Since they're double, you need prevent them from being too close.
       // Otherwise, you'll probably see stack overflow.
       // Consider this case:
       // f(x): x=1, 0<x<8;  x*x, x<=0 or x>=8
       // low = 1, high = 10, epsilon = 10
       if (high - low < 0.5)
       {
          samples.push_back(f(mid));
          return;
       }   

       // The order you write the recursive calls guarantees you
       // the sampling order is from left to right.
       if (f(mid) - f(low) > epsilon)
       {
          sample(samples, low, mid);
       }

       samples.push_back(f(mid));

       if (f(high) - f(mid) > epsilon)
       {
          sample(samples, mid, high);
       }   
    }

Answer 2

Я бы рекомендовал следующий подход:

1. Не используйте два вектора, а один вектор с парами или пользовательский struct для представления параметров и значений:

   struct eval_point {
       double parameter;
       double value;
   };
   
   std::vector<eval_point> evaluated_points;
   

2. Измените свой алгоритм, чтобы записать результаты вычислений в выходной итератор:

   template<class F, class output_iterator_type>
   void sample(F someFunctor, double lower, double upper,
               output_iterator_type out) {
       double t = (lower + upper)/2;
       eval_point point = { t, f(t) };
   
       if (f(upper) - point.value > epsilon) {
           *out = point;
           ++out;
           sample(f, t, upper, out);
       }
       if (point.value - f(lower) > epsilon) {
           *out = point;
           ++out;
           subsample2 = sample(f, lower, t, out);
       }
   }
   

   Выше приведена модификация вашего псевдокода, показывающая, как он может выглядеть при использовании выходного итератора. Это не проверено, поэтому я не уверен, правильно ли это. В принципе, вы бы назвали это так:

   std::vector<eval_point> results;
   sample(someFunction, 0, 100, std::back_inserter<eval_point>(results));
   

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

   std::vector<eval_point> results(lower_bound_for_samples);
   sample(someFunction, 0, 100, results.begin());
   

Затем вам нужно будет добавить дополнительный счетчик, чтобы отслеживать количество сэмплов.

Answer 3

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