logo标签列表

我该如何优化一个多重（矩阵）开关/案例算法？

algorithmmatrixswitch-statement
5

这种（矩阵）算法是否可以进行优化：

//        | case 1 | case 2 | case 3 |
//  ------|--------|--------|--------|
//        |        |        |        |
//  case a|   a1   |   a2   |   a3   |
//        |        |        |        |
//  case b|   b1   |   b2   |   b3   |
//        |        |        |        |
//  case c|   c1   |   c2   |   c3   |
//        |        |        |        |

switch (var)
    {
      case 1:
      switch (subvar)
      {
        case a:
          process a1;
        case b:
          process b1;    
        case c:
          process c1;
      }
      case 2:
      switch (subvar)
      {
        case a:
          process a2;
        case b:
          process b2;    
        case c:
          process c2;
      }
      case 3:
      switch (subvar)
      {
        case a:
          process a3;
        case b:
          process b3;    
        case c:
          process c3;
      }
    }

这段代码相当简单，但是随着更多的“switch / case”，你需要想象更复杂的情况。

我使用了3个变量。根据它们取值为1、2、3或a、b、c或alpha、beta、charlie，有不同的处理过程。除了通过一系列“switch / case”来优化之外，还有其他方法吗？

（问题已经在此处用法语提出。）

编辑：（从Dran Dane对下面评论的回应中得出。这些也可以在这个更重要的地方！）
“优化”是指编写更少的代码，减少“switch / case”的数量。这个想法是为了提高可读性、可维护性，而不是性能。

也许有一种通过“责任链”来写更少的代码的方法，但这种解决方案并不是在所有方面都最优的，因为它需要创建许多内存中的对象。

1
当你说“优化”时，你究竟想要优化什么？可读性、性能、代码大小、可维护性？从你的写作方式来看，这应该已经从性能的角度相当快了。 - SingleNegationElimination
TokenMacGuy，我简直不敢相信你不明白他想要什么 :) - Valentin Golev
当我谈到“优化”时，我首先考虑的是写更少的代码，少用“switch / case”。我想提高可读性、可维护性，而不是性能。 - Bastien Vandamme
我认为可以通过“责任链”来减少代码量，但这种解决方案并非在所有情况下都是最优的。我认为这是因为它需要在内存中创建许多对象。 - Bastien Vandamme
@Dran - 当您使用“优化”一词来指代提高可读性/可维护性而非性能时，您使用的术语与大多数软件工程师所期望的完全相反。这不是一个好主意。 - Stephen C
显示剩余2条评论
11个回答
14
看起来你需要的是一个'有限状态机'，通过使用这些情况，你可以激活不同的进程或“状态”。在C语言中，通常使用函数指针数组（矩阵）来实现此目的。
因此，你可以创建一个数组，并在正确的索引处放置正确的函数指针，然后使用你的“var”作为正确“process”的索引，然后调用它。你可以在大多数语言中完成这个过程。这样，机器的不同输入会激活不同的进程并将其带入不同的状态。这对于许多应用非常有用；我自己在MCU开发中经常使用它。
编辑：Valya指出我可能应该展示一个基本模型：
stateMachine[var1][var2]();   // calls the right 'process' for input var1, var2
4
抱歉，我会删除我的回答。 - Valentin Golev
2
非常感谢，这里很少见到这种成熟的态度，真希望我能给你点赞。 - Robert Massaioli
这比使用 switch 更快吗？（我不确定编译器如何优化 switch，但是，通过使用带有指针的矩阵，您需要进行一次额外的内存访问以将函数指针从矩阵中提取出来并使用，还需要为该函数作用域分配内存，这是否实际上比移动 switch 更快？）在我看来，使用矩阵+函数指针，您可以通过两个索引的乘法获得正确的函数，然后执行正确的函数，而如果 switch 没有以任何方式优化，则需要进行多个 if/else 比较。 - Fernando Barbosa Gomes
如果矩阵实际上是一个大小为WxH的一维数组，并且通过形式为inline int p2d(x,y,rowLength){ return x + y*rowLength}; 的内联函数计算数组中的位置，访问方式为functionArrayp2d(var1,var2,rowLength); 那么速度会稍微快一些。这将导致少一次内存访问以获取函数地址，代价是一次乘法运算（比内存访问快得多）。 - Fernando Barbosa Gomes
5

