Добавление в массив элемента

← →
@!!ex © (2008-03-26 06:53) [0]

Есть массив элементов.
Один поток перебирает элементы и обрабатывает их.
Второй, изредка дергает функцию добавления элементов в массив.
Вопрос в том, насколько корректно, что в массив добавляются элементы во время обработки массива другим потоком?
Смотрю, вроде никаких проблем не возникает. Ну добавились элементы, потом их просто игнорирует и обрабатывает при повторном проходе.
Но это первый взгляд. А на самом деле как?

← →
MBo © (2008-03-26 07:05) [1]

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

← →
@!!ex © (2008-03-26 07:13) [2]

Обработка:
procedure TObjectsControl.Update(dt: integer); var Index:integer; begin for Index:=0 to count-1 do Items[Index].Update(dt); end;

Добавление:
procedure TObjectsControl.Assign(GameObject: TGameObject); begin inc(Count); SetLength(Items,Count); Items[Count-1]:=GameObject; Items[Count-1].Enabled:=true; end;

Если синхронизировать, то весь смысл использования потоков теряется, скорость один в 1, как на одном потоке.

← →
@!!ex © (2008-03-26 07:19) [3]

Подумал сделать вот так:

Lock:TCriticalSection; procedure TObjectsControl.Update(dt: integer); var Index:integer; Obj:TGameObject; begin for Index:=0 to count-1 do begin Lock.Enter; Obj:=Items[Index]; Lock.Leave; Obj.Update(dt); end; end; procedure TObjectsControl.Assign(GameObject: TGameObject); begin Lock.Enter; inc(Count); SetLength(Items,Count); Items[Count-1]:=GameObject; Items[Count-1].Enabled:=true; Lock.Leave; end;
Это нормальный подход?

← →
TUser © (2008-03-26 07:20) [4]

Пример неприятности.

Первый поток
while i<= length do
something with A[i]
inc (i);

Второй поток
SetLength (A, length + 1);
A[lenght-1] := anyshing.

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

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

flag := false;
SetLength (A, length + 1);
A[lenght-1] := anyshing.
Flag := true;

а первый

while true do
while not flag do begin end;
do somthing with A[i];
inc (i);
if i > length then break;

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

← →
TUser © (2008-03-26 07:21) [5]

> @!!ex © (26.03.08 07:13) [2]
>
>

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

← →
MBo © (2008-03-26 07:24) [6]

>SetLength(Items,Count);

При этом Items располагается по новому адресу со всеми вытекающими....

Кстати, у тебя массив наращивается по одному элементу - это невыгодно, частые перераспределения памяти.

← →
MBo © (2008-03-26 07:25) [7]

http://mbo88.narod.ru/ToC.html

← →
TUser © (2008-03-26 07:27) [8]

> При этом Items располагается по новому адресу со всеми вытекающими.
> ...
>

Да, действительно. Мои рассуждения можно не читать.

← →
MBo © (2008-03-26 07:28) [9]

Посмотри еще TThreadList в classes - там простейшая защита крит. секцией

← →
@!!ex © (2008-03-26 07:31) [10]

> Но вообще, не стоит оно того, - поставь критические секции.
> В общем случае, даже с применением такого флага могут быть
> проблемы.

В [3] поставил критические секции. Правильно?

> >SetLength(Items,Count);
> При этом Items располагается по новому адресу со всеми вытекающими....

Да, я поэтому поставил критически секции. Правильно?

> Кстати, у тебя массив наращивается по одному элементу -
> это невыгодно, частые перераспределения памяти.

Количество элементов очень маленькое(в среднем 20, больше 50 редко). И меняется обычно не больше 1 раза в секунду, ну максимум 5.
Где массивы большие, там по другому реализовано. Выделение блоками, по 10, плюс удаление не уменьшает массив. Поэтому массив доходит до некоторого количества и замораживается, хотя элементы продолжают добавлятся и удалятся.

← →
tesseract © (2008-03-26 10:22) [11]

> В [3] поставил критические секции. Правильно?

Обычно так и делаеться. Хотя есть варианты с потокобезопастным Tlist или очередью (не родным).

← →
Паша 1 (2008-03-26 11:35) [12]

> MBo © (26.03.08 07:05) [1]

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

← →
@!!ex © (2008-03-26 12:16) [13]

> ну откуда неприятности?

Realloc массива, перенос его в другой участок памяти

← →
Паша 1 (2008-03-26 12:23) [14]

а! пардон, нумер [6] не увидел. а что, в другом потоке ссылка на массив "левая" остается? я с работой на низком уровне не сталкивался просто

← →
tesseract © (2008-03-26 12:24) [15]

> зачем там критические секции с массивом? я не прав?

Они и не для массива нужны. Дабы значение переменной не напоминало функцию Random.

> Количество элементов очень маленькое(в среднем 20, больше
> 50 редко).

А почему просто не сделать тогда массив длины MAX_LEN и отдельно переменную ArrayLength?

> [16] Mystic © (26.03.08 13:27)

Хотя бы потому, что я не уверен, что количество элементов в дальнейшем не вырастет.
Да и не вижу смысла приходить к искусственным ограничениям.
Там где массив большой и часто обнеовляется, все работает немного по другому, а смысл оптимизировать то, что и так быстро работает?

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

Это не оптимизация, удо еще и удобство работы: не нужны вызовы SetLength. Это всегда так: в чем-то выигрываешь, в чем-то проигрываешь...

Ограничения же можно ввести, например
(1) из условий задачи (например на шахматной доске 64 клетки)
(2) из разумных пределов, превышение которого наверняка вызовет сбой в программе (например у нас есть N объектов, а затем в памяти строится все перестановки этих объектов. Таких перестановок N!, логично что число N можно ограничить, скажем, 1000. Ибо 1000! уже 4.0E2567, и навряд ли в ближайшем будущем быстродействие и память достигнет таких пределов, чтобы их можно было сгенерить.

> @!!ex (26.03.2008 6:53:00) [0]

Ты про динамические массивы?
И не видишь проблем, они же перемещаются в памяти.

> Mystic (26.03.2008 13:27:16) [16]

И последовательность, снача присвоение, а потом наращивание счетчика. Правда остается еще и удаление, где это не поможет.

> [19] Anatoly Podgoretsky © (26.03.08 15:14)

Так в [2] вынес в критическую секцию.

> [20] Anatoly Podgoretsky © (26.03.08 15:17)

ТАк вроде for в начале расчитывает условие выхода и потом его не трогает?

Удаление - в отдельной критической секции. Когда элементы удаляются доступ запрещен к массиву.

IMXO:
При заданных условиях по кол-ву элементов массива [10]
конечно нужно использовать статиеский массив конечной разумной
длины.В структуру элtмента можно добавить поле индекса элемента в
массиве (или м.б. номер его поступления), индексу 0 соответствует
невалидный элемент, тогда легко будет удалять элементы присваивая им
индекс=0. Естественно поле индекса должно заполняться последним.

Добавление в массив элемента Найти похожие ветки