Обсуждение темы "Как правильно перемешивать массивы", в FAQ Опции

[IUnknown]

М

Обсуждение темы в FAQ, Как правильно перемешивать массивы Тема в FAQ разделена. Предлагаю обсуждать здесь, после обсуждения дополнить или исправить тему в FAQ.

Не надо уводить от одной задачи, и приводить к другой...

Вот так, как ты написал в самом верхнем примере, не делается перемешивание. Так генерируются данные уже в перемешанном виде, правда? А то как ты показывешь ниже - это как раз перемешивание (т.е., ранее сгенерировал в прямой последовательности, а потом - перетусовал)... Есть 2 большие разницы между этими вещами. Не надо их сливать в одно, и уж тем более - нельзя сравнивать их быстродействие. Потому что я могу с легкостью сделать так:

for i := 1 to n do begin
  repeat
    candidat := random(n) + 1; // от 1 до n
    can := container.exists(candidat);
  until can;
  container.push_back(candidat);
end;

, и все будет по-прежнему работать; независимо от того, насколько сложный объект содержится в контейнере, он будет инициализироваться целочисленным значением ОДИН раз, и не будет никаких копирований с места на место, которые могут запросто убить весь тот прирост производительности (если он даже и есть): тебе для того, чтобы поменять местами 2 элемента массива надо инициализировать временный элемент, потом произвести 3 операции копирования, потом временный элемент деинициализировать. Это может быть дольше, чем мой цикл

Кстати, (Показать/Скрыть)

не надо опять заводить песню о том, что цикл может стать бесконечным. Не может. Ты либо уже уймись, либо приводи конкретные примеры. Стал у тебя ХОТЬ РАЗ он бесконечным? Нет. С чего тогда весь сыр-бор? Я точно так же могу сказать: при выполнении твоего кода может внезапно отказать хард. Поэтому его использовать нежелательно. Не надо использовать грязных приемов ведения дискуссии, я тоже очень хорошо умею это делать, поэтому вычисляю их сразу...

Особенно актуально все вышесказанное становится в свете того, что ты сам заговорил о "сапёре" - ну вот решил я написать "сапёра" с использованием ООП (и не надо мне говорить что это неправильно - как хочу, так и пишу), а твой способ, как оказывается, просто не подходит для этого (если работать сразу с массивом объектов).

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

Вот так (Показать/Скрыть)

procedure swap(var index : array of integer;
               i, j : integer);
var T : Integer;
begin
   T := Index[i - 1];
   Index[i - 1] := Index[j - 1];
   Index[j - 1] := T;
end;

type
   MyRec =
   object
      ix : Integer;
      // other fields and/or methods
   end;

const
   n = 20;
var
   i, j : integer;
   Arr : array[1 .. n] of MyRec;

   Index : array[1 .. n] of Integer;

begin
   for i := 1 to n do Index[i] := i;

   for i := 20 downto 2 do
   begin
      j := random(i)+1;
      swap(index, i, j);
   end;

   for i := 1 to n do
      arr[ index[i] ].ix := i; // или вызвать тут конструктор, если он есть

   for i := 1 to n do write(arr[i].ix:3);
   writeln;

end.

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