Является ли использование StringBuilder правильным решением для F #?

Ответ 1

Я думаю, что использование StringBuilder в F # отлично - тот факт, что sb.Append возвращает текущий экземпляр StringBuilder, означает, что его можно легко использовать с помощью функции fold. Несмотря на то, что это по-прежнему необходимо (объект мутирован), он достаточно хорошо подходит к функциональному стилю, когда вы не показываете ссылки на StringBuilder.

Но в равной степени вы можете просто построить список строк и объединить их с помощью String.concat - это почти так же эффективно, как использование StringBuilder (оно медленнее, но не намного), и оно значительно быстрее, чем объединение строк с использованием +)

Итак, списки дают вам такую ​​же производительность, но они неизменяемы (и хорошо работают с concurrency и т.д.) - они были бы хорошо подходят, если бы вы строили строку алгоритмически, потому что вы можете просто добавлять строки к фронту список - это очень эффективная операция над списками (а затем обратная строка). Кроме того, использование выражений в списках дает вам очень удобный синтаксис:

// Concatenating strings using + (2.3 seconds)
let s1 = [ for i in 0 .. 25000 -> "Hello " ] |> Seq.reduce (+)
s1.Length

// Creating immutable list and using String.concat (5 ms)
let s2 = [ for i in 0 .. 25000 -> "Hello " ] |> String.concat ""
s2.Length

// Creating a lazy sequence and concatenating using StringBuilder & fold (5 ms)
let s3 = 
  seq { for i in 0 .. 25000 -> "Hello " }
  |> Seq.fold(fun (sb:System.Text.StringBuilder) s -> 
      sb.Append(s)) (new System.Text.StringBuilder())
  |> fun x -> x.ToString()
s3.Length

// Imperative solution using StringBuilder and for loop (1 ms)
let s4 = 
  ( let sb = new System.Text.StringBuilder()
    for i in 0 .. 25000 do sb.Append("Hello ") |> ignore
    sb.ToString() )
s4.Length

Время было измерено на моей довольно быстрой рабочей машине, используя #time в F # Interactive - вполне вероятно, что в релиз-сборке было бы быстрее, но я думаю, что они довольно репрезентативны.

Ответ 2

Если вам нужна высокопроизводительная конкатенация sting, тогда построитель строк, вероятно, правильный путь, однако есть способы сделать функционал строки более функциональным. Вообще говоря, если вам нужна изменчивость в функциональной программе, подходящий способ сделать это - создать для нее функциональную оболочку. В F # это обычно выражается как выражение вычисления. Ниже приведен пример выражения вычисления конструктора строк здесь.

Пример использования:

//Create a function which builds a string from an list of bytes
let bytes2hex (bytes : byte []) =
    string {
        for byte in bytes -> sprintf "%02x" byte
    } |> build

//builds a string from four strings
string {
        yield "one"
        yield "two"
        yield "three"
        yield "four"
    } |> build

Изменить: Я сделал новую реализацию вышеупомянутого выражения вычислений, а затем запустил выпуск версии четырех решений Tomas плюс мое выражение вычисления и выражение вычисления, которое я ранее связывал.

s1 elapsed Time: 128150 ms  //concatenation
s2 elapsed Time: 459 ms     //immutable list + String.concat
s3 elapsed Time: 354 ms     //lazy sequence and concatenating using StringBuilder & fold 
s4 elapsed Time: 39 ms      //imperative
s5 elapsed Time: 235 ms     //my computation expression
s6 elapsed Time: 334 ms     //the linked computation expression

Обратите внимание, что s3 занимает в 9 раз больше, чем императив, а s5 занимает всего 6 раз.

Вот моя реализация выражения вычисления построителя строк:

open System.Text

type StringBuilderUnion =
| Builder of StringBuilder
| StringItem of string

let build = function | Builder(x) -> string x | StringItem(x) -> string x

type StringBuilderCE () =
    member __.Yield (txt : string) = StringItem(txt)
    member __.Yield (c : char) = StringItem(c.ToString())
    member __.Combine(f,g) = Builder(match f,g with
                                     | Builder(F),   Builder(G)   ->F.Append(G.ToString())
                                     | Builder(F),   StringItem(G)->F.Append(G)
                                     | StringItem(F),Builder(G)   ->G.Insert(0, F)
                                     | StringItem(F),StringItem(G)->StringBuilder(F).Append(G))
    member __.Delay f = f()
    member __.Zero () = StringItem("")
    member __.For (xs : 'a seq, f : 'a -> StringBuilderUnion) =
                    let sb = StringBuilder()
                    for item in xs do
                        match f item with
                        | StringItem(s)-> sb.Append(s)|>ignore
                        | Builder(b)-> sb.Append(b.ToString())|>ignore
                    Builder(sb)

let builder1 = new StringBuilderCE ()

Функция таймера (обратите внимание, что каждый тест выполняется 100 раз):

let duration f = 
    System.GC.Collect()
    let timer = new System.Diagnostics.Stopwatch()
    timer.Start()
    for _ in 1..100 do
        f() |> ignore
    printfn "elapsed Time: %i ms" timer.ElapsedMilliseconds