Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 2019.01.27;
Скачать: [xml.tar.bz2];

Вниз

Поиск алгоритма   Найти похожие ветки 

 
Тимохов Дима ©   (2016-10-13 12:29) [0]

Коллеги!

1. Знаю, что тут бывает много людей, знающих алгоритмы. Буду рад, если поможете.

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

3. Итак суть задачи.

Есть массив A:
  а. Занимает много памяти.
  б. Элемент массива большой (т.е. не ссылка на что-то).
  в. Есть операция перестановки Swap(I, J).

Есть массив Б:
  а. Содержит Integer.
  б. Кол-во элементов равно кол-ву элементов А.
  в. Каждый элемент массива содержит индекс из А.

Задача:
  С помощью операции Swap переставить в А элементы так, чтобы порядок следования элементов был равен тому, который указан в массиве Б.

Ограничения:
  а. Массив А - большой. Поэтому нельзя создавать копию А и перетаскивать в нее соотв. значения из А.
  б. Время N.

Пример:
Исходно: А = [a, b, c], Б = [1, 2, 0]
После применения алгоритма: A = [b, c, a]  - на первом месте становится элемент А с индексом Б[0], на втором Б[1], на третьем Б[2].

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

Благодарю, если подскажите.


 
iop ©   (2016-10-13 12:56) [1]

исходный управляющий механизм неверен.

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

это оно там вначале так стояло, или его уже задвинули свапом?


 
iop ©   (2016-10-13 13:00) [2]

к тому же управляющая инфа в Б актуальна только на начало сортировки.
и ее актуальность протухнет после первых же свапов.


 
iop ©   (2016-10-13 13:08) [3]

хотя если скользить слева направо по длине Б и делать свап если справа меньше чем слева.
если больше то свап не делать


 
Тимохов Дима ©   (2016-10-13 13:11) [4]


> iop ©   (13.10.16 12:56) [1]
> исходный управляющий механизм неверен.


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

Повторюсь. У меня есть ощущение, что задача решаема и не нова. Должен быть алгоритм известный.


 
iop ©   (2016-10-13 13:27) [5]

и помнить, кто куда был переставлен.

перестановок много. запаришься запоминать кто куда был переставлен и откуда и после скольки перестановок он там оказался.

есть два подхода.

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

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

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


 
Rouse_ ©   (2016-10-13 13:59) [6]

Двунаправленный список вместо первого элемента. Незачто Дим


 
Sha ©   (2016-10-13 14:07) [7]

> Тимохов Дима ©   (13.10.16 12:29)

Массив Б задает перестановку элементов массива А,
поэтому удобнее всего использовать то,
что любая перестановка есть совокупность независимых циклов.

Т.е. переставлять удобнее операцией Swap(), у которой произвольное число аргументов.

Ранее использованные при этой позиции можно помечать -1 или собственным номером.

Вот и весь алгоритм.

Если N-местный Swap() не разрешается использовать,
то его можно эмулировать N-1 двуместными.


 
Sha ©   (2016-10-13 15:19) [8]


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;


 
Тимохов Дима ©   (2016-10-13 17:47) [9]


> 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{no last element} 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;



 
Sha ©   (2016-10-13 17:53) [10]

> Тимохов Дима ©   (13.10.16 17:47) [9]
> Честно скажу, очень детально не вникал, но сложность все же не N.
> Ибо Swap идет в цикле в цикле. Т.е. N в какой-то степени.
> Думаю, что N^2 в общем случае.
> Виноват, если не точно написал в исходной постановке,
> что сложность (кол-во вызовов) именно Swap д.б. N.

а ты попробуй вникнуть


 
iop ©   (2016-10-13 17:57) [11]

все верно.
если задумал круглое носить, то надо носить. а квадратное катать.

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

сортируем пользовательский список колонок по индексам и слева направо присваиваем индексы живым колонкам грида.

почему так просто, хотя по сути это то же самое?
потому что переставляемую колонку берем не по индексу, а по имени поля.
и потому что свап не нужен.

вывод:
если есть несколько однотипных элементов и рука уже потянулась объявить массив - останови ее и подумай.
массив ли здесь удобен.


 
Тимохов Дима ©   (2016-10-13 18:29) [12]


> Sha ©   (13.10.16 17:53) [10]
> > Тимохов Дима ©   (13.10.16 17:47) [9]
> > Честно скажу, очень детально не вникал, wap д.б. N.
> а ты попробуй вникнуть


