Оптимальное распределение переменных и динмассивов в памяти

[Sonic86]

Как при выполнении программы в памяти физически хранятся динамические массивы, и насколько это оптимально в плане использованной памяти и скорости доступа к данным?
Т.е. пусть есть некая программа. В процессе ее выполнения в ней создаются, дополняются и удаляются динамические массивы, для простоты только одномерные (переменную, наверное, можно считать динамическим массивом длины $1$). Будем считать, что память имеет вид ленты, имеющей начало слева и потенциально бесконечна вправо, ячейки нумеруются натуральными числами. Заполняется память слева направо. На каждом шаге $j, 1\leqslant j\leqslant N$ обозначим $n_j$ - максимальный номер памяти, в котором записан какой-либо элемент массива, либо какая-то информация, порожденная программой в результате работы, связанная с хранением динамических массивов (например у список это, если не ошибаюсь, - ссылка на следующий элемент массива). Для простоты считаем, что все $n_j\neq 0$. А $m_j$ обозначим число занятых ячеек. Эффективностью выделения памяти назовем величину $E=\frac{1}{N}\sum\limits_{j=1}^N\frac{m_j}{n_j}$. Понятно, что $E\leqslant 1$. Но каково оно? И еще будем рассматривать скорость доступа к памяти (например, $O(1), O(\ln n), O(n)$). Я не знаю, насколько такая модель соответствует работе с реальными динамическими массивами, но вроде не сильно искажает ситуацию. Предполагая такую модель, хочу узнать, каков оптимальный способ выделения памяти по эффективности выделения памяти и скорости доступа к ней. Единый показатель эффективности сконструировать затрудняюсь. Наверное, память тоже надо как-то учитывать асимптотически или нет...
Может надо какое-то распределение операций с массивами задать?

Я погуглил, но не нашел толком явно ответа на вопрос. Вот в Педивикии что-то нашел (и тут еще), но конкретного ответа нет и ссылок на литературу тоже нет. Т.е. можно как-то предположить, что скорость доступа при работе с кучей - это $O(\ln n)$, что неплохо, но вот эффективность выделения памяти затрудняюсь сказать.
И вот это еще:

Цитата:

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

но тоже локальное описание...

Буду рад ссылкам на книжки. Надеюсь, что это где-то разобрано.

[Pavia]

Цитата:

Как при выполнении программы в памяти физически хранятся динамические массивы, и насколько это оптимально в плане использованной памяти и скорости доступа к данным?

По разному хранят. Но обычно так размер массива, а далее элементы.
Память с+N; c - константа много меньше N скорость доступа O(1)
Е=1 при N стремящейся к бесконечности.

Из почитать могу посоветовать Кнут искусство программирования.

Алгоритмов распределения динамической памяти много и это отдельный разговор.

Цитата:

что скорость доступа при работе с кучей - это

Доступ к элементам в куча по определению O(1).

[Munin]

Тема большая. Для начала, второй (кажется) том Кнута. Дальше литература по операционным системам, так как стратегии выделения памяти, их оптимальность - в основном забота ОС. Язык иногда занимается своей организацией кучи, но только когда он довольно экзотичен по сравнению со стандартными запросами: LISP, Prolog, FORT. Языки типа C++, Java - более стандартны в этом плане. В C++ можно всё взять в свои руки, см. Александреску и книги по стандартной библиотеке. Ещё тема близко соприкасается со сборкой мусора, иногда это объединяют в одну подсистему: блок памяти хранит и служебную информацию о своём размещении, и о своём статусе в сборке мусора.

Обязательный background - динамические структуры данных, как минимум до B-деревьев включительно.

[Pavia]

Munin

Цитата:

В C++ можно всё взять в свои руки,

С++ не позволяет делать полноценную сборку мусора в отличии от java.

Цитата:

Java - более стандартны в этом плане

Это как посмотреть. Мне объясняли по другому. И java я бы посоветовал изучить отдельно. Так как её принципы совершенно отличаются от Си++.

[Sonic86]

Pavia в сообщении #640914 писал(а):

По разному хранят. Но обычно так размер массива, а далее элементы.
Память с+N; c - константа много меньше N скорость доступа O(1)
Е=1 при N стремящейся к бесконечности.

Вот в это я сейчас не могу поверить Простой пример:
1. Создаем массив $A$ длины $10$.
2. Создаем массив $B$ длины $100$.
3. Удаляем массив $A$.
Чему равно $E$ на 3-м шаге?
Вообще $c+N$ - это очень хорошо (по идее только скорость доступа $O(\ln n)$ все-таки, сложение-то надо выполнить для получения номера элемента). Но вот $E$ тогда хромает по-моему.

Pavia в сообщении #640914 писал(а):

Доступ к элементам в куча по определению O(1).

