朱莉娅：如何获得一个给定的字符串s的随机排列？

Question

我想到了两种不同的方法，但都显得很丑陋。

1. 变换字符串s到一个数组a通过split婷，然后再次使用sample(a, length(s), replace=false)和join阵列成一个字符串

2. 优惠RandomPermutationr长度length(s)和join单s[i]为i在r。

什么是正确的方法？不幸的是，没有匹配sample(::String, ::Int64; replace=false)的方法。

Answer 1

也许定义String一个shuffle方法构成类型盗版，但是，无论如何，这里有一个建议implemetation：

Base.shuffle(s::String) = isascii(s) ? s[randperm(end)] : join(shuffle!(collect(s))) 

Answer 2

如果你想挤掉从shuffle性能，那么你可以考虑：

function shufflefast(s::String) 
    ss = sizeof(s) 
    l = length(s) 

    ss == l && return String(shuffle!(copy(Vector{UInt8}(s)))) 

    v = Vector{Int}(l) 
    i = start(s) 
    for j in 1:l 
     v[j] = i 
     i = nextind(s, i) 
    end 

    p = pointer(s) 
    u = Vector{UInt8}(ss) 
    k = 1 
    for i in randperm(l) 
     for j in v[i]:(i == l ? ss : v[i+1]-1) 
      u[k] = unsafe_load(p, j) 
      k += 1 
     end 
    end 
    String(u) 
end 

对于大字符串是超过4倍的ASCII和3倍更快UTF-8快。

遗憾的是凌乱的 - 所以我宁愿把它作为一个练习。但是，它只使用导出的函数，所以它不是黑客。

Answer 3

在博古米尔斯基的回答的优化技巧的启发，下面是几乎相同的性能版本，但更清楚一点（在我看来），并利用其本身可以是一个有价值的第二效用函数：

function strranges(s)  # returns the ranges of bytes spanned by chars 
    u = Vector{UnitRange{Int64}}() 
    sizehint!(u,sizeof(s)) 
    i = 1 
    while i<=sizeof(s) 
     ii = nextind(s,i) 
     push!(u,i:ii-1) 
     i = ii 
    end 
    return u 
end 

function shufflefast(s) 
    ss = convert(Vector{UInt8},s) 
    uu = Vector{UInt8}(length(ss)) 
    i = 1 
    @inbounds for r in shuffle!(strranges(s)) 
     for j in r 
      uu[i] = ss[j] 
      i += 1 
     end 
    end 
    return String(uu) 
end 

例时机：

julia> using BenchmarkTools 

julia> s = "ďaľšý" 

julia> @btime shuffle($s)  # shuffle from DNF's answer 
    831.200 ns (9 allocations: 416 bytes) 
"ýľďša" 

julia> @btime shufflefast($s) # shuffle from this answer 
    252.224 ns (5 allocations: 432 bytes) 
"ľýďaš" 

julia> @btime kaminskishufflefast($s) # shuffle from Kaminski's answer 
    197.345 ns (4 allocations: 384 bytes) 
"ýašďľ" 

Answer 4

编辑：好一点的性能 - 见代码注释

这是博古米尔卡明斯基的ANS WER其中我试图避免计算长度（*），如果它不是必要的：

function shufflefast2(s::String) 
    ss = sizeof(s) 
    local l 

    for l in 1:ss 
     #if ((codeunit(s,l) & 0xc0) == 0x80) 
     if codeunit(s,l)>= 0x80 # edit (see comments bellow why) 
      break 
     end 
    end 

    ss == l && return String(shuffle!(copy(Vector{UInt8}(s)))) 

    v = Vector{Int}(ss) 
    i = 1 
    l = 0 
    while i<ss 
     l += 1 
     v[l] = i 
     i = nextind(s, i) 
    end 
    v[l+1] = ss+1 # edit - we could do this because ss>l 

    p = pointer(s) 
    u = Vector{UInt8}(ss) 
    k = 1 
    for i in randperm(l) 
     # for j in v[i]:(i == l ? ss : v[i+1]-1) 
     for j in v[i]:v[i+1]-1 # edit we could do this because v[l+1] is defined (see above) 
      u[k] = unsafe_load(p, j) 
      k += 1 
     end 
    end 
    String(u) 
end 

实施例定时ASCII字符串：

julia> srand(1234);@btime for i in 1:100 danshufflefast("test") end 
    19.783 μs (500 allocations: 34.38 KiB) 

julia> srand(1234);@btime for i in 1:100 bkshufflefast("test") end 
    10.408 μs (300 allocations: 18.75 KiB) 

julia> srand(1234);@btime for i in 1:100 shufflefast2("test") end 
    10.280 μs (300 allocations: 18.75 KiB) 

差过小，有时bkshufflefast更快。性能必须相同。整个长度必须被计数并且有相同的分配。为Unicode字符串

实施例定时：

julia> srand(1234);@btime for i in 1:100 danshufflefast(s) end 
    24.964 μs (500 allocations: 42.19 KiB) 

julia> srand(1234);@btime for i in 1:100 bkshufflefast(s) end 
    20.882 μs (400 allocations: 37.50 KiB) 

julia> srand(1234);@btime for i in 1:100 shufflefast2(s) end 
    19.038 μs (400 allocations: 40.63 KiB) 

shufflefast2是一个小但明显更快这里。比丹的解决方案多一点分配比博略米尔的功能和少一些的分配。

（*） - 我一点希望，在朱莉娅的字符串实施将在未来和长度速度可能会更快，比现在。