F # урожай! оператор - реализация и возможные эквиваленты С#
В настоящее время я изучаю F #, и мне очень нравится оператор yield!
(yield-bang). Не только для его названия, но и для того, что он делает, конечно.
Оператор yield!
в принципе позволяет вам вывести все элементы последовательности из выражения последовательности. Это полезно для составления счетчиков. Поскольку я регулярно сталкиваюсь с большими сложными счетчиками, меня интересуют стратегии, которые мы можем использовать, чтобы разбить их и составить их из более простых счетчиков.
К сожалению, оператор yield!
недоступен в С#. Насколько я понимаю, то, что он делает, похоже на foreach (var x in source) yield x;
, но книга, которую я читаю (Petricek Real World F # - Manning) предлагает что он имеет лучшую производительность...
- Итак, что именно делает компилятор F # здесь? (Да, я могу посмотреть на него, используя Reflector, но я хотел бы получить более подробное описание механизма).
Чтобы получить аналогичную конструкцию в С#, я исследовал несколько способов, но ни один из них не столь краток, как оператор yield!
, и я также не уверен в их сложности. Может ли кто-нибудь запросить ввод, если мои номера BigO верны?
-
Разбить перечислитель на несколько частных счетчиков, а затем вывести каждый элемент из общего счетчика:
foreach (var x in part1()) yield x
foreach (var x in part2()) yield x
Это приведет к "двойному урону" для каждого элемента. Значит, O (2n)? (или, возможно, хуже?) Во всяком случае, использование этого подхода не позволяет мне использовать yield break;
из любого из моих подчастей.
-
Разбить перечислитель на несколько частных счетчиков, а затем перевести все частные счетчики из публичного счетчика:
return part1().Concat(part2())
Я считаю, что это ничем не отличается от вышеупомянутого решения, потому что Concat()
реализуется так, как я изложил выше.
Любые другие варианты?
Ответы
Ответ 1
Относительно того, как компилятор переводит операцию yield!
, в статье, которую цитирует Томас Левеске в своем ответе, иллюстрируется одна методика реализации в разделе 4.3 ( в частности, их пример, охватывающий цифры 7-9, иллюстрирует общую стратегию). Я не думаю, что есть хороший способ сделать это изнутри блока итератора на С# - так как я понимаю ваши предлагаемые решения, они могут привести к квадратичному поведению при использовании рекурсивно. Вы всегда можете вручную создать подкласс NestedEnumerable<T>
для достижения преимуществ по производительности, но это будет довольно уродливым по сравнению с использованием обычного блока итератора.
Ответ 2
В текущей версии С# я не думаю, что у вас есть другие варианты, кроме foreach... yield return
и Concat
. Я согласен с тем, что было бы неплохо иметь оператор yield!
в С#, это сделало бы некоторые конструкции более элегантными, но я сомневаюсь, что эта функция когда-либо попадет в список "must-have", поскольку мы без труда можем обойтись без нее.
Вам может быть интересна эта исследовательская статья MS, в которой представлена новая конструкция yield foreach
:
IEnumerable<XmlNode> Traverse(XmlNode n)
{
yield return n;
foreach (XmlNode c in n.ChildNodes)
yield foreach Traverse(c);
}
Относительно вашего вопроса о сложности: в обоих случаях это O (n). O (2n) не используется, поскольку он обозначает ту же сложность, что и O (n) (линейный). Я не думаю, что вы можете сделать лучше, чем с текущими функциями С#...
Ответ 3
В С# нет прямого аналога yield!
. В настоящее время вы придерживаетесь комбинации foreach
и yield return
.
Однако, IIRC, LINQ предлагает нечто подобное, а именно оператор запроса SelectMany
, который переводит на С# как несколько предложений from .. in ..
.
(Я надеюсь, что я не смешиваю две разные концепции, но IIRC, как yield!
, так и SelectMany
являются, по существу, "уплощающими" проекциями, т.е. иерархия объектов "сплющена" в список. )