为什么在 Julia 中创建字符串这么慢？

Question

我正在维护一个 Julia 库，其中包含一个函数，用于在长字符串中每 80 个字符后插入一个新行。

当字符串超过 100 万个字符时，此函数变得非常慢（秒或更长时间）。时间似乎比线性增加更多，也许是二次增加。我不明白为什么。有人可以解释一下吗？

这是一些可重现的代码：

function chop(s; nc=80)
    nr   = ceil(Int64, length(s)/nc)
    l(i) = 1+(nc*(i-1)) 
    r(i) = min(nc*i, length(s))
    rows = [String(s[l(i):r(i)]) for i in 1:nr]
    return join(rows,'\n')
end

s = "A"^500000

chop(s)

似乎这一行是花费最多时间的地方：rows = [String(s[l(i):r(i)]) for i in 1:nr]

这是否意味着初始化一个新的 String 需要很长时间？这并不能真正解释超线性运行时间。

我知道构建字符串的规范快速方法是使用 IOBuffer 或更高级别的 StringBuilders 包：https://github.com/davidanthoff/StringBuilders.jl

谁能帮我理解为什么上面的代码这么慢？

奇怪的是，下面的速度要快得多，只需添加 s = collect(s):

function chop(s; nc=80)
    s = collect(s) #this line is new
    nr   = ceil(Int64, length(s)/nc)
    l(i) = 1+(nc*(i-1)) 
    r(i) = min(nc*i, length(s))
    rows = [String(s[l(i):r(i)]) for i in 1:nr]
    return join(rows,'\n')
end

Answer 1

String 在 Julia 中是不可变的。如果您需要以这种方式处理字符串，最好先创建一个 Vector{Char}，以避免重复分配新的大字符串。

Answer 2

你可以对字节进行操作

function chop2(s; nc=80)
    b = transcode(UInt8, s)
    nr   = ceil(Int64, length(b)/nc)
    l(i) = 1+(nc*(i-1)) 
    r(i) = min(nc*i, length(b))
    dat = UInt8[]
    for i in 1:nr
        append!(dat, @view(b[l(i):r(i)]))
        i < nr && push!(dat, UInt8('\n'))
    end
    String(dat)
end

和基准测试（快大约 5000 倍）：

 @btime chop($s);
  1.531 s (6267 allocations: 1.28 MiB)

julia> @btime chop2($s);
  334.100 μs (13 allocations: 1.57 MiB)

备注：

此代码仍然可以通过 pre-allocating dat 稍微快一些，但我尝试与原始代码相似。
当你和这个方法都没有 unicode 字符时，将无法工作，因为你不能在中间剪切 unicode 字符

Answer 3

我更喜欢使用通用的 one-liner 解决方案，即使它比 Przemysław 提议的要慢一点（我已经优化它是为了简单而不是速度）：

chop_and_join(s::Union{String,SubString{String}}; nc::Integer=80) =
    join((SubString(s, r) for r in findall(Regex(".{1,$nc}"), s)), '\n')

好处是它可以正确处理所有 Unicode 字符，并且还可以处理 SubString{String}。

解决方案的工作原理

给定的解决方案如何工作：

findall(Regex(".{1,$nc}") returns 热切匹配最多 nc 个字符的范围向量；
接下来我创建一个 SubString(s, r) 来避免分配，使用由 r.
最后全部以\n作为分隔符连接起来。

OP 解决方案有什么问题

第一次尝试：

不建议使用您选择的函数名称chop，因为它会掩盖来自 Base Julia 的同名函数；
length(s) 被多次调用，是一个昂贵的函数；它应该只被调用一次并存储为一个变量；
通常使用 length 是不正确的，因为 Julia 使用字节索引而不是字符索引（有关解释，请参阅 here）
String(s[l(i):r(i)]) 效率低下，因为它分配了两次 String（实际上不需要外部 String）

第二次尝试：

执行 s = collect(s) 解决了多次调用 length 和不正确使用字节索引的问题，但效率低下，因为它不必要地分配 Vector{Char} 并且还使您的代码 type-unstable（当您分配给变量 s 的值与最初存储的类型不同时）；
做 String(s[l(i):r(i)]) 首先分配一个小的 Vector{Char} 然后分配 String

什么是快速解决方案

如果你想要比正则表达式更快的东西并且更正你可以使用这个代码：

function chop4(s::Union{String, SubString{String}}; nc::Integer=80)
    @assert nc > 0
    isempty(s) && return s
    sz = sizeof(s)
    cu = codeunits(s)
    buf_sz = sz + div(sz, nc)
    buf = Vector{UInt8}(undef, buf_sz)
    start = 1
    buf_loc = 1
    while true
        stop = min(nextind(s, start, nc), sz + 1)
        copyto!(buf, buf_loc, cu, start, stop - start)
        buf_loc += stop - start
        if stop == sz + 1
            resize!(buf, buf_loc - 1)
            break
        else
            start = stop
            buf[buf_loc] = UInt8('\n')
            buf_loc += 1
        end
    end
    return String(buf)
end

Answer 4

这与@PrzemyslawSzufel 的版本具有相似的性能，但更简单。

function chop3(s; nc=80)
    L = length(s)
    join((@view s[i:min(i+nc-1,L)] for i=1:nc:L), '\n')
end

我没有选择 firstindex(s)，lastindex(s) 因为字符串可能没有任意索引，但无论如何都没有区别。

@btime chop3(s) setup=(s=randstring(10^6))  # 1.625 ms (18 allocations: 1.13 MiB)
@btime chop2(s) setup=(s=randstring(10^6))  # 1.599 ms (14 allocations: 3.19 MiB)

更新：根据@BogumiłKamiński 的建议，使用 ASCII 字符串，sizeof 的这个版本甚至快了 60%。

function chop3(s; nc=80)
    L = sizeof(s)
    join((@view s[i:min(i+nc-1,L)] for i=1:nc:L), '\n')
end

Answer 5

在一位大学生的帮助下，我们找出了导致所提供的实施如此缓慢的主要原因。

原来length(::String)在Julia中有时间复杂度O(n)，结果不缓存，所以字符串越长调用越多到 length 这本身需要的时间越长，输入越长。请参阅 this Reddit post 以了解对该现象的详细讨论：

将字符串收集到向量中解决了瓶颈，因为向量的长度是 O(1) 而不是 O(n)。

这当然不是解决一般问题的最佳方法，但它是一个单行更改，可以加快所提供的代码。

为什么在 Julia 中创建字符串这么慢？

Why is string creation so slow in Julia?

string

julia

解决方案的工作原理

OP 解决方案有什么问题

什么是快速解决方案