我正在维护一个 Julia 库，其中包含一个函数，用于在长 string 中每 80 个字符后插入一个新行。
当 string 超过 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 需要很长时间？这并不能真正解释超线性运行时间。
我知道构建 strings 的规范快速方法是使用 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回答1
String 在 Julia 中是不可变的。如果您需要以这种方式使用 string，最好先创建一个 Vector{Char}，以避免重复分配新的、大的 strings。
回答2
我的偏好是使用通用的单线解决方案，即使它比 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}")返回一个与nc字符热切匹配的范围向量；- 接下来我创建一个避免分配的
SubString(s, r)，使用由r迭代的返回范围。 - 最后 all 以
\n作为分隔符。
OP 解决方案有什么问题
第一次尝试：
- 不建议使用您选择的函数名称
chop，因为它会遮盖 Base Julia 中具有相同名称的函数； length(s)被多次调用，这是一个昂贵的函数；它应该只被调用一次并作为变量存储；- 通常使用
length是不正确的，因为 Julia 使用字节索引而不是字符索引（有关说明，请参见 https://bkamins.github.io/julialang/2020/08/13/strings.html） String(s[l(i):r(i)])效率低下，因为它分配了两次String（实际上不需要外部String）
第二次尝试：
- 执行
s = collect(s)解决了多次调用length和错误使用字节索引的问题，但效率低下，因为它不必要地分配Vector{Char}并且它使您的代码类型不稳定（因为您分配给变量svalue 与最初存储的类型不同）； - 做
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回答3
您可以对字节进行操作
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 字符
回答4
在一位同事的帮助下，我们找出了导致提供的实现如此缓慢的主要原因。
原来length(::String)在Julia中有时间复杂度O(n)，而且结果没有被缓存，所以string越长，对length的调用越多，这本身花费的时间越长，输入的时间就越长。请参阅 https://www.reddit.com/r/Julia/comments/cpi06c/lengthstring_considered_harmful/，了解有关该现象的详细讨论：
将 string 收集到向量中解决了瓶颈，因为向量的长度是 O(1) 而不是 O(n)。
当然，这绝不是解决一般问题的最佳方法，但它是一种可以加快所提供代码的单行更改。
回答5
这与@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) 因为 strings 可能没有任意索引，但无论如何都没有区别。
@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 strings，这个带有 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