2

同じインターフェイスを実装するオブジェクトのベクトルの効率的なアクセスを実装する必要があります。今までは、仮想関数で継承を使用していました。インターフェイスは、純粋仮想関数を持つ抽象クラスとして定義され、オブジェクトの各クラスは仮想関数を実装します。オブジェクトのベクトルは、単純に抽象クラスのポインターのベクトルです (動的な訪問の例については、メッセージの最後を参照してください)。

オブジェクト コレクションにすばやくアクセスする必要があります。私はコンパイル時にオブジェクトのすべての可能なクラスを知っているので、boost::variant を使用してオブジェクトのコレクション (つまり、boost::variant のベクトル) を実装しました。コレクションを通過するには、ビジター スキームの追加定義が必要です。すべてのオブジェクトが同じインターフェイスを実装していることを明示するために、CRTP を使用して静的継承を取得しました。インターフェイスは CRTP 抽象化であり、オブジェクトの各クラスはテンプレート化された CRTP 抽象クラスから派生しています。

CRTP 実装の例を次に示します。インターフェイスは、2 つの関数f()と を定義するだけg(double)です。2 つの派生クラスがあり、インターフェイスC1C2実装しています (動作は同じです)。

#include <vector>
#include <boost/foreach.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/variant.hpp>

namespace testVariantSimple
{

  // Definition of the interface (abstract class).
  template< typename C >
  struct CBase
  {
    void f() { static_cast<C&>(*this).f(); }
    int g(const double & x) { return static_cast<C&>(*this).g(x); }
  };

  // Definition of the first implementation.
  struct C1 : public CBase<C1>
  {
    void f();
    int g(const double & x);
  };
  void C1::f() { return ; }
  int C1::g(const double & x) { return sizeof(x); }

  // Definition of the second implementation.        
  struct C2 : public CBase<C2>
  {
    void f();
    int g(const double & x);
  };
  void C2::f() { return ; }
  int C2::g(const double & x) { return sizeof(x); }

  // Definition of the visitor for the first function of the interface.  
  class f_visitor : public boost::static_visitor<int>
  {
  public:
    template< typename C >
    int operator()(CBase<C> &c ) const { c.f(); return 0; }
  };

  // Definition of the visitor for the second function of the interface.  
  struct g_visitor : public boost::static_visitor<int>
  {
    const double & x;
    g_visitor( const double & x ) : x(x) {}
  public:
    template< typename C >
    int operator()(CBase<C> & c) const { return c.g(x);  }
  };

  // Example of use: construct a random collection and visit it.
  void test(int nbSample)
  {
    typedef boost::variant<C1,C2> CV;
    std::vector<CV> vec;

    for( int i=0;i<nbSample;++i ) 
      {
    switch( std::rand() % 2 )
      {
      case 1:       vec.push_back( C1() ); break;
      case 2:       vec.push_back( C2() ); break;
      }
      }

    double argdouble;
    BOOST_FOREACH(CV & c, vec)
      {
    boost::apply_visitor( f_visitor(), c );
    g_visitor g(argdouble);
    boost::apply_visitor( g, c );
      }
  }
}

このコードは機能し、動的継承を使用するコードよりも 15 倍効率的です (動的を使用するコードについては、メッセージの最後を参照してください)。CRTP に慣れていない人にとっては、コードを読むのは少し難しくなりますが、維持したり書いたりするのは難しくありません。インターフェイスは CRTP で明示的であるため、ビジターの実装はかなり単純ですが、冗長であり、理解するのも使用するのも面倒です。

私の質問は簡単です: CRTP インターフェイスから自動的に訪問者を定義することは可能ですか? f_visitorandの余分な定義を避け、次のg_visitorような読みやすい外観を得たいと思います。

   BOOST_FOREACH( CV & c, vec )
   {
      c.f();
      c.g(argdouble);
   }

ご協力いただきありがとうございます。興味のある読者のために、仮想継承を使用した同じコードを次に示します。

namespace testDynamicSimple
{
  struct CBase
  {
    virtual void f() = 0;
    virtual int g(const double & x) = 0;
  };

  struct C1 : public CBase  
  {
    void f() {}
    int g(const double & x) { return 1; }
  };
  struct C2 : public CBase
  {
    void f() {}
    int g(const double & x) { return 2; }
  };

