Ненормальное программирование (cерия 2). Memento...

Работа с памятью всегда остается одной из самых чудесных вещей, какие имеются в программировании вообще. И сегодня – небольшая заметка об одной особенности, которая имеются в этой сфере у Delphi.

В Delphi отсутствует как таковая проверка выхода за границы при обращении к элементам массива, поэтому можно обратиться к тем «элементам», которые лежат в памяти перед или после самого массива. Обычно точно не получится сказать, что же именно будет там находиться, однако, если мы объявляем, к примеру, одновременно два массива, то они с достаточно большой долей вероятности будут располагаться в памяти последовательно один за другим.

Что же нам может дать подобное поведение компилятора, кроме проблем?

Разберем простейшую задачу:
Имеются 2 массива по… Ммм… Предположим по 8 элементов (заполним их с помощью генератора псевдослучайных чисел). И элементы этих двух массивов нужно переставить таким образом, чтобы в первом были минимальные элементы из двух исходных массивов, а во втором – максимальные.


Задача элементарная и сводится обычно к двум вариантам: либо это последовательный поиск минимальных/максимальных элементов и постепенная перестановка, либо объединение двух исходных массивов в третий и его сортировка с помощью стандартных средств.

Но… Delphi в силу той особенности, о которой мы сегодня говорим, позволяет провернуть очень изящный фортель, а именно – отсортировать сразу оба массива как один. К тому же для этого даже не нужно делать ничего особенного: просто достаточно сортировать первый массив «сдвинув» его правую границу на длину второго массива.

{$APPTYPE CONSOLE}

uses
  SysUtils;

{ Стандартный алгоритм "быстрой" сортировки (можно использовать любой другой) }
procedure qSort(var a: array of Integer; low, high: Integer);
var
  i, j, x: Integer;
  t: Integer;
begin
      i := low;
      j := high;
      x := a[(low + high) div 2];
      repeat
          while a[i] < x do inc(i);
          while a[j] > x do dec(j);
          if i <= j then
            begin
              t := a[i];
              a[i] := a[j];
              a[j] := t;
              inc(i);
              dec(j);
            end;
      until (i > j);

      if low < j then qSort(a, low, j);
      if i < high then qSort(a, i, high);
end;

{ Это сделано для красивого вывода массивов }
procedure Print(a: array of Integer; name: String);
var
  i: Integer;
begin
  Write(name, ': [ ');
  for i := 0 to length(a) - 1 do
    if i < length(a) - 1 then
      Write(a[i]:3, ', ')
    else
      WriteLn(a[i]:3, ']');
end;

var
  i: integer;
  a, b: array [0..7] of Integer;
begin
  { Заполняем массивы }
  Randomize;
  for i := 0 to length(a) - 1 do
    begin
      a[i] := Random(256);
      b[i] := Random(256);
    end;

  { Выводим, чтобы посмотреть, что было }
  Print(a, 'A');
  Print(b, 'B');
  WriteLn;

  { Сортируем все 16 элементов }
  qSort(a, 0, 15);

  { Выводим, чтобы посмотреть, что стало }
  Print(a, 'A');
  Print(b, 'B');
  WriteLn;

  ReadLn;
end.


Как видите – все просто! Разве что не все позволяют так делать (к примеру, Free Pascal не даст так просто гулять по чужой памяти).

PS.: Напоследок, попробуйте решить задачу тем же способом, если будет 2 массива по 10 элементов типа Byte.

Похожие записи для топика «Ненормальное программирование (cерия 2). Memento...»

Комментарии (1) свернуть  |  развернуть

  • avatar
  • belan
  • 13 апреля 2012, 20:57
+1
— спасибо за интересную публикацию, очень полезно!

Прокомментировать