Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3862378 Sat, 02 Apr 2022 16:08:03 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3862378 Цитата Majestio @ 02.04.22, 09:36

Неужели при сборке нельзя определить для какой платформы собирается билд?

Кстати, вопрос открытый!
(Сейчас апробирую отличный совет выше).

Как из программы на Си/C++ определить - в какой ОС ее пытаются скомпилировать?
Если компилировать в Qt, то тут все относительно просто: в Windows есть макрос WINVER, а в Linux его, разумеется, нет.
Но, увы, Qt не всегда спасает. Например, я не знаю, как установить 64bit Qt под Windows.
По этой причине я, например, в Win 7 64bit программы отлаживаю в Qt 32bit и уже отлаженную программу в командной строке компилирую в mingw64 уже под 64bit Windows.
(Дело в том, что в компиляторе mingw64 нет встроенного макроса WINWER и его приходиться указывать явно в командной строке).

А так было бы неплохо в самой программе узнавать, в какой ОС и какой разрядности ее пытаются скомпилировать, - можно было бы избавиться от многих строк условной компиляции.

P.S. Что касается cSl, то я забыл удалить этот комментарий, который сделал лет 5 назад, когда был в Си еще совсем зеленым.
Слэш нужен для того, чтобы выводить данные в файлы, расположенные в разных директориях. А слэш, как известно, в Win и в Linux разный. Спасибо Билли Гейтсу.]]> mkudritsky C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3862370 Sat, 02 Apr 2022 09:36:55 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3862370 Цитата mkudritsky @ 02.04.22, 04:53

char cSl = '/'; // По переменной cSl далее в программе определяется, где мы находимся (Linux, Windows)

Просто дичь! Неужели при сборке нельзя определить для какой платформы собирается билд?
Что может быть проще?]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3862359 Sat, 02 Apr 2022 04:53:51 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3862359 Чтобы не читать все выше, изложу суть проблемы - надо выделить оперативную память в максимальных количествах для решения некоторых труднорешаемых комбинаторных задач.
Но при этом надо, чтобы эта память не выравнивалась по словам (32bit), а заполнялась полезными данными подряд, "плечом к плечу", без "дырок" и "проплешин" на выравнивание данных.
Да, при этом время расчетов возрастает на 30-40%, но зато абсолютно вся память используется!

Сейчас я этой цели достигаю следующим образом.
Текст фрагмента программы (кстати, для Linux и для Windows) приведен с подробными комментариями:

#ifndef WINVER

#include <sys/sysinfo.h> // Linux

#else

#include <sysinfoapi.h> // Windows

#endif

// Информация об основных параметрах ОС (главным образом - RAM)

#ifndef WINVER

struct sysinfo osInfo;

char cSl = '/'; // По переменной cSl далее в программе определяется, где мы находимся (Linux, Windows)

#else

MEMORYSTATUSEX osInfo;

char cSl = '\';

#endif

// Переключение локали для вывода кирилицы в терминальном окне

setlocale(LC_CTYPE, "");

unsigned long long int

// Масимальный объем выделенной динамической памяти, смещение относительно начального адреса, вспомогательная переменная

iMemMax, iMem, iDMem;

// Начальное значение смещения относительно начального адреса

iMem = 0;

// Чтение информации о состоянии операционной системы

#ifndef WINVER

sysinfo(&osInfo);

iMemMax = osInfo.freeram - (osInfo.freeram / 100) * 4; // 4% от свободной памяти

iDMem = osInfo.totalram / 1000 + 1;

#else

osInfo.dwLength = sizeof(osInfo);

if (!GlobalMemoryStatusEx(&osInfo)) { // osInfo.freeram;

PrintCons("Не могу определить размер динамической памяти!\n");

return -1;

}

iMemMax = osInfo.ullAvailPhys;

iDMem = osInfo.ullTotalPhys / 1000 + 1;

#endif

// Выделение максимально возможного объема динамической памяти RAM

pByte = (char*)calloc(iMemMax, sizeof(char));

while (!pByte && (iMemMax > iDMem)) {

iMemMax -= iDMem;

pByte = (char*)calloc(iMemMax, sizeof(char));

}

if (!pByte) {

PrintCons("Не могу выделить динамическую память!\n");

return -1;

}

#ifndef WINVER

printf("Динамической памяти RAM = "); printf("%lld Mbyte\n", iMemMax / 1048576); // 1048576 = 1024 *1024

#else