  bool test(int nbSample)
  {
    typedef boost::shared_ptr<CBase> CV;
    std::vector<CV> vec;
    for( int i=0;i<nbSample;++i ) 
      {
    switch( std::rand() % 5 )
      {
      case 1:       vec.push_back( CV(new C1()) ); break;
      case 2:       vec.push_back( CV(new C2()) ); break;
      }
      }

    double argdouble = 0.0;
    BOOST_FOREACH( CV & c, vec)
    {
      c->f();
      c->g(argdouble);
    }
  }
}
4

1 に答える 1

1

免責事項:これは答えではなく、特定の問題を解決するために使用できるさまざまなアプローチのベンチマークにすぎません。

アイデアは、boost::variant他の手法 (生ポインターの仮想関数、共有ポインターの仮想関数、および他のいくつかの手法) と比較することです。私が使用したベンチマークコードは次のとおりです。

#include <vector>
#include <boost/foreach.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/variant.hpp>
#include <memory>
#include <type_traits>

namespace novirtual {

  struct C {
    void f() {}
    int g(const double &x) { return 1; }
  };

  void test(int nbSample) {

    std::vector<C> vec;
    vec.reserve(nbSample);
    for (int i = 0; i < nbSample; ++i)
      vec.emplace_back(C());

    double argdouble = 0.0;
    BOOST_FOREACH(C &c, vec) {
      c.f();
      c.g(argdouble);
    }
  }
}
namespace crtp {

// Definition of the interface (abstract class).
template <typename C> struct CBase {
  void f() { static_cast<C &>(*this).f(); }
  int g(const double &x) { return static_cast<C &>(*this).g(x); }
};

// Definition of the first implementation.
struct C1 : public CBase<C1> {
  void f();
  int g(const double &x);
};
void C1::f() { return; }
int C1::g(const double &x) { return sizeof(x); }

// Definition of the second implementation.
struct C2 : public CBase<C2> {
  void f();
  int g(const double &x);
};
void C2::f() { return; }
int C2::g(const double &x) { return sizeof(x); }

// Definition of the visitor for the first function of the interface.
class f_visitor : public boost::static_visitor<int> {
public:
  template <typename C> int operator()(CBase<C> &c) const {
    c.f();
    return 0;
  }
};

// Definition of the visitor for the second function of the interface.
struct g_visitor : public boost::static_visitor<int> {
  const double &x;
  g_visitor(const double &x) : x(x) {}

public:
  template <typename C> int operator()(CBase<C> &c) const { return c.g(x); }
};

// Example of use: construct a random collection and visit it.
void test(int nbSample) {
  typedef boost::variant<C1, C2> CV;
  std::vector<CV> vec;
  vec.reserve(nbSample);
  for (int i = 0; i < nbSample; ++i) {
    switch (std::rand() % 2) {
    case 0:
      vec.push_back(C1());
      break;
    case 1:
      vec.push_back(C2());
      break;
    }
  }

  double argdouble;
  BOOST_FOREACH(CV & c, vec) {
    boost::apply_visitor(f_visitor(), c);
    g_visitor g(argdouble);
    boost::apply_visitor(g, c);
  }
}
}

namespace virt_fun {
struct CBase {
  virtual void f() = 0;
  virtual int g(const double &x) = 0;
};

struct C1 : public CBase {
  void f() {}
  int g(const double &x) { return 1; }
};
struct C2 : public CBase {
  void f() {}
  int g(const double &x) { return 2; }
};

void test(int nbSample) {
  std::vector<CBase *> vec;
  vec.reserve(nbSample);
  for (int i = 0; i < nbSample; ++i) {
    switch (std::rand() % 2) {
    case 0:
      vec.push_back(new C1());
      break;
    case 1:
      vec.push_back(new C2());
      break;
    }
  }

  double argdouble = 0.0;
  BOOST_FOREACH(CBase * c, vec) {
    c->f();
    c->g(argdouble);
  }
}
}

namespace shared_ptr {
struct CBase {
  virtual void f() = 0;
  virtual int g(const double &x) = 0;
};

struct C1 : public CBase {
  void f() {}
  int g(const double &x) { return 1; }
};
struct C2 : public CBase {
  void f() {}
  int g(const double &x) { return 2; }
};

void test(int nbSample) {
  typedef boost::shared_ptr<CBase> CV;
  std::vector<CV> vec;
  vec.reserve(nbSample);
  for (int i = 0; i < nbSample; ++i) {
    switch (std::rand() % 2) {
    case 0:
      vec.push_back(CV(new C1()));
      break;
    case 1:
      vec.push_back(CV(new C2()));
      break;
    }
  }

  double argdouble = 0.0;
  BOOST_FOREACH(CV & c, vec) {
    c->f();
    c->g(argdouble);
  }
}
}

