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

Question

У меня есть много истинных / ложных результатов, сохраненных как биты в long[] массивах. У меня их огромное количество (миллионы и миллионы длинных).

Например, скажем, у меня есть только пять результатов, у меня было бы:

+----- condition 5 is true
|
|+---- condition 4 is false
||
||+--- condition 3 is true
|||
|||+-- condition 2 is true
||||
||||+- condition 1 is false
10110

У меня также есть несколько деревьев, представляющих такие выражения, как:

condition1 AND (condition2 OR (condition3 AND condition 4))

Деревья очень простые, но очень длинные. Они в основном выглядят так (ниже приведено упрощение, просто чтобы показать, что у меня есть):

class Node {    
    int operator();
    List<Node> nodes;
    int conditionNumber();    
}

По существу, либо узел является листом, а затем имеет номер условия (соответствует одному из битов в массивах long []), либо узел не является листом и, следовательно, ссылается на несколько подузлов.

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

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

Поэтому мне нужно пройтись по дереву и ответить либо true, либо false, в зависимости от содержимого дерева и содержимого long[].

Метод, который мне нужно оптимизировать, выглядит следующим образом:

boolean solve( Node node, long[] trueorfalse ) {
   ...
}

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

Зная, что у меня будет только несколько деревьев (может быть, до ста или около того), но миллионы и миллионы long[], чтобы проверить, какие шаги я могу предпринять, чтобы оптимизировать это?

Очевидное рекурсивное решение передает параметры (дерево (sub) и long [], я мог бы избавиться от long[], не передавая его в качестве параметра), и довольно медленно для всех рекурсивных вызовов и т. Д. I нужно проверить, какой оператор используется (И или ИЛИ или НЕ и т. д.), и в нем достаточно много операторов if / else или switch.

Я не ищу другой алгоритм (его нет), поэтому я не ищу перехода от O (x) к O (y), где y будет меньше, чем x.

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

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

Есть идеи, кроме генерации байт-кода для каждого дерева?

Теперь, если я хочу попробовать маршрут генерации байт-кода, как мне это сделать?

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

• , в которые ветви И оцениваютfalse
• , какие ветви ИЛИ приводят к истине

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

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

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

Answer 3

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

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

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

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