printf("Динамической памяти RAM = "); printf("%I64d Mbyte\n", iMemMax / 1048576); // 1048576 = 1024 *1024

#endif

// Пример работы с динамической памятью ("нарезание" кусков памяти относительно pByte в пределах iMemMax

int *Ivar, *Iopt; // Массивы с последовательностями индексов городов (текущий и оптимальный) при решении Задачи Коммивояжера

int Ng = 300; // Число городов в Задаче Коммивояжера; может вводиться из консоли

// Массив размером Ng для хранения промежуточных маршрутов

Ivar = (int *)(pByte + iMem); // calloc(Ng, sizeof(int));

iMem += Ng * sizeof(int);

if (iMem > iMemMax)

{printf("Не могу выделить память!\n"); free(pByte); return -1;}

// Массив для хранения оптимального маршрута

Iopt = (int *)(pByte + iMem); // calloc(Ng, sizeof(int));

iMem += Ng * sizeof(int);

if (iMem > iMemMax)

{printf("Не могу выделить память!\n"); free(pByte); return -1;}

// Ну и так далее. Идея, наверное, понятна!

// Освобождается выделенная динамическая память одним элегантным движением:

free(pByte);

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

Так вот, ту часть данных, которая не меняет структуру, располагаем сразу за началом глобального массива pByte и запоминаем смещение:
iMemCONST = iMem;
Ну а те данные, которые динамически меняют структуру в процессе счета (цикла) располагаем за смещением iMemCONST, периодически возвращаясь к этому смещению для выстраивания от него новой, измененной, структуры данных.
Очень удобно! Я даже не знаю, как это сделать просто и безошибочно только лишь при помощи malloc/calloc и free...]]> mkudritsky C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3739353 Sat, 09 Sep 2017 04:23:33 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3739353 Qraizer C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3739352 Sat, 09 Sep 2017 00:56:43 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3739352 Все действительно оказалось просто: требуемую память (благо, что ее размер можно вычислить заранее) надо запрашивать сразу, а не по мере выполнения программы.
Ну и после выделения требуемого очень большого фрагмента RAM надо просто расставить по нему указатели требуемым образом.

Вот фрагмент кода решения Задачи Коммивояжера методом динамического программирования:

#include <stdlib.h>

#include <stdio.h>

//-------------------------------------

typedef struct {// Структура со свойствами города текущего состояния

char sNg; // Номер города нижележащего состояния, куда оптимально надо идти из текущего состояния. Принадлежит базису текущего состояния!

unsigned short Smin; // Минимальная длина пути коммивояжера в текущее состояние

} sG;

typedef char sG[3]; // Первый байт - номер города текущего состояния; и 2+3 байты - минимальная длина пути коммивояжера в текущее состояние

//-------------------------------------

int Ng, Nc, // Число городов коммивояжера и число базисов состояний (Nc=2**Ng-1)

iSost, // Базис (1-биты) и конечные города состояния (0-биты)

*bNg; // Массив "битов", соответствующих номерам городов (1-бит номер города, остальные 0-биты)

sG **Ns, // Массив соответсвия "Базис=>Ссылка на его набор sG" (всего Nc)

*Ndat; // Массив элементов sG для каждого состояния (всего их Ng*2**(Ng-1))

unsigned long long int Lsost, // Счетчик размера всей необходимой структуры (в байтах)

Ldat; // Счетчик состояний (структур sG в массиве Ndat)

//-------------------------------------------------------------------------------------------------