namespace virt_cont {

struct CBase {
  virtual void f() = 0;
  virtual int g(const double &x) = 0;
  virtual ~CBase() = default;
};

struct C1 final : public CBase {
  void f() {}
  int g(const double &x) { return 1; }
};
struct C2 final : public CBase {
  void f() {}
  int g(const double &x) { return 2; }
};

struct foo {
  std::aligned_storage<sizeof(C2)>::type buf;
  CBase *ptr;

  foo(C1 c) { ptr = new ((void *)&buf) C1(c); }
  foo(C2 c) { ptr = new ((void *)&buf) C2(c); }

  foo(foo &&x) : buf(x.buf) { ptr = reinterpret_cast<CBase *>(&buf); } // UB

  foo &operator=(foo &&x) {
    buf = x.buf;
    return *this;
  } // maybe UB?

  ~foo() { ptr->~CBase(); }
};
void test(int nbSample) {
  std::vector<foo> vec;
  vec.reserve(nbSample);
  for (int i = 0; i < nbSample; ++i) {
    switch (std::rand() % 2) {
    case 0:
      vec.emplace_back(C1());
      break;
    case 1:
      vec.emplace_back(C2());
      break;
    }
  }

  double argdouble = 0.0;
  BOOST_FOREACH(foo & c, vec) {
    c.ptr->f();
    c.ptr->g(argdouble);
  }
}
}

namespace locals {
struct CBase {
  virtual void f() = 0;
  virtual int g(const double &x) = 0;
  virtual ~CBase() = default;
};

struct C1 final : public CBase {
  void f() {}
  int g(const double &x) { return 1; }
};
struct C2 final : public CBase {
  void f() {}
  int g(const double &x) { return 2; }
};

void test(int nbSample) {
  C1 c1;
  C2 c2;

  std::vector<CBase *> vec;
  vec.reserve(nbSample);
  for (int i = 0; i < nbSample; ++i) {
    switch (std::rand() % 2) {
    case 0:
      vec[i] = &c1;
      break;
    case 1:
      vec[i] = &c2;
      break;
    }
  }

  double argdouble = 0.0;
  BOOST_FOREACH(CBase * c, vec) {
    c->f();
    c->g(argdouble);
  }
}
}

#include <chrono>
#include <string>

#define VER 4

int main(int argc, char *argv[]) {

  int n = 100000;
  for (int i = 0; i < 4; ++i) {

    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();

#if VER == 0
    virt_fun::test(n);
#elif VER == 1
    shared_ptr::test(n);
#elif VER == 2
    crtp::test(n);
#elif VER == 3
    virt_cont::test(n);
#elif VER == 4
    locals::test(n);
#endif

    end = std::chrono::system_clock::now();

    std::chrono::duration<double> elapsed_seconds = end - start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);

    std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";

    n *= 10;
  }
  return 0;
}

コードは次のようにコンパイルされましclang++ -O3 main.cpp -I/Users/aaragon/Local/includeた。

$ clang++ --version
Apple LLVM version 5.1 (clang-503.0.40) (based on LLVM 3.4svn)
Target: x86_64-apple-darwin13.3.0
Thread model: posix

2.6 GHz Intel Core i7プロセッサと16 GB 1600 MHz DDR3 RAMを搭載した Macbook Pro で動作します。

これらの結果は、元のコードのバグ修正に加えて、@dyp によって提供された、std::aligned_storage. 以下の表では、no virtual列は継承がまったくないことに対応しており、参考として示されています。

  |    size   | no virtual| raw ptr   | shared_ptr |  variant  | wrapper   |  locals   |
  |-----------|-----------|------------|-----------|-----------|-----------|-----------|
  |    100000 | 0.000235s | 0.008309s |  0.030801s | 0.003935s | 0.004222s | 0.001925s |
  |   1000000 | 0.002053s | 0.061843s |  0.288403s | 0.029874s | 0.033697s | 0.01478s  |
  |  10000000 | 0.017687s | 0.627659s |  2.91868s  | 0.29699s  | 0.322109s | 0.141245s |
  | 100000000 | 0.177425s | 6.2493s   | 28.9586s   | 3.00427s  | 3.21402s  | 1.40478s  |

この段階では、非常に遅く、 とラッパーboost::shared_ptrの間に明確な勝者がないことは確かです。boost::variant

于 2014-08-19T09:16:14.890 に答える