STL for_each с несколькими возвращаемыми значениями и / или функтором виртуального базового класса - PullRequest
Новая
       33

STL for_each с несколькими возвращаемыми значениями и / или функтором виртуального базового класса

2 голосов
/ 11 сентября 2011

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

Создать функцию, которая зацикливается только на данных один раз и вычисляет оба значения, легко, но мне нужно вернуть оба. Чтобы использовать с for_each, мне нужно возвращать оба вычисленных значения на каждой итерации, чтобы STL мог их суммировать. Насколько я понимаю, это невозможно, так как for_each ожидает возвращения одного значения.

Цель использования for_each, помимо более чистого кода (возможно?), Состоит в том, чтобы в конечном итоге перейти к многопоточной или многопроцессорной реализации, чтобы цикл данных мог выполняться параллельно, чтобы все работало быстрее.

Мне предложили посмотреть на использование функтора вместо функции. Однако это поднимает две проблемы.

  1. Как использование функтора вместо этого позволит возвращать накопление двух значений?
  2. У меня есть два метода применения этого алгоритма. Текущий код имеет виртуальный базовый класс, а затем два класса, которые наследуют и реализуют фактический рабочий код. Я не могу понять, как создать «виртуальный функтор», чтобы каждый класс методов мог реализовывать свою собственную версию.

Спасибо!

Ответы [ 2 ]

6 голосов
/ 11 сентября 2011

Вот пример использования функтора для параллельного выполнения двух накоплений. 

struct MyFunctor
{
    // Initialise accumulators to zero
    MyFunctor() : acc_A(0), acc_B(0) {}

    // for_each calls operator() for each container element
    void operator() (const T &x)
    {
        acc_A += x.foo();
        acc_B += x.bar();
    }

    int acc_A;
    int acc_B;
};


// Invoke for_each, and capture the result
MyFunctor func = std::for_each(container.begin(), container.end(), MyFunctor());

[Обратите внимание, что вы также можете рассмотреть возможность использования std::accumulate() с соответствующей перегрузкой для operator+.]

Что касается виртуальных функторов, вы не можете делать это напрямую, поскольку функции STL принимают функторы по значению, а не по ссылке (так что у вас возникнет проблема среза).Вам нужно будет реализовать своего рода «прокси-функтор», который, в свою очередь, содержит ссылку на ваш виртуальный функтор. * В следующих строках: 

struct AbstractFunctor
{
    virtual void operator() (const T &x) = 0;
};

struct MyFunctor : AbstractFunctor
{
    virtual void operator() (const T &x) { ... }
};

struct Proxy
{
    Proxy(AbstractFunctor &f) : f(f) {}
    void operator() (const T &x) { f(x); }
    AbstractFunctor &f;
};

MyFunctor func;
std::for_each(container.begin(), container.end(), Proxy(func));

* СкоттМейерс дает хороший пример этой техники в пункте 38 своего превосходного Эффективного STL .

4 голосов
/ 11 сентября 2011

Три (основных) подхода

Хорошо, в итоге я сделал три (основные) реализации (с небольшими вариациями).Я сделал простой тест, чтобы увидеть, есть ли различия в эффективности.Проверьте раздел тестов внизу

1.std::for_each с лямбдой c ++ 0x

Использование некоторых сочетаний клавиш c ++ 0x: см. http://ideone.com/TvJZd

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

int main()
{
    std::vector<int> a = { 1,2,3,4,5,6,7 };

    int sum=0, product=1;

    std::for_each(a.begin(), a.end(), [&] (int i) { sum+=i; product*=i; });

    std::cout << "sum: " << sum << ", product: " << product << std::endl;

    return 0;
}

Печать 

sum: 28, product: 5040

Как уже упоминалось другимиобычно вы предпочитаете нормальный цикл: 

for (int i: a)
{ sum+=i; product*=i; }

Что на

  • короче,
  • более разборчиво,
  • менее неожиданно(ref-capturing) и
  • , вероятно, более оптимизируемый компилятором

Кроме того, очень близко в non-c ++ 11 / 0x: 

for (std::vector<int>::const_iterator it=a.begin(); it!=a.end(); ++it)
{ sum+=*it; product*=*it; }

2,std::accumulate с рукописным объектом-аккумулятором

Добавлен объект на основе std::accumulate: см. http://ideone.com/gfi2C

struct accu_t
{
    int sum, product;
    static accu_t& handle(accu_t& a, int i)
    {
        a.sum+=i;
        a.product*=i;
        return a;
    }
} accum = { 0, 1 };

accum = std::accumulate(a.begin(), a.end(), accum, &accu_t::handle);

3.std::accumulate с std::tuple

Хорошо, я не удержался.Вот пример с accumulate, но работающий с std::tuple (устраняя необходимость в типе функтора): см. http://ideone.com/zHbUh

template <typename Tuple, typename T>
    Tuple handle(Tuple t, T v)
{
    std::get<0>(t) += v;
    std::get<1>(t) *= v;
    return t;
}

int main()
{
    std::vector<int> a = { 1,2,3,4,5,6,7 };

    for (auto i=1ul << 31; i;)
    {
        auto accum = std::make_tuple(0,1);
        accum = std::accumulate(a.begin(), a.end(), accum, handle<decltype(accum), int>);

        if (!--i)
            std::cout << "sum: " << std::get<0>(accum) << ", product: " << std::get<1>(accum) << std::endl;
    }

    return 0;
}

Тесты:

Измеряется путем накопления2 << 31 раз (см. Фрагмент для варианта на основе std :: tuple).Протестировано только с -O2 и -O3: </p>

  • нет измеримых различий между любым из показанных подходов (0,760 с):

  • все варианты демонстрируют увеличение скорости более чем в 18 раз при переходе от -O2 к-O3 (от 13,8 до 0,760 с), опять же, независимо от выбранной реализации

  • tuple / accumulate производительность остается неизменной с Tuple& handle(Tuple& t, T v) (для справки).
...