Today I learned that... (Slice здорового человека)

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

Today I learned that... (Slice здорового человека)

Сообщение runewalsh » 16.04.2018 11:34:26

...есть синтаксис для слайсов, начинающихся с произвольного элемента — A[first .. last] (Open array parameters, «As of FPC 2.2...»):
Код: Выделить всё
type
   TIntegerDynArray = array of integer;

   procedure Print(const a: array of integer);
   var
      v: integer;
   begin
      for v in a do write(v, ' ');
   end;

var
   a: TIntegerDynArray;

begin
   a := TIntegerDynArray.Create(0, 11, 22, 33, 44, 55);
   Print(a[2..4]); // 22, 33, 44
end.

Это означает, что «универсальные» функции, типа сортировки поддиапазона в QSort, можно реализовывать полностью на open array, вместо first: PItem; count: SizeInt:
Код: Выделить всё
type
   Item = integer;

   procedure QSort(var a: array of Item);
   var
      i, j: SizeInt;
      avg, t: Item;
   begin
      if length(a) < 2 then exit;
      i := 0;
      j := High(a);
      avg := a[(i + j) div 2];
      repeat
         while a[i] < avg do inc(i);
         while a[j] > avg 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;
      QSort(a[0 .. j]);
      QSort(a[i .. High(a)]);
   end;

А если вдруг настанут тяжёлые времена и на руках окажутся только указатель и количество — переинтерпретировать их как массив:
Код: Выделить всё
type
   ItemArray = array[0 .. 0] of Item; PItemArray = ^ItemArray;

var
   i, count: SizeInt;
   x: ^Item;

begin
   count := 100;
   x := GetMem(count * sizeof(Item));
   try
      for i := 0 to count-1 do x[i] := random(100);
      QSort(PItemArray(x)^[0 .. count-1]);
      for i := 0 to count-2 do Assert(x[i] <= x[i + 1], 'sort failed');
   finally
      FreeMem(x);
   end;
end.
Последний раз редактировалось runewalsh 16.04.2018 19:46:01, всего редактировалось 2 раз(а).
Аватара пользователя
runewalsh
постоялец
 
Сообщения: 403
Зарегистрирован: 27.04.2010 00:15:25

Re: Slice здорового человека. Today I learned that...

Сообщение wavebvg » 16.04.2018 12:23:38

runewalsh писал(а):если вдруг настанут тяжёлые времена

А они действительно настанут, потому что QSort работать не будет с безразмерным буфером
wavebvg
постоялец
 
Сообщения: 286
Зарегистрирован: 28.02.2008 04:57:35

Re: Today I learned that... (Slice здорового человека)

Сообщение runewalsh » 16.04.2018 13:51:07

Ты не понял.
Параметры «array of» невидимо передаются как first: PItem + count. Они не безразмерные.
Но часто всё равно делают функции с явными first и count, для универсальности (пример — реализация QSort в Classes.TList).
Речь о том, что благодаря синтаксису слайсов это не очень-то и нужно.
QSortOpenArray(a[7..10]) эквивалентно QSortMemoryBlock(@a[7], 4), но выглядит красивее.
Эта возможность заслуживает более широкой известности, потому что я никогда не видел, чтобы её использовали (и вообще только что узнал), зато передачу диапазона ячеек по @ или StartIndex вижу постоянно.
Аватара пользователя
runewalsh
постоялец
 
Сообщения: 403
Зарегистрирован: 27.04.2010 00:15:25

Re: Today I learned that... (Slice здорового человека)

Сообщение wavebvg » 16.04.2018 17:36:33

runewalsh писал(а):Ты не понял.
Параметры «array of» невидимо передаются как first: PItem + count. Они не безразмерные.
Но часто всё равно делают функции с явными first и count, для универсальности (пример — реализация QSort в Classes.TList).
Речь о том, что благодаря синтаксису слайсов это не очень-то и нужно.
QSortOpenArray(a[7..10]) эквивалентно QSortMemoryBlock(@a[7], 4), но выглядит красивее.
Эта возможность заслуживает более широкой известности, потому что я никогда не видел, чтобы её использовали (и вообще только что узнал), зато передачу диапазона ячеек по @ или StartIndex вижу постоянно.

Да, вычитал внимательнее, без ссылки на документацию и не подумал об этой возможности (и не знал про неё в FPC). Вообще-то, очень спорно все происходит и проверять не охота, но... Если работает -- выглядит красиво, но использовать как-то страшно... Да и на каждый рекурсивный вызов сортировки процессору приходится делать больше, а для сортировки красивостью можно и пожертвовать.
wavebvg
постоялец
 
Сообщения: 286
Зарегистрирован: 28.02.2008 04:57:35

Re: Today I learned that... (Slice здорового человека)

Сообщение runewalsh » 16.04.2018 18:52:30

Добавил ссылку на документацию в ОП-пост.
В том-то и дело, что разницы нет. Open arrays и слайсы для них (псевдофункция Slice, а теперь и вот это) — синтаксическая обёртка для манипуляций с парой «указатель + количество». Проверил сейчас варианты вот такой функции (всё под -O4). Можно видеть, что код с array of и first + count, действительно, почти аналогичен, что и требовалось доказать; для варианта со слайсом почему-то не соптимизировалась хвостовая рекурсия, но это ерунда (разница в 1 операцию).
signed.png


А теперь о грустном.
unsigned.png

Беззнаковый вариант чуть ли не вдвое короче. Со знаковыми числами компилятору сложнее работать — так, деления на степени двойки хуже оптимизируются сдвигами, что мы и наблюдаем. Усугубляет ситуацию то, что в Паскале типы всевозможных length() — знаковые (SizeInt), чтобы в циклах от 0 до Count - 1 не возникало антипереполнений при Count = 0. В C-языках такой проблемы нет в принципе, потому что там for — это while, размеры контейнеров — беззнаковый size_t и никаких «-1» в for (size_t i = 0; i < Count; i++) не вылезает.

Такое, действительно, неустранимо при использовании array of. Но это немного другое и мало кто над этим задумывается, в их число не входят даже авторы TList.Sort, спокойно использующие longint и, соответственно, не имеющие оправданий не использовать слайсы ;).

И вообще скорость ни при чём и на Sort свет клином не сошёлся, я часто передаю поддиапазоны в array of и слайсы удобнее и безопаснее, чем откатываться на указатели, вот.

Добавлено спустя 17 минут 30 секунд:
НУ А ХОТЯ:
unsigned+slice.png

Короче, слайсы могут слегка помешать оптимизации (как ни странно; в C обычно мешают именно non-restricted указатели), но в куда меньшей мере, чем некоторые вещи, которые никто не стесняется использовать.
У вас нет необходимых прав для просмотра вложений в этом сообщении.
Аватара пользователя
runewalsh
постоялец
 
Сообщения: 403
Зарегистрирован: 27.04.2010 00:15:25


Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: Yandex [Bot] и гости: 3

Рейтинг@Mail.ru