Более элегантный способ написать код принятия решений, который оценивает несколько входов с разными приоритетами?

Ответ 1

Самое главное - иметь код, который заявляет, что входные данные и их относительные приоритеты являются простыми, короткими и изящными. Вот один из способов написать этот код:

PreferencedDecisionMaker pdm = new PreferencedDecisionMaker();
pdm.Push(false, leftExists, rightExists, upExists, downExists);
pdm.Push(0);
pdm.Push(false, leftFree,   rightFree,   upFree,   downFree  );
pdm.Push(false, pushedLeft, pushedRight, pushedUp, pushedDown);
pdm.Push(1);
switch(pdm.Decision)
{
    case 1: GoLeft();  break;
    case 2: GoRight(); break;
    case 3: GoUp();    break;
    case 4: GoDown();  break;
}

Здесь входы объявляются в основном табличным форматом. Приоритет каждого входа определяется упорядочением строк. Каждый столбец соответствует возможному выводу.

"Сложность" этого кода равна n × m.

(Хотя я использовал отступ, чтобы сделать это похожим на таблицу, более сложные условия ввода не позволят каждой строке располагаться аккуратно на одной строке. Это не имеет значения: важный бит в том, что есть только n × m. Возможность сделать его похожим на таблицу, когда условия коротки, это просто хороший бонус.)

Менее важным является фактический закулисный код для принятия решения (тип PreferencedDecisionMaker). Существует несколько способов расчета наилучшего решения на основе приоритета. Superpig предложил забить, что хорошо. Но я закончил тем, что решил использовать метод исключения, используя бит-поле. Я разместил свой код для этого ниже.

Использование битового поля имеет большое преимущество в том, что не нужно выделять кучную память для массивов. Единственным недостатком является то, что он ограничен 32 параметрами.

Следующий код не был тщательно протестирован. И я не заполнил все 32 версии метода Push. Он использует измененную структуру, которая является "непослушной" - преобразование ее в неизменяемую структуру должно быть простым. Или вы можете сделать это классом, но тогда вы потеряете преимущество, избегая выделения кучи.

struct PreferencedDecisionMaker
{
    private uint availableOptionsBits;

