为什么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=收集（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

我更倾向于使用通用的单行解决方案，即使它比Przemysaw提出的要慢一点（我已经为简单而不是速度而优化了它）：

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字符，并且还可以处理子字符串{String}。

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

• findall（Regex（“..{1，$nc}”）返回一个范围向量，该向量与多达nc个字符的范围匹配

第一次尝试：

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

第二次尝试：

• 执行s=Collection（s）解决了多次调用长度和错误使用字节索引的问题，但效率低下，因为它不必要地分配Vector{Char}并且它还使您的代码类型不稳定（因为您分配给与最初存储的类型不同的变量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 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)

注意事项：

• 通过预先分配dat，此代码仍然可以稍微快一点，但我尝试与原始代码类似。
• 当使用Unicode字符时，您和这种方法都不起作用，因为您不能在中间剪切Unicode字符

Answer 3

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