Чудеса оптимизации?
// PascalABC.NET 3.1, сборка 1174 от 22.02.2016
begin
var n:=ReadInteger('n=');
var s:=ReadSeqInteger(n);
var d:=ReadInteger('d=');
Writeln('Среднее ',s.Where(x->x>d).Average)
end.
Результат удивил. Программа сначала запросила ввод n, а потом, совершенное неожиданно, ввод d. И только затем перешла к чтению элементов последовательности. Все-таки хочется, чтобы последовательность ввода определял программист, а не компилятор.
Ну, если бы Вы сказали ToArray, то было бы так как Вы хотите. А так - последовательности ленивы. Привыкайте 
Я знаю, что последовательности ленивы, но не предполагал, что настолько! Их лень так заразительна, что она даже на ввод перекидывается…
(помните из анекдота? - А петух ваш кур-то топчет? - Да, кур, петухов, кошек, собак…на жену заглядываться начал, потому и продаю!")
Но все же плохо, что эта лень делает поведение программы непредсказуемым.
P.S. Если бы я добавил .ToArray, то это было бы странно, поскольку тогда проще ReadArray использовать.
Прошло несколько дней и вот- “Только бледнолицый может дважды наступить на одни и те же грабли” (с) Рискуя навлечь на себя праведный гнев “Отцов-Основателей” все же помещу еще раз описание проблемы. Скажем так, в назидание другим бледнолицым.
Наткнулся на школьную задачу, где предлагалось в произвольном целочисленном массиве элементы с НЕЧЕТНЫМИ номерами упорядочить по возрастанию их значений. И стало интересно получить решение с максимальным использованием возможностей версии 3.1, т.е. “написать покороче”.
Первый шаг - перейти к динамическим массивам, т.е. принять к сведению, что работать будем с ЧЕТНЫМИ индексами из-за нумерации от 0, а не с помощью чисел натурального ряда. Т.е. надо обрабатывать элементы с индексами i=0,2,…2k, i<=n-1 для массива из n элементов.
Дальнейшие шаги: выделить упомянутые выше элементы, упорядочить их по возрастанию, поместить в последовательность и заместить элементами этой последовательности нужные элементы в исходном массиве. Была написана программа, которая дала удивительные результаты и которую затем я щедро снабдил трассировочным выводом. Вот эта программа:
// PascalABC.NET 3.1, сборка 1174 от 22.02.2016
begin
var n:=ReadInteger('n=');
var a:=ArrRandom(n,10,99);
Writeln('a: ',a);
var b:=Range(0,n-1,2).Select(i->a.ElementAt(i)).Sorted;
Writeln('b: ',b);
var i:=0;
while i<=n-1 do begin
var j:=i div 2;
Writeln('Проход по циклу номер ',j+1);
Writeln('a[',i,']=',a[i],', b[',j,']=',b.ElementAt(j));
a[i]:=b.ElementAt(j);
Writeln('a[',i,']=',a[i],', b[',j,']=',b.ElementAt(j));
Writeln('a: ',a);
i+=2
end;
Writeln('a: ',a)
end.
И вот выдача:
n= 10
a: [33,13,51,91,89,70,30,89,72,79]
b: [30,33,51,72,89]
Проход по циклу номер 1
a[0]=33, b[0]=30
a[0]=30, b[0]=30
a: [30,13,51,91,89,70,30,89,72,79]
Проход по циклу номер 2
a[2]=51, b[1]=30
a[2]=30, b[1]=30
a: [30,13,30,91,89,70,30,89,72,79]
Проход по циклу номер 3
a[4]=89, b[2]=30
a[4]=30, b[2]=30
a: [30,13,30,91,30,70,30,89,72,79]
Проход по циклу номер 4
a[6]=30, b[3]=30
a[6]=30, b[3]=30
a: [30,13,30,91,30,70,30,89,72,79]
Проход по циклу номер 5
a[8]=72, b[4]=72
a[8]=72, b[4]=72
a: [30,13,30,91,30,70,30,89,72,79]
a: [30,13,30,91,30,70,30,89,72,79]
Хорошо видно, что посредством метода .ElementAt() из последовательности b извлекаются, мягко говоря, странные значения. Ну и результат, соответственно… в мусорную корзину.
Переход к массивам посредством добавления .ToArray радикально все меняет и программа сразу становится работоспособной:
// PascalABC.NET 3.1, сборка 1174 от 22.02.2016
begin
var n:=ReadInteger('n=');
var a:=ArrRandom(n,10,99);
Writeln('a: ',a);
var b:=Range(0,n-1,2).Select(i->a.ElementAt(i)).Sorted.ToArray;
Writeln('b: ',b);
var i:=0;
while i<=n-1 do begin
var j:=i div 2;
Writeln('Проход по циклу номер ',j+1);
Writeln('a[',i,']=',a[i],', b[',j,']=',b[j]);
a[i]:=b[j];
Writeln('a[',i,']=',a[i],', b[',j,']=',b[j]);
Writeln('a: ',a);
i+=2
end;
Writeln('a: ',a)
end.
Трассировка показывает, что все происходит строго так, как положено.
n= 10
a: [89,83,59,21,29,54,31,86,73,44]
b: [29,31,59,73,89]
Проход по циклу номер 1
a[0]=89, b[0]=29
a[0]=29, b[0]=29
a: [29,83,59,21,29,54,31,86,73,44]
Проход по циклу номер 2
a[2]=59, b[1]=31
a[2]=31, b[1]=31
a: [29,83,31,21,29,54,31,86,73,44]
Проход по циклу номер 3
a[4]=29, b[2]=59
a[4]=59, b[2]=59
a: [29,83,31,21,59,54,31,86,73,44]
Проход по циклу номер 4
a[6]=31, b[3]=73
a[6]=73, b[3]=73
a: [29,83,31,21,59,54,73,86,73,44]
Проход по циклу номер 5
a[8]=73, b[4]=89
a[8]=89, b[4]=89
a: [29,83,31,21,59,54,73,86,89,44]
a: [29,83,31,21,59,54,73,86,89,44]
Последовательность в самостоятельном виде использовать практически нельзя: пресловутая “обезьяна с гранатой” рядом с последовательностями отдыхает. Т.е. мы должны понимать, что практически любой метод, примененный к массиву, силится превратить массив в последовательность (и обычно это ему удается!) и забыв прилепить в конце строки .ToArray мы сразу же получаем объект, который в будущем (возможно, уже в следующем операторе) сделает нам “бо-бо”.
Вот к чему ведет “ленивость”, если ей потакать…
Ваша ошибка - в этой строке. Поскольку вычисления - ленивые, то строка
срабатывает всякий раз с новым массивом a. Поймите - массив захватывается не по значению, а по ссылке.
Концептуально - использовать в таких задачах b.ElementAt(j) неправильно, потому что для нахождения j-того элемента перебираются предшествующие j-1.
Я думаю, что Вы слишком решительно отвергаете для себя последовательности. Интуиция тут Вас подводит, но это не значит, что последовательности плохие - это значит лишь, что Вы используете неадекватные для задачи средства. Ленивость сама по себе это ни плохо ни хорошо - плохо использовать ее неправильно и не в тех задачах.
Всё-таки, мне кажется, что Вы пока не разобрались с этими вещами, иначе не были бы так неосторожны.
Давайте еще раз.
Последовательность нельзя рассматривать как набор данных. Последовательность - это алгоритм получения данных. Причем, срабатывает этот алгоритм в последний момент - когда нужно вывести данные последовательности, посчитать по ним скаляр или превратить их в массив. До этого последовательность остаётся всего лишь алгоритмом - ничем больше.
Например, в приведенной Вами строке:
b не хранит данные. Они еще не вычислены. Они даже не начинали вычисляться. b хранит лишь алгоритм будущего вычисления последовательности (и его параметры), причем, с тем a, которое будет в тот момент когда мы последовательность начнем вычислять. Поэтому напиши Вы хоть Range(0,1000000000).ВсёЧтоТам - эта строчка проработает мгновенно, поскольку она не проходит еще по последовательности, она всего лишь запоминает данные для будущего срабатывания алгоритма. И даже Sorted не приводит еще к срабатыванию алгоритма. Заставляет впервые сработать алгоритм b.ElementAt(j), поскольку превращает последовательность в скаляр. Увы - это крайне неэффективно, потому что при каждом вызове b.ElementAt(j) будет вызываться алгоритм, хранящийся в b и последовательность будет перебираться с начала.
Вот собственно и причина всех бед.
Ровно так же будет работать ваша программа на C# и VB.NET, так же будут работать аналогичные алгоритмы в Haskell - собственно, везде где есть ленивые вычисления.
Просто их надо использовать там, где уместно, и здесь старый опыт - не союзник.
Ленивость вещь сложная: в Хаскеле даже среднего уровня прогарммист, как правило, не может предсказать многих побочных эффектов её массового применения (там всё ленивое). Так что проблемы предсказуемы. Но нужно, конечно, пытаться развить новую интуицию.
Существует большой класс задач, в которых необходимо, так или иначе, учитывать позицию элемента среди себе подобных. Насколько я понял объяснения, последовательности тут использовать не получается, а методы динамических массивов почти всегда ленивы. Отсюда - либо постоянные ToArray в конце цепочек, либо старые добрые циклы…
Я пока не представляю себе, как можно эффективно решить такую задачу без “традиционных” циклов: упорядочить по неубыванию элементы массива, расположенные между парой его элементов, имеющих минимальное и максимальное значение. Т.е. я могу найти минимум, максимум, но найти их положение в массиве уже так просто не могу. Тем более, не могу извлечь элементы из образовавшегося промежутка и упорядочив их, вставить полученную группу элементов “назад” в массив. Традиционные циклы решают задачу прямо на месте, ведь стоит только найти границы интервала. а отсортировать на нем элементы не проблема.
Возможно, конечно, что пока мне не попались задачи, где последовательности могли бы быть полезны именно как самостоятельные объекты. Был бы благодарен за примеры подобных простых задачек и их решений.
Возможно, существуют разные уровни “ленивости”. Да, с ленивостью в концепции Haskell мне не приходилось сталкиваться, поскольку так уж случилось, что по работе я последние лет 15 просидел на работе c различными большими СУБД и там вообще было нереально изучать что-то дополнительное. Но, как ни странно, быть может, в БД зачастую тоже используются похожие принципы отложенной обработки данных, например, у серверов БД хранится не SQL-выборка, а некий “план выполнения”, составленный оптимизатором и пользователь по запросу получает результат по кусочкам. Да чего ходить далеко: в свое время “настольная FoxPro” еще под DOS умудрялась за доли секунды формировать выборку объeмом в десятки тысяч записей на процессоре i386. А потому что она и не думала эту выборку делать - как только какие-то данные просили в пределах этой выборки, в этот момент она их и получать начинала. Но там было все “нормально” - когда к этому курсору не обратись - данные он всегда одни и те же возвращал. Как и другие SQL-сервера. Вот это концепция меня и подвела: я отлично сознавал, что “ленивость” - это именно алгоритм, “план выполнения”, но вот того, что все будет лениво по-иному, я не ожидал. Что ж, спасибо за разъяснения, буду иметь в виду в дальнейшем.
Несомненно, последовательности не заменят массивы. И массивы более эффективны. Особенно когда что-то надо делать “по месту”.
С последовательностями в основном работают так: последовательность целиком преобразуют в другую последовательность, последовательности сливают, соединяют, разъединяют и т.п.
То есть, стиль решения - другой.
Вот - решение Вашей задачи:
begin
var n := 10;
var a := ArrRandom(n,10,99).Println;
var a1 := a.Where((x,i)->i mod 2 = 0);
var a2 := a.Where((x,i)->i mod 2 <> 0);
a1.Sorted.Interleave(a2).Println;
end.
Вы правы - эта задача гораздо лучше решается с массивами. Пытаться использовать тут “новые возможности” - неправильно
Наверно что-то не подключено, потому что при запуске пишет, что неизвеcтно имя Interleave
А Вы скачайте новую версию - в ней много добавлений в методы расширения. В ней можно заодно глянуть, как реализована Interleave.
Кстати, если использовать все новые методы расширения, то так - еще проще:
begin
var n := 10;
var a := ArrRandom(n,10,99).Println;
var pp := a.Partition((x,i)->i mod 2 = 0); // разбили на две последовательности
pp[0].Sorted.Interleave(pp[1]).Println;
end.
Но пока для этого кода у нас плохо работает Intellisense
Вот с этим не совсем удачно решен вопрос: нет информирования своевременного о выходе новой версии. Зачастую на странице загрузки находится информация о старой версии, поэтому приходится ежедневно скачивать, ставить… и убеждаться, что версия не поменялась. Или поменялась. Вот не далее как днем я скачивал - еще была 1174 от 22.02. Т.е. я её закачивал 23,24,25,… 29 февраля. На всякий случай))
Жаль, конечно, если Intellisense неактуален - ведь это был по сути единственный источник получения актуальной информации.
Скачал. Ставить нужно StandardPack, потому что в MiniPack вошел какой-то совсем уж урезанный Intellisense, в нем пропало почти все, что было раньше по “новинкам”.
На странице загрузки написано, когда версия обновилась. К сожалению, именно в данном случае мы очень спешили - поэтому не всё ещё готово. Intellisense всегда запаздывает - доделаем - но там мелочи. Мы сейчас работаем над обновлённой справкой по модулю PABCSystem.
Про MiniPack - а нельзя ли сказать, что конкретно в Intellisense не работает? С нашей точки зрения работает всё.
Сейчас абсолютно все программы сами проверяют обновления и спрашивают, надо ли скачать. Хотелось бы иметь такое в Паскале.
Уже нельзя, потому что я поверх поставил StadardPack. Может, мне не повезло и что-то криво встало, но не было подсказа по ArrRandom, для созданного по ArrRandom массива присутствовали только первые несколько строчек в Intellisense…
Увы, не каждый раз. Про версию 1174 не было ни слова в “Скачать” - только про 1172. А на страничке “Что нового” - вообще версия 1167, а потом сразу 1179.
Для этого, опять же, надо сначала, чтобы на сайте с обновлением лежала некоторая своевременно обновляемая сигнатура.
Там не было ничего нового
Поставил поверх с сайта. Подсказка по ArrRandom работает. В MiniPack только задачника нет.
Значит мне не повезло при установке и вопрос снимается. Есть полный смысл соответствующие сообщения удалить, чтобы людей не смущать.
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021