这个问题没有好的答案 :-(

因为回答的很多取决于：

  • 有效目标（“优化”是什么意思，嵌套开关有什么不好）
  • 应用这个结构的上下文（应用程序的隐含需求是什么）

TokenMacGuy提出了关于目标的明智问题。我花时间在法国网站上检查了问题及其回复，对目标仍然感到困惑...... Dran Dane最新的回复似乎指向减少代码量/提高可读性，但让我们确认一下：

  • 处理速度：嵌套开关非常高效，可能只需要不到3次乘法就可以得到映射表中的索引，但可能并非如此。
  • 可读性：是的，可能是一个问题。随着变量和级别的增加，组合爆炸会发生，并且开关语句的格式倾向于将分支点和相关值分散在一个长的垂直跨度上。在这种情况下，使用初始化为fct的指针的三维（或更高维）表格将分支值和要调用的函数重新组合成单行。
  • 编写更少的代码：抱歉，在这里帮不上太多忙；归根结底，我们需要考虑相对较高的组合数量，“映射”，无论其形式如何，都必须写在某个地方。像TokenMacGuy这样的代码生成器可能会有所帮助，在这种情况下似乎有点过度杀伤力。生成器有其用处，但我不确定这种情况是否适用。两种情况之一：如果变量和级别的数量足够小，则生成器不值得使用（设置它的时间比首次编写实际代码更长），如果变量和级别的数量很大，则生成的代码很难阅读、难以维护......

简而言之，我的建议是采用法国网站上描述的表/矩阵方法来使代码更易读（并且更快地编写）。

这个解决方案分为两部分：
三维数组（3级）的一次性初始化；（或者，如果喜欢，可以使用“更花哨”的容器结构：例如树）。这可以通过以下代码完成：

// This is positively more compact / readable
...
FctMap[1][4][0] = fctAlphaOne;
FctMap[1][4][1] = fctAlphaOne;
..
FctMap[3][0][0] = fctBravoCharlie4;
FctMap[3][0][1] = NULL;   // impossible case
FctMap[3][0][2] = fctBravoCharlie4;    // note how the same fct may serve in mult. places

并且一个相对简单的代码片段，无论何时需要调用这些函数：

if (FctMap[cond1][cond2][cond3]) {
  retVal = FctMap[cond1][cond2][cond3](Arg1, Arg2);
  if (retVal < 0)
      DoSomething(); // anyway we're leveraging the common api to these fct not the switch alternative ....
}

如果组合空间相对稀疏（开关“树”中的许多“分支”未被使用）或某些功能需要不同的参数集，则可能会促使人们不使用上述解决方案; 对于这两种情况，我想提出 Joel Goodwin 最初在此处提出的解决方案，它基本上将几个级别的各种键组合成一个更长的键（如果需要，使用分隔符字符），从而将问题“展平”为一个长但单一级别的开关语句。
现在...
实际讨论应该是关于我们为什么需要这样的映射/决策树。要回答这个问题，需要了解底层应用程序的真正性质。当然，我并不是说这表明设计不良。在某些应用程序中，大型调度部分可能是有意义的。但是，即使使用 C 语言（法国站点的贡献者似乎将其淘汰为面向对象设计），也可以采用面向对象的方法和模式。无论如何，我偏离了主题...）可能应用程序整体上采用替代设计模式会更好，其中“关于何时调用什么”的信息树已分布在几个模块和/或几个对象中。
抱歉用比较抽象的术语来谈论这个问题，只是因为缺乏具体应用程序的细节... 重点仍然是：质疑我们需要这个大型调度树的想法；考虑应用程序整体的替代方法。
祝你好运！;-)
4

