Самый эффективный способ удалить элементы в массиве

[ZW]

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

[debi12345]

Посмотрите в MSEgui, файл "msedatalist.pas". Автор - жутко ненавидит "variants", все тестирует на размер и скорость, поэтому "там" - для простых типов. Думаю, Ваш случай.

Код по части удаления выглядит примерно так:

--------------

procedure deleteitem(var dest: stringarty; index: integer);
begin
if (index < 0) or (index > high(dest)) then begin
tlist.Error(SListIndexError, Index);
end;
dest[index]:= '';
move(dest[index+1],dest[index],sizeof(pointer)*(high(dest)-index));
pointer(dest[high(dest)]):= nil;
setlength(dest,high(dest));
end;

procedure deleteitem(var dest: msestringarty; index: integer);
begin
if (index < 0) or (index > high(dest)) then begin
tlist.Error(SListIndexError, Index);
end;
dest[index]:= '';
move(dest[index+1],dest[index],sizeof(pointer)*(high(dest)-index));
pointer(dest[high(dest)]):= nil;
setlength(dest,high(dest));
end;

procedure deleteitem(var dest: integerarty; index: integer);
begin
if (index < 0) or (index > high(dest)) then begin
tlist.Error(SListIndexError, Index);
end;
move(dest[index+1],dest[index],sizeof(integer)*(high(dest)-index));
setlength(dest,high(dest));
end;

procedure deleteitem(var dest: realarty; index: integer);
begin
if (index < 0) or (index > high(dest)) then begin
tlist.Error(SListIndexError, Index);
end;
move(dest[index+1],dest[index],sizeof(real)*(high(dest)-index));
setlength(dest,high(dest));
end;

procedure deleteitem(var dest: pointerarty; index: integer);
begin
if (index < 0) or (index > high(dest)) then begin
tlist.Error(SListIndexError, Index);
end;
move(dest[index+1],dest[index],sizeof(integer)*(high(dest)-index));
setlength(dest,high(dest));
end;

Примечания :

1) *arty - динамические массивы
2) msestring = widestring
3) для корректировки освободившего места используется сверх-быстрая низкоуровневая "move".

------------

А Ваш "критерий отсева" прямо напрашивается на дополнительный callback-параметр = адрес функции-компаратора, к вышеприведенным процедурам.

[ZW]

Спасибо за информацию. Но неполучается.
У меня такая структура данных:
p[j].x[y]
То есть p : array of x;

Убирать надо элемент x (то есть массив) из p[j]
Исходная процедура такая:
procedure deleteitem(var dest: integerarty; index: integer);
begin
if (index < 0) or (index > high(dest)) then begin
tlist.Error(SListIndexError, Index);
end;
move(dest[index+1],dest[index],sizeof(integer)*(high(dest)-index));
setlength(dest,high(dest));
end;

Но при компиляции возникает ругань на строку setlength(dest,high(dest));
на несовместимость типов.

[debi12345]

Спасибо за информацию. Но неполучается.
У меня такая структура данных:
p[j].x[y]
То есть p : array of x;

Убирать надо элемент x (то есть массив) из p[j]
Исходная процедура такая:
procedure deleteitem(var dest: integerarty; index: integer);
begin
if (index < 0) or (index > high(dest)) then begin
tlist.Error(SListIndexError, Index);
end;
move(dest[index+1],dest[index],sizeof(integer)*(high(dest)-index));
setlength(dest,high(dest));
end;

Но при компиляции возникает ругань на строку setlength(dest,high(dest));
на несовместимость типов.

А если перевести на массив указателей : array of ^x ?

"Там" есть такая же процедура для указателей. Хотя и возня с динамической памятью, но обычно так и делается.

[ZW]

А если перевести на массив указателей : array of ^x ?

"Там" есть такая же процедура для указателей. Хотя и возня с динамической памятью, но обычно так и делается.

А как перевести и как с ним работать?

[SergKam]

а может компилятор не понимает что такое integerarty; ?

[ZW]

а может компилятор не понимает что такое integerarty; ?

Нет, я ему вместо integerarty прописал array of integer

[debi12345]

Нет, я ему вместо integerarty прописал array of integer

А зря. Есть в FPC такой баг-перестраховка на Var-аргументах :

--------------
proc ( var arg: array of integer; ..)
begin
..
setlength(arg, value)
..
end;
-------------

будет ругаться, зато :

----------------
type

integerarty = array of integer;

var
..

proc ( var arg: integerarty; ..)
begin
..
setlength(arg, value)
..
end;
-------------

работает на "ура"


Я тоже не сразу понял, почему автор MSEgui всегда объявляет новый тип для открытых массивов.

[ZW]

Нет, я ему вместо integerarty прописал array of integer

А зря. Есть в FPC такой баг-перестраховка на Var-аргументах :

------------------

работает на "ура"


Я тоже не сразу понял, почему автор MSEgui всегда объявляет новый тип для открытых массивов.

Мда... до этого я бы фиг додумался:)
Но каким образом считать память, что бы вынести элемент из двумерного массива?
Вернее из записи p[j].x[y]
То есть p : array of x;
можно ли рассматривать таким образом: если high(x)=5, то длина записи p[j] 6*integer
то есть move(dest[index+1],dest[index],sizeof(integer)*(high(dest)-index));

превращается в move(p[index+1],p[index],6*sizeof(integer)*(high(p)-index));
или как?

[debi12345]

Мда... до этого я бы фиг додумался:)

Если хотите - напишите баг-репорт (хотя 99% что это давно замечено).

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

Попробуйте sizeof(YOUR_TYPE), как в следующем примере :

//-------------
program test;

type

rec1 = record
tag: PChar;
data: integer;
end;

rec1arrty = array of rec1;

var

i: integer;
var1: rec1arrty;

procedure deleteitem(var dest: rec1arrty; index: integer);
begin
move(dest[index+1],dest[index],sizeof(rec1arrty)*(high(dest)-index));
setlength(dest,high(dest));
end;


begin
setlength(var1,3);

var1[0].tag:= 'mumu';
var1[0].data:= 1;

var1[1].tag:= 'bebe';
var1[1].data:= 2;

var1[2].tag:= 'gaga';
var1[2].data:= 3;

writeln(#13#10+'Before deletion:'+#13#10);
for i:= 0 to high(var1) do begin
writeln(var1[i].tag,'= ',var1[i].data);
end;

deleteitem(var1,1);

writeln(#13#10+'After deletion:'+#13#10);
for i:= 0 to high(var1) do begin
writeln(var1[i].tag,'= ',var1[i].data);
end;

end.
//----

[jwv]

Но каким образом считать память, что бы вынести элемент из двумерного массива?
Вернее из записи p[j].x[y]
То есть p : array of x;
можно ли рассматривать таким образом: если high(x)=5, то длина записи p[j] 6*integer
то есть move(dest[index+1],dest[index],sizeof(integer)*(high(dest)-index));

превращается в move(p[index+1],p[index],6*sizeof(integer)*(high(p)-index));
или как?

Если x это array of integer, то в p хранятся ссылки на масив.
т.е. независимо от того сколько элементов в x, размер элемента в p равен SizeOf(Pointer).

[ZW]

работает нормально только при удалении последнего элемента:(

[debi12345]

работает нормально только при удалении последнего элемента:(

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

[ZW]

работает нормально только при удалении последнего элемента:(

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

мда.... учитывая что там три динамических массива на месте x. Выглядит все печально:(
как нехочется лезть в указатели...

[jwv]

мда.... учитывая что там три динамических массива на месте x. Выглядит все печально:(
как нехочется лезть в указатели...

закинь сюда описание типа.