如何高效识别字符串命令？

Question

给定一系列命令和非常独特的代码，每个代码必须运行：

if(cmd == "cmd.setBoosterRocket")
    ...
else if(cmd == "cmd.windSales")
    ...
else if(cmd == "cmd.selfDustruct")
    ...
else if(cmd == "cmd.unleashHounds")
    ...

如何优化？放入switch语句，即?

我考虑制作一个哈希向量：

std::hash<std::string> hasher;
for(std::string command : m_commandList)
    m_mashes.push_back(hasher(command)

但是向量不能作为 switch case 语句的一部分访问，因为它不是 constexpr。字符串命令列表在编译时是已知的，我可能会对哈希值进行硬编码……但这似乎不是一个好主意。

Answer 1

一种可能的方法是标记化：创建一个 enum 类型和一个字典。通过这种方式，您可以利用开关（以比硬编码哈希对程序员和编译器更友好的方式）并且只有对数复杂度。

enum Command {SET_BOOSTER_ROCKET, WINDSALES, ETC};
const std::map<std::string, Command> commands = {
  {"cmd.setBoosterRocket", SET_BOOSTER_ROCKET},
  {"cmd.windsales", WINDSALES},
  {"othercommands", ETC},
};

然后

auto cmd_it = commands.find(cmd);
if(cmd_it == commands.end()) { // ERROR }
switch(cmd_it->second){
  case SET_BOOSTER_ROCKET:
    // your code
  break;
  case WINDSALES:
    // your code
  break;
  // etc
}

如果您有很多事情要开始，那么像这样标记您的命令可能会有点乏味，但它在可扩展性和可读性之间取得了很好的平衡。

Answer 2

好吧，为您的用例编写一个简单的哈希函数：

static constexpr hasher = [](auto&& s){ return char(s.size() < xyz ? 0 : expr); };

如果您的 std::string 使用 SBO（几乎所有人都这样做），您还可以利用您的 std::string 具有最小保留大小的优势，并放弃上面的大小检查以获得更高的性能。

将结果保持在明显的严格范围内，以使编译器支持跳转-table。

接下来，使用宏来避免重复：

#define CASE(s) \
        break; \
    case hasher(s): \
        if (std::string_view(s) != cmd) \
            break;

是的，您不能使用（错误？）功能失败。如果您真的想要其中之一，请使用goto。

现在您可以编写 switch 语句了：

switch (hasher(cmd)) {
CASE("cmd.setBoosterRocket")
    ...
CASE("cmd.windSales")
    ...
CASE("cmd.selfDustruct")
    ...
CASE("cmd.unleashHounds")
    ...
...
}

大多数编译器会就重复的 case 语句向您发出警告，因此 fiddle 使用散列，直到您获得便宜、独特且紧密绑定的散列。

不要忘记#undef CASE限制宏范围。

Answer 3

另一种方法是创建单独的函数来处理每种情况，然后创建一个地图作为“调度程序”：

const static std::unordered_map<std::string, void(*)()> dispatcher{ 
   { "cmd.setBoosterRocket",  &setBoosterRocketHandler },
   { "cmd.windSales",  &windSalesHandler },
   { "cmd.selfDustruct",  &selfDustructHandler },
   { "cmd.unleashHounds",  &sunleashHoundsHandler },
};

auto const it = dispatcher.find(cmd);

if (it == dispatcher.end()) { /* handle default case */ }
else { (*it)(); }

Answer 4

使用 C++20，constexpr 可用于定义 index-lambda 以提高效率。

static constexpr auto commands = { "cmd.setBoosterRocket", "cmd.windSales", ... };

constexpr auto index = [&](std::string s) -> size_t { /*...*/ };

switch(quick_index(cmd))
{
    case index("cmd.setBoosterRocket"):
        // ...
        break;

    default:
        // ...
        break;
}

对于 quick_index，不必是 constexpr，您可以例如使用 unordered_map 在 O(1).

中查找字符串的索引

这是一个使用二进制搜索的完整示例（constexpr，因此它可以同时用于 index 和 quick_index）。

#include <algorithm>
#include <array>
#include <iostream>
#include <string_view>

using namespace std;

template<class ForwardIt, class T, class Compare = std::less<>>
constexpr ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp = {})
{
   first = std::lower_bound(first, last, value, comp);
   return first != last && !comp(value, *first) ? first : last;
}

int main()
{
    constexpr auto sorted = [](array<string_view, 3> a) {sort(a.begin(), a.end()); return a;};
    
    static constexpr auto commands = sorted({ "bar", "foo", "foobar" });
    
    constexpr auto index = [&](string_view s)
        { return binary_find(commands.begin(), commands.end(), s)-commands.begin(); };

    string_view cmd = "bar";

    switch(index(cmd))
    {
        case index("bar"):
            cout << "bartender" << endl;
            break;

        case index("foo"):
            cout << "fighter" << endl;
            break;

        case index("foobar"):
            cout << "fighter bartender" << endl;
            break;
            
        default:
            cout << "moo" << endl;
            break;
    }
}

如何高效识别字符串命令？

How to efficiently identify string commands?

c++

string

hash

performance