Выполнение последовательностей с помощью while и for-do, по сравнению с прямой реализацией `IEnumerable <T>`

Ответ 1

Хорошо, я сделаю снимок. Все результаты кода и тестов можно найти здесь.

Lazy v Eager Секвенции медленные. Понимание медленное. Они представляют собой удобную абстракцию, которая включает в себя множество генерируемых компилятором решений и распределений, и их вообще следует избегать вообще, если первичность важна. Все рассматриваемые иммы легко поддаются простому нелакому решению.

// ~50% faster for given test case
// still ~20% faster even for length 1.5M string
let eager1 (value: string) =
    let result = ResizeArray(value.Length)
    for i in 0 .. value.Length - 1 do
        if not (Char.IsLowSurrogate(value.[i]))
        then result.Add(Char.ConvertToUtf32(value, i))
    result.ToArray()

Generic v Non. В тестовой функции вызывается общий код.

Добавьте оператор регистрации для обоих .Current impls и передайте свою выходную последовательность на |> Seq.iter (printfn "%d"), и вы увидите ее генерируемую.

Вы тестировали в FSI? По какой-то причине FSI "печатает несколько элементов этой последовательности на консоль", код завершается в не-общий путь, но это не влияет на исполняемый код. Может быть, это то, что вы видели?

Циклы в seq {} Петли внутри seq { }, а другие выражения вычислений не являются регулярными циклами. (на самом деле почти ничего "нормального" взгляда внутри вычисляющих выражений на самом деле нормально, что является видом точки:)) Как указано в выражении вычисления docs, цикл for заканчивается кодированием как итерация по другому перечислимому. Циклы while немного проще.

Это более или менее объясняет, почему ваша "попытка 1" намного медленнее - цикл for приводит к распределению и повторению еще одного seq внутри вашего seq.

Трубопровод через API-интерфейсы Seq. Да, на каждом шаге это создаст новые сегменты. Если "реальная работа" задействована очень маленькая, как в этом примере, тогда накладные расходы начинают доминировать.

Быстрее. Ваши последующие оптимизации удаляют слои абстракции, и поэтому, хотя у меня нет точных объяснений, кажется разумным, что они немного ускоряются.

.AsEnumerable() Это довольно странно, я могу воспроизвести значительное ускорение, которое вы видите. Очень странно, учитывая, что метод расширения AsEnumerable ничего не делает, но возвращает свой вход напрямую!

Структура сгенерированного кода в этом случае очень различна. Возможно, это как-то патологический случай в оптимизаторе. Интересная находка.

Вариации. Я обнаружил, что результаты значительно меняются при включении/отключении оптимизаций и при выборе x64 vs x86. Возьмите это за то, что это стоит.

Обновить после изменения контрольных показателей и требований OP

Array.toSeq Здесь нет необходимости использовать Array.toSeq и предсказуемо перетащить производительность моего предлагаемого решения. Array.toSeq и Seq.ofArray больше для безопасности (убедитесь, что полученный seq не может быть преобразован обратно в массив потребителем и мутирован), чем преобразование типа.

Лучший выбор:

• Просто верните массив seq<_> при его возврате
• Обновите свои другие API, чтобы принять гибкий тип #seq<'t>, тогда даже простой массив в порядке

Обновленные требования С учетом вновь выявленных ограничений:

• Обработка строк настолько велика, что даже 1 или 2 копии вызовут OOM
• Частая ранняя выручка при обработке

тогда ясно, что ленивый подход будет более уместным, по крайней мере в некоторых случаях.

Тем не менее, даже с учетом этих требований, при тестировании с вашими новыми критериями, не-ленивые решения по-прежнему очень хорошо работают во всех случаях, кроме OOM или огромного ввода с ранней выдачей.

См. мой gist, приведенный выше для получения результатов. Он включает в себя альтернативные нелазные реализации:

let eager2 (value: string) =
    let result = ResizeArray(value.Length)
    for i in 0 .. value.Length - 1 do
        if not (Char.IsLowSurrogate(value.[i]))
        then result.Add(Char.ConvertToUtf32(value, i))
    // cast result so that return type isn't array
    (result.ToArray()) :> seq<_>

let eager3 (value: string) =
    let result = ResizeArray(value.Length)
    for i in 0 .. value.Length - 1 do
        if not (Char.IsLowSurrogate(value.[i]))
        then result.Add(Char.ConvertToUtf32(value, i))
    // ToArray() causes another copy to be generated.
    // Avoiding that is a win in large-input scenarios, but at a cost
    // of otherwise slower processing
    (result) :> seq<_>

Улучшение ленивого решения

Вот дальнейшая оптимизация ленивого подхода, прямое интегрирование всей логики, исключение использования перечислителя строк и исключение рекурсии.

В большинстве случаев этот парень, по-видимому, избивает не-ленивые решения!

let lazy5 (value : string) =         
    let inline getEnum() = 
        let i = ref -1
        { new IEnumerator<int> with
              member __.Current = Char.ConvertToUtf32(value, !i)
          interface System.Collections.IEnumerator with
              member __.Current =  box (Char.ConvertToUtf32(value, !i))
              member __.MoveNext() = 
                      incr i
                      if !i >= value.Length then false else
                      if not (Char.IsLowSurrogate(value.[!i])) then true else
                      incr i
                      !i < value.Length                  
              member __.Reset() = failwith "reset"
          interface IDisposable with
              member __.Dispose() = () }
    { new IEnumerable<int> with
          member __.GetEnumerator() = getEnum()
      interface IEnumerable with
          member __.GetEnumerator() = getEnum() :> IEnumerator }

Резюме

Первое решение seq с открытым исходным кодом отлично смотрится и выполняет хорошо заданные ограничения. Я попытался дать некоторый контекст, почему предлагаемые альтернативы могут быть медленнее, надеюсь, это полезно. Мне удалось выжать немного больше перфоманса, объединив все в эксликт IEnumerable.

В зависимости от ограничений и ввода, решение, отличное от лени, может быть хорошим выбором. Я предложил несколько вариантов здесь. Как всегда, вам нужно будет протестировать в своей реальной среде.