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 являются, по существу, "уплощающими" проекциями, т.е. иерархия объектов "сплющена" в список. )