Александр, виноват - был не прав. Сложность тоже N.

Скажи, пожалуйста, это твой алгоритм или из литературы? Кнута, например.
Я почему спрашиваю - ощущение, что эти алгоритмы уже все разработаны в рамках теории. Не хочу в следующий раз сам придумывать, что к чему. Поучиться хочу. Тема то хоть какая, где эти алгоритмы изучают?


 
Юрий Зотов ©   (2016-10-13 18:41) [13]

> Тимохов Дима ©   (13.10.16 17:47) [9]

>> Rouse_ ©   (13.10.16 13:59) [6]
>> Двунаправленный список вместо первого элемента.

> Долго думал. Не сообразил, что ты имеешь в виду.

type
 PDataRecord = ^TDataRecord;
 TDataRecord = packed record
   Data: тип_данных (тот же, что у элементов массива A);
   Prev: PDataRecord; // Адрес предыдущей записи, у первой - nil
   Next: PDataRecord; // Адрес следующей записи, у последней - nil

FirstDataRecord: PDataRecord; // Адрес первой записи в списке


И вместо массива A строим список записей TDataRecord. После чего можем перемещать элементы этого списка как угодно, просто меняя значения полей Prev и Next в элементах. Причем скорость такой сортировки будет очень высокой, так как сами элементы никуда не перемещаются.

По сравнению с массивом, объем данных увеличивается не сильно:
количество_элементов * 2 * SizeOf(Pointer)


 
Игорь Шевченко ©   (2016-10-13 18:59) [14]


> Тема то хоть какая, где эти алгоритмы изучают?


Крайне рекомендую почитать
https://www.ozon.ru/context/detail/id/20883551/

В то время процент правильных книжек был больше, хотя книжек меньше :)


 
Sha ©   (2016-10-13 20:10) [15]

> Тимохов Дима ©   (13.10.16 18:29) [12]

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

Опять же есть Липский и http://guildalfa.ru/alsha/node/26


 
Тимохов Дима ©   (2016-10-13 22:31) [16]

Коллеги, всем спасибо!

Есть, что поизучать.
Да и задачу решил.


> Sha ©   (13.10.16 20:10) [15]

Спасибо!
Вот же у программистов мука...
Сижу и думаю, какой алгоритм брать - свой или твой.
Свой - он свой. Твой - проще.
Вот вопрос))


 
Sha ©   (2016-10-13 23:37) [17]

> Тимохов Дима ©   (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;


 
Sha ©   (2016-10-13 23:41) [18]

В предыдущем посте опечатка: в 10 раз медленнее стандартного


 
Тимохов Дима ©   (2016-10-14 00:35) [19]


> Sha ©   (13.10.16 23:37) [17]


> Чтоб совсем помочь тебе определиться

Спасибо. Буду изучать!

ЗЫ Просмотрел твой алгоритм. Кажется (помню, что креститься надо когда кажется:) ), что понимаю, как он работает. А, может, и не понимаю. Но, чьерт попьери, вот как ты его придумал?! Вот свой я придумал, как говорил, индукцией - написал на бумажке, заметил закономерности, запрограммировал - экспериментально (миллионы случайных перестановок случайных данных с верификацией) доказал правильность. А вот в твоем случае - как проходило построение алгоритма? Понимаю, что вопрос, скорее, философский. Но все же, поделись, пожалуйста))


 
Sha ©   (2016-10-14 07:30) [20]

> Тимохов Дима ©   (14.10.16 00:35) [19]

Есть теория, первые изучаемые там теоремы о том,
что любая перестановка разложима на независимые циклы,
т.е. представима в виде суперпозиции независимых циклических перестановок,
а любой цикл длины N разложим на N-1 транспозицию.
И то, и другое легко программируется.

P.S. Хорошая теория очень практична.


 
Тимохов Дима ©   (2016-10-16 22:19) [21]


> Sha ©   (14.10.16 07:30) [20]

Спасибо. Буду думать и читать.



Страницы: 1 вся ветка

Форум: "Прочее";
Текущий архив: 2019.01.27;
Скачать: [xml.tar.bz2];

Наверх





Память: 0.66 MB
Время: 0.035 c
15-1476460332
Belkin
2016-10-14 18:52
2019.01.27
Warning: Duplicate resource


15-1476350942
Тимохов Дима
2016-10-13 12:29
2019.01.27
Поиск алгоритма





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский