| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Доступная память
guav © (2007-12-20 12:01:00)Существует код, выполнение которого потребляет много памяти.
Есть возможность выделять меньше памяти, но это увеличит время выполнения.
Понятно, что 2 ГБ выделить не удастся, выделять 16 МБ, при наличии 512 МБ ОЗУ - не оптимально.
Выделять столько, сколько выделится без ошибки также не оптимально, т.к. интенсивное использование своп-файла замедляет работу больше, чем выполнение алгоритма с меньшим объёмом памяти.
Как узнать сколько памяти лучше выделить ?
Предполагается выделение непрерывной области памяти, однако можно реализовать работу и с кусками, если оно того стоит.
guav (2007-12-27 22:59:00) [1]> [20] MBo © (27.12.07 16:07)
Понял, спасибо.
> [21] Rouse_ © (27.12.07 16:22)
Никак.
Задача была постраратся не использовать своп файл, а не выделять память именно в ОЗУ.
Rouse_ (2007-12-27 16:22:00) [2]А как вы без использования AWE собираетесь выделять память именно в ОЗУа не там где захочет система? Менеджер памяти AFAIK не поддерживает AWE :)
MBo (2007-12-27 16:07:00) [3]для 2) есть модификации, позволяющие найти пересечения со всеми интервалами, а не только одно, но в Кормене это дается как дополнительная задача
массив с бинарным поиском хорош, если набор статичен, а если добавлять-удалять требуется, то дерево эффективнее
guav (2007-12-27 00:25:00) [4]Я прочитал про два варианта дерева отрезков.
1. Дерево отсортировано по точкам деления диапазонов, тогда узел, относящийся к диапазону содержит интервалы, пересекающие эту точку деления. Дочерние узлы - то же самое для частей диапазонов, на которые диапазон разделён точкой в узле. Это дерево позволяет найти все пересечения с заданным интервалом.
2. Дерево отсортировано по началам интервалом. Каждый узел содержит ровно один интервал, также содержит максимальное значение конца интервала в подузлах относящихся к меньшим значениям. Это дерево позволяет найти одно пересечение с заданным интервалом.
Вопрос по варианту 1 - как реализовать баланисрование дерева ?
Вопрос по варианту 2 - а если просто отсортировать массив по началам интервалов, и добавить в него максимумы (для каждого k-того элемента, максимум из 0..k), и производить в таком массиве бинарный поиск в соответствии с алгоритмом поиска узла в дереве, получится ли так ?
MBo (2007-12-26 17:42:00) [5]interval tree обычно делают на основе RB_tree или другого сбалансированного дерева, в Кормене описано, какие функции добавляются.
Реализацию RB_tree найти нетрудно (на дельфи, например, есть в исходниках к книге Бакнелла), готовое интервальное дерево редко встречается
guav (2007-12-26 16:25:00) [6]Да, действительно памяти на хранение дерева нужно намного меньше чем памяти на хранение массива индексируемого по значениям. Я пробовал строить дерево, сортированное по началам интервалов, и время оказалось приемлемым. Соответственно, interval tree должно работать хорошо. Осталось только его реализовать.
guav (2007-12-21 19:38:00) [7]> [15] MBo © (21.12.07 18:08)
Спасибо, похоже что то что нужно.
Попробую позже.
MBo (2007-12-21 18:08:00) [8]Возможно, в качестве структуры данных могло бы подойти дерево отрезков (interval tree)
guav (2007-12-21 17:32:00) [9]> [13] MBo © (21.12.07 14:56)
TPartCoordinates это поддиапазоны некого большого диапазона (большой диапазон, размер известен заранее, от 0 до какого-либо int64 значения).
Относится сюда:
property Parts[Integer: Integer]: TPartCoordinates read;
Нужно отслеживать наложения частей различных TObjectOnMap (сами TObjectOnMap не имеют наложений на себя).
MBo (2007-12-21 14:56:00) [10]К сожалению, я не понял, какие именно пересечения нужно отслеживать, и к чему относится TPartCoordinates.
Я почему интересуюсь - а вдруг для твоих целей подойдет какая-либо хитрая структура данных...
guav (2007-12-21 13:51:00) [11]> [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)
> Просто подход к решению задачи сделан не с того конца.
А с какого надо ?
Сергей М. (2007-12-21 08:23:00) [12]
> guav © (20.12.07 17:43) [9]
> Вопрос [0] - бредовый ?
Ну почему же ?
Не такой уж и бредовый.
Просто подход к решению задачи сделан не с того конца.
MBo (2007-12-21 06:56:00) [13]>Скажем так, есть большое число целочисленных массивов, надо найти все "конфликты", под конфликтом понимается наличие одинакового элемента в двух разных массивах.
А можно поподробнее о задаче, и как реализован алгоритм?
guav (2007-12-20 17:43:00) [14]> [6] Сергей М. © (20.12.07 17:19)
Вопрос [0] - бредовый ?
guav (2007-12-20 17:40:00) [15]> [5] MBo © (20.12.07 16:30)
Скажем так, есть большое число целочисленных массивов, надо найти все "конфликты", под конфликтом понимается наличие одинакового элемента в двух разных массивах.
> [6] Сергей М. © (20.12.07 17:19)
Я понимаю что в таком случае ничего разумного сделать нельзя. Цацки не только не поделят память но и процессорное время, и винт тоже будут "гонять". И вообще ни стрелялки ни моя цацка действительно рассчитаны, что большинство ресурсов во время работы принадлежит им. Меня бы устроил результат во время стреляния "памяти нет вообще", если бы ставилась цель работа во время стреляния.
Eraser (2007-12-20 17:36:00) [16]
> Сергей М. © (20.12.07 17:19) [6]
той, которая на фореграунде ;-)
Сергей М. (2007-12-20 17:19:00) [17]
> guav © (20.12.07 16:14) [3]
Юзер сидит и играется в капризную цацку-стрелялку, требующую для "нормальной работы", скажем, 0.5Гб ОЗУ.
При этом юзер желает одновременно играться и в твою цацку, которая не менее капризна и тоже желает энное кол-во опер.памяти для якобы комфортной работы юзера.
При всем том на борту установлено шиш да маленько ОЗУ.
Вопрос на засыпку: какой цацке система должна отдать приоритет при распределении ресурсов физ.памяти - твоей или той стрелялке ?)
MBo (2007-12-20 16:30:00) [18]В подобной задаче я половину ОЗУ выделял на машине с 512 и больше, и четверть ОЗУ на машине с 256
P.S. А что за алгоритм?
homm (2007-12-20 16:23:00) [19]> [3] guav © (20.12.07 16:14)
> Я думаю, что система как то может сказать, сколько памяти
> легко выделить,
Проблема в том, что как только ты выделишь столько памяти, система попытается скомпенсировать недостаток и вытеснит другие приложения или твое ,что-бы снова освободить столько же. Используй 40%, врял ти ошибешся на сильно.
guav (2007-12-20 16:14:00) [20]> [1] Eraser © (20.12.07 12:37)
Слишком сложно. Ну и сверхточность не нужна, выделение 150 МБ там где можно выделить 240 МБ - это вполне приемлемо.
> [2] homm © (20.12.07 12:47)
А если не спрашивать ? Зачем пользователю опции, не имеющие отношения к выполняемой задачи ?
Я думаю, что система как то может сказать, сколько памяти легко выделить, и задача [0] не является чем-то необычным.
| |
Страницы: 