Как я могу оптимизировать алгоритм множественного (матричного) переключения / случая?

Question

Можно ли оптимизировать этот (матричный) алгоритм:

//        | 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 или альфа, бета, у Чарли есть разные процессы для достижения. Можно ли оптимизировать его любым другим способом, кроме как через серию «переключатель / кейс»?

(вопрос уже задан на французском здесь ).

Редактировать : (из ответов Драна Дейна на комментарии ниже. Они также могут быть в этом более заметном месте!)
« optimize » следует понимать как наличие для записи меньшего количества кода , меньшего числа «переключатель / регистр». Идея состоит в том, чтобы улучшить удобочитаемость, удобство обслуживания , , а не производительность.

Возможно, есть способ написать меньше кода с помощью «Цепочки ответственности», но это решение не оптимально во всех отношениях, поскольку требует создания множества объектов в памяти.

Answer 1

Звучит так, как будто вам нужен «Конечный автомат» , где с помощью этих случаев вы можете активировать различные процессы или «состояния». В Си это обычно делается с помощью массива (матрицы) указателей на функции.

Таким образом, вы, по сути, составляете массив и помещаете правильные указатели на функции в правильных указателях, а затем используете свой «var» как указатель на правильный «процесс» и затем вызываете его. Вы можете сделать это на большинстве языков. Таким образом, различные входы в машину активируют разные процессы и переводят их в разные состояния. Это очень полезно для многочисленных приложений; Я сам все это время использую в разработке MCU.

Редактировать: Валя указала, что мне, вероятно, следует показать базовую модель:

stateMachine[var1][var2]();   // calls the right 'process' for input var1, var2

Answer 2

На этот вопрос нет хороших ответов :-(

потому что большая часть ответа зависит от

• Эффективные цели (что означает «оптимизировать», что неприятно во вложенных переключателях)
• Контекст, в котором будет применяться эта конструкция (каковы конечные потребности приложения)

TokenMacGuy был мудрым, чтобы спросить о целях. Я нашел время, чтобы проверить вопрос и его ответы на французском сайте, и все еще озадачен целями ... Последний ответ Драна Дейна, похоже, указывает на уменьшение количества кода / улучшение читабельности, но давайте рассмотрим наверняка:

• Скорость обработки: не проблема, вложенные переключатели достаточно эффективны, возможно, не более 3-х умножений, чтобы получить индекс для таблицы карты, но, возможно, даже нет.
• Удобочитаемость: да, возможно, проблема, так как число переменных и уровень увеличиваются, начинается комбинаторный взрыв, а также формат оператора switch имеет тенденцию распространять точку ветвления и связанные значения по длинному вертикальному отрезку. В этом случае 3-мерная (или более) таблица инициализируется с помощью fct. pointers объединяет значения разветвления и функцию для вызова в одну строку.
• Написание меньшего количества кода: Извините, здесь не так много помощи; в конце дня мы должны учитывать относительно большое количество комбинаций, и «карта», независимо от ее формы, должна быть где-то записана. Генераторы кода, такие как 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 ....
}

Случай, который может подсказать один НЕ , использующий вышеупомянутое решение, равен , если пространство комбинации сравнительно редко заполнено (многие «ветви» в «дереве» коммутатора не используются) или , если для некоторых функций требуется другой набор параметров ; Для обоих этих случаев я бы хотел подключить решение, предложенное Джоэлем Гудвином сначала здесь , и которое по существу объединяет различные ключи для нескольких уровней в один более длинный ключ (с символом-разделителем, если необходимо), по сути сведение проблемы обратно к длинному, но одноуровневому переключателю .

Сейчас ...

Реальное обсуждение должно быть о , зачем нам сначала нужно такое отображение / дерево решений . Чтобы ответить на это, к сожалению, необходимо понять истинную природу основного приложения. Конечно, я не говорю, что это свидетельствует о плохом дизайне. Большой раздел диспетчеризации может иметь смысл в некоторых приложениях. Тем не менее, даже с языком C (который авторы французского сайта, по-видимому, дисквалифицировали для объектно-ориентированного дизайна), можно принять объектно-ориентированную методологию и шаблоны. В любом случае, я расходлюсь ...) Вполне возможно, что приложение в целом будет лучше обслуживаться альтернативными шаблонами проектирования, где «информационное дерево о том, что вызывать, когда» будет распределено в нескольких модулях и / или нескольких объектах.

