Julia: как получить случайную перестановку заданной строки s?

Возможно, определение Stringметода для создания Stringпиратства типа, но, во всяком случае, вот предлагаемая реализация:

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

Если вы хотите сжать производительность, 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.

К сожалению, это грязно, поэтому я бы скорее рассматривал это как упражнение. Однако он использует только экспортированные функции, поэтому это не взломать.

Вдохновленный оптимизационными трюками в ответе Bogumil Kaminski, следующая версия с почти такой же производительностью, но немного более ясная (на мой взгляд) и использующая вторую функцию полезности, которая может быть полезной сама по себе:

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 = "dalsy"

julia> @btime shuffle($s)       # shuffle from DNF's answer
  831.200 ns (9 allocations: 416 bytes)
"yldsa"

julia> @btime shufflefast($s)   # shuffle from this answer
  252.224 ns (5 allocations: 432 bytes)
"lydas"

julia> @btime kaminskishufflefast($s)  # shuffle from Kaminski's answer
  197.345 ns (4 allocations: 384 bytes)
"yasdl"

EDIT: немного лучше - см. Комментарии к коду

Это от ответа Богумила Камински, где я стараюсь избежать вычисления длины (*), если это не обязательно:

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 быстрее. Производительность должна быть одинаковой. Вся длина должна быть подсчитана, и есть одинаковое распределение.

Пример времени для строки в Юникоде:

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 немного, но явно быстрее. Немного больше, чем функция Богумила, и немного меньше, чем в решении Дэна.

(*) - Я немного надеюсь, что реализация String в Julia будет быстрее в будущем, и длина может быть намного быстрее, чем сейчас.