Уплотнение элементов в памяти

← →
TUser © (2005-05-27 12:12) [0]

Все никак не могу придумать. Есть массив элементов в памяти. В начале работа алгоритма он полностью заполнен. Алгоритм последовательно удаляет элементы из массива (помечает их как Deleted), причем на каждом шаге просматривается весь массив и удаляется один элемент. В результате массив оказывается фрагментированным. При последующем просмотре приходится тратить время на просмотр пустых ячеек (помеченных флагом Deleted).

Соотвественно поддерживается две величины - FMaxIndex (самый большой индекс) и FCount (количество неудаленных элементов). В начале работы FMaxIndex = FCount-1, при удалении элементов FCount уменьшается, а FMaxIndex остается неизменным.

Есть также процедура дефрагментации, которая умеет собрать все непустые ячейки в начало массива. Ее работа эквивалентная 2м проходам по массиву (ну или 3м - не важно, какая-то константа). после ее работы массив не содержит пустот (в диапахоне 0..FMaxIndex), и выполнено условие FMaxIndex = FCount-1.

Пусть в некоторый момент FCount < FMaxIndex, и мы проводим дефрагментацию. Понятно, что при последующих N удалениях мы сэкономим N*(FMaxIndex-FCount) шагов при просмотре массива. Сама же операция дефрагментации требует 2*FMaxIndex шагов. Понятно, что дефрагментация будет выгодна, если N*(FMaxIndex-FCount) > 2*FMaxIndex.

Вот хочу посоветоваться, при каких условиях надо проводить дефрагментацию, чтобы получился максимально быстрый код? Можно, например, проводить ее только после такого количества шагов, когда получена выгода от предыдущей дефрагментации, можно фиксировать N и дефрагментировать тогда, когда будет получена выгода при следующих N шагах, можно еще бог знает что придумать. Но обшая задача такая - на данном шаге есть FMaxCount и FCount (и возможно N - но как его тогда выбирать?), надо придумать такое условие проведения (или непроведения) дефрагментации, чтобы оптимизировать алгоритм по скорости.

← →
Virgo_Style © (2005-05-27 12:15) [1]

TUser © (27.05.05 12:12)

А список нельзя использовать?

← →
DiamondShark © (2005-05-27 12:18) [2]

Завести второй массив, в котором хранить индексы пустых элементов.
Доступ ко второму массиву сделать как очередь FIFO.
В этом случае поиск пустого элемента выполняется за время О(1)

← →
Eraser © (2005-05-27 12:19) [3]

TUser © (27.05.05 12:12)

Сколько примерно элиментов в массиве?

← →
DiamondShark © (2005-05-27 12:22) [4]

Ой. Что-то я не так понял.

← →
DiamondShark © (2005-05-27 12:23) [5]

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

← →
-=XP=- © (2005-05-27 12:25) [6]

А список нельзя использовать?

TList? (Или Вы не про него?) Он тоже производит переупорядочивание после каждого удаления (последнего элемента):

procedure TList.Delete(Index: Integer); begin ... if Index < FCount then System.Move(FList^[Index + 1], FList^[Index], (FCount - Index) * SizeOf(Pointer)); ... end;

Или Вы про такой список (?):

PItem = ^TItem; TItem = record Value: TValueType; Next: PItem; end;

Тогда удаление:

var
Item: PItem;
Tmp: PItem;
...
Tmp := Item^.Next;
Item^.Next := Item^.Next^.Next;
FreeMem(Tmp);

← →
КаПиБаРа © (2005-05-27 12:26) [7]

TUser © (27.05.05 12:12)
Задачу объясни по русски. А то даже
Ой. Что-то я не так понял.
(с) DiamondShark

← →
Anatoly Podgoretsky © (2005-05-27 12:27) [8]

А при удалении обмен значений, удаляемого и последнего, с корректировкой FCount, FMaxIndex тогда совсем не нужен. Или важен порядок элементов?

← →
TUser © (2005-05-27 12:54) [9]

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

Поиск пустого элемента не нужен вообще. При дефрагментации просматриваем массив и копируем непустые элементы на место пустых. [8] неподходит, т.к. важен порядок следования элементов.

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

← →
boriskb © (2005-05-27 12:58) [10]

TUser © (27.05.05 12:54) [9]
Вопрос:
Чего больше в задаче:
а) изменения массива (дополнение/удаление элементов)
б) поиска в массиве
???

