Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
SungMaster
1 / 1 / 0
Регистрация: 25.10.2010
Сообщений: 29
1

Оптимизация структуры данных для экономии памяти

16.01.2015, 17:13. Просмотров 244. Ответов 0
Метки нет (Все метки)

Здравствуйте! Я пытаюсь реализовать алгоритм работы с бинарными диаграмами решений (БДР, BDD), предоставленный в 4-м томе "Искусства программирования". Кнут предлагает использовать структуру
C
1
2
3
    unsigned long long V : 8;//индекс переменной
    unsigned long long LO : 28;//ход при значении 0
    long long HI : 28;//ход при значении 1
которая компактно помещается в quadword. Но не все так просто.

Зайду сдалека. Поскольку адрес на 64-й архитектуре никак не поместится в 28 бит, узлы я собираюсь хранить в динамически выделяемых массивах размером в 2^8 или 2^16 элементов, адреса блоков будут храниться в отдельном динамическом массиве (для ускорения доступа к узлу по его индексу). Но есть один крайне неприятный нюанс - для работы двух алгоритмов описанной структуры недостаточно, нужны дополнительные поля.

Для работы алгоритма редукции каждому узлу нужно дополнительное поле AUX, размер которого должен быть не меньше размера поля HI. Держать это поле в структуре на постоянной основе не самый оптиматьный вариант, т.к. нужда в нем есть не так часто. Создавать блоки полей AUX для некоторых блоков узлов тоже не вариант, поскольку одновременно в памяти может находиться несколько диаграмм, а определить, узлы каких диаграмм находяться в блоке практически невозможно, а создавать поля сразу для всех диаграмм накладно. Была идея на время работы алгоритма редукции создавать открытую хеш-таблицу, которая будет ставить в соответсвие индексу узла поле из выделенного массива (благо посчитать сколько полей понадобится возможность есть). Но при таком подходе не только усложняется доступ до поля (а в данном алгоритме на него ложится большая часть операций), но и расход памяти возрастет приблизительно вдвое, что плохо.

Также для работы алгоритма синтеза диаграммы в базе БДР каждому узлу понадобится поле REF, в котором будет храниться количество вхождений в данный узел. По-идеи 2 байт должно хватить. Но существует и другой алгоритм синтеза, которому это поле совсем не нужно. Оба алгоритма нужны, поскольку в различных случаях результаты их работы могут сильно отличаться.

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

Куда предложите деть эти поля так, чтобы потери памяти из-за них были минимальными, а доступ к ним не нужно было оформлять в 5 строчек? Проблема экономии настолько важна, потому что например для представления битового умножения двух кортежей длиной 16 потребуется диаграмма в 136 млн узлов.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2015, 17:13
Ответы с готовыми решениями:

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

Можно ли создать в C++ ограниченную переменную (для экономии памяти) без использования классов
Например, переменную, скажем, test, которая принимает значение в диапазоне (-180..+180)

Структуры. Оптимизация занимаемой памяти
Всем привет. Пытаюсь разобраться с объявлением структур без "мусорных" байтов, но почему-то тип...

Аллокирование памяти для структуры
Нужно зааллокировать память для структуры struct Baze { char artist; char...

Ошибка при освобождении памяти (block type is valid) и неправильный вывод структуры данных
Доброго времени суток. У меня есть класс вектор для реализации длинной арифметики. Возникли...

0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2015, 17:13

Динамическое выделение памяти для структуры в функции
Объясните не могу понять. На С++ пишу совсем недавно. Суть вопроса, при первом запуске программы...

Понятие структуры данных. Элементарные структуры данных. Простые структуры данных
Понятие структуры данных. Элементарные структуры данных. Простые структуры данных: методы...

Ошибка при выделении памяти динамически для структуры
Есть программа. Вылетает ошибка. Если gets(BLOCKNOTE.NAME) заменить на cin>>BLOCKNOTE.NAME все...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.