    private static readonly int[] MultiplyDeBruijnBitPosition = {
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

    public int Decision
    {
        get
        {
            uint v = availableOptionsBits;

            // Find position of lowest set bit in constant time
            // http://stackoverflow.com/a/757266/165500
            return MultiplyDeBruijnBitPosition[((uint)((v & -v) * 0x077CB531U)) >> 27];
        }
    }

    private void InternalPush(uint preference)
    {
        if(availableOptionsBits == 0)
            availableOptionsBits = preference;
        else
        {
            uint combinedBits = availableOptionsBits & preference;
            if(combinedBits != 0)
                availableOptionsBits = combinedBits;
        }
    }

    public void Push(int option)
    {
        if(option < 0 || option >= 32) throw new ArgumentOutOfRangeException("Option must be between 0 and 31");
        InternalPush(1u << option);
    }

    // ... etc ...
    public void Push(bool p0, bool p1, bool p2, bool p3, bool p4) { InternalPush((p0?1u:0u) | ((p1?1u:0u)<<1) | ((p2?1u:0u)<<2) | ((p3?1u:0u)<<3) | ((p4?1u:0u)<<4)); }
    // ... etc ...
}

Ответ 2

Это по существу проблема классификации; вы хотите что-то вроде дерева решений (или дерева поведения). Вы пытаетесь взять кучу дискретных входов для ситуации (достоверность, степень помола, направление нажатия и т.д.) И классифицировать результат как "вверх, вниз, влево или вправо".

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

Я думаю, вы могли бы построить таблицу поиска. У вас есть 4 бита, указывающих, действительно ли направление, 4 бита, указывающие, занято ли направление, и 2 бита, указывающие направление нажатия, всего на 10 бит - так, что 1024 различных ситуации и поведение в каждом из них могут быть описывается всего двумя битами (так, 1 байт), что делает общий размер таблицы 1024 байта.

Единая запись будет такой структурой:

union DecisionSituation
{
    unsigned short Index;
    struct
    {       
        bool ValidLeft : 1;
        bool ValidRight : 1;
        bool ValidUp : 1;
        bool ValidDown : 1;
        bool OccupiedLeft : 1;
        bool OccupiedRight : 1;
        bool OccupiedUp : 1;
        bool OccupiedDown : 1;
        Direction PushDirection : 2; 
    } Flags;
}

Вы описали бы свою ситуацию, заполнив флаги в этой структуре, а затем прочитав значение "Index", чтобы получить индекс таблицы поиска.

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

int leftScore = (leftExists << 4) | (leftFree << 3) | (pushedLeft << 2) | 1;
int rightScore = (rightExists << 4) | (rightFree << 3) | (pushedRight << 2) | 0;

// Find the highest scoring direction here

// If none of the scores are at least (1 << 4) it means none of them existed
if(highest score < (1 << 4)) return nothing;

// otherwise just return the highest scoring direction

Ответ 3

Когда у вас есть группа операторов if, обычно они могут быть реорганизованы с использованием полиморфизма в сочетании с шаблоном state:

В качестве введения, пожалуйста, смотрите следующее видео от Misko Hevery (вам понравится)

http://www.youtube.com/watch?v=4F72VULWFvc&feature=player_embedded#!

Это резюме из презентации:

Большинство, если их можно заменить полиморфизмом (подклассом)

Это желательно, потому что:

• Функции без ifs легче читать, чем с ifs
• Функции без ifs легче протестировать
• Связанные ветки ifs попадают в один и тот же подкласс

Использовать полиморфизм (подклассы)

• Если вы проверяете объект, он должен вести себя по-разному на основе его состояния
• Если вам нужно проверить одно и то же условие в нескольких местах

Используйте, если

• Оценки обследований примитивных объектов ( > , <, ==,! =)
• ... другие виды использования, но сегодня мы фокусируемся на том, чтобы избежать, если

Полиморфное решение часто лучше, потому что

• Новое поведение может быть добавлено без исходного кода
• Каждая операция/проблема разделяется в отдельном файле
• Легко тестировать/понимать

ИЗМЕНИТЬ

На первый взгляд, используя шаблон состояния с полиморфизмом, решение будет выглядеть более сложным, поскольку оно предполагает, что вам понадобится больше классов, чем раньше, но компромисс намного лучше, если вы начнете писать тесты для такого рода кода вы найдете, что легче тестировать, легче читать и понимать, а потому проще поддерживать и расширять (прямо сейчас вы только что разместили о движении вправо или влево, но представьте, если позже вам нужно двигаться вверх и вниз, если вы не будете реорганизовывать свой код сейчас, добавление новых функций будет настоящей PITA)

У вас будет что-то вроде:

// represents the current position
class MyClass
{
  public int X;
  public int Y;
}
abstract class NodeMoving
{
   abstract void Move();
   abstract bool IsValid(MyClass myclass);
}
abstract class NodeMovingLeft : NodeMoving
{
   override void Move()
   {
      // add code to move left
      if(this.IsValid(MyClass myclass))
      {
         // move
      }
   }
}
abstract class NodeMovingRight : NodeMoving
{
   override void Move()
   {
      // add code to move right
      if(this.IsValid(MyClass myclass))
      {
         // move
      }
   }
}
// and then start modeling the different states
class RightFree : NodeMovingRight
{
   override bool IsValid(MyClass myclass)
   {
      // add condition to validate if the right is free
   }
}
// combining conditions
class PushedLeft : NodeMovingLeft
{
   override bool IsValid(MyClass myclass)
   {
      // code to determine if it has been pushed to the left
   }
}
class LeftFree : PushedLeft
{
   override bool IsValid(MyClass myclass)
   {
      // get condition to indicate if the left is free
      var currentCondition = GetCondition();
      // combining the conditions
      return currentCondition && base.IsValid(myClass);
   }
}

Вам нужно будет добавить необходимые свойства, чтобы вычислить условия и выполнить движение

Стоит отметить, насколько малы методы, (да, у вас будет больше, чем раньше), но они могут быть протестированы изолированно очень просто.

Изменить 2 - добавить приоритет

Ну, теперь, когда у нас есть простой конечный автомат, нам нужно оценить приоритеты, один из способов сделать это (и я хотел бы услышать, как улучшить его), используя очередь приоритетов:

http://www.codeproject.com/Articles/13295/A-Priority-Queue-in-C

Он будет выглядеть примерно так:

