Доступная память

← →
guav © (2007-12-20 12:01) [0]

Существует код, выполнение которого потребляет много памяти.
Есть возможность выделять меньше памяти, но это увеличит время выполнения.
Понятно, что 2 ГБ выделить не удастся, выделять 16 МБ, при наличии 512 МБ ОЗУ - не оптимально.
Выделять столько, сколько выделится без ошибки также не оптимально, т.к. интенсивное использование своп-файла замедляет работу больше, чем выполнение алгоритма с меньшим объёмом памяти.

Как узнать сколько памяти лучше выделить ?

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

← →
Eraser © (2007-12-20 12:37) [1]

> guav © (20.12.07 12:01)

думаю, что эврестически составить таблицу соответсвия количества ОЗУ, установленного на машине с количеством памяти, которое можно выделить..
можно еще ввести поправку на количество уже занятой физ. памяти.

← →
homm © (2007-12-20 12:47) [2]

Лучше спросить об этом пользователя, а по умолчанию сделать 40% от ОЗУ.

← →
guav © (2007-12-20 16:14) [3]

> [1] Eraser © (20.12.07 12:37)

Слишком сложно. Ну и сверхточность не нужна, выделение 150 МБ там где можно выделить 240 МБ - это вполне приемлемо.

> [2] homm © (20.12.07 12:47)

А если не спрашивать ? Зачем пользователю опции, не имеющие отношения к выполняемой задачи ?

Я думаю, что система как то может сказать, сколько памяти легко выделить, и задача [0] не является чем-то необычным.

← →
homm © (2007-12-20 16:23) [4]

> [3] guav © (20.12.07 16:14)
> Я думаю, что система как то может сказать, сколько памяти
> легко выделить,

Проблема в том, что как только ты выделишь столько памяти, система попытается скомпенсировать недостаток и вытеснит другие приложения или твое ,что-бы снова освободить столько же. Используй 40%, врял ти ошибешся на сильно.

← →
MBo © (2007-12-20 16:30) [5]

В подобной задаче я половину ОЗУ выделял на машине с 512 и больше, и четверть ОЗУ на машине с 256

P.S. А что за алгоритм?

← →
Сергей М. © (2007-12-20 17:19) [6]

> guav © (20.12.07 16:14) [3]

Юзер сидит и играется в капризную цацку-стрелялку, требующую для "нормальной работы", скажем, 0.5Гб ОЗУ.

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

При всем том на борту установлено шиш да маленько ОЗУ.

Вопрос на засыпку: какой цацке система должна отдать приоритет при распределении ресурсов физ.памяти - твоей или той стрелялке ?)

← →
Eraser © (2007-12-20 17:36) [7]

> Сергей М. © (20.12.07 17:19) [6]

той, которая на фореграунде ;-)

← →
guav © (2007-12-20 17:40) [8]

> [5] MBo © (20.12.07 16:30)

Скажем так, есть большое число целочисленных массивов, надо найти все "конфликты", под конфликтом понимается наличие одинакового элемента в двух разных массивах.

> [6] Сергей М. © (20.12.07 17:19)

Я понимаю что в таком случае ничего разумного сделать нельзя. Цацки не только не поделят память но и процессорное время, и винт тоже будут "гонять". И вообще ни стрелялки ни моя цацка действительно рассчитаны, что большинство ресурсов во время работы принадлежит им. Меня бы устроил результат во время стреляния "памяти нет вообще", если бы ставилась цель работа во время стреляния.

← →
guav © (2007-12-20 17:43) [9]

> [6] Сергей М. © (20.12.07 17:19)

Вопрос [0] - бредовый ?

← →
MBo © (2007-12-21 06:56) [10]

>Скажем так, есть большое число целочисленных массивов, надо найти все "конфликты", под конфликтом понимается наличие одинакового элемента в двух разных массивах.

А можно поподробнее о задаче, и как реализован алгоритм?

← →
Сергей М. © (2007-12-21 08:23) [11]

> guav © (20.12.07 17:43) [9]
> Вопрос [0] - бредовый ?

Ну почему же ?
Не такой уж и бредовый.
Просто подход к решению задачи сделан не с того конца.

← →
guav © (2007-12-21 13:51) [12]

> [10] MBo © (21.12.07 06:56)
> А можно поподробнее о задаче, и как реализован алгоритм?

