开发者

Most effective method of executing functions an in unknown order

开发者 https://www.devze.com 2023-04-03 08:42 出处:网络
Let\'s say I have a large, between 50 and 200, pool of individual functions whose job it is to operate on a single object and modify it.The pool of functions is selectively put into a single array and

Let's say I have a large, between 50 and 200, pool of individual functions whose job it is to operate on a single object and modify it. The pool of functions is selectively put into a single array and arranged in an arbitrary order.

The functions themselves take no arguments outside of the values present within the object it is modifying, and in this way the object's behavior is determined only by which functions are executed and in what order.

A way I have tentatively used so far is this, which might explain better what my goal is:

class Behavior{
    public:
    virtual void act(Object * obj) = 0;
};

class SpecificBehavior : public Behavior{
    // many classes like this exist
    public:
    void act(Object * obj){ /* do something specific with obj*/ };
};

class Object{
    public:
    std::list<Behavior*> behavior;

    void behave(){
        std::list<Behavior*>::iterator iter = behavior.front();
        while(iter != behavior.end()){
             iter->act(this);
             ++iter;
        };
    };
};

My Question is, what is the most efficient way in C++ of organizing such a pool of functions, in terms of performance and maintainability. This is for some A.I research I am doing, and this methodology is what most closely matches what I am trying to achieve.

edits: The array itself can be changed at any time by any other part of the code not listed here, but it's guaranteed to never change during the call to behave(). The array it is stored in needs to 开发者_如何学Gobe able to change and expand to any size


If the behaviour functions have no state and only take one Object argument, then I'd go with a container of function objects:

#include <functional>
#include <vector>

typedef std::function<void(Object &)> BehaveFun;
typedef std::vector<BehaveFun> BehaviourCollection;

class Object {
  BehaviourCollection b;

  void behave() {
    for (auto it = b.cbegin(); it != b.cend(); ++it) *it(*this);
  }
};

Now you just need to load all your functions into the collection.


if the main thing you will be doing with this collection is iterating over it, you'll probably want to use a vector as dereferencing and incrementing your iterators will equate to simple pointer arithmetic.

If you want to use all your cores, and your operations do not share any state, you might want to have a look at a library like Intel's TBB (see the parallel_for example)


I'd keep it exactly as you have it. Perofmance should be OK (there may be an extra indirection due to the vtable look up but that shouldn't matter.)

My reasons for keeping it as is are:

  1. You might be able to lift common sub-behaviour into an intermediate class between Behaviour and your implementation classes. This is not as easy using function pointers.

    struct AlsoWaveArmsBase : public Behaviour 
    {
       void act( Object * obj )
       {
          start_waving_arms(obj); // Concrete call
          do_other_action(obj);   // Abstract call
          end_waving_arms(obj);   // Concrete call
       }
       void start_waving_arms(Object*obj);
       void end_waving_arms(Object*obj);
       virtual void do_other_actions(Object * obj)=0;
    };
    
    struct WaveAndWalk : public AlsoWaveArmsBase
    {
       void do_other_actions(Object * obj) { walk(obj); }
    };
    
    struct WaveAndDance : pubic AlsoWaveArmsBase
    {
       void do_other_actions(Object * obj) { walk(obj); }    
    }
    
  2. You might want to use state in your behaviour

    struct Count : public Behavior
    {
       Behaviour() : i(0) {}
       int i;
       void act(Object * obj)
       {
          count(obj,i);
          ++i;
       }
    }
    
  3. You might want to add helper functions e.g. you might want to add a can_act like this:

    void Object::behave(){
      std::list<Behavior*>::iterator iter = behavior.front();
      while(iter != behavior.end()){
         if( iter->can_act(this) ){
            iter->act(this);
         }
         ++iter;
       };
     };
    

IMO, these flexibilities outweigh the benefits of moving to a pure function approach.


For maintainability, your current approach is the best (virtual functions). You might get a tiny little gain from using free function pointers, but I doubt it's measurable, and even if so, I don't think it is worth the trouble. The current OO approach is fast enough and maintainable. The little gain I'm talking about comes from the fact that you are dereferencing a pointer to an object and then (behind the scenes) dereferencing a pointer to a function (which happening as the implementation of calling a virtual function).

I wouldn't use std::function, because it's not very performant (though that might differ between implementations). See this and this. Function pointers are as fast as it gets when you need this kind of dynamism at runtime.

If you need to improve the performance, I suggest to look into improving the algorithm, not this implementation.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号