int main(void) {

// Размер структуры

printf("Размер структуры sG = %lu\n", sizeof(sG));

// Задание числа городов

printf("Число городов Ng = ");

scanf("%d",&Ng);

// Нахождение числа базисов состояний (2**Ng)

Nc=1;

Nc=(Nc<<Ng);

Nc-=1; // Nc=2**Ng-1

printf("Число базисов состояний Nc = %i\n", Nc);

// Задание вспомогательных массивов данных

bNg=(int*)calloc(Ng,sizeof(int)); // Бит <--> город. Массив малый и его не считаем в Lsost

Ns=(sG**)calloc(Nc,sizeof(sG*)); // Ns содержит ссылки на элементы массива Ndat для каждого базиса

Lsost=Nc*sizeof(sG*); // такую RAM мы уже выделили (массив указателей размером Nc)

printf("Размер массива базисов состояний = %llu\n", Lsost);

Ldat=Ng*((1+Nc)>>1); // Число состояний коммивояжера

Ndat=(sG*)calloc(Ldat,sizeof(sG)); // Ng*2**(Ng-1) элементов sG - данные для каждого состояния коммивояжера

if (!Ndat)

{ printf("Не могу выделить память!\n"); return 1; }

Lsost+=Ldat*sizeof(sG);

printf("Размер всей структуры данных поиска = %llu\n", Lsost);

// Заполнение битов-городов

bNg[0]=1; // Для i-го города i-й бит в целой переменной типа int равен 1; остальные биты - 0

for (int i=1; i<Ng ; i++)

bNg[i]=bNg[i-1]<<1;

// Построение всей структуры графа поиска. Выделение необходимой для расчетов памяти

Ns[0]=Ndat; // sG состояний с нулевым базисом находятся в самом начале массива Ndat

sG* NdatProm=Ndat; // Указатель для перемещения между элементами Ndat

for (iSost=0; iSost<Nc-1; iSost++) {

int j1=0; // Начало вычисления кратности текущего состояния (подсчет ненулевых битов в числе iSost

for (int j=0; j<Ng; j++)

if (iSost & bNg[j]) j1++; // Счетчик увеличивается только на 1-битах

NdatProm+=(Ng-j1);

Ns[iSost+1]=NdatProm; // Выделена память для всех состояний с текущим базисом iSost

}

printf("Завершение расчетов\n");

// Освобождение ранее выделенной памяти:

free(bNg); // Освобождение массива битов-городов

free(Ns);

free(Ndat); // Удаление массива состояний (ссылки на структуру для каждого базиса)

} // Завершение программы main

Отличие от предыдущего кода состоит в том, что введен массив Ndat с данными для всех состояний коммивояжера и потом в нем просто расставляются адреса базисов состояний, хранимые в массиве Ns.
Ура! Память я отвоевал! Больше дыр в RAM не образуется и данные для каждого состояния упаковываются "плечом к плечу".

Какова же плата за такое расположение данных, которые теперь не выравниваются по степени двойки?
Вот результаты расчетов на машине с 16Гб RAM и процессором Intel Core i7 2600K.
Решается честная разомкнутая Задача Коммивояжера в 64bit архитектуре на одном ядре CPU:

I. Число городов = 25
Старый метод выделения памяти: Tсчета=134сек; RAM=1949Мб
Новый метод выделения памяти: Tсчета=153сек; RAM=1458Мб

II. Число городов = 26
Старый метод выделения памяти: Tсчета=294сек; RAM=4000Мб
Новый метод выделения памяти: Tсчета=342сек; RAM=3013Мб

III. Число городов = 27
Старый метод выделения памяти: Tсчета=660сек; RAM=8208Мб
Новый метод выделения памяти: Tсчета=753сек; RAM=6219Мб

ВЫВОДЫ:
1. Упаковывание RAM "плечом к плечу" ведет к экономии памяти на примерно 24%, но увеличивает время расчетов примерно на 12-14%.
2. Оказалось, что функция calloc() - НЕ медленная процедура. В более ранних реализациях алгоритма я использовал calloc() для выделения памяти (по три байта) для каждого из миллиардов состояний да еще и в процессе расчетов! И все считалось по старому методу быстро. Кстати, метод new из C++ тоже быстро выделяет память.
3. Третье замечание экзотическое! :) Оказалось, что в OS Android память функцией calloc() выделяется оригинальным образом - вне зависимости от реального наличия свободной RAM. Например, на смартфоне с 2Гб RAM, из которой свободно 1.4Гб RAM, можно выделить и 3Гб, и почти 4Гб RAM! И даже расставить в этой виртуальной памяти метки!
Например, у меня в 32bit Android 5.0 память перестала выделяться (calloc() выдала NULL) только при запросе массива RAM более 4Гб.
Справедливости ради, в честных Linux-ах с выделением памяти все нормально - ОС следит за тем, чтобы запрашиваемый кусок RAM действительно был в наличии.
В Андроиде использовался компилятор C/C++ c4droid.

Итак, всем спасибо за советы!
Проблема решена.

