Функции последовательностей из PABCSystem, реализованные повторным проходом по последовательности


#1

Некоторые экстеншн-методы последовательностей из PABCSystem вызывают проход по входной последовательности 2 раза.Так не должно быть, ни 1 из стандартных функций последовательностей так не делает. Если не смотреть в исходники - не возможно узнать почему вдруг появилось неожиданное поведение. Более подробно я описал всё в #1451.

Я взялся переписать такие функции без костылей. Сюда буду складывать перед тем как сделать пулл-реквест.

Найдены уже SplitAt, Partition и UnZipTuple. Кто найдёт ещё - напишите.


#2

SplitAt:

type
  SplitAtHelper<T>=class
    
    source: sequence of T;
    ind: integer;
    
    fst_done: boolean;
    enm: IEnumerator<T>;
    fst_temp: List<T>;
    
    
    
    function f_fst: sequence of T;
    begin
      if fst_temp = nil then
      begin
        
        enm := source.GetEnumerator;
        var c := ind;
        while (c <> 0) and enm.MoveNext do
        begin
          yield enm.Current;
          c -= 1;
        end;
        fst_done := true;
        
      end else
      begin
        
        yield sequence fst_temp;
        fst_temp := nil;
        
      end;
    end;
    
    function f_snd: sequence of T;
    begin
      if not fst_done then
      begin
        fst_temp := nil;
        fst_temp := f_fst.ToList;
      end;
      
      while enm.MoveNext do
        yield enm.Current;
      
      fst_done := false;
    end;
    
    constructor(source: sequence of T; ind: integer);
    begin
      self.source := source;
      self.ind := ind;
    end;
    
  end;

/// Разбивает последовательности на две в позиции ind
function MySplitAt<T>(Self: sequence of T; ind: integer): (sequence of T, sequence of T); extensionmethod;
begin
  var a := new SplitAtHelper<T>(self, ind);
  Result := (a.f_fst, a.f_snd);
end;

function test: sequence of integer;
begin
  writeln('calculated');
  yield sequence Arr(1,2,3,4,5,6,7,8);
end;

begin
  var t := test.MySplitAt(4);
  var lc := 5;
  
  writeln;
  writeln(0);
  loop lc do writeln(t[0]);
  
  writeln;
  writeln(1);
  loop lc do writeln(t[1]);
  
  writeln;
  writeln(0);
  loop lc do writeln(t[0]);
  
  writeln;
  writeln(1);
  loop lc do writeln(t[1]);
  
  writeln;
  writeln(0);
  loop lc do writeln(t[0]);
  
  writeln;
  writeln(1);
  loop lc do writeln(t[1]);
  
  writeln;
  writeln(0);
  loop lc do writeln(t[0]);
  
  readln;
end.

#3

Вам никто не разрешит перегонять последовательность в список. Пожалейте силы на Pull Request. Напишите свои функции и пользуйтесь в своё удовольствие


#4

Почему? А Reverse значит изгой? Он то перегоняет всю последовательность в список.

Если бы вы были правы - функции вроде GroupBy и Reverse проходили бы последовательность много раз. Но они всё делают единожды. Почему вы это игнорируете?


#5

Reverse - да, изгой - там по-другому не сделаешь.

Основное правило с последовательностями - не выделять дополнительную память. Иначе смысла в последовательностях нет никакого.

Мы это правило нарушать не будем. Если Вам нужна другая функциональность - напишите и пользуйтесь.


#6

Методы последовательностей стандартной библиотеки:

Которые не выделяют доп память на элементы (их 36)
Aggregate
All
Any
Append
AsEnumerable
Average
Cast
Concat
Contains
Count
DefaultIfEmpty
ElementAt
ElementAtOrDefault
First
FirstOrDefault
Last
LastOrDefault
LongCount
Max
Min
OfType
Prepend
Select
SelectMany
SequenceEqual
Single
SingleOrDefault
Skip
SkipWhile
Sum
Take
TakeWhile
Where
Zip
AsParallel
AsQueryable
И которые выделяют (их 15) (я не считал Max и т.п., ибо они выделяют память не под элементы, и всегда одинаковый объём)
Distinct
Except
GroupBy
GroupJoin
Intersect
Join
OrderBy
OrderByDescending
Reverse
ToArray
ToDictionary
ToHashSet
ToList
ToLookup
Union

Почти треть стандартных библиотек (коллекции + Linq) - изгои? Зато то что вы написали - это святое. А может всё же это вы их неправильно используете?

И - теперь, когда я по ним всем прошёлся - это уже 100% информация: ни 1 из них не проходит последовательность больше 1 раза. Все кому это надо - выделяют доп. память.


#7

Да, отличная работа - спасибо.

Теперь сами посмотрите: выделяют память только те методы, которые не могут не выделять. Сразу отбросим

ToArray
ToDictionary
ToHashSet
ToList
ToLookup

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

Остальные - ещё раз повторю - невозможно написать не выделяя память.

SplitAt относится к тем 36-ти. В промышленной библиотеке Cadenza ровно этот код.

В любом случае напишите функции, какие удобно Вам, и пользуйтесь. Стандартная библиотека не может покрыть всех применений.


