Заполнения массива случаными неповторяющимися значениями 2

Delphi , Синтаксис , Массивы

Автор: Иваненко Фёдор Григорьевич

Приведу стандартную процедуру, работает в шесть раз быстрее, не имеет ограничений, да и кода поменьше :)

procedure FillArray(var A: array of Integer);
var
  I, S, R: Integer;
begin
  for I := 0 to High(A) do
    A[I] := I;
  for i := High(A) downto 0 do
  begin
    R := Random(I);
    S := A[R];
    A[R] := A[I];
    A[I] := S;
  end;
end;

Преобразование процедуры для заполнения массива случайными уникальными значениями!

Вот разбивка кода:

1. Процедура FillArray принимает в качестве входного параметра переменный массив целых чисел.
2. Первый цикл (for I := 0 to High(A) do) инициализирует каждый элемент в массиве индексным значением (т.е., A[I] := I;).
3. Второй цикл (for i := High(A) downto 0 do) перемешивает элементы массива случайно.

Вот шаг за шагом объяснение процесса перемешивания:

• R := Random(I);: генерирует случайный индекс R между 0 и I.
• S := A[R];: присваивает значение по индексу R временной переменной S.
• A[R] := A[I];: обменивает значение по индексу R с значением по индексу I.
• A[I] := S;: присваивает оригинальное значение S обратно индексу I.

Процесс повторяется, пока все элементы не будут перемешены.

Вам также было сказано, что эта процедура работает быстрее других решений. Я хотел бы увидеть бенчмарк для проверки этого утверждения. В целом, алгоритмы с меньшим количеством циклов и более простой логикой tend to be more efficient. Однако, разница в производительности может не быть значительной, если вы работаете с массивами среднего размера или под очень специфическими обстоятельствами.

Один из потенциальных проблем этого подхода - он имеет время сложности O(n^2), где n - размер массива. Это потому, что внешний цикл итерирует каждый элемент в массиве, а внутренний цикл также итерирует каждый элемент. Для больших массивов это может привести к проблемам с производительностью.

Альтернативное решение было бы использовать более эффективный алгоритм для генерации случайных перестановок,such as the Fisher-Yates shuffle or the Knuth Shuffle. Эти алгоритмы имеют время сложности O(n), что делает их более подходящими для больших массивов.

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

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Массивы ::