← →
-=XP=- © (2005-05-27 13:08) [11]

Насчет дефрагментации "При дефрагментации просматриваем массив и копируем непустые элементы на место пустых". Не знаю, что быстрее:
1. При каждом удалении перемещать "хвост" целиком на один элемент к началу массива (перемещение блока памяти). Итого, 10 тыс. элементов - 10 тыс. перемещений за все время работы алгоритма. Перемещаются большие куски памяти, но это работа контроллера памяти и процессора без вмешательства Вашей программы.
2. Просмотр массива и копирование с места на место по одному элементы массива (я правильно понял?)? Итого, до 10 тыс. (в худшем случае) операций копирования на каждую операцию дефрагметации.

← →
Eraser © (2005-05-27 13:15) [12]

TUser © (27.05.05 12:54) [9]

Может стОит вообще отказаться от дефрагментации по ходу заполнения, а дефрагментировать после окончания вычислений?

Ведь базы данных не упаковываются посреди транзакций... а тут ситуация чем то напоминает БД, только + порядок элиментов тут важен...

← →
DiamondShark © (2005-05-27 13:28) [13]

> TUser © (27.05.05 12:54) [9]

Связные списки сохраняют порядок следования и не требуют дефрагментации.

Доступ к структуре толко последовательный, или требуется произвольный?

← →
TUser © (2005-05-27 13:29) [14]

> Чего больше в задаче:

Примерно поровну

> -=XP=- © (27.05.05 13:08) [11]

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

procedure RemakeArray; // с упращениями function GetNextGap (St: integer): integer; begin result:={первый пустой элемент с индексом <> St} end; function GetNextLine (St: integer): integer; begin result:={первый непустой элемент с индексом <> St} end; // прим. если GetNextGap и GetNextLine не могут до конца // массива найти нужный элемент, то result:=FMaxIndex+1; var h: integer; g1, ln, g2: integer; n: integer; i: integer; begin g1:=GetNextGap (0); h:=g1-1; repeat ln:=GetNextLine(g1); g2:=GetNextGap (ln); {move ln..g2-1 to h+1} n:=g2-ln; if ln <= FMaxIndex then begin MoveMemory (@FArray[h+1],@FArray[ln],sizeof(TElement)*n); ZeroMemory (@FArray[h+n+1],sizeof(TElement)*(ln-h-1)); end; h:=h+n; g1:=g2; until g1 > FMaxIndex; FMaxIndex:=h; end;

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

← →
TUser © (2005-05-27 13:35) [15]

> Может стОит вообще отказаться от дефрагментации по ходу заполнения, а дефрагментировать после окончания вычислений?

Да в принципе так и есть сейчас. И ускорение от этой дефрагментации получается незначительное (сейчас). Но вот шило в одном месте у меня требует дальнейшей оптимизации - хочется придумать какой-то другой способ выбора моментов для дефрагментации.

> DiamondShark © (27.05.05 13:28) [13]

Требуется произвольный

> с упрОщениями

← →
pasha_golub © (2005-05-27 14:35) [16]

А может дефрагментацию делать во время простоя приложения (OnIdle) или нужно делать во время вычислений?

← →
-=XP=- © (2005-05-27 14:43) [17]

А может дефрагментацию делать во время простоя приложения (OnIdle) или нужно делать во время вычислений?

О! Точно! В отдельном потоке! :)

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

← →
-=XP=- © (2005-05-27 14:45) [18]

то на двухпроцессорной системе

В смысле, на P4 c HT - тоже.

← →
КаПиБаРа © (2005-05-27 14:48) [19]

TUser © (27.05.05 13:35) [15]
Размер элемента массива какой? Если элементы большие то в массиве можно дердать указатели на них.

← →
-=XP=- © (2005-05-27 14:48) [20]

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

А давайте Вы напишите простенький класс, реализующий связанный список, который будет выглядеть для Вашей программы как массив. Подставите его в программу - и посмотрите, что получилось. Работы - на два часа, не больше.

P.S. Только не говорите, куда мне нужно идти. :)

← →
Digitman © (2005-05-27 14:51) [21]

> При последующем просмотре приходится тратить время на просмотр
> пустых ячеек (помеченных флагом Deleted).

зато то же самое время с лихвой компенсирует временные издержки на реаллокацию памяти

← →
TUser © (2005-05-27 14:57) [22]

А может дефрагментацию делать во время простоя приложения (OnIdle) или нужно делать во время вычислений?

