Здравствуйте, Sinclair, Вы писали:

_>>Ну linq то тут в любом случае проиграл бы, просто из-за тормознутости сопрограмм, необходимости копирования и т.п.
S>Теоретически — нет. Ничто не мешает потенциальному компилятору породить оптимальный код — наоборот, ему это сделать проще, чем в случае чисто императивного решения, т.к. намерение и механизм его реализации явно разделены.
S>Я практически уверен, что если мы попробуем записать точно такой же код на cовременном C++ (с лямбдами и прочим), то результат будет неотличимым от ручного выписывания циклов for.
S>Потому, что компиляторы C++ построены с применением агрессивного инлайнинга, а дальше SSA, сonstant propagation, и moving subexpression out of loop делают свою работу.

Это смотря чем ты предполагаешь заменить yield (в C++17 его пока ещё нет, т.к. как раз не смогли договориться в споре о преимуществах stackfull и stackless сопрограмм). Последние кстати как раз лоббировала MS.

S>То есть "тормознутость сопрограмм" — это ограничения JIT по инлайнингу кода. "необходимость копирования" — это как раз из-за того, что инлайнинг не случился, и нет возможности передвинуть подвыражение.

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

_>>Это в любой задаче из данной области. А вот в данной конкретной задаче (где у нас вложенные коллекции и условие по предыдущему элементу) появился ещё и дополнительный алгоритмический провал.
_>>Конечно. Но если ты будешь вставлять условия фильтрации грубо говоря не в блоке where, а внутри некой своей дополнительной функции, генерирующей пары, то это будет по сути уже не linq, а тот же самый императивный код.
S>Нет, я не буду вставлять условия фильтрации внутри дополнительной функции.
S>Я сначала натравлю на коллекцию коллекций функцию, вычисляющую атрибут, а уже потом выполню PairScan:
S>

S>from pair in (from c in collectionsList select new {c, count=(from i in c where i > 2).Count()}).PairScan() where ... select ...
S>

S>Но это, по сути, беспредметный разговор. На всякий случай напомню, что код с Lag и прочим прекрасно компилируется в SQL, а его уже исполняет движок СУБД, способный радикальнейшим образом переставить порядок операций.
S>Это означает, что потенциально мы можем заменить все эти примитивные версии операторов Where и Select на их ExpressionTree-аналоги, а в методы ToList и GetEnumerable() встроить полноценный компилятор, способный выполнять агрессивный инлайнинг делегатов и оптимизацию циклов.
S>Более того, мы можем сделать так, чтобы вся эта адская магия срабатывала только тогда, когда у нас количество элементов в коллекции больше порогового, потому что на сотне элементов все эти вот "втрое медленнее" будут незаметны даже в микроскоп.

Ну как бы в данной подветке мы обсуждали исключительно работу с коллекциями. С СУБД и так всё понятно — там где есть Lag, имеем решение. Разве что было интересно глянуть на внутреннее устройство этой Lag (наверняка же там выбран наиболее эффективный вариант, причём не из теории).