Да ну! Почему?
Или я немного неточно сформулировал: пусть есть имя массива и номер его объекта. Сколько надо операций в зависимости от размера всей занимаемой памяти (или от чего?), чтобы вытащить этот элемент?

Pavia в сообщении #640914 писал(а):

Из почитать могу посоветовать Кнут искусство программирования.

Munin в сообщении #640951 писал(а):

Для начала, второй (кажется) том Кнута.

О! Прекрасно! Я посмотрю тогда сначала, чтобы простые вещи не спрашивать.

Munin в сообщении #640951 писал(а):

Обязательный background - динамические структуры данных, как минимум до B-деревьев включительно.

Ну да

Munin в сообщении #640951 писал(а):

Дальше литература по операционным системам, так как стратегии выделения памяти, их оптимальность - в основном забота ОС. Язык иногда занимается своей организацией кучи, но только когда он довольно экзотичен по сравнению со стандартными запросами: LISP, Prolog, FORT. Языки типа C++, Java - более стандартны в этом плане. В C++ можно всё взять в свои руки, см. Александреску и книги по стандартной библиотеке.

Вообще, я так думал. Я буду юзать процедуру в программе, исполняющей произвольный код. Для его исполнения мне надо как-то создавать, хранить и удалять переменные, выделять оптимально под них память. Т.е. мне явно надо знать, понятно, что это в обычных программах делается где-то далеко от программиста (в ОС например), и в обычных случаях мне туда лезть незачем. Я решил спросить, как это делается в обычном случае, поскольку это как-то делается и наверняка оптимально. И как-то желательно знать независимо от языка наверное

[venco]

В разных языках настолько по разному, что абстрагироваться невозможно.
Крайние случаи, наверное - C/C++ и JavaScript.
В C обращение к элементу массива - от 1 до 5 инструкций на i385, в зависимости от оптимизации и размера элементов. В JavaScript - явно не константа, и вообще зависит от количества переменных.
В C адрес динамических переменных не меняется и ваша "эффективность" зависит от порядка выделения и освобождения памяти, а в JavaScript куча периодически уплотняется.

[Munin]

Pavia в сообщении #641007 писал(а):

С++ не позволяет делать полноценную сборку мусора в отличии от java.

Если полностью делать её руками, то позволяет. А Java как раз не даёт её контролировать, что в некоторых ситуациях не даёт возможности назвать её полноценной. Редко, к счастью.

Sonic86 в сообщении #641014 писал(а):

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

На этом уровне можно ни о чём не заботиться. Что вы вкладываете в слова "выделять оптимально под них память"?

Практический совет:
1. Сначала реализуйте функциональность.
2. Потом, если возникнут критические проблемы с эффективностью (например, программа работает трое суток вместо 0,3 сек), занимайтесь оптимизацией, начиная с профилирования и выяснения, в чём проблема.
3. Прежде всего решайте проблему изменением алгоритмов и структур данных.
4. Потом занимайтесь мелкой оптимизацией.
5. И только если всё перечисленное не помогает, и проблема действительно в эффективности распределения памяти, пробуйте другие стандартные решения, или занимайтесь их модификацией.
Вероятность прохождения с каждого шага на последующий - примерно 1:10 - 1:100. Так что заранее, засучив рукава, думать об эффективности распределения памяти, вообще не нужно.

Pavia в сообщении #641007 писал(а):

И java я бы посоветовал изучить отдельно. Так как её принципы совершенно отличаются от Си++.

Ну может быть. По крайней мере, как я понимаю, с навыками C++ можно спокойно в Java делать то же самое, и не получать проблем.

[Pavia]

Sonic86
Обычно память ограниченна и для хранения адреса достаточно одного машинноо слова. И сложение выполняется за константное время. У Кнута это описанно.
Также советую прочитать
«Введение в Операционные Системы» Дмитрия Иртегова Глава 4 управление памятью.

Лично когда прилось переписовать стандартную библиотеку. Пришлось создавать кучу. Стараля выбрать алгоритм самый простой, но и эффективный. Уложился в 170 строк. Сравнивать разные алгоритмы трудно, так как нет критерия оптимальности. Но в часи моих тестах он превосходил стандартный алгоритм кучи.

[Munin]

Pavia в сообщении #641117 писал(а):

Сравнивать разные алгоритмы трудно, так как нет критерия оптимальности.

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

[Lyoha]

Pavia в сообщении #641007 писал(а):

Munin

Цитата:

В C++ можно всё взять в свои руки,

С++ не позволяет делать полноценную сборку мусора в отличии от java.

Ну от чего же. Желающие могут всё загнать в stl и boost и получить полную сборку мусора.

[Sonic86]

Ладно, Жабу я пока игнорирую.

Munin в сообщении #641111 писал(а):

Что вы вкладываете в слова "выделять оптимально под них память"?

