Некоторые экстеншн-методы последовательностей из PABCSystem вызывают проход по входной последовательности 2 раза.Так не должно быть, ни 1 из стандартных функций последовательностей так не делает. Если не смотреть в исходники - не возможно узнать почему вдруг появилось неожиданное поведение. Более подробно я описал всё в #1451.
Я взялся переписать такие функции без костылей. Сюда буду складывать перед тем как сделать пулл-реквест.
Найдены уже SplitAt, Partition и UnZipTuple. Кто найдёт ещё - напишите.
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.
Почему? А Reverse значит изгой? Он то перегоняет всю последовательность в список.
Если бы вы были правы - функции вроде GroupBy и Reverse проходили бы последовательность много раз. Но они всё делают единожды. Почему вы это игнорируете?
Методы последовательностей стандартной библиотеки:
Которые не выделяют доп память на элементы (их 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 и т.п., ибо они выделяют память не под элементы, и всегда одинаковый объём)
Почти треть стандартных библиотек (коллекции + Linq) - изгои? Зато то что вы написали - это святое. А может всё же это вы их неправильно используете?
И - теперь, когда я по ним всем прошёлся - это уже 100% информация: ни 1 из них не проходит последовательность больше 1 раза. Все кому это надо - выделяют доп. память.
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 раза.
@Сергей, а вы проверяли эффективность скомпилированного кода на скорость/память – действительно 100% оверхед? За исключением человекочитаемости (вроде рекурсии), иногда ради памяти приходится жертвовать скоростью и наоборот, потому что выигрыш [особенно значительный] сразу по памяти и скорости говорит о серьёзном просчёте или изначально неверном варианте
Это не так просто. Всё зависит от того, как сложно посчитать входную последовательность. Если входная последовательность будет выполнять сложные вычисления - разница будет значительной.
Но, дело всё же не в производительности, а в том - что для всех методов .Net можно ожидать сколько раз будет пройдена последовательность (всегда 1), а тут нет даже в описании ничего про то что последовательность считается несколько раз. При захвате и изменении внешних переменных - это может оказаться неожиданной проблемой, а значит ошибкой которую будет сложно найти.
Понятно, не какой-то промежуточный шаг или оптимизация на память или скорость, а ради эффективной однозначности. Хотя двойная прогонка видимо с неудачной конверсии, но может есть рабочий пример, когда нынешняя реализация выдаёт неверный результат из-за двойственности?
Неверный это только при захвате и изменении внешней переменной:
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.
Скажите, а как Вы собираетесь реализовывать 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;
Я его уже почти дописал, я остановился сначала с вами решить всё. Но идея такая: когда читают из 1 коллекции - все элементы которые не подходят её записывать в список с именем temp, а когда из второй коллекции начнут читать - сначала выдать весь этот список, а потом начинать дальше идти по сорс коллекции.
(при этом temp это поле доп. класса который будет только в реализации PABCSystem, поэтому в программы он не будет попадать. Так же, через доп класс, реализованы большинство таких сложный функции из стандарта .Net )
Нет конечно, это ужасное решение. Потому что тут все элементы и обязательно придётся перенести в новый список. На самом деле в реализации всего подобного действует очень простая логика, надо думать что может понадобится в каждый момент и это и выдавать. Не знаю как полностью объяснить, но когда понял - становится очень просто.
Это только в худшем случае. Если дело будет касаться эффективности - можно считать сначала ту часть, которая скорее всего будет содержать больше элементов (по случаю это можно определить обычно).
И - в который раз говорю, дело не в эффективности, а в том что ни 1 из стандартных .Net функций не вычисляет последовательность >1 раза. И это вызовет непонятно поведение, у любого человека привыкшего к нормальную поведению функций последовательностей.
Всё же их >50 всего, а в PABCSystem таких очень мало, я вот умудрился только недавно наткнуться на них.
Не знал этого, ибо сильно удручает. Напомню, что в случае ввода последовательности с клавиатуры, двойное обращение к ней приведет к повторному запросу ввода.
begin
Writeln(ReadSeqInteger(25).Partition(t->t>0))
end.
Тут последовательность из 25 чисел придется вводить дважды. Это ужасно. Для всех подобных реализаций в Справке просто необходимо указать, что в случае использования расширений для последовательностей, вводимых с клавиатуры, данные придется перевводить. Выглядит какой-то капитуляцией перед реализацией: “извините, народ, мы пока что не смогли это сделать, как надо”.
Я уж не говорю о том, что будет, если отдать на вход последовательность от датчика случайных чисел.
Так и есть. Конвертируйте последовательность в массив для подобных применений. Последовательность не хранится в памяти - это её основное свойство. Кто этим не умеет пользоваться - плодят темы на форуме ))
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021