根据语言不同，以(var, subvar)为键、一级函数作为值的哈希表（或者使用最适合您所用语言的方式来近似模拟，例如Java中实现某个适当接口的类的实例）可能会提供最佳性能。从该哈希表中根据相应的键获取函数（或其他内容），并执行它，这种方法的极简洁和高度可读性，对于熟悉该语言和此类函数习惯用法的读者非常友好。

1
函数指针的概念可能是最好的选择（如 mjv、Shhnap 所述）。但是，如果每个 case 下的代码相当简短，那么使用函数指针可能会过度设计，导致比预期更加混乱。在这种情况下，我可能会实现一些简洁易读的东西，例如：
string decision = var1.ToString() + var2.ToString() + var3.ToString();
switch(decision)
{
    case "1aa":
        ....
    case "1ab":
        ....

}

由于不熟悉您的具体情况，也许之前的建议更为恰当。

我认为这个问题是关于C#的（因此大量使用ToString），至少这是我从法语页面中获得的信息。而且我不会说任何法语。 =）但是你的观点对于C++来说是正确的，你将被迫使用不愉快的枚举来使用这种“简写”逻辑。 - Joel Goodwin
1

是的，有一种更简单、更快速、更简洁的方法来解决这个问题。这个想法基本上与Alex Martelli提出的相同。不再将您的问题看作是二维的，而是将其视为一个一维查找表。

这意味着将var、subvar、subsubvar等组合起来，获取一个唯一的键并将其用作查找表入口。

具体的实现方式取决于所使用的编程语言。在Python中，只需将var、subvar等组合为元组，并将其用作字典键即可。

对于C或类似的语言，通常较简单的做法是将每个键转换为枚举，然后使用逻辑运算符将它们组合成一个数字，这样您就可以在switch语句中使用它（这也是使用switch而不是字符串比较和级联ifs的简单方法）。这样做还可以获得其他好处。最初switch的不同分支中通常会有几个相同的处理。使用最初的形式很难使它明显。您可能有一些对同一函数的调用，但它们在代码中的不同位置。现在，您只需要在编写switch语句时将相同的情况分组即可。

我在生产代码中多次使用了这样的转换，它易于实现和维护。

总之，你可以得到类似这样的东西...混合函数显然取决于你的应用程序具体情况。

switch (mix(var, subvar))
{
      case a1:
          process a1;
      case b1:
          process b1;    
      case c1:
          process c1;
      case a2:
          process a2;
      case b2:
          process b2;    
      case c2:
          process c2;
      case a3:
          process a3;
      case b3:
          process b3;    
      case c3:
          process c3;
}
1

我曾经遇到过完全相同的问题，尽管是针对一个五个参数嵌套开关的混乱情况。我想，为什么要自己打这些O(N5)的情况呢？为什么要发明“嵌套”函数名称，如果编译器可以为我完成这个任务。所有这些都导致了一个“嵌套专用模板开关”，引用了一个“专用模板数据库”。

写起来有点复杂。但我发现它很值得：它产生了一个非常容易维护、调试、添加等的“知识”数据库......而且我必须承认：一种自豪感。

// the return type: might be an object actually _doing_ something
struct Result {
  const char* value;
  Result(): value(NULL){}
  Result( const char* p ):value(p){};
};

一些用于开关的变量类型：

 // types used:
 struct A { enum e { a1, a2, a3 }; };
 struct B { enum e { b1, b2 }; };
 struct C { enum e { c1, c2 }; };

知识库的“前向声明”：嵌套开关的“API”。
 // template database declaration (and default value - omit if not needed)
 // specializations may execute code in stead of returning values...
 template< A::e, B::e, C::e > Result valuedb() { return "not defined"; };

