-
Коллеги!
1. Знаю, что тут бывает много людей, знающих алгоритмы. Буду рад, если поможете.
2. К моему стыду я не смог сам придумать алгоритм. А найти в интернете не вышло, ибо не знаю по каким ключевым словам искать.
3. Итак суть задачи.
Есть массив A:
а. Занимает много памяти.
б. Элемент массива большой (т.е. не ссылка на что-то).
в. Есть операция перестановки Swap(I, J).
Есть массив Б:
а. Содержит Integer.
б. Кол-во элементов равно кол-ву элементов А.
в. Каждый элемент массива содержит индекс из А.
Задача:
С помощью операции Swap переставить в А элементы так, чтобы порядок следования элементов был равен тому, который указан в массиве Б.
Ограничения:
а. Массив А - большой. Поэтому нельзя создавать копию А и перетаскивать в нее соотв. значения из А.
б. Время N.
Пример:
Исходно: А = [a, b, c], Б = [1, 2, 0]
После применения алгоритма: A = [b, c, a] - на первом месте становится элемент А с индексом Б[0], на втором Б[1], на третьем Б[2].
У меня есть ощущение, что это какой-то стандартный алгоритм. Просто я его не знаю.
Благодарю, если подскажите.
-
исходный управляющий механизм неверен.
ибо после очередного свапа как ты отличишь b стоящее в нулевой позиции массива а.
это оно там вначале так стояло, или его уже задвинули свапом?
-
к тому же управляющая инфа в Б актуальна только на начало сортировки.
и ее актуальность протухнет после первых же свапов.
-
хотя если скользить слева направо по длине Б и делать свап если справа меньше чем слева.
если больше то свап не делать
-
> iop © (13.10.16 12:56) [1]
> исходный управляющий механизм неверен.
Никто не мешает сделать еще один массив индексов и помнить, кто куда был переставлен. Но я пока в этих индексах запутался.
Повторюсь. У меня есть ощущение, что задача решаема и не нова. Должен быть алгоритм известный.
-
и помнить, кто куда был переставлен.
перестановок много. запаришься запоминать кто куда был переставлен и откуда и после скольки перестановок он там оказался.
есть два подхода.
академический.
это произвольная взятая наугад структура языка и долгий поиск "научного" алгоритма перестановок
разумный.
структура выбирается так, чтобы перестановки выполнялись за один проход и без головной боли.
в твоем случае взятая наугад структура - это массив.
элементы которого ничего не помнят про то где они были секунду назад
-
Двунаправленный список вместо первого элемента. Незачто Дим
-
> Тимохов Дима © (13.10.16 12:29)
Массив Б задает перестановку элементов массива А,
поэтому удобнее всего использовать то,
что любая перестановка есть совокупность независимых циклов.
Т.е. переставлять удобнее операцией Swap(), у которой произвольное число аргументов.
Ранее использованные при этой позиции можно помечать -1 или собственным номером.
Вот и весь алгоритм.
Если N-местный Swap() не разрешается использовать,
то его можно эмулировать N-1 двуместными.
-
type
TElem= int64;
TElems= array of TElem;
TPlaces= array of integer;
procedure Swap(var e1, e2: TElem);
begin;
e1:=e1 xor e2;
e2:=e1 xor e2;
e1:=e1 xor e2;
end;
procedure Place(a: TElems; b: TPlaces);
var
i, j, k: integer;
begin;
for i:=0 to Length(b)-1 do begin;
j:=i;
while true do begin;
k:=b[j]; b[j]:=j;
if k=i then break;
Swap(a[j],a[k]);
j:=k;
end;
end;
end;
procedure TMainForm.Button1Click(Sender: TObject);
var
a: TElems;
b: TPlaces;
i: integer;
begin;
SetLength(a,6); a[0]:=0; a[1]:=1; a[2]:=2; a[3]:=3; a[4]:=4; a[5]:=5;
SetLength(b,6); b[0]:=1; b[1]:=2; b[2]:=0; b[3]:=5; b[4]:=4; b[5]:=3;
Place(a, b);
for i:=0 to Length(a)-1 do Memo1.Lines.Add(IntToStr(a[i]));
end;
-
> Sha © (13.10.16 15:19) [8]
Честно скажу, очень детально не вникал, но сложность все же не N. Ибо Swap идет в цикле в цикле. Т.е. N в какой-то степени. Думаю, что N^2 в общем случае. Виноват, если не точно написал в исходной постановке, что сложность (кол-во вызовов) именно Swap д.б. N.
> Rouse_ © (13.10.16 13:59) [6]
> Двунаправленный список вместо первого элемента. Незачто Дим
Долго думал. Не сообразил, что ты имеешь в виду. ----- НО! Вдохновленный тем, что задача скорее решаема, чем нет, написал свой вариант! И не спрашивайте, как он работает!)) Делал методом индукции: от частного к общему. Нашел закономерности, запрограммировал, и проверил статистически. Самое главное тут массив P. Он содержит позиции элементов, которые в ходе перестановок тоже меняются. Сложность N!
procedure SwapInt64(var E1, E2: Int64);
var
Temp: Int64;
begin
Temp := E1;
E1 := E2;
E2 := Temp;
end;
procedure SwapInteger(var E1, E2: Integer);
var
Temp: Integer;
begin
Temp := E1;
E1 := E2;
E2 := Temp;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
A: array of Int64;
B, P: array of Integer;
I, J, K: Integer;
begin
SetLength(A, 8); A[0]:=5; A[1]:=2; A[2]:=3; A[3]:=7; A[4]:=1; A[5]:=6; A[6]:=4; A[7]:=0;
SetLength(B, 8); B[0]:=7; B[1]:=4; B[2]:=1; B[3]:=2; B[4]:=6; B[5]:=0; B[6]:=5; B[7]:=3;
SetLength(P, Length(B));
for I := 0 to Length(B)-1 do
P[B[I]] := I;
for I := 0 to Length(B)-1-1 do
begin
J := B[I];
K := P[I];
if I <> J then
begin
SwapInt64(A[I], A[J]);
SwapInteger(B[I], B[K]);
SwapInteger(P[I], P[J]);
end;
end;
for I := 0 to Length(A)-1 do
Memo1.Lines.Add(IntToStr(A[I]));
end;
-
> Тимохов Дима © (13.10.16 17:47) [9]
> Честно скажу, очень детально не вникал, но сложность все же не N.
> Ибо Swap идет в цикле в цикле. Т.е. N в какой-то степени.
> Думаю, что N^2 в общем случае.
> Виноват, если не точно написал в исходной постановке,
> что сложность (кол-во вызовов) именно Swap д.б. N.
а ты попробуй вникнуть
-
все верно.
если задумал круглое носить, то надо носить. а квадратное катать.
похожий пример из античности:
грид с порядком колонок установленным в дизайне и пользовательская настройка очередности колонок.
сортируем пользовательский список колонок по индексам и слева направо присваиваем индексы живым колонкам грида.
почему так просто, хотя по сути это то же самое?
потому что переставляемую колонку берем не по индексу, а по имени поля.
и потому что свап не нужен.
вывод:
если есть несколько однотипных элементов и рука уже потянулась объявить массив - останови ее и подумай.
массив ли здесь удобен.
-
> Sha © (13.10.16 17:53) [10]
> > Тимохов Дима © (13.10.16 17:47) [9]
> > Честно скажу, очень детально не вникал, wap д.б. N.
> а ты попробуй вникнуть
Александр, виноват - был не прав. Сложность тоже N.
Скажи, пожалуйста, это твой алгоритм или из литературы? Кнута, например.
Я почему спрашиваю - ощущение, что эти алгоритмы уже все разработаны в рамках теории. Не хочу в следующий раз сам придумывать, что к чему. Поучиться хочу. Тема то хоть какая, где эти алгоритмы изучают?
-
> Тимохов Дима © (13.10.16 17:47) [9]>> Rouse_ © (13.10.16 13:59) [6]>> Двунаправленный список вместо первого элемента. > Долго думал. Не сообразил, что ты имеешь в виду. type
PDataRecord = ^TDataRecord;
TDataRecord = packed record
Data: тип_данных (тот же, что у элементов массива A);
Prev: PDataRecord;
Next: PDataRecord;
FirstDataRecord: PDataRecord; И вместо массива A строим список записей TDataRecord. После чего можем перемещать элементы этого списка как угодно, просто меняя значения полей Prev и Next в элементах. Причем скорость такой сортировки будет очень высокой, так как сами элементы никуда не перемещаются. По сравнению с массивом, объем данных увеличивается не сильно: количество_элементов * 2 * SizeOf(Pointer)
-
-
> Тимохов Дима © (13.10.16 18:29) [12]Не помню, где бы встречался конкретно этот алгоритм. Но в теории групп есть много всего про перестановки, и много похожего обычно всплывает на практических занятиях) Опять же есть Липский и http://guildalfa.ru/alsha/node/26
-
Коллеги, всем спасибо!
Есть, что поизучать.
Да и задачу решил.
> Sha © (13.10.16 20:10) [15]
Спасибо!
Вот же у программистов мука...
Сижу и думаю, какой алгоритм брать - свой или твой.
Свой - он свой. Твой - проще.
Вот вопрос))
-
> Тимохов Дима © (13.10.16 22:31) [16] > Сижу и думаю, какой алгоритм брать - свой или твой. > Свой - он свой. Твой - проще. Вот тут похожий случай: http://www.sql.ru/forum/1234205/kto-smozhet-zastavit-3-potoka-rabotat-so-skorostu-odnogoсвой алгоритм генерации сочетаний оказался примерно в 10 раз менее стандартного) Чтоб совсем помочь тебе определиться - вот пара быстрых реализаций, с двуместным и многоместным свопами: type
TElem= integer;
PElems= PIntegerArray;
PPlaces= PIntegerArray;
procedure Place1(a: PElems; b: PPlaces; count: integer);
var
temp: TElem;
i, j, k: integer;
begin;
for i:=count-1 downto 1 do begin;
j:=i;
while true do begin;
k:=b[j]; b[j]:=j;
if k=i then break;
temp:=a[j]; a[j]:=a[k]; a[k]:=temp; //Swap(a[j],a[k]);
j:=k;
end;
end;
end;
procedure Place2(a: PElems; b: PPlaces; count: integer);
var
temp: TElem;
i, j, k: integer;
begin;
for i:=count-1 downto 1 do begin;
k:=b[i];
if k<>i then begin;
j:=i; b[j]:=j; temp:=a[j];
repeat;
a[j]:=a[k];
j:=k; k:=b[j]; b[j]:=j;
until k=i;
a[j]:=temp;
end;
end;
end;
function FormatArray(a: PElems; count: integer): string;
var
i: integer;
begin;
Result:='';
for i:=0 to count-1 do Result:=Result+' '+IntToStr(a[i]);
end;
procedure TMainForm.Button1Click(Sender: TObject);
var
a, b: array of integer;
i, j, k, count: integer;
t: array[0..2] of cardinal;
begin;
// SetLength(a,6); a[0]:=0; a[1]:=1; a[2]:=2; a[3]:=3; a[4]:=4; a[5]:=5;
// SetLength(b,6); b[0]:=1; b[1]:=2; b[2]:=0; b[3]:=5; b[4]:=4; b[5]:=3;
count:=10;
SetLength(a,count);
SetLength(b,count);
for i:=0 to count-1 do a[i]:=i;
for i:=0 to count-1 do b[i]:=i;
for i:=count-1 downto 1 do begin;
j:=Random(i+1);
k:=a[j]; a[j]:=a[i]; a[i]:=k;
end;
t[0]:=GetTickCount;
for i:=1 to 1000000 do begin; Place1(@a[0], @b[0], count); Place1(@b[0], @a[0], count); end;
t[1]:=GetTickCount;
for i:=1 to 1000000 do begin; Place2(@a[0], @b[0], count); Place2(@b[0], @a[0], count); end;
t[2]:=GetTickCount;
Memo1.Lines.Add(FormatArray(@a[0], count));
Memo1.Lines.Add(FormatArray(@b[0], count));
Memo1.Lines.Add(IntToStr(t[1]-t[0]));
Memo1.Lines.Add(IntToStr(t[2]-t[1]));
end;
-
В предыдущем посте опечатка: в 10 раз медленнее стандартного
-
> Sha © (13.10.16 23:37) [17]
> Чтоб совсем помочь тебе определиться
Спасибо. Буду изучать!
ЗЫ Просмотрел твой алгоритм. Кажется (помню, что креститься надо когда кажется:) ), что понимаю, как он работает. А, может, и не понимаю. Но, чьерт попьери, вот как ты его придумал?! Вот свой я придумал, как говорил, индукцией - написал на бумажке, заметил закономерности, запрограммировал - экспериментально (миллионы случайных перестановок случайных данных с верификацией) доказал правильность. А вот в твоем случае - как проходило построение алгоритма? Понимаю, что вопрос, скорее, философский. Но все же, поделись, пожалуйста))
|
Есть новые 
Нет новых [134431 +15][b:0][p:0.002]