Julia：与えられた文字列のランダムな並べ替えを得る方法？

Question

私は2つの異なる方法を考えましたが、どちらもかなり醜いようです。

1. iための単一s[i]をsplitティンそれによってアレイaに文字列sを変換し、その文字列に再び

2. をsample(a, length(s), replace=false)とjoinアレイを使用すると、長さlength(s)のRandomPermutationrを取得し、joinr。

正しい方法はありますか？残念ながら、sample(::String, ::Int64; replace=false)に一致する方法はありません。

Answer 1

はおそらくStringためshuffle方法を定義することは著作権侵害を入力し構成する、しかし、とにかく、ここで提案実装だ：

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 

を

大きな文字列の場合、ASCIIでは4倍、UTF-8では3倍高速です。

残念ながら、それは乱雑です - 私はむしろ運動としてそれを扱うでしょう。ただし、エクスポートされた関数のみを使用するため、ハックではありません。 Bogumilカミンスキーの答えでは、最適化のトリックに触発

Answer 3

、以下では、ほぼ同じ性能を持つバージョンですが、少し（私の意見では）明確にし、それ自体が価値であってもよい第2のユーティリティ関数を使用して：

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

EDIT：少し良いパフォーマンス - 参照コードが

コメントこれはBogumilカミンスキーの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は明らかに速く、ここで少ししかしです。 Bogumilの機能よりも少し多く割り当てられ、Danのソリューションよりも割り当てが少し少なくなっています。

（*） - JuliaでのString実装が将来的に早くなり、長さが今よりもはるかに早くなることを少し希望します。