P.S. Это была вторая проблема при построении эффективного алгоритма решения Задачи Коммивояжера (ЗК).
Первый вопрос, который я задавал, был о возможности решения ЗК в 32bit ОС Linux, но с использованием технологии PAE (это оказалось невозможным).
http://forum.sources.ru/index.php?act=Sele...sult_type=posts
Третья проблема, которую я собираюсь решить, - использовать многоядерность современных процессоров для решения ЗК. Например, на Intel Core i7 2600K собираюсь в 8 раз сократить время расчетов за счет распараллеливания вычислений.
И, наконец, в-четвертых, собираюсь попробовать решать эти задачи в OS Windows. В отличии от OS Linux операционки от Microsoft раньше были очень плохо приспособлены для решения подобного рода задач. Главная проблема, которую я здесь у MS обнаружил, - неконтролируемый сброс огромных массивов данных в SWAP. Сами понимаете, что при этом становится с временами решения ЗК! Это провал! Посмотрим, что стало нового в этом вопросе в Windows 7 и в Windows 10!]]> mkudritsky C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738691 Sat, 02 Sep 2017 12:55:50 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738691 Как я сам не додумался! Тут ведь все достаточно просто:
1. Заранее расчитать размер и одним движением запросить сразу огромный кусок памяти и указатель на его начало.
Кстати, так будет несложно и контролировать возможность выделения нужного "куска" памяти значением функции calloc()
2. Уже в имеющемся куске памяти просто расставить указатели нужным мне образом!
Все!

Вижу максимум 2-3 обращения к функции calloc()
И, кстати, все запрашиваемые массивы памяти будут многократно кратны степени 2:
1. Массив базисов указателей на данные каждого состояния.
Размер: ziseof(sG*)*2**(Ng) - куда уж кратнее степени 2.

2. Массив данных для каждого состояния.
Размер: sizeof(sG)*Ng*2**(Ng-1) - тоже самое многократно кратен 2.

В общем, пока беру тайм-аут.
Тоже иногда надо отдыхать!
В ближайшее время доложу о результатах.]]> mkudritsky C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738686 Sat, 02 Sep 2017 11:52:05 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738686 Цитата mkudritsky @ 02.09.17, 03:34

Почему память функцией calloc() выделяется не "плечом к плечу", а с "дырами"?

Попробуй выделять большой кусок (или куски) самостоятельно - их и пользуй. Выделение памяти - операция небыстрая. Сократив количество "выделений" - ускоришь выполнение, и избавишься от "дырок".]]> JoeUser C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738682 Sat, 02 Sep 2017 11:09:11 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738682 amk C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738668 Sat, 02 Sep 2017 09:43:05 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738668 Стало немного понятно. Сам я на C/C++ работаю всего два года, да и то - только с прикладными задачами типа Задачи Коммивояжера.
До этого всю жизнь работал на Pascal...

Только что провел эксперименты со структурой данных (вместо массива).
То есть начальный код программы выделения памяти теперь выглядит так:

#include <stdlib.h>

#include <stdio.h>

//-------------------------------------

typedef struct {// Структура со свойствами города текущего состояния

unsigned short Smin; // Минимальная длина пути коммивояжера в текущее состояние

} sG;

// typedef char sG[3]; // Первый байт - номер города текущего состояния; и 2+3 байты - минимальная длина пути коммивояжера в текущее состояние

//-------------------------------------

(Остальное - без изменений)

Теперь память выделяется так, если использовать структуру:
1. Ng=25 Реально=2308Мб, Lsost=1946
С массивом было: Реально=1685Мб, Lsost=1527Мб

2. Ng=26 Реально=4744Мб, Lsost=4027Мб
С массивом было: Реально=4000Мб, Lsost=3154Мб

ВЫВОД: все равно для хранения данных с описанием состояний выгодно использовать массив char sG[3], а не структуру.
Памяти для работы программы с массивом расходуется меньше.

Тут есть еще один вопрос... Касательно работы с чтением/записью данных.
А. С номером города, в котором находится коммивояжер в текущем состоянии все просто:
sG.sNg - это при работе со структурой
sG[0] - а это при работе с массивом.

Б. А вот с кратчайшим путем в текущее состояние все сложнее.
sG.Smin - со структурой-то все просто!
А вот при работе с массивом этот Smin должен вытягиваться из двух байт, начиная с sG[1]
Сейчас у меня в полной программе работа с данными осуществляется так (фрагменты кода):

Чтение

unsigned short *Smin=(unsigned short*)(Ns[iSostDn][0]+1);

unsigned short Sprom=*Smin+Smatr[m][j];

Запись

unsigned short *Smin=(unsigned short*)(Ns[iSost][j-k]+1);

*Smin=S1;

