为什么 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

我的偏好是使用通用的单行解决方案，即使它比 Przemys\xc5\x82aw 提出的要慢一点（我已经为了简单性而不是速度而对其进行了优化）：

\n

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

\n

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

\n

该解决方案如何运作

\n

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

\n

\n
• findall(Regex(".{1,$nc}")返回一个与字符急切匹配的范围向量nc；
\n
• SubString(s, r)接下来，我使用 迭代的返回范围创建一个避免分配的对象r。
\n
• 最后全部作为分隔符连接起来\\n。
\n

\n

OP解决方案有什么问题

\n

第一次尝试：

\n

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

\n

第二次尝试：

\n

\n
• 这样做解决了多次s = collect(s)调用和错误使用字节索引的问题，但效率低下，因为它进行了不必要的分配，而且还使您的代码类型不稳定（因为您分配给与原始存储类型不同的变量值）；lengthVector{Char}s
\n
• 首先String(s[l(i):r(i)])分配一小部分Vector{Char}，然后分配String
\n

\n

什么是快速解决方案

\n

如果您想要比正则表达式更快并且正确的东西，您可以使用以下代码：

\n

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

\n

Answer 3

您可以对字节进行操作

\n

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

\n

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

\n

 @btime chop($s);\n  1.531 s (6267 allocations: 1.28 MiB)\n\njulia> @btime chop2($s);\n  334.100 \xce\xbcs (13 allocations: 1.57 MiB)\n

\n

笔记：

\n

\n
• 通过预分配，这段代码仍然可以稍微快一些dat，但我尝试与原始代码类似。
\n
• 当有 unicode 字符时，无论是你的还是这种方法都不起作用，因为你不能在中间剪切 unicode 字符
\n

\n

Answer 4

在同事的帮助下，我们找到了导致所提供的实现如此缓慢的主要原因。

事实证明，Julialength(::String)具有时间复杂度O(n)，并且结果不会被缓存，因此字符串越长，对其length本身花费的时间越多，输入的时间也越长。请参阅此 Reddit 帖子，了解对这一现象的深入讨论：

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

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