Извините, чтобы говорить об этом в довольно абстрактных терминах, это просто отсутствие специфики приложения ... Суть остается: бросить вызов идее, что нам нужно это большое диспетчерское дерево; подумайте об альтернативных подходах к применению в целом.

Алорс, Бонн Шанс! ; -)

Answer 3

В зависимости от языка, некоторая форма хэш-карты с парой (var, subvar) в качестве ключа и первоклассными функциями в качестве значений (или того, что ваш язык предлагает для наилучшего приближения, например экземпляры классов, расширяющие некоторый надлежащий интерфейс в Java), вероятно, обеспечит высочайшую производительность - и полная краткость извлечения соответствующей функции (или чего-либо еще ;-) из карты на основе ключа и ее выполнения) приводит к высокой читабельности для читателей, знакомых с языком и подобным функционалом. идиомы.

Answer 4

Однажды у меня была точно такая же проблема, хотя для имманентного беспорядка 5-параметрического вложенного переключателя. Я подумал, зачем сам печатать все эти случаи O (N ⁵ ), зачем даже придумывать имена «вложенных» функций, если компилятор может сделать это для меня. И все это привело к «вложенному специализированному переключателю шаблонов», ссылающемуся на «специализированную базу данных шаблонов».

Это немного сложно написать. Но я нашел, что это того стоит: в результате получается «база знаний», которую очень легко поддерживать, отлаживать, добавлять и т. Д. И я должен признать: чувство гордости *

// 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;
}

Answer 5

Да, есть определенно более простой способ сделать это, и быстрее и проще . Идея в основном та же, что предложена Алексом Мартелли. Вместо того, чтобы рассматривать вашу проблему как двумерную, воспринимайте ее как некоторую таблицу поиска в одном измерении.

Это означает объединение var, subvar, subsubvar и т. Д., Чтобы получить один уникальный ключ и использовать его в качестве точки входа в таблицу поиска.

Способ сделать это зависит от используемого языка. С Python, сочетающим var, subvar и т. Д. Для создания кортежа и использования его в качестве ключа в словаре, достаточно.

При использовании языка C и т. Д. Обычно проще преобразовать все ключи в перечисления, а затем объединить их с помощью логических операторов, чтобы получить только одно число, которое можно использовать в коммутаторе (это также простой способ использовать коммутатор вместо сравнения строк с каскадированием сослагательное наклонение). Вы также получаете другую выгоду, делая это. Вполне обычно, что несколько обработок в разных ветвях начального переключателя одинаковы. С начальной формой это довольно сложно сделать очевидным. Вероятно, у вас будет несколько вызовов к одним и тем же функциям, но в разных точках кода. Теперь вы можете просто сгруппировать идентичные случаи при написании ключа.

Я несколько раз использовал такое преобразование в рабочем коде, и его легко выполнять и поддерживать.

В общем, вы можете получить что-то вроде этого ... функция микширования, очевидно, зависит от особенностей вашего приложения.

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;
}

Answer 6

Идея указателя на функцию, вероятно, лучше всего (согласно mjv, Shhnap).Но, если код в каждом случае довольно мал, он может быть излишним и привести к большему запутыванию, чем предполагалось.В этом случае я мог бы реализовать что-то быстрое и быстрое для чтения, например:

string decision = var1.ToString() + var2.ToString() + var3.ToString();
switch(decision)
{
    case "1aa":
        ....
    case "1ab":
        ....

}

Незнаком с вашим конкретным сценарием, поэтому, возможно, предыдущие предложения более уместны.

Answer 7

Решение от 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();

Answer 8

Если ваш язык 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
}

Answer 9

Если вы просто пытаетесь исключить двухуровневые операторы switch / case (и сохранить некоторое вертикальное пространство), вы можете закодировать два значения переменной в одно значение, а затем включить его:

// 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;
}

Answer 10

Если C ++ является опцией, я бы попробовал использовать виртуальную функцию и, возможно, двойную диспетчеризацию. Это может сделать его намного чище. Но это, вероятно, окупится, только если у вас будет еще много дел.

Эта статья на DDJ.com может быть хорошей записью.