Как исследовать пространственную сложность алгоритмов сортировки?

Если бы я реализовал три алгоритма сортировки на С++, а затем хотел бы изучить их сложность пространства/объем оперативной памяти, которую они занимают. Как я мог это сделать? Существуют ли какие-либо стандартные или сторонние библиотеки, которые я могу использовать?


c++ sorting space-complexity
person Felix Rosén    schedule 25.05.2019    source источник
comment
посмотрите на valgrind общее использование кучи (я не знаю, интересует ли вас также использование стека). Но ваш вопрос странный, только о роде? не пространство, используемое самим деревом?   -  person bruno    schedule 25.05.2019
comment
Без загрузки каких-либо сторонних инструментов или зависимостей один простой и простой способ - просто запустить его, скажем, с числами 10 ^ 6, проверить объем оперативной памяти, который он занимает, в диспетчере задач и т. д., а затем запустить его с числами 2 * 10 ^ 6 и посмотрите, насколько увеличится использование вашей оперативной памяти.   -  person ruohola    schedule 25.05.2019
comment
Если вы реализуете алгоритм, то очень легко определить объемную сложность по самому коду.   -  person Phil1970    schedule 25.05.2019
comment
Обычно вы определяете временную и пространственную сложность, анализируя алгоритм, а не фактическое использование памяти вашей реализацией.   -  person BessieTheCookie    schedule 25.05.2019

Ответы (2)


arrow_upward
1
arrow_downward

Это под Unix/Linux? Если это так, вы можете вычислить разницу между значениями, возвращаемыми sbrk(0) в начале и в конце вашей программы. Это даст общий объем кучи памяти во время выполнения.

См. страницу руководства на sbrk(2). "Вызов sbrk() с приращением 0 можно использовать для поиска текущего местоположения прерывания программы."

(дополнение) Используя игрушечную программу на C++, которая просто выделяет один большой вектор, оказывается, что среда выполнения GNU C++ имеет тенденцию выделять очень большие объекты, используя mmap(), а не sbrk().

Использование strace:

$ strace ./vec1.x |& grep map
...
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f4ac2b42000
mmap(NULL, 800002048, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f4a93051000
...
$

Вы также можете выполнить grep с помощью brk вместо map.

Использование Валгринд:

$ valgrind ./sbrk1.x
...
==22223==   total heap usage: 3 allocs, 3 frees, 800,073,728 bytes allocated
....
$

Надеюсь, поможет !

person jpmarinier    schedule 25.05.2019
comment
Хороший! Я думаю, это то, что я ищу, проверю! Спасибо - person Felix Rosén; 25.05.2019
comment
Я не могу заставить его работать с sbrk. sbrk(0) возвращает указатель, а не значение. Как тогда рассчитать разницу? Я также пытаюсь разыменовать этот указатель, но тогда я получаю только адрес (я думаю). У вас есть примеры кода о том, как его использовать? - person Felix Rosén; 30.05.2019
comment
@ Феликс Розен - вы не хотите разыменовывать указатели, возвращаемые sbrk(), поскольку они указывают на еще нераспределенный вакуум. Идея состоит в том, чтобы получить два указателя, возвращаемых sbrk(0), скажем, sbrk1 и sbrk2, взятых до и после создания ваших структур данных. Затем вы приводите эти два значения к char* и вычитаете их. Это дает вам количество выделенных байтов. Например: size_t diff = static_cast‹char*›(sbrk2) - static_cast‹char*›(sbrk1); - person jpmarinier; 31.05.2019
comment
Спасибо! Я сделал, как вы сказали, но разница, к сожалению, 0 - person Felix Rosén; 31.05.2019

arrow_upward
0
arrow_downward

Если вы хотите изучить их сложность - как асимптотическую функцию - вы не сможете сделать это эмпирически, например. путем перехвата выделений и освобождений. Вам нужно будет получить асимптотические границы максимального объема выделенного пространства, тщательно проанализировав свой код. Автоматизировать эту задачу в общем случае теоретически невозможно, так как ваша программа может быть сколь угодно сложной.

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

В той степени, в которой вы просите программный инструмент для измерения выделенной суммы во время запуска, это не относится к теме StackOverflow, и вам следует спросить на softwarerecs.stackexchange.com.

person einpoklum    schedule 25.05.2019