#8

Ну почему же:

function _Reverse<T>(self: sequence of T): sequence of T;
begin
  
  var n := 0;
  var last: T;
  foreach var a in self do
  begin
    last := a;
    n += 1;
  end;
  if n=0 then exit;
  yield last;
  
  for var i := n-1 downto 1 do
  begin
    var enm := self.GetEnumerator;
    loop i do enm.MoveNext;
    yield enm.Current;
  end;
  
end;

begin end.

Так же с абсолютно всеми методами из стандарта .Net, где применяется выделение доп. памяти - можно обойтись и многократными проходами по последовательности.

Вы про ту которая сдохла 6 лет назад, только прожив < 2 лет, получила всего 23 звезды на гитхабе, и ни 1 issue-бага там же? Я, пожалуй, в этот раз даже проверять не буду действительно ли там так реализовано, потому что это ну совсем не показатель.

Да, но она может хотя бы не противоречить более низкоуровневой стандартной библиотеке. В которой, как я уже ни раз сказал - НИГДЕ нету такого чтоб экстеншн метод вычислял последовательность >1 раза.


#9

@Сергей, а вы проверяли эффективность скомпилированного кода на скорость/память – действительно 100% оверхед? За исключением человекочитаемости (вроде рекурсии), иногда ради памяти приходится жертвовать скоростью и наоборот, потому что выигрыш [особенно значительный] сразу по памяти и скорости говорит о серьёзном просчёте или изначально неверном варианте


#10

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

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


#11

Понятно, не какой-то промежуточный шаг или оптимизация на память или скорость, а ради эффективной однозначности. Хотя двойная прогонка видимо с неудачной конверсии, но может есть рабочий пример, когда нынешняя реализация выдаёт неверный результат из-за двойственности?


#12

Неверный это только при захвате и изменении внешней переменной:

function ReadToEnd(self: System.IO.StreamReader): sequence of string; extensionmethod;
begin
  while not self.EndOfStream do
    yield self.ReadLine;
end;

begin
  var sr := System.IO.File.OpenText('inp.txt');
  writeln(sr.ReadToEnd.SplitAt(5));
end.

А так - проблема именно в


#13

Скажите, а как Вы собираетесь реализовывать Partition? У нас так:

function Partition<T>(Self: sequence of T; cond: T->boolean)
  : (sequence of T, sequence of T); extensionmethod;
begin
  Result := (Self.Where(cond), Self.Where(x -> not cond(x)));
end;

А Вы наверное списком:

function Partition<T>(Self: sequence of T; cond: T->boolean)
  : (sequence of T, sequence of T); extensionmethod;
begin
  var l := Self.ToList; // Второй проход по списку не страшен - побочного эффекта не будет
  Result := (l.Where(cond), l.Where(x -> not cond(x)));
end;

Или того хуже двумя?


#14

Я его уже почти дописал, я остановился сначала с вами решить всё. Но идея такая: когда читают из 1 коллекции - все элементы которые не подходят её записывать в список с именем temp, а когда из второй коллекции начнут читать - сначала выдать весь этот список, а потом начинать дальше идти по сорс коллекции.

(при этом temp это поле доп. класса который будет только в реализации PABCSystem, поэтому в программы он не будет попадать. Так же, через доп класс, реализованы большинство таких сложный функции из стандарта .Net )

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


#15

Ещё раз - вы будете использовать список только для половины элементов (то есть для работы вашей функции будет требоваться O(n) памяти)?

И вы всерьёз считаете эту реализацию более эффективной?


#16

Кстати, чтобы Вы быстро увидели - файл справки по blockFileOfT отображается так:

и гиперссылки не работают. Посмотрите, как оформляется кодировка в html.


#17

Это только в худшем случае. Если дело будет касаться эффективности - можно считать сначала ту часть, которая скорее всего будет содержать больше элементов (по случаю это можно определить обычно).

И - в который раз говорю, дело не в эффективности, а в том что ни 1 из стандартных .Net функций не вычисляет последовательность >1 раза. И это вызовет непонятно поведение, у любого человека привыкшего к нормальную поведению функций последовательностей.

Всё же их >50 всего, а в PABCSystem таких очень мало, я вот умудрился только недавно наткнуться на них.


#18

Сейчас попробую с гитхаба скачать, ибо у меня версия на компе норм. Но это вообще не в эту тему. Перенесите пожалуйста сюда.

P.S. кхм у меня и из Samples работает норм, ну сейчас действительно пойду посмотрю как кодировку устанавливать в html…


#19

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

begin
  Writeln(ReadSeqInteger(25).Partition(t->t>0))
end.

Тут последовательность из 25 чисел придется вводить дважды. Это ужасно. Для всех подобных реализаций в Справке просто необходимо указать, что в случае использования расширений для последовательностей, вводимых с клавиатуры, данные придется перевводить. Выглядит какой-то капитуляцией перед реализацией: “извините, народ, мы пока что не смогли это сделать, как надо”.

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


#20

Так и есть. Конвертируйте последовательность в массив для подобных применений. Последовательность не хранится в памяти - это её основное свойство. Кто этим не умеет пользоваться - плодят темы на форуме ))