Здравствуйте, alex_public, Вы писали:
_>Ну linq то тут в любом случае проиграл бы, просто из-за тормознутости сопрограмм, необходимости копирования и т.п.
Теоретически — нет. Ничто не мешает потенциальному компилятору породить оптимальный код — наоборот, ему это сделать проще, чем в случае чисто императивного решения, т.к. намерение и механизм его реализации явно разделены.
Я практически уверен, что если мы попробуем записать точно такой же код на cовременном C++ (с лямбдами и прочим), то результат будет неотличимым от ручного выписывания циклов for.
Потому, что компиляторы C++ построены с применением агрессивного инлайнинга, а дальше SSA, сonstant propagation, и moving subexpression out of loop делают свою работу.
То есть "тормознутость сопрограмм" — это ограничения JIT по инлайнингу кода. "необходимость копирования" — это как раз из-за того, что инлайнинг не случился, и нет возможности передвинуть подвыражение.
Ещё раз подчеркну: декларативность linq к этому никакого отношения не имеет. Абсолютно императивный код, написанный на современном шарпе и обработанный современным джитом, подвержен ровно тем же затруднениям.
_>Это в любой задаче из данной области. А вот в данной конкретной задаче (где у нас вложенные коллекции и условие по предыдущему элементу) появился ещё и дополнительный алгоритмический провал.
_>Конечно. Но если ты будешь вставлять условия фильтрации грубо говоря не в блоке where, а внутри некой своей дополнительной функции, генерирующей пары, то это будет по сути уже не linq, а тот же самый императивный код.
Нет, я не буду вставлять условия фильтрации внутри дополнительной функции.
Я сначала натравлю на коллекцию коллекций функцию, вычисляющую атрибут, а уже потом выполню PairScan:
from pair in (from c in collectionsList select new {c, count=(from i in c where i > 2).Count()}).PairScan() where ... select ...
Но это, по сути, беспредметный разговор. На всякий случай напомню, что код с Lag и прочим прекрасно компилируется в SQL, а его уже исполняет движок СУБД, способный радикальнейшим образом переставить порядок операций.
Это означает, что потенциально мы можем заменить все эти примитивные версии операторов Where и Select на их ExpressionTree-аналоги, а в методы ToList и GetEnumerable() встроить полноценный компилятор, способный выполнять агрессивный инлайнинг делегатов и оптимизацию циклов.
Более того, мы можем сделать так, чтобы вся эта адская магия срабатывала только тогда, когда у нас количество элементов в коллекции больше порогового, потому что на сотне элементов все эти вот "втрое медленнее" будут незаметны даже в микроскоп.