Так я же написал (хотя не полностью):

Sonic86 в сообщении #640893 писал(а):

Для простоты считаем, что все $n_j\neq 0$. А $m_j$ обозначим число занятых ячеек. Эффективностью выделения памяти назовем величину $E=\frac{1}{N}\sum\limits_{j=1}^N\frac{m_j}{n_j}$.

Munin в сообщении #641111 писал(а):

Практический совет:
...
Вероятность прохождения с каждого шага на последующий - примерно 1:10 - 1:100. Так что заранее, засучив рукава, думать об эффективности распределения памяти, вообще не нужно.

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

venco в сообщении #641028 писал(а):

В C адрес динамических переменных не меняется и ваша "эффективность" зависит от порядка выделения и освобождения памяти

Хотя бы средний случай было бы интересно знать.

Pavia в сообщении #641117 писал(а):

Также советую прочитать
«Введение в Операционные Системы» Дмитрия Иртегова Глава 4 управление памятью.

Спасибо, почитаю.

В общем я пока почитаю....

-- Ср ноя 07, 2012 13:28:16 --

Блин, а в Кнуте какой том? А то тут с содержанием все плохо...

[Munin]

Sonic86 в сообщении #641139 писал(а):

Писать надо сразу правильным алгоритмом, чтоб потом не переписывать

Размечтались. Определить, что правильно, до того, как набьёте на реализации конкретной задачи шишки, нельзя.

Sonic86 в сообщении #641139 писал(а):

Так я же написал (хотя не полностью)

Во-первых, так определённая эффективность разработчика обычно не интересует. Во-вторых, она очень сильно зависит от того, какие запросы на размещение выдаёт программа. Например, можно запрашивать одинаковые блоки, и освобождать их редко, а можно самые разные, и освобождать их часто.

-- 07.11.2012 17:46:34 --

Sonic86 в сообщении #641139 писал(а):

Блин, а в Кнуте какой том? А то тут с содержанием все плохо...

1 том раздел 2.5. Содержание см. http://en.wikipedia.org/wiki/The_Art_of ... ed_volumes

[Munin]

(Оффтоп)

У Иртегова хорошие эпиграфы подобраны :-)

[Sonic86]

Munin в сообщении #641148 писал(а):

1 том раздел 2.5. Содержание см. http://en.wikipedia.org/wiki/The_Art_of ... ed_volumes

Как хорошо, что оно есть!!!

Иртегова легче читать, хотя у него и у Кнута примерно одно и то же. Но я так понял, что неявно предполагается, что под один объект выделяется один кусок памяти, либо противный случай просто не рассматривается. А мне хотя бы придумать, как можно дополнять массив, чтобы потом быстро к нему обращаться.

Как в реальных программах выделяется, тоже не уверен, что понял. Пока представляется так: статическим объектам память выделяется сразу, динамическим объектам память выделяется большими кусками, причем достаточно большая, чтобы объекты влазили в нее целиком, в результате скорость доступа максимально. Оптимальным распределением памяти занимаются описанные алгоритмы и в результате получается чаще всего $E\leqslant 2$. Хотя вроде есть намеки на то, что иногда объект разбивается в памяти на куски. На какие и на сколько - не ясно.

Самые простые варианты, которые сам придумал, такие (случай высвобождения памяти не рассматривал, хотя бы дополнение массивов рассмотреть):

1. Делаем 2 массива. В 1-м храним имена переменных и массивов и номер ячейки памяти, с которых они начинаются. Во 2-м массиве храним значения, причем в случае выделения куска памяти под часть массива последняя ячейка используется как указатель на начало следующего куска массива. Тогда получается $E\leqslant 2$, но скорость доступа возрастает до $O(n)$.

2. Опять делаем 2 массива. Опять в 1-м храним имена переменных и массивов и номер ячейки памяти, с которых они начинаются. Во 2-м массиве выделяем столько памяти, сколько нужно под массив. Тогда, если высвобождения памяти нет, то $E=1$, скорость доступа максимальна, но в случае дополнения существующих массивов старые куски переписываются целиком в новые за $O(n)$.

3. Опять делаем 2 массива. Опять в 1-м храним имена переменных и массивов и номер ячейки памяти, с которых они начинаются. Во 2-м массиве для каждого массива выделяем на 1-м шаге $m$ ячеек, а на $k$-м $m\cdot 2^{k-1}$ ячеек. В результате будет $E\leqslant 2$, скорость доступа $O(\ln n)$ и выделение памяти работает за $O(1)$.

(Оффтоп)

(этот алгоритм меня особенно радует)

Можно это все, конечно, как-то допилить.

С другой стороны, мне сказали, что в C++.net есть какие-то двойные списки, в которых 2-й аргумент может быть произвольным типом. TList и THashMap вроде. Если найду, наверное буду их использовать. Неохота мучиться...