И мне такой код не кажется элегантным.
Боюсь, что пройдет пару лет и я уже не смогу расшифровать, как в этой части программа работает!
Нельзя ли как-то поэлегантнее указать, что адрес переменной unsigned short Smin совпадает с адресом Ns[][]+1 (то есть вторым элементом массива sG[3])?
Пробовал здесь задействовать union, но что-то не получилось у меня - все данные динамические...]]> mkudritsky C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738664 Sat, 02 Sep 2017 08:47:09 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738664 Цитата mkudritsky @ 02.09.17, 03:34

Почему память функцией calloc() выделяется не "плечом к плечу", а с "дырами"?

Это особенность работы менеджера динамической памяти. Не знаю как в gcc, а в msvc в 32-битном приложении каждый блок памяти, выделяемый calloc, new и т.п., во-первых, содержит служебный заголовок размером 8 байт, во-вторых, сам размер выделяемого блока округляется вверх до границы 8 байт. Отсюда и "дыры". Плюс к этому, менеджер динамической памяти (кучи), запрашивает\резервирует память у ОС блоками с определенной гранулярностью (в Win - кратно 64 Кб) и не может размещать данные, выделенные одним calloc, в разных блоках. Поэтому возможны доп. "дыры" в конце\хвосте этих зарезервированных блоков, если ни один из запрашиваемых размеров calloc не умещается в оставшийся "хвост" ни одного их зарезервированных блоков памяти.

Цитата mkudritsky @ 02.09.17, 06:45

К сожалению, как видим, ОС Linux за кампанию с gcc не позволяют упаковать данные максимально плотно.
Неужели нельзя задать gcc никакие ключи?

При использовании стандартных аллокаторов памяти ключи врядли помогут. Единственный способ - использовать собственный менеджер памяти, который будет резервировать память у ОС средствами АПИ (в винде через VirtualAlloc) и выделять ее под струкутры\массивы приложения без лишних накладных расходов (заголовков и выравниваний размеров), свойственных стандартным аллокаторам.]]> leo C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738660 Sat, 02 Sep 2017 08:20:33 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738660 Цитата mkudritsky @ 02.09.17, 06:45

К сожалению, как видим, ОС Linux за кампанию с gcc не позволяют упаковать данные максимально плотно.Неужели нельзя задать gcc никакие ключи?Для меня пока важна экономия памяти, а не быстродействие...

Кое-что задавать там можно, но возможности ограничены упаковкой памяти внутри структуры. Сама структура всё равно будет выравниваться на границу, кратную степени 2
Так что если надо упаковывать максимально плотно, придётся паковать вручную.

Однако, подозреваю, такое уплотнение позволит добавить всего один, максимум два, города.]]> amk C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738657 Sat, 02 Sep 2017 06:45:13 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738657 sG.sNg - 1 байт, текущий город, в котором находится коммивояжер.
sG.Smin - 2 байта, минимальный путь, ведущий в текущее состояние
занимают всего 3 байта.

Впрочем, об этом написано в учебниках по C/C++, то есть структуры выравниваются компилятором по 2, 4, 8, 16 и т.п. байт - для оптимизации кода.
Именно поэтому мне пришлось объявлять свойства состояния sG так, как это объявлено в программе.

К сожалению, как видим, ОС Linux за кампанию с gcc не позволяют упаковать данные максимально плотно.
Неужели нельзя задать gcc никакие ключи?
Для меня пока важна экономия памяти, а не быстродействие...

P.S. Только что добрался до ПЭВМ с 16Гб RAM и провел вычисления для 27 городов:
Ng=27, реально требуемая память - около 8208Мб, переменная Lsost - 6510Mb.]]> mkudritsky C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738653 Sat, 02 Sep 2017 04:20:43 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738653 В идеале структура sG занимает 3 байта (1+2), а выделять по 3 байта ОС будет только в особо сложных/крайних своих состояниях. Т.о. выделит некое большее кратное двойке.
Если не идеал, то компилятор увидит, что структура sG занимает кратное двойке памяти (вроде стало лучше), и тогда расхождений в числах не будет. Но для этого надо, чтобы ОС умела выделять такие крохотные куски, кои согласованы с градацией компилятора.]]> Славян C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738652 Sat, 02 Sep 2017 03:34:09 +0000 Дыры при выделении памяти для решения Задачи Коммивояжера https://forum.sources.ru/index.php?showtopic=411266&view=findpost&p=3738652 Количество состояний растет экспоненциальным образом с ростом числа городов, которые надо обойти коммивояжеру.
Каждое состояние хранит в RAM свои данные.

