Выход F#! оператор — Реализация и возможные эквиваленты C#

В настоящее время я изучаю F#, и мне очень нравится оператор yield! (выход-взрыв). Не только из-за его названия, но и из-за того, что он делает, конечно.

Оператор yield! в основном позволяет вам получить все элементы последовательности из выражения последовательности. Это полезно для составления перечислителей. Поскольку я регулярно сталкиваюсь с большими и сложными счетчиками, меня интересуют стратегии, которые мы можем использовать, чтобы разбить их и составить из более простых счетчиков.

К сожалению, оператор yield! недоступен в C#. Насколько я понимаю, то, что он делает, похоже на foreach (var x in source) yield x; но книгу, которую я читаю (Petricek's Real World F# - Manning) предполагает лучшую производительность...

  • Так что же именно здесь делает компилятор F#? (Да, я могу посмотреть на него и с помощью Reflector, но хотелось бы более подробного описания механизма).

Чтобы получить аналогичную конструкцию в C#, я исследовал несколько способов, но ни один из них не является таким кратким, как оператор 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() реализовано так, как я описал выше.

Любые другие варианты?


c# f# yield ienumerable enumerators
person Johannes Rudolph    schedule 17.08.2010    source источник

Ответы (3)


arrow_upward
6
arrow_downward

Относительно того, как компилятор транслирует операцию yield!, статья, на которую ссылается Томас Левеск в своем ответе иллюстрирует один метод реализации в разделе 4.3 (в частности, их пример, охватывающий рисунки 7-9, иллюстрирует общую стратегию). Я не думаю, что есть хороший способ сделать это из блока итератора в С# - насколько я понимаю ваши предложенные решения, они оба могут привести к квадратичному поведению при рекурсивном использовании. Вы всегда можете вручную создать подкласс NestedEnumerable<T> для повышения производительности, но это будет довольно уродливо по сравнению с использованием обычного блока итератора.

person kvb    schedule 17.08.2010

arrow_upward
7
arrow_downward

В текущей версии С# я не думаю, что у вас есть другие варианты, кроме foreach... yield return и Concat. Я согласен, что было бы неплохо иметь оператор yield! в C#, это сделало бы некоторые конструкции намного более элегантными, но я сомневаюсь, что эта функция когда-либо попадет в список «обязательных», поскольку мы можем легко обойтись без нее.

Вам может быть интересна эта научная статья по 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) (линейная). Я не думаю, что вы можете добиться большего успеха с текущими функциями С#...

person Thomas Levesque    schedule 17.08.2010
comment
Как указано в статье, которую вы цитируете, при рекурсивном использовании есть случаи, когда yield! (что эквивалентно гипотетическому yield foreach в С#) равно O (n), а foreach ... yield return ... равно O (n ^ 2). - person kvb; 17.08.2010
comment
@kvb: Верно, это то, о чем я говорю, извините, если это неясно. - person Johannes Rudolph; 17.08.2010

arrow_upward
4
arrow_downward

Прямого аналога yield! в C# нет. В настоящее время вы застряли с комбинацией foreach и yield return.

Однако IIRC, LINQ предлагает нечто подобное, а именно оператор запроса SelectMany, который переводится на C# как несколько предложений from .. in ...

(Я надеюсь, что не смешиваю две разные концепции, но IIRC, как yield!, так и SelectMany, по сути, являются «сглаживающими» проекциями, т. е. иерархия объектов «сглаживается» в список.)

person stakx - no longer contributing    schedule 17.08.2010