Здравствуйте.
Есть одномерный массив элементов некоторого типа.
Для определенного типа элементов процедура перестановки соседних элементов может быть такой
procedure RevCns(var c: TCns; i: Integer);
var p: TCn;
begin
p:= c[i]; c[i]:= c[i+1]; c[i+1]:= p;
end;
Необходимо написать универсальную процедуру перестановки его соседних элементов для массива любого типа.
Можно ли это сделать. Если можно, то как?
Уважаемые авторы вопросов! Большая просьба сообщить о результатах решения проблемы на этой странице. Иначе, следящие за обсуждением, возможно имеющие аналогичные проблемы, не получают ясного представления об их решении. А авторы ответов не получают обратной связи. Что можно расценивать, как проявление неуважения к отвечающим от автора вопроса.
17-01-2023 01:43 | Комментарий к предыдущим ответам
Дополнение к предидущему коментарию. На самом деле немного не так написал. Это вот эта версия опасна
так как как раз в нее в качестве первого аргумента можно подставить все, что угодно, и проверок тут не делается а приводистя аргумент к TArray<T>, со всеми вытекающими, практика показывает, что в случае ошибки отлавливать ее можно неопределенное время :D
А как раз для класса TSwapper
TSwapper=class
class procedure RevCns<T>(var A: T; i: Integer);
end;
при реализации первым делом проверяется что A это tkArray или tkDynArray, если нет то исключение, так что в с RTTI можно реализовать не только универсально но и сейфово.
17-01-2023 00:38 | Комментарий к предыдущим ответам
А зачем тогда с мувами возиться, разве вот так не будет работать
Да вы праввы мувы в такой реализации ни к чему. Они там появились у меня по инерции :) , просто я бы лично пользовался вторым вариантом функции
так как указывать при вызове тип явно, очень может быть неудобно. Ну а таком случае без мувов никак.
А чем тогда иеговистский дженерик лучше православных решений на Delphi 7? :-)
К тому же, глобальная функция не может быть определена с дженериками (компилятор подсказал :-))
По моему дженерик в данной ситуации лучшее решение. Согласитесь реализация функции котоую вы сами написали выглядит наиболее просто и читабельно. Но при вызове надо указывать тип явно, это жирный минус для меня. То что глобальной функции не определить не велика проблема, хотя да бывает хочется, чтобы лишнего не писать. Но я бы, если бы мне надо было делал бы какой то такой class
TSwapper=class
class procedure RevCns<T>(var A: T; i: Integer);
end;
Тогда вызов
TSwapper.RevCns(A,i)
Вобщем та же глобальная функция по сути. Реализация этого метода намного более заморочливое дело чем те первые два варианта, но зато наиболее универсальное решение, для любых типов массивов, а не только для TArray<T>. А это может быть очень важно. Минус один в качестве первого аргумента можно подстваить все что угодно и даже исключения может не быть в рантайме, если не то подставил :), но это плата за универсальность. Реализовать это в Delphi7 никак нельзя.
А зачем тогда с мувами возиться, разве вот так не будет работать
procedure TForm1.RevCns<T>(var A: TArray<T>; i: Integer);
var
p: T;
begin
p := A[i];
A[i] := A[i+1];
A[i+1] := p;
end;
?
>>> но тут уже надо в теле функции через RTTI находить тип масиива и пользуя информацию TTypeData делать необходимые манипуляции
А чем тогда иеговистский дженерик лучше православных решений на Delphi 7? :-)
К тому же, глобальная функция не может быть определена с дженериками (компилятор подсказал :-))
Хмммм... А дженерики то зачем? Или только православный Delphi7? :D
procedure TForm1.RevCns<T>(var c: TArray<T>; i: Integer);
var p : T;
sz : integer;
begin
sz:=sizeof(T);
Move(c[i],p,sz);
Move(c[i+1],c[i],sz);
Move(p,c[i+1],sz);
end;
При вызове функции тип нужно будет явно указать, например:
var arr_uint8:TArray<uint8>;
тогда вызов RevCns<uint8>(arr_uint8,5);
Можно модифицировать функцию так чтобы не указывать тип явно при вызове:
procedure TForm1.RevCns1<T>(var c; i: Integer; e: T);
var p : T;
sz : integer;
begin
sz:=sizeof(T);
Move(TArray<T>(c)[i],p,sz);
Move(TArray<T>(c)[i+1],TArray<T>(c)[i],sz);
Move(p,TArray<T>(c)[i+1],sz);
end;
тогда вызов RevCns1(arr_uint8,5,arr_uint8[0]) , здесь уже конечно ответсвенность за передачу параметра var лежит на програмисте.
Если нужно, чтобы массив был кастомный, а не TArray<T>, то generic функция может быть вида TForm1.RevCns<T>(var c: T; i: Integer), но тут уже надо в теле функции через RTTI находить тип масиива и пользуя информацию TTypeData делать необходимые манипуляции.
16-11-2022 01:08 | Комментарий к предыдущим ответам
Аналогичный оптимизационный подход я наблюдал в ассемблерной реализации процедуры Move: там сначала выполняется MOVSD, копируя основную часть блоками по ч байта, а остаток добирается командами MOVSW и MOVSB.
Я обычно не занимаюсь такой оптимизацией и использую MOVSD или MOVSW только тогда, когда из постановки задачи следует, что длина области данных всегда кратна 4 или 2. В остальных случаях использую MOVSB.
Кстати, раз уж пошла речь об оптимизации... Поскольку из четырех локальных переменных в любой конкретный момент времени требуется не больше одной, то можем еще и стек оптимизировать
procedure SwapMem(p1,p2:pointer;len:integer);
var i64:Int64;
i:Integer absolute i64;
w:word absolute i64;
b:byte absolute i64;
begin
14-11-2022 18:30 | Комментарий к предыдущим ответам
to Geo
Оказывается блоки памяти можно обменивать эффективнее. Реализацию подсмотрел в CompareMem
procedure SwapMem(p1,p2:pointer;len:integer);
var i64:Int64;
i:Integer;
w:word;
b:byte;
begin
while len>=8 do
begin
i64:=pInt64(p1)^;
pInt64(p1)^:=pInt64(p2)^;
pInt64(p2)^:=i64;
inc(pInt64(p1));
inc(pInt64(p2));
dec(len,8);
end;
if len>=4 then
begin
i:=pInteger(p1)^;
pInteger(p1)^:=pInteger(p2)^;
pInteger(p2)^:=i;
inc(pInteger(p1));
inc(pInteger(p2));
dec(len,4);
end;
if len>=2 then
begin
w:=pWord(p1)^;
pWord(p1)^:=pWord(p2)^;
pWord(p2)^:=w;
inc(pWord(p1));
inc(pWord(p2));
dec(len,2);
end;
if len=1 then
begin
b:=pByte(p1)^;
pByte(p1)^:=pByte(p2)^;
pByte(p2)^:=b;
end;
end;
14-11-2022 13:10 | Комментарий к предыдущим ответам
to NERO:
Точно. Мы немножко проигрываем в быстродействии, немножко выигрываем в использовании памяти и очень сильно выигрываем в читаемости кода, так как избавляемся от ассемблера. Респект.
14-11-2022 00:45 | Комментарий к предыдущим ответам
to GEO
В массиве фиксированных типах данных, промежуточный буффер не нужен. Вместо обмена цельных фрагментов (move), нужно делать циклический обмен байтов, между условными указателями p1 (первый фрагмент) и p2 (второй фрагмент), на длину фрагмента, используя только один промежуточный байт. Далее выставляем указатели p1, p2 на новые участки фрагментов и повторяем цикл
Пример кода выполняющего быструю сортировку для integer.
procedure _SortArrInteger(p_bg,p_end:pointer); // l,r
Var pB,pE:pointer;
t,m:integer;
Begin
if (NativeUInt(p_bg)>=NativeUInt(p_end)) then exit; // if (l>=r) then exit;
Repeat
pB:=p_bg; // i:=l;
pE:=p_end; // j:=r;
m:=pInteger(NativeUInt(p_bg)+(((NativeUInt(p_end)-NativeUInt(p_bg)) shr 3) shl 2))^; // m:=a[(l+r) shr 2];
//m:=pInteger(((Int64(p_end)+Int64(p_bg)) shr 3) shl 2)^; // m:=a[(l+r) shr 2];
Repeat
While pInteger(pB)^<m do Inc(pInteger(pB)); // While a[i]<m do Inc(i); // сортировка в порядке возрастания, то a[i]>m
While pInteger(pE)^>m do Dec(pInteger(pE)); // While a[j]>m do Dec(j); // a[j]<m
if NativeUInt(pB)<=NativeUInt(pE) then // if i<=j then
Begin
if pB<>pE then // if i<>j then
Begin
t:=pInteger(pB)^; // t:=a[i];
pInteger(pB)^:=pInteger(pE)^; // a[i]:=a[j];
pInteger(pE)^:=t; // a[j]:=t;
End;
Inc(pInteger(pB)); // Inc(i);
Dec(pInteger(pE)); // Dec(j);
End;
Until (NativeUInt(pB)>NativeUInt(pE)); // Until i>j;
if (NativeUInt(p_bg)<NativeUInt(pE)) then // if l<j then
_SortArrInteger(p_bg,pE); // Sort(a,l,j);
p_bg:=pB; // l:=i;
Until (NativeUInt(pB)>=NativeUInt(p_end)); // Until i>=r;
End;
procedure SortArrInteger(p:pointer;len:integer);
var pt:pointer;
begin
if len>1 then
begin
pt:=p;
inc(pInteger(pt),len-1);
_SortArrInteger(p,pt);
end;
end;
// пример работы
var id:integer;
s:AnsiString;
begin
for id:=0 to 10 do
begin
a[id]:=random(65536);
write(a[id]);
write(' | ');
end;
writeln;
SortArrInteger(@a[0],11);
for id:=0 to 10 do
begin
write(a[id]);
write(' | ');
end;
writeln;
// в данном случае сортировка будет выполняться по последней букве
s:='qweytyuiopasdfghjklz'; // qwey
SetLength(s,20);
writeln(s);
SortArrInteger(@s[1],length(s) div 4);
writeln(s);
s:='qwertyuiopasdfghjklz'; // qwer
SetLength(s,20);
writeln(s);
SortArrInteger(@s[1],length(s) div 4);
writeln(s);
Если у вас в массиве фиксированный тип данных, то, с помощью указателей, можно написать несколько процедур, для конкретного типа. Ну или одну универсальную, с передачей размера типа. Таким макаром у меня сделана быстрая сортировка которая может отсортировать хоть что: массив байтов, массив integer'ов, строку, участок памяти, да хоть байты переданные внутри типа int64, или же word внутри переданного integer, разницы нет.
Также можно написать универсальную процедуру, которая сможет отсортировать хоть массив из 3 байт (тип данных), хоть из 5 (вся обработка идет побайтово). И это работает не в теории, а на практике. Учите указатели и дерзайте.
Для удобства я декларировал процедуры следующим образом:
Ночью мысль в голове продолжала крутиться... Если мы можем ограничить сверху размер ячейки массива (разумным числом)? то можно и от ассемблера убежать, и с динамической памятью не связываться, а просто выделить в локальных переменных буфер достаточного размера и использовать его
procedure RevCns(Data: Pointer; Index, Size: Integer);
var
Tmp: array[1..100] of Byte; // выделяем в стеке буфер на 100 байт
Ptr: Pointer;
begin
Ptr := Pointer(Integer(Data) + Index * Size);
Move(Ptr^, Tmp, Size);
Move(Pointer(Integer(Ptr) + Size)^, Ptr^, Size);
Move(Tmp, Pointer(Integer(Ptr) + Size)^, Size);
end;
Массив в Delphi — это непрерывная область памяти, размер которой равен произведению количества элементов на размер одного элемента: первые N байт (где N — размер элемента) отведены под самый первый элемента, следующие — под второй и так далее. Соответственно, поменять местами два элемента — означает поменять местами содержимое двух подобластей памяти.
И вот ту начинается фигня. У массивов разного типа будет разные размер одного элемента. Так что ваша универсальная процедура не сможет узнать, массив каких элементов передан ей на вход (если можно как-то подключить и использовать RTTI — это не ко мне). Ну и еще более мелкая фигня — строгая типизация данных: для универсальная процедуры должен быть строго прописан тип параметров, то есть какой именно массив будет подаваться на вход.
Если допустить, что все массивы будут иметь размер элемента 4 байта (LongInt, LongWord, String, Pointer, классы), то выкрутиться можно. Если же нет, то придется третьим параметром передавать размер ячейки, то есть объявление процедуры будет таким:
Я отказался от передачи массива как var, заменив указателем на область данных, и сделал это вот почему: массивы бывают динамические и статические. И если переменная, являющаяся статическим массивом, содержит сами данные, то для динамического массива она содержит указатель на область данных. Ниже я покажу, как можно будет вызывать эту процедуру и для тех, и для других массивов. Ещё один момент: статические массивы могут начинаться с нуля, с единицы и вообще с любого целого числа. Этого мы тоже не сможем узнать. Поэтому Index в данном случае — это номер смещения элемента относительно начала массива. То есть для самого первого элемента массива индекс будет 0, для следующего 1 и так далее, независимо от того, какая именно размерность у этого массива. Для динамических массивов индексация всегда начинается с нуля, так что для них проблем не будет.
Вступление закончено, можно переходить к реализации. Набросал по-быстрому вариант на ассемблере:
procedure RevCns(Data: Pointer; Index, Size: Integer); register;
asm
push ebp
push esi
push edi
mov esi,eax
mov eax,edx
mul ecx
add esi,eax
mov eax,ecx
add eax,3
and eax,not 3
add eax,2*4
mov edx,esp
sub esp,eax
mov ebp,esp
push edx
mov [ebp],esi
mov [ebp+4],ecx
lea edi,[ebp+8]
rep movsb
push esi
mov ecx,[ebp+4]
mov edi,[ebp]
rep movsb
lea esi,[ebp+8]
mov ecx,[ebp+4]
pop edi
rep movsb
pop eax
mov esp,eax
pop edi
pop esi
pop ebp
end;
Возможно не самый грамотный, не самый эффективный и не самый красивый вариант, но вполне рабочий. Процедура, получив на вход ссылку на область данных массива, меняет местами элемент с номером Index и следующий за ним элемент. Никаких проверок не производится, данные должны быть корректны, то есть параметр Data реально должен указывать на область данных массива, который содержит, как минимум, Index+2 элемента (имеется и элемент Index, и следующий за ним элемент) размером Size байт.
Если сделать на чистом Паскале, то получится что-то такое:
Но здесь мне не нравится, что на каждый вызов нужно память аллокировать и освобождать. Если процедура будет вызываться иногда, то фиг с ней. Но если будет вызываться многократно при обработке какого-то массива, то затраты времени на манипуляции с динамической памятью могут оказаться большими, что отрицательно скажется на времени обработки всего массива. Ассемблерный же вариант выделяет место под временную переменную в стеке, что происходит мгновенно. Но там могут быть проблемы, если размер элемента массива слишком велик. Типа, если больше порядка 4К или больше на одну ячейку массива, то может привести к ошибкам.
Теперь про вызов. Безопасный вызов будет выглядеть так
var
A: TSomeArray;
begin
// ...
RevCns(@A[Low(A)], 3, SizeOf(A[Low(A)]));
На всякий случай пояснения.
Low(A) возвращает номер самого меньшего элемента массива. Работает и для статических, и для динамических массивов.
Тогда A[Low(A)] — это самый первый элемент массива, а @A[Low(A)] — указатель на самый первый элемент массива и, соответственно, на область данных массива.
SizeOf(A[Low(A)]) — размер в байтах самого первого элемента массива. А поскольку в паскале в массиве все элементы одного типа, то... в общем, понятно.
Может быть, и вариант с дженериками подойдет. Но это уже не ко мне.
Могу добавить еще одно, правда, не знаю, насколько это может оказаться полезным для вас. В стандарте языка C++, реализованном в интегрированной среде Borland C++ Builder 6.0 и выше, допускается использование и создание шаблонов классов и функций, в которых возможно использование типов данных как параметров. Вполне возможно, что в новейших версиях Delphi реализованы аналогичные структуры ( хотя я в этом не уверен и не знаю ). С применением подобных структур решение вашей проблемы, можно сказать, лежит на блюдечке с голубой каемочкой ... )))
Если версия среды поддерживает шаблоны, то в модуле System.Generics.Collections есть класс TArray.
По примеру реализованных методов можно написать свой класс или отнаследоваться с добавлением swap.
Определите массив указателей типа Pointer. Все объекты некоторого типа размещайте в динамической памяти с установлением на них соответствующих указателей-элементов массива. Перестановка местами двух указателей, как у вас это сделано с элементами вашего массива, будет эквивалентна изменению порядка следования объектов в массиве. Указатели типа Pointer можно устанавливать на объекты любых типов с соответствующим приведением указателя к нужному типу.
Как-то так ...
Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter. Функция может не работать в некоторых версиях броузеров.