(Оффтоп)

Munin в сообщении #641148 писал(а):

Размечтались. Определить, что правильно, до того, как набьёте на реализации конкретной задачи шишки, нельзя.

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

[Munin]

Sonic86 в сообщении #641673 писал(а):

А мне хотя бы придумать, как можно дополнять массив, чтобы потом быстро к нему обращаться.

Для этого вам придётся отказаться от того, чтобы содержать его в виде массива. Например, можно организовать множество кусков, каждый из которых многоэлементный как массив, а сами куски организованы в список или дерево - за счёт небольшого числа кусков, доступ к нужному куску будет быстрый. Но в стандартных библиотеках такого нет, надо реализовать самому, впрочем, на основе имеющихся std::vector, std::list, std::map/set это делается легко и непринуждённо.

Кроме того, надо подумать, а нужно ли вам при этом всё держать в массиве. std::map может вас вполне устраивать. И разумеется, код надо писать так, чтобы сменить тип контейнера при необходимости можно было легко, не переделывая всего написанного.

Sonic86 в сообщении #641673 писал(а):

Пока представляется так: статическим объектам память выделяется сразу, динамическим объектам память выделяется большими кусками, причем достаточно большая, чтобы объекты влазили в нее целиком, в результате скорость доступа максимально.

С точки зрения языка (и программиста) динамическому объекту выделяется ровно столько памяти, сколько ему нужно. Статический (в смысле static) объект размещается ещё на этапе компиляции и загрузки, в отдельном разделе статических данных. Автоматический (auto) - в момент входа в блок (в Си) или выполнения объявления объекта (C++), в стеке.

Рекомендуется почитать про объектные и загрузочные форматы, работу линкера и загрузчика, работу стека при входе/выходе из функций. Распределение памяти - тема, опирающаяся на этот background. То есть, конечно, в детали она не лезет, но по крайней мере отсюда следует, с какими запросами имеет дело система памяти ОС.

Sonic86 в сообщении #641673 писал(а):

Хотя вроде есть намеки на то, что иногда объект разбивается в памяти на куски.

Это только в случае, если язык позволяет это делать, не предоставляет пользователю слишком низкоуровневого доступа к структуре данных. Например, C++ такого не позволяет никогда. А какой-нибудь APL - может запросто. Или PHP.

Sonic86 в сообщении #641673 писал(а):

скорость доступа возрастает до

Не скорость доступа возрастает, а время доступа возрастает :-) А скорость - падает.

Sonic86 в сообщении #641673 писал(а):

3. Опять делаем 2 массива. Опять в 1-м храним имена переменных и массивов и номер ячейки памяти, с которых они начинаются. Во 2-м массиве для каждого массива выделяем на 1-м шаге $m$ ячеек, а на $k$-м $m\cdot 2^{k-1}$ ячеек. В результате будет $E\leqslant 2$, скорость доступа $O(\ln n)$ и выделение памяти работает за $O(1)$. (этот алгоритм меня особенно радует)

Именно так все и делают, но к сожалению, вы неправильно оценили характеристики. Время доступа как раз $O(1),$ а время выделения памяти амортизированно $O(\ln n),$ но если массив попал на границу размера $m\cdot 2^{k-1},$ и в него автоматной очередью добавляют-убирают последнюю ячейку, то время выделения памяти может неоправданно вырасти. Для этого, освобождают память не сразу, как только массив окажется умещающимся в $m\cdot 2^{k-1}$ ячеек, а с существенной задержкой, например, когда он достигнет размера $m\cdot 2^{k-2}.$

Sonic86 в сообщении #641673 писал(а):

С другой стороны, мне сказали, что в C++.net есть какие-то двойные списки, в которых 2-й аргумент может быть произвольным типом. TList и THashMap вроде. Если найду, наверное буду их использовать. Неохота мучиться...

Не знаю, что там в C++.net, а в стандартной библиотеке C++ есть и std::list, и std::map, а в новой редакции стандарта - и хэш-таблицы std::unordered_map (если вы работаете в старой версии, используйте хэш-таблицы из Boost-а boost::unordered_map).

Sonic86 в сообщении #641673 писал(а):

Если найду, наверное буду их использовать. Неохота мучиться...

Так бы сразу и использовали стандартные контейнеры, зачем всё это накручивать?

Sonic86 в сообщении #641673 писал(а):

Ну может кто-то уже набил шишки и написал книжку о шишках, которую я прочту.

Это хорошо бы, но шишки у всех разные, индивидуальные.

Sonic86 в сообщении #641673 писал(а):

Наконец, можно и в голове поперебирать, это не всегда сложно.

Нет, пока до реализации дело не дойдёт, заранее угадать, на чём будут шишки, нельзя.