Там нет простоя

> Размер элемента массива какой? Если элементы большие то в массиве можно дердать указатели на них.

См [9]. В массиве реально храняться указатели, поскольку тип элементов - это класс.

← →
pasha_golub © (2005-05-27 14:58) [23]

Digitman © (27.05.05 14:51) [21]
Согласен. Но у автора ведь чисто академический интерес. Так сказать разминка для мозга, если я правильно его понял.

← →
TUser © (2005-05-27 14:58) [24]

> зато то же самое время с лихвой компенсирует временные издержки на реаллокацию памяти

Вот в тот-то и вопрос - в какие моменты надо проводить реаллокацию (т.е. я так понимаю имелась в виду дефрагментация), чтобы получить оптимальную скорость.

> Согласен. Но у автора ведь чисто академический интерес. Так сказать разминка для мозга, если я правильно его понял.

Скажем так - если не получиться это сделать - я не заплАчу, если получиться - возьму себе пирожок с полку :)

var A: array[0..9999] of PData; Max: integer = 10000; NewMax: integer; begin { Тут подготовка данных } while (Max > 0) do begin for i := 0 to Max - 1 do begin { Тут выполняем обработку согласно алгоритма, а потом } if not {Элемент не нужен} then begin A[NewMax] := A[i]; NewMax := NewMax + 1; end else FreeMem(A[i]); end; Max := NewMax; NewMax := 0; end; end;

Где-то так...?

{ Тут выполняем обработку согласно алгоритма, а потом }

Читать как: { Тут выполняем обработку элемента массива A[i] согласно алгоритма, а потом }

Ну как результаты?
Интересно.
:о)

> [14] TUser © (27.05.05 13:29)

Можешь ускорить используя вместо MoveMemory и ZeroMemory соответственно Move и FillChar которые и вызываются в тех функциях.

А вообще опиши для чего такой массив нужен? Может можно гораздо проще сделать.

> Ну как результаты?

Докладываю. Сначала скажем так. Есть убывающая последовательность чисел C[0] > C[1] > ... C[n-1], где C[0] - изначальное число FCount, а остальные числа - это такие значения, при которых проводится реструктурирование. C[n-1] - это конечное число элементов. Положим также C[n]:=0.

Тогда между C[i] и C[i+1] мы выполняем всегда C[i] шагов для удаления каждого элемента, а всего мы это делаем С[i]-C[i+1] раз. Дефрагментация занимает 2*C[i] шагов.

После достижения C[n-1] мы также проводим дефрагментацию ценой 2*C[n-1]. Поэтому общее количество шагов есть
Summ(i:=0..n-1)((C[i]-C[i+1])*C[i]+2*C[i])-C[n-1]*C[n-1]
Надо найти такую последоватльность чисел, при которой эта сумма минимальна. (Заранее число таких числел нам неизвестно.)

Я немного поигрался на бумаге и вроде бы получается, что надо брать C[i+1]:=C[i] shr 1. Потом написал тест, который это проверяет. Погеймился в эту программу. Получается, что такой результат не оптимален, но близок к оптимальному. Исходники этого теста могу выложить, если кому надо.

Короче, у себя я так и сделал - вычисляю последующее число FCount, требующее дефрагментации, как C[i] shr 1. Разогналось примерно на 25%.

> Можешь ускорить используя вместо MoveMemory и ZeroMemory соответственно Move и FillChar которые и вызываются в тех функциях.

Это копейки

Как я понял, тебе надо просто держать несколько индексов по массиву... Один для дефрагментации и т. д. Вообще, эта задача, только в более общей форме, суть представление строк таблицы в БД

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

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

мне кажется, использование списка -- хорошая идея.
список -- это не TList, а связанный двунаправленный список. аля с++ std::list<Т>

можно попробовать скрестить список с массивом..

пускай каждый неудаленный элемент в массиве знает 2 индекса (или указателя - 1 пень) -- недуаленного элемента, следующего за ним, и неудаленного эелемента, предшествующего ему.
То есть это фактически и есть двунаправленный список, все элементы которого расположены в массиве. тогда при каждом проходе по этому "списку" ты будешь проверять только нужные элементы..
и дефрагментация вообще окажется не нужной..

для быстрой вставки можно выстроить такой же "список" для пустых элементов

тогда при удалении/вставке, элемент за время О(1) удаляется из одного списка и регистрируется в другом.

Уплотнение элементов в памяти Найти похожие ветки