string - 为什么在 Julia 中创建 string 如此缓慢?

我正在维护一个 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} 并且它使您的代码类型不稳定(因为您分配给变量 s value 与最初存储的类型不同);
  • 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

相似文章

julia - 在 Julia 中构建 CPLEX 失败

我正在尝试在计算机集群上的Julia中安装CPLEX。执行Pkg.build("CPLEX")时出现以下错误。看来我没有通过正确的道路。我知道如何在本地计算机上更正它,但谁能告诉我如何在计算机集群上修...

最新文章