实际的切换逻辑（简明版）

 // template layer 1: work away the first parameter, then the next, ...
 struct Switch {

   static Result value( A::e a, B::e b, C::e c ) {
     switch( a ) {
          case A::a1: return SwitchA<A::a1>::value( b, c );
          case A::a2: return SwitchA<A::a2>::value( b, c );
          case A::a3: return SwitchA<A::a3>::value( b, c );
          default: return Result();
     }
   }

   template< A::e a > struct SwitchA {

     static Result value( B::e b, C::e c ) {
       switch( b ) {
            case B::b1: return SwitchB<a, B::b1>::value( c );
            case B::b2: return SwitchB<a, B::b2>::value( c );
            default: return Result();
       }
     }

     template< A::e a, B::e b > struct SwitchB {

       static Result value( C::e c ) {
         switch( c ) {
               case C::c1: return valuedb< a, b, C::c1 >();
               case C::c2: return valuedb< a, b, C::c2 >();
               default: return Result();
         }
       };
     };

   };
 };

还有知识库本身

 // the template database
 //
 template<> Result valuedb<A::a1, B::b1, C::c1 >() { return "a1b1c1"; }
 template<> Result valuedb<A::a1, B::b2, C::c2 >() { return "a1b2c2"; }

这是它的使用方式。

int main()
{
     // usage:
     Result r = Switch::value( A::a1, B::b2, C::c2 ); 
     return 0;
}
0

来自 developpez.com 的解决方案： 是的，您可以进行优化并使其更加简洁。您不能在工厂中使用这样的“职责链”：

public class ProcessFactory {
    private ArrayList<Process> processses = null;

    public ProcessFactory(){
        super();

        processses = new ArrayList<Process>();

        processses.add(new ProcessC1());
        processses.add(new ProcessC2());
        processses.add(new ProcessC3());
        processses.add(new ProcessC4());                    
        processses.add(new ProcessC5(6));                   
        processses.add(new ProcessC5(22));
    }

    public Process getProcess(int var, int subvar){
        for(Process process : processses){
            if(process.canDo(var, subvar)){
                return process;
            }
        }

        return null;
    }
}

那么，就像您的进程实现了一个带有canXXX接口的进程一样，您可以轻松使用：

new ProcessFactory().getProcess(var,subvar).launch();
0
也许你想要的是代码生成吗？
#! /usr/bin/python
first = [1, 2, 3]
second = ['a', 'b', 'c']

def emit(first, second):
    result = "switch (var)\n{\n"
    for f in first:
        result += " case {0}:\n switch (subvar)\n {{\n".format(f)
        for s in second:
            result += "  case {1}:\n   process {1}{0};\n".format(f,s)
        result += " }\n"
    result += "}\n"
    return result

print emit(first,second)
#file("autogen.c","w").write(emit(first,second))

这很难读，当然，你可能真的想要一个更好的模板语言来完成你的肮脏工作，但这将简化你任务的一些部分。

0

如果你只是想消除两级的开关/情况语句（并节省一些垂直空间），你可以将两个变量值编码为单个值，然后在其上进行切换：

// Assumes var is in [1,3] and subvar in [1,3]
// and that var and subvar can be cast to int values
switch (10*var + subvar)
{
    case 10+1:
        process a1;
    case 10+2:
        process b1;
    case 10+3:
        process c1;  
//
    case 20+1:
        process a2;
    case 20+2:
        process b2;
    case 20+3:
        process c2;  
//
    case 30+1:
        process a3;
    case 30+2:
        process b3;
    case 30+3:
        process c3;
//
    default:
        process error;
}
0
如果您使用的编程语言是C#，并且您的选项足够短且不包含特殊字符，您可以使用反射，在几行代码中完成它。这样，您就不必手动创建和维护函数指针数组，而是使用框架提供的一个！像这样：
using System.Reflection;
...

void DispatchCall(string var, string subvar)
{
  string functionName="Func_"+var+"_"+subvar;
  MethodInfo m=this.GetType().GetMethod(fName);
  if (m == null) throw new ArgumentException("Invalid function name "+ functionName);
  m.Invoke(this, new object[] { /* put parameters here if needed */ });
}

void Func_1_a()
{
   //executed when var=1 and subvar=a
}

void Func_2_charlie()
{
   //executed when var=2 and subvar=charlie
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接