Оптимизация оценки дерева логической логики

Чтобы максимизировать возможности быстрой оценки, вам нужно сделать свой собственный прогноз ветвления.

Возможно, вы захотите профилировать его, подсчитывая

• какие ветви И оцениваются как ложные
• какие ветви ИЛИ приводят к истинному

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

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

Я надеюсь, что все это имеет смысл, потому что я понимаю, что прозаическая версия скучна. Однако, как сказал Ферма, пример кода слишком велик, чтобы уместиться в это поле :)

Существует простой и быстрый способ оценить логические операции, подобные этой, в C. Предполагая, что вы хотите оценить z=(x op y), вы можете сделать это:

 z = result[op+x+(y<<1)];

Таким образом, op будет кратным 4, чтобы выбрать вашу операцию AND, OR, XOR и т. д. Вы создаете таблицу поиска для всех возможных ответов. Если эта таблица достаточно мала, вы можете закодировать ее в одно значение и использовать сдвиг вправо и маску для выбора выходного бита:

z = (MAGIC_NUMBER >> (op+x+(y<<1))) & 1;

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

Для маленьких деревьев это выигрыш. Для более крупных деревьев с коротким замыканием это, вероятно, не является выигрышем, потому что среднее количество ветвей, которые необходимо оценить, составляет от 2 до 1,5, что является огромным выигрышем для больших деревьев. YMMV.

EDIT: Если подумать, вы можете использовать что-то вроде списка пропуска для реализации короткого замыкания. Каждая операция (узел) будет включать в себя значение сравнения и количество пропусков. если результат соответствует значению сравнения, вы можете пропустить следующие значения счетчика пропусков. Таким образом, список будет создан из обхода дерева в глубину, и первый дочерний элемент будет включать количество пропусков, равное размеру другого дочернего элемента. Это немного усложняет оценку каждого узла, но допускает короткое замыкание. Тщательная реализация может сделать это без какой-либо проверки условий (думаю, в 1 или 0 раз больше количества пропусков).

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

((word&1) && ((word&2) || ((word&4) && (word&8))))

Это может быть скомпилировано на лету всякий раз, когда деревья меняются, и загружается результирующий байт-код / ​​dll, и все это занимает меньше секунды.

Дело в том, что в настоящее время вы интерпретируете содержимое деревьев. Превращение их в скомпилированный код должно заставить их работать в 10-100 раз быстрее.

ДОБАВЛЕНО в ответ на ваши комментарии об отсутствии JDK. Затем, если вы не можете сгенерировать байт-код Java, я бы попытался написать свой собственный интерпретатор байт-кода, который работал бы как можно быстрее. Это может выглядеть примерно так:

while(iop < nop){
  switch(code[iop++]){
    case BIT1: // check the 1 bit and stack a boolean
      stack[nstack++] = ((word & 1) != 0);
      break;
    case BIT2: // check the 2 bit and stack a boolean
      stack[nstack++] = ((word & 2) != 0);
      break;
    case BIT4: // check the 4 bit and stack a boolean
      stack[nstack++] = ((word & 4) != 0);
      break;
    // etc. etc.
    case AND: // pop 2 booleans and push their AND
      nstack--;
      stack[nstack-1] = (stack[nstack-1] && stack[nstack]);
      break;
    case OR: // pop 2 booleans and push their OR
      nstack--;
      stack[nstack-1] = (stack[nstack-1] || stack[nstack]);
      break;
  }
}

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

Кроме того, вы могли бы упростить его, изменив законы Де Моргана, чтобы вы могли проверять более одного бита за раз.