    // you could place the priorities in a service to reuse it
    var priorities = new HashSet<NodeMoving>();

    priorities.Add(new RightExists());
    priorities.Add(new PushedLeft());

    var currentPosition = new MyClass { X = 1, Y = 2 };

    foreach (var priority in priorities)
    {
        if (priority.IsValid(currentPosition))
        {
            priority.Move();
            break;
        }
    }

    // output is: RightExists

    // now changing the priority order
    foreach (var priority in priorities.Reverse())
    {
        if (priority.IsValid(currentPosition))
        {
            priority.Move();
            break;
        }
    }

    // output is: PushedLeft

Ответ 4

Используйте шаблон state. Нарисуйте диаграмму состояний, которая содержит все ваши разные состояния и разрешенные переходы между ними. При кодировании у него есть подкласс состояний для каждого node. Каждое состояние node/class будет определять входные данные и сделать привод соответствующим переходом к следующему разрешенному состоянию. Я не думаю, что вы можете избежать множества государств, о которых вы говорите.

Ответ 5

Не работает ли это:

if(!leftExists) {
    if(rightExists) {
        GoRight();
    } else {
        // Panic!
    }
} else if(!rightExists) {
    GoLeft();
} else if(rightFree || leftFree && !(rightFree && leftFree)) {
    if(rightFree) {
        GoRight();   
    } else {
        GoLeft();
    }
} else if(pushedRight) {
    // Assumption: pushedLeft and pushedRight cannot both be true?
    GoRight();
} else {
    // PushedLeft == true, or we just prefer to move left by default
    GoLeft();
}   

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

Ответ 6

Я бы придерживался модификации вашего решения.

Считаете ли вы, что GoLeft в функции, которая также возвращает, осталось или нет? Если это не сложная функция, и вы называете это LOT, а тестирование показывает, что ее нужно оптимизировать, что бы я делал.

Если вы это сделаете, это станет следующим. Это в основном то, что вы делаете, но легче читать.

Я уверен, что я получу downvotes для этого, поскольку он не OO и не использует шаблон команды, но он отвечает на вопрос, и его легко читать;) Для более сложной проблемы, я думаю об использовании этих ответов, но для этой конкретной проблемы я бы придерживался простого ответа.

if(pushedLeft && leftFree && GoLeft())    ;
else if(pushedRight && rightFree && GoRight())    ;
else if(leftFree && GoLeft())    ;
else if(rightFree && GoRight())    ;
else if(pushedLeft && GoLeft())    ;
else if(pushedRight && GoRight())    ;
else if(GoLeft())    ;
else if(GoRight())    ;
// else do nothing...

Ответ 7

Чтобы понять это, я рекомендую следующие меры:

• решить, какие из операторов, которые объединены в операторах if, весит больше

• распутать инструкции if, в результате чего вложенные операторы if, такие как

  if (moveRight) 
  {
      if (pushedleft)
      {
          /// ...
      }
  }
  

• когда у вас это есть, начните упаковывать всю условную логику в методы, например. HandleMoveRight

• выполнив это, вы можете начать извлечение классов, заканчивая шаблоном команды.

Теперь у вас больше нет проблем с добавлением дополнительных функций, а сложность - плоская.

Ответ 8

Я думаю, что шаблон состояния - это правильный подход, рекомендованный @john2lob. Вам также нужен какой-то подход дерева решений для определения следующего перехода на действия "push" / "free" / "событий" событий. Кстати: какая разница между "свободным" и "существует"?