Псевдокод:
type TPartCoordinates = record Start, End: Int64; // или Start, Count - не важно. end; TObjectOnMap = class(...) ... property PartsCount: Integer read; property Parts[Integer: Integer] read; procedure NotifyInterception(PositionInMap: Int64); end; var Objects: array of TObjectOnMap;

Задача вызвать все NotifyInterception.

а) Двойной цикл это слишком долго, время O(N^2), N = Length(Objects), но памяти O(1)
б) Построить массив от PositionInMap и на основании его обнаруживать пересечения - один проход т.е. время O(N), но памяти O(N) где N - максимальное значение координаты.
в) Решение - разбить "массив от PositionInMap" на части, осуществить проход распределяющий какой из TObjectOnMap к каким частям относится, для каждой части применить подход (б). Размер частей определяется, чтобы часть поместилась в память.
Время выходит O(N*M) M - число частей, памяти O(1). Это в худшем случае, а лучшем случае, когда каждый элемент попал только в одну часть, время будет O(N).
На практике, если разбивать на 2 части или на 10 частей, время будет примерно одинаково (всего лишь в 3 р. больше чем (а), при том что в случае (а) может не хватить памяти, а этот вариант всегда работает), т.е. наблюдается ситуация близкая к "лучшему случаю". Однако, если разбивать на очень большое число частей, время начнёт расти, т.к. требование "лучшего случая" начинает нарушатся.
Соответственно оптимальным является этот вариант, но для "максимальной оптимальности" лучше знать сколько памяти можно "легко взять".

> [11] Сергей М. © (21.12.07 08:23)
> Просто подход к решению задачи сделан не с того конца.

А с какого надо ?

← →
MBo © (2007-12-21 14:56) [13]

К сожалению, я не понял, какие именно пересечения нужно отслеживать, и к чему относится TPartCoordinates.

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

← →
guav © (2007-12-21 17:32) [14]

> [13] MBo © (21.12.07 14:56)

TPartCoordinates это поддиапазоны некого большого диапазона (большой диапазон, размер известен заранее, от 0 до какого-либо int64 значения).
Относится сюда:
property Parts[Integer: Integer]: TPartCoordinates read;
Нужно отслеживать наложения частей различных TObjectOnMap (сами TObjectOnMap не имеют наложений на себя).

← →
MBo © (2007-12-21 18:08) [15]

Возможно, в качестве структуры данных могло бы подойти дерево отрезков (interval tree)

Да, действительно памяти на хранение дерева нужно намного меньше чем памяти на хранение массива индексируемого по значениям. Я пробовал строить дерево, сортированное по началам интервалов, и время оказалось приемлемым. Соответственно, interval tree должно работать хорошо. Осталось только его реализовать.

interval tree обычно делают на основе RB_tree или другого сбалансированного дерева, в Кормене описано, какие функции добавляются.
Реализацию RB_tree найти нетрудно (на дельфи, например, есть в исходниках к книге Бакнелла), готовое интервальное дерево редко встречается

Я прочитал про два варианта дерева отрезков.
1. Дерево отсортировано по точкам деления диапазонов, тогда узел, относящийся к диапазону содержит интервалы, пересекающие эту точку деления. Дочерние узлы - то же самое для частей диапазонов, на которые диапазон разделён точкой в узле. Это дерево позволяет найти все пересечения с заданным интервалом.
2. Дерево отсортировано по началам интервалом. Каждый узел содержит ровно один интервал, также содержит максимальное значение конца интервала в подузлах относящихся к меньшим значениям. Это дерево позволяет найти одно пересечение с заданным интервалом.

Вопрос по варианту 1 - как реализовать баланисрование дерева ?
Вопрос по варианту 2 - а если просто отсортировать массив по началам интервалов, и добавить в него максимумы (для каждого k-того элемента, максимум из 0..k), и производить в таком массиве бинарный поиск в соответствии с алгоритмом поиска узла в дереве, получится ли так ?

для 2) есть модификации, позволяющие найти пересечения со всеми интервалами, а не только одно, но в Кормене это дается как дополнительная задача

массив с бинарным поиском хорош, если набор статичен, а если добавлять-удалять требуется, то дерево эффективнее

А как вы без использования AWE собираетесь выделять память именно в ОЗУ а не там где захочет система? Менеджер памяти AFAIK не поддерживает AWE :)

> [20] MBo © (27.12.07 16:07)

Понял, спасибо.

> [21] Rouse_ © (27.12.07 16:22)

Никак.
Задача была постраратся не использовать своп файл, а не выделять память именно в ОЗУ.

Доступная память Найти похожие ветки