Для каждого состояния память выделяется функцией языка C calloc()
В конце программы выделенная память освобождается функцией free()

Вот программа, демонстрирующая выделение памяти в Задаче Коммивояжера.
Выделенная память (главные массивы) считается переменной Lsost
Расчеты проводились в OS Runtu 16.04 64bit (клон Ubuntu). В ПК установлено 8Гб RAM.
Компиляция проводилась командой:

$gcc -std=c11 ZKmass.c

ZKmass.c

#include <stdlib.h>

#include <stdio.h>

//-------------------------------------

struct sG {// Структура со свойствами города текущего состояния

unsigned short Smin; // Минимальная длина пути коммивояжера в текущее состояние

};

//-------------------------------------

int Ng, Nc, // Число городов коммивояжера и число состояний (Nc=2**Ng)

iSost, // Адреса базисов состояний

*bNg; // Массив "битов", соответствующих номерам городов

sG **Ns; // Массив состояний коммивояжера (не более Ng*2**(Ng-1))

unsigned long long int Lsost; // Счетчик размера всей необходимой структуры (в байтах

//-------------------------------------------------------------------------------------------------

int main(void) {

// Размер структуры

printf("Размер структуры sG = %lu\n", sizeof(sG));

// Задание числа городов

printf("Число городов Ng = ");

scanf("%d",&Ng);

// Нахождение числа базисов состояний (2**Ng)

Nc=1;

Nc=(Nc<<Ng); // Nc=2**Ng

printf("Число базисов состояний Nc = %i\n", Nc);

// Задание вспомогательных массивов данных

bNg=(int*)calloc(Ng,sizeof(int)); // Бит <--> город

Ns=(sG**)calloc(Nc,sizeof(sG*)); // Массив базисов состояний. Значения - ссылки на массивы со свойствами городов состояний

Lsost=Nc*sizeof(sG*); // такую RAM мы уже выделили (массив указателей размером Nc)

printf("Размер структуры базисов сосотяний = %llu\n", Lsost);

// Заполнение битов-городов

bNg[0]=1; // Для i-го города i-й бит в целой переменной типа int равен 1; остальные биты - 0

for (int i=1; i<Ng ; i++)

bNg[i]=bNg[i-1]<<1;

// Построение всей структуры графа поиска. Выделение необходимой для расчетов памяти

for (iSost=0; iSost<Nc-1; iSost++) {

int j1=0; // Начало вычисления кратности текущего состояния (подсчет ненулевых битов в числе iSost

for (int j=0; j<Ng; j++)

if (iSost & bNg[j]) j1++; // Счетчик увеличивается только на 1-битах

Ns[iSost]=(sG*)calloc(Ng-j1,sizeof(sG)); // Выделена память для всех состояний с текущим базисом iSost

Lsost+=(Ng-j1)*sizeof(sG); // Увеличен счетчик выделенной памяти

}

printf("Общий размер структуры состояний = %llu\n", Lsost);

// Освобождение ранее выделенной памяти:

free(bNg); // Освобождение массива битов-городов

for (int j=0; j<Nc-1; j++) // Освобождение структур поиска для каждого базиса состояний коммивояжера

free(Ns[j]);

free(Ns); // Удаление массива состояний (ссылки на структуру для каждого базиса)

} // Завершение программы main

Так в чем, собственно, проблема?
А проблема вот в чем:
1. Для числа городов Ng=25 переменная Lsost показывает, что выделяется примерно 1527Мб RAM.
Однако в Диспетчере задач памяти выделяется 1685Мб - более чем на 100Мб превышает ожидаемую величину.

2. Дальше - больше. :(
Для числа городов Ng=26 переменная Lsost показывает, что выделяется примерно 3155Мб RAM.
Однако в Диспетчере задач памяти выделяется 4000Мб - уже почти на 1Гб превышает ожидаемую величину.

Вот и возникает вопрос: почему это памяти при решении Задачи Коммивояжера затрачивается существенно больше, чем я ожидаю?
Почему память функцией calloc() выделяется не "плечом к плечу", а с "дырами"?
Может компилятор как-то выравнивает выделяемую память по каким-то сегментам?

P.S. Та же картина наблюдается, если программу переписать на C++, соотвественно заменив calloc/free на new/delete и компилировать программу командой:
$c++ -m64 ZKmass.cpp]]> mkudritsky C/C++: Общие вопросы