8

我正在尝试使用编译时生成的数组来实现一个快速函数调度程序,以便能够在运行时在 O(1) 中使用它。

一些代码行只是为了澄清:

template<int i>
void f()
  {
  // do stuff 
  }

// specialized for every managed integer 
template<>
void f<1>
{
// do stuff
}

Dispatcher<1,5,100,300> dispatcher;  
dispatcher.execute(5); // this should call f<5>()

让我们将 N 称为调度程序的输入数(在本例中为 4),将 M 称为调度程序输入的最大值(在本例中为 300)。

我已经能够创建一个大小等于 M 的数组。这利用了这样一个事实,即在运行时您可以执行以下操作:

dispatcher.execute(5) -> internalArray[5]();

这当然可行,但对于大尺寸的数组是不可行的。

最好的办法是只生成一个包含 N 个元素的数组,并做一些数学技巧将输入索引转换为第二个数组的索引。

在示例中,将 1,5,100,300 分别转换为 0,1,2,3。我已经能够做一种预处理方法来转换它们,但我正在寻找一种方法来避免这一步。

换句话说,我认为我正在寻找某种最小的完美散列,可以在编译时以非常有效的方式用于我的特定情况(理想情况下没有任何开销,例如:goto: MyInstruction)。

我不是在寻找使用虚函数、std::map 或复杂操作的替代方案。

请问有什么不清楚的。

PS我正在使用C++ 11,但欢迎任何想法

[编辑] 我知道标签是 GCC 的值语言扩展。有了这些,我也许可以实现我的目标,但需要一个可移植的解决方案。

4

5 回答 5

7

好吧,我不知道你是否能够做你想做的事。为任何输入创建一个完美的散列函数的代码在我看来很漂亮......不可行。

无论如何,这是编写代码的简单解决方案。它是 C++17,但可以通过一些技巧与 C++11 一起使用。

template<int i> void f();

template <int... Is>
struct Dispatcher
{
    template <int I> constexpr auto execute_if(int i)
    {
        if  (I == i)
            f<I>();
    }

    constexpr auto execute(int i)
    {
        (execute_if<Is>(i), ...);
    }
};

auto test()
{
    Dispatcher<1,5,100,300> dispatcher;  
    dispatcher.execute(5);
}

上面的代码只是一个简单的跳转,因为5它是一个编译时间常数:

test():                               # @test()
        jmp     void f<5>()            # TAILCALL

如果参数是运行时变量,那么它会进行一系列比较:

auto test(int i)
{
    Dispatcher<1,5,100,300> dispatcher;  
    dispatcher.execute(i);
}
test(int):                               # @test(int)
        cmp     edi, 99
        jg      .LBB0_4
        cmp     edi, 1
        je      .LBB0_7
        cmp     edi, 5
        jne     .LBB0_9
        jmp     void f<5>()            # TAILCALL
.LBB0_4:
        cmp     edi, 100
        je      .LBB0_8
        cmp     edi, 300
        jne     .LBB0_9
        jmp     void f<300>()          # TAILCALL
.LBB0_9:
        ret
.LBB0_7:
        jmp     void f<1>()            # TAILCALL
.LBB0_8:
        jmp     void f<100>()          # TAILCALL

可以改进该解决方案以执行二分搜索,但这并不是微不足道的。

于 2018-11-14T11:38:39.050 回答
4

在@bolov 的回答的基础上,可以i通过更改在不是常量时使用任意调度算法:

constexpr auto execute(int i)
{
    (execute_if<Is>(i), ...);
}

至:

constexpr auto execute(unsigned i)
{
    (execute_if<Is>(i), ...);
}

然后添加:

constexpr auto execute (int& i)
{
    // Add arbitrary dispatch mechanism here
}

完整的示例,与 C++11 兼容并在不是常量时使用相当笨重的std::map(最坏情况复杂度 log n) (我放弃了这些东西以使 C++11 中的生活更轻松):iconstexpr

#include <map>
#include <iostream>

std::map <int, void (*) ()> map;

template <int i> void f ();
template <> void f <1> () { std::cout << "f1\n"; }
template <> void f <2> () { std::cout << "f2\n"; }
template <> void f <3> () { std::cout << "f3\n"; }
template <> void f <4> () { std::cout << "f4\n"; }
template <> void f <5> () { std::cout << "f5\n"; }

template <int ... Is>
struct Dispatcher
{
    template <int first> void execute_if (int i)
    {
        if (first == i)
        {            
            std::cout << "Execute f" << i << " via template\n";
            f <first> ();
        }
    }

    template <int first, int second, int... rest> void execute_if (int i)
    {
        if (first == i)
        {            
            std::cout << "Execute f" << i << " via template\n";
            f <first> ();
        }
        else
            execute_if <second, rest...> (i);
    }

    void execute (unsigned i)
    {
        execute_if <Is...> (i);
    }

    void execute (int& i)
    {
        std::cout << "Execute f" << i << " via map\n";
        map.at (i) ();
    }
};

