Здравствуйте! Я пытаюсь реализовать алгоритм работы с бинарными диаграмами решений (БДР, BDD), предоставленный в 4-м томе "Искусства программирования". Кнут предлагает использовать структуру
struct node{
unsigned long long V : 8;//индекс переменной
unsigned long long LO : 28;//ход при значении 0
long long HI : 28;//ход при значении 1
}
которая компактно помещается в quadword. Но не все так просто как хотелось бы.
Зайду сдалека. Поскольку адрес на 64-й архитектуре никак не поместится в 28 бит, узлы я собираюсь хранить в динамически выделяемых массивах размером в
или
элементов, адреса блоков будут храниться в отдельном динамическом массиве (для ускорения доступа к узлу по его индексу). Но есть один крайне неприятный нюанс - для работы двух алгоритмов описанной структуры недостаточно, нужны дополнительные поля.
Для работы алгоритма редукции каждому узлу нужно дополнительное поле AUX, размер которого должен быть не меньше размера поля HI. Держать это поле в структуре на постоянной основе не самый оптиматьный вариант, т.к. нужда в нем есть не так часто. Создавать блоки полей AUX для некоторых блоков узлов тоже не вариант, поскольку одновременно в памяти может находиться несколько диаграмм, а определить, узлы каких диаграмм находяться в блоке практически невозможно, а создавать поля сразу для всех диаграмм накладно. Была идея на время работы алгоритма редукции создавать открытую хеш-таблицу, которая будет ставить в соответсвие индексу узла поле из выделенного массива (благо посчитать сколько полей понадобится возможность есть). Но при таком подходе не только усложняется доступ до поля (а в данном алгоритме на него ложится большая часть операций), но и расход памяти возрастет приблизительно вдвое, что плохо.
Также для работы алгоритма синтеза диаграммы в базе БДР каждому узлу понадобится поле REF, в котором будет храниться количество вхождений в данный узел. По-идеи 2 байт должно хватить. Но существует и другой алгоритм синтеза, которому это поле совсем не нужно. Оба алгоритма нужны, поскольку в различных случаях результаты их работы могут сильно отличаться.
Была идея добавить к структуре только одно поле в 4 байта (чтобы туда помещалось AUX), но постоянно использовать его как REF, а в алгоритме редукции выгружать содержимое полей REF в какой-то временный буфер, использовать поля как AUX, а потом загружать содержимое обратно. Но и этот подход может привести в утечке памяти.
Куда предложите деть эти поля так, чтобы потери памяти из-за них были минимальными, а доступ к ним не нужно было оформлять в 5 строчек? Проблема экономии настолько важна, потому что например для представления битового умножения двух кортежей длиной 16 потребуется диаграмма в 136 млн узлов.