int main()
{
    map [1] = f <1>;
    map [2] = f <2>;
    map [3] = f <3>;
    map [4] = f <4>;
    map [5] = f <5>;

    Dispatcher <1, 2, 4> dispatcher;  
    dispatcher.execute (2);
    int i = 4;
    dispatcher.execute (i);
}

输出:

Execute f2 via template
f2
Execute f4 via map
f4

现场演示


编辑:根据 OP 的要求,这是一个使用二进制搜索而不是std::map. 关键是在构造函数中构建要搜索的数组Dispatcher

#include <vector>
#include <iostream>

template <int i> void f ();
template <> void f <1> () { std::cout << "f1\n"; }
template <> void f <2> () { std::cout << "f2\n"; }
template <> void f <3> () { std::cout << "f3\n"; }
template <> void f <4> () { std::cout << "f4\n"; }
template <> void f <5> () { std::cout << "f5\n"; }

using ve = std::pair <int, void (*) ()>;

template <int ... Is>
struct Dispatcher
{
    template <int first> void execute_if (int i)
    {
        if (first == i)
        {            
            std::cout << "Execute f" << i << " via template\n";
            f <first> ();
        }
    }

    template <int first, int second, int... rest> void execute_if (int i)
    {
        if (first == i)
        {            
            std::cout << "Execute f" << i << " via template\n";
            f <first> ();
        }
        else
            execute_if <second, rest...> (i);
    }

    void execute (unsigned i)
    {
        execute_if <Is...> (i);
    }

    void execute (int& i)
    {
        std::cout << "Execute f" << i << " via binary search\n";
        auto lb = lower_bound (indexes.begin (), indexes.end (), ve (i, nullptr), 
            [] (ve p1, ve p2) { return p1.first < p2.first; });    
        if (lb != indexes.end () && lb->first == i)
            lb->second ();
    }

    template <int first> void append_index ()
    {
        indexes.emplace_back (ve (first, f <first>));
    }

    template <int first, int second, int... rest> void append_index ()
    {
        append_index <first> ();
        append_index <second, rest...> ();
    }

    Dispatcher ()
    {
        append_index <Is...> ();
    }

private:
    std::vector <ve> indexes;
};

int main()
{
    Dispatcher <1, 2, 4> dispatcher;  
    dispatcher.execute (2);
    int i = 4;
    dispatcher.execute (i);
}

现场演示

于 2018-11-14T15:52:40.023 回答
2

OP 要求constexpres遵循 bolov 的解决方案示例的 C++11 解决方案,以保持 -ness。

嗯......我不认为这是一个好主意,因为constexprC++11 中的函数/成员需要递归并返回一个值。并且编译器对模板递归提出了严格的限制,如果N(the sizeof...(Is)) 很高,这可能是一个问题。

无论如何......我能想象的最好的是以下

template <int... Is>
struct Dispatcher
{
    template <typename = void>
    constexpr int execute_h (int) const
     { /* wrong case; exception? */ return -1; }

    template <int J0, int ... Js>
    constexpr int execute_h (int i) const
     { return J0 == i ? (f<J0>(), 0) : execute_h<Js...>(i); }

    constexpr int execute (int i) const
     { return execute_h<Is...>(i); }
};

可以使用,计算f<>()编译时间,如下

void test()
{
    constexpr Dispatcher<1,5,100,300> dispatcher;  
    constexpr auto val1 = dispatcher.execute(5);
    constexpr auto val2 = dispatcher.execute(6);

    std::cout << val1 << std::endl; // print 0 (5 is in the list)
    std::cout << val2 << std::endl; // print -1 (6 isn't in the list)
}

f<>()必须是constexpr,并且在 C++11 中,不能返回void;我用过以下

template <int i>
constexpr int f ()
 { return i; }
于 2018-11-14T14:15:45.380 回答
2

bolov解决方案的一点改进(恕我直言)

写入execute_ifreturn true, whenf<I>()执行, or false, else

template <int I>
constexpr auto execute_if (int i) const
{ return I == i ? f<I>(), true : false; }

而不是使用逗号运算符进行模板折叠

template <int ... Is>
constexpr auto execute(int i) const
 { (execute_if<Is>(i), ...); }

我们可以使用 or ( ||) 运算符

template <int ... Is>
constexpr auto execute(int i) const
 { (execute_if<Is>(i) || ...); }

使用逗号操作符,execute_is<Is>(i)永远被调用Is,当第一个Is等于i;时也是如此。使用||我们有短路,也就是说,execute_is<Is>(i)只有在我们得到一个Is等于 时才会调用它i

于 2018-11-14T17:36:21.740 回答
0

理论上(!)您可以使用 C++ 模板创建完美的哈希函数。

  • 这个问题有关于如何创建完美哈希函数的代码(使用蛮力,所以它只适用于相对较小的集合)。
  • 这个问题表明C++模板是图灵完备的,所以应该可以将上面的代码转换成C++模板。
  • 甚至可以使用C preprocessor,因为它不需要无限循环。

但我认为这样做是相当困难的。

于 2019-05-09T09:37:04.477 回答