#37999

Committed 02 Feb 2025 07:22AM UTC coverage: 17.218% (-8.3%) from 25.515%

Build # #37999

Build Type

push

local

Committed by

web-flow

Commit Message

bpart: Start tracking backedges for bindings (#57213)

This PR adds limited backedge support for Bindings. There are two
classes of bindings that get backedges:

1. Cross-module `GlobalRef` bindings (new in this PR)
2. Any globals accesses through intrinsics (i.e. those with forward
edges from #57009)

This is a time/space trade-off for invalidation. As a result of the
first category, invalidating a binding now only needs to scan all the
methods defined in the same module as the binding. At the same time, it
is anticipated that most binding references are to bindings in the same
module, keeping the list of bindings that need explicit (back)edges
small.

Run Details

7 of 30 new or added lines in 3 files covered. (23.33%)

4235 existing lines in 124 files now uncovered.

7882 of 45779 relevant lines covered (17.22%)

98289.89 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.92

/stdlib/Random/src/misc.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

## rand!(::BitArray) && bitrand

function rand!(rng::AbstractRNG, B::BitArray, ::SamplerType{Bool})
    isempty(B) && return B
    Bc = B.chunks
    rand!(rng, Bc)
    Bc[end] &= Base._msk_end(B)
    return B
end

"""
    bitrand([rng=default_rng()], [dims...])

Generate a `BitArray` of random boolean values.

# Examples
```jldoctest
julia> bitrand(Xoshiro(123), 10)
10-element BitVector:
 0
 1
 0
 1
 0
 1
 0
 0
 1
 1
```
"""
bitrand(r::AbstractRNG, dims::Dims)   = rand!(r, BitArray(undef, dims))
bitrand(r::AbstractRNG, dims::Integer...) = rand!(r, BitArray(undef, convert(Dims, dims)))

bitrand(dims::Dims)   = rand!(BitArray(undef, dims))
bitrand(dims::Integer...) = rand!(BitArray(undef, convert(Dims, dims)))


## randstring (often useful for temporary filenames/dirnames)

"""
    randstring([rng=default_rng()], [chars], [len=8])

Create a random string of length `len`, consisting of characters from
`chars`, which defaults to the set of upper- and lower-case letters
and the digits 0-9. The optional `rng` argument specifies a random
number generator, see [Random Numbers](@ref).

# Examples
```jldoctest
julia> Random.seed!(3); randstring()
"Lxz5hUwn"

julia> randstring(Xoshiro(3), 'a':'z', 6)
"iyzcsm"

julia> randstring("ACGT")
"TGCTCCTC"
```

!!! note
    `chars` can be any collection of characters, of type `Char` or
    `UInt8` (more efficient), provided [`rand`](@ref) can randomly
    pick characters from it.
"""
function randstring end

let b = UInt8['0':'9';'A':'Z';'a':'z']
    global randstring

    function randstring(r::AbstractRNG, chars=b, n::Integer=8)
        T = eltype(chars)
        if T === UInt8
            str = Base._string_n(n)
            GC.@preserve str rand!(r, UnsafeView(pointer(str), n), chars)
            return str
        else
            v = Vector{T}(undef, n)
            rand!(r, v, chars)
            return String(v)
        end
    end

    randstring(r::AbstractRNG, n::Integer) = randstring(r, b, n)
    randstring(chars=b, n::Integer=8) = randstring(default_rng(), chars, n)
    randstring(n::Integer) = randstring(default_rng(), b, n)
end


## randsubseq & randsubseq!

# Fill S (resized as needed) with a random subsequence of A, where
# each element of A is included in S with independent probability p.
# (Note that this is different from the problem of finding a random
#  size-m subset of A where m is fixed!)
function randsubseq!(r::AbstractRNG, S::AbstractArray, A::AbstractArray, p::Real)
    require_one_based_indexing(S, A)
    0 <= p <= 1 || throw(ArgumentError("probability $p not in [0,1]"))
    n = length(A)
    p == 1 && return copyto!(resize!(S, n), A)
    empty!(S)
    p == 0 && return S
    nexpected = p * length(A)
    sizehint!(S, round(Int,nexpected + 5*sqrt(nexpected)))
    if p > 0.15 # empirical threshold for trivial O(n) algorithm to be better
        for i = 1:n
            rand(r) <= p && push!(S, A[i])
        end
    else
        # Skip through A, in order, from each element i to the next element i+s
        # included in S. The probability that the next included element is
        # s==k (k > 0) is (1-p)^(k-1) * p, and hence the probability (CDF) that
        # s is in {1,...,k} is 1-(1-p)^k = F(k).   Thus, we can draw the skip s
        # from this probability distribution via the discrete inverse-transform
        # method: s = ceil(F^{-1}(u)) where u = rand(), which is simply
        # s = ceil(log(rand()) / log1p(-p)).
        # -log(rand()) is an exponential variate, so can use randexp().
        L = -1 / log1p(-p) # L > 0
        i = 0
        while true
            s = randexp(r) * L
            s >= n - i && return S # compare before ceil to avoid overflow
            push!(S, A[i += ceil(Int,s)])
        end
        # [This algorithm is similar in spirit to, but much simpler than,
        #  the one by Vitter for a related problem in "Faster methods for
        #  random sampling," Comm. ACM Magazine 7, 703-718 (1984).]
    end
    return S
end

"""
    randsubseq!([rng=default_rng(),] S, A, p)

Like [`randsubseq`](@ref), but the results are stored in `S`
(which is resized as needed).

# Examples
```jldoctest
julia> S = Int64[];

julia> randsubseq!(Xoshiro(123), S, 1:8, 0.3)
2-element Vector{Int64}:
 4
 7

julia> S
2-element Vector{Int64}:
 4
 7
```
"""
randsubseq!(S::AbstractArray, A::AbstractArray, p::Real) = randsubseq!(default_rng(), S, A, p)

randsubseq(r::AbstractRNG, A::AbstractArray{T}, p::Real) where {T} =
    randsubseq!(r, T[], A, p)

"""
    randsubseq([rng=default_rng(),] A, p) -> Vector

Return a vector consisting of a random subsequence of the given array `A`, where each
element of `A` is included (in order) with independent probability `p`. (Complexity is
linear in `p*length(A)`, so this function is efficient even if `p` is small and `A` is
large.) Technically, this process is known as "Bernoulli sampling" of `A`.

# Examples
```jldoctest
julia> randsubseq(Xoshiro(123), 1:8, 0.3)
2-element Vector{Int64}:
 4
 7
```
"""
randsubseq(A::AbstractArray, p::Real) = randsubseq(default_rng(), A, p)


## rand Less Than Masked 52 bits (helper function)

"Return a sampler generating a random `Int` (masked with `mask`) in ``[0, n)``, when `n <= 2^52`."
ltm52(n::Int, mask::Int=nextpow(2, n)-1) = LessThan(n-1, Masked(mask, UInt52Raw(Int)))

## shuffle & shuffle!

"""
    shuffle!([rng=default_rng(),] v::AbstractArray)

In-place version of [`shuffle`](@ref): randomly permute `v` in-place,
optionally supplying the random-number generator `rng`.

# Examples
```jldoctest
julia> shuffle!(Xoshiro(123), Vector(1:10))
10-element Vector{Int64}:
  5
  4
  2
  3
  6
 10
  8
  1
  9
  7
```
"""
function shuffle!(r::AbstractRNG, a::AbstractArray)
    # keep it consistent with `randperm!` and `randcycle!` if possible
    require_one_based_indexing(a)
    n = length(a)
    @assert n <= Int64(2)^52
    n == 0 && return a
    mask = 3
    @inbounds for i = 2:n
        j = 1 + rand(r, ltm52(i, mask))
        a[i], a[j] = a[j], a[i]
        i == 1 + mask && (mask = 2 * mask + 1)
    end
    return a
end

function shuffle!(r::AbstractRNG, a::AbstractArray{Bool})
    old_count = count(a)
    len = length(a)
    uncommon_value = 2old_count <= len
    fuel = uncommon_value ? old_count : len - old_count
    fuel == 0 && return a
    a .= !uncommon_value
    while fuel > 0
        k = rand(r, eachindex(a))
        fuel -= a[k] != uncommon_value
        a[k] = uncommon_value
    end
    a
end

shuffle!(a::AbstractArray) = shuffle!(default_rng(), a)

"""
    shuffle([rng=default_rng(),] v::AbstractArray)

Return a randomly permuted copy of `v`. The optional `rng` argument specifies a random
number generator (see [Random Numbers](@ref)).
To permute `v` in-place, see [`shuffle!`](@ref). To obtain randomly permuted
indices, see [`randperm`](@ref).

# Examples
```jldoctest
julia> shuffle(Xoshiro(123), Vector(1:10))
10-element Vector{Int64}:
  5
  4
  2
  3
  6
 10
  8
  1
  9
  7
```
"""
shuffle(r::AbstractRNG, a::AbstractArray) = shuffle!(r, copymutable(a))
shuffle(a::AbstractArray) = shuffle(default_rng(), a)

shuffle(r::AbstractRNG, a::Base.OneTo) = randperm(r, last(a))

## randperm & randperm!

"""
    randperm([rng=default_rng(),] n::Integer)

Construct a random permutation of length `n`. The optional `rng`
argument specifies a random number generator (see [Random
Numbers](@ref)). The element type of the result is the same as the type
of `n`.

To randomly permute an arbitrary vector, see [`shuffle`](@ref) or
[`shuffle!`](@ref).

!!! compat "Julia 1.1"
    In Julia 1.1 `randperm` returns a vector `v` with `eltype(v) == typeof(n)`
    while in Julia 1.0 `eltype(v) == Int`.

# Examples
```jldoctest
julia> randperm(Xoshiro(123), 4)
4-element Vector{Int64}:
 1
 4
 2
 3
```
"""
randperm(r::AbstractRNG, n::T) where {T <: Integer} = randperm!(r, Vector{T}(undef, n))
randperm(n::Integer) = randperm(default_rng(), n)

"""
    randperm!([rng=default_rng(),] A::Array{<:Integer})

Construct in `A` a random permutation of length `length(A)`. The
optional `rng` argument specifies a random number generator (see
[Random Numbers](@ref)). To randomly permute an arbitrary vector, see
[`shuffle`](@ref) or [`shuffle!`](@ref).

# Examples
```jldoctest
julia> randperm!(Xoshiro(123), Vector{Int}(undef, 4))
4-element Vector{Int64}:
 1
 4
 2
 3
```
"""
function randperm!(r::AbstractRNG, a::Array{<:Integer})
    # keep it consistent with `shuffle!` and `randcycle!` if possible
    n = length(a)
    @assert n <= Int64(2)^52
    n == 0 && return a
    a[1] = 1
    mask = 3
    @inbounds for i = 2:n
        j = 1 + rand(r, ltm52(i, mask))
        if i != j # a[i] is undef (and could be #undef)
            a[i] = a[j]
        end
        a[j] = i
        i == 1 + mask && (mask = 2 * mask + 1)
    end
    return a
end

randperm!(a::Array{<:Integer}) = randperm!(default_rng(), a)


## randcycle & randcycle!

"""
    randcycle([rng=default_rng(),] n::Integer)

Construct a random cyclic permutation of length `n`. The optional `rng`
argument specifies a random number generator, see [Random Numbers](@ref).
The element type of the result is the same as the type of `n`.

Here, a "cyclic permutation" means that all of the elements lie within
a single cycle.  If `n > 0`, there are ``(n-1)!`` possible cyclic permutations,
which are sampled uniformly.  If `n == 0`, `randcycle` returns an empty vector.

[`randcycle!`](@ref) is an in-place variant of this function.

!!! compat "Julia 1.1"
    In Julia 1.1 and above, `randcycle` returns a vector `v` with
    `eltype(v) == typeof(n)` while in Julia 1.0 `eltype(v) == Int`.

# Examples
```jldoctest
julia> randcycle(Xoshiro(123), 6)
6-element Vector{Int64}:
 5
 4
 2
 6
 3
 1
```
"""
randcycle(r::AbstractRNG, n::T) where {T <: Integer} = randcycle!(r, Vector{T}(undef, n))
randcycle(n::Integer) = randcycle(default_rng(), n)

"""
    randcycle!([rng=default_rng(),] A::Array{<:Integer})

Construct in `A` a random cyclic permutation of length `n = length(A)`.
The optional `rng` argument specifies a random number generator, see
[Random Numbers](@ref).

Here, a "cyclic permutation" means that all of the elements lie within a single cycle.
If `A` is nonempty (`n > 0`), there are ``(n-1)!`` possible cyclic permutations,
which are sampled uniformly.  If `A` is empty, `randcycle!` leaves it unchanged.

[`randcycle`](@ref) is a variant of this function that allocates a new vector.

# Examples
```jldoctest
julia> randcycle!(Xoshiro(123), Vector{Int}(undef, 6))
6-element Vector{Int64}:
 5
 4
 2
 6
 3
 1
```
"""
function randcycle!(r::AbstractRNG, a::Array{<:Integer})
    # keep it consistent with `shuffle!` and `randperm!` if possible
    n = length(a)
    @assert n <= Int64(2)^52
    n == 0 && return a
    a[1] = 1
    mask = 3
    # Sattolo's algorithm:
    @inbounds for i = 2:n
        j = 1 + rand(r, ltm52(i-1, mask))
        a[i] = a[j]
        a[j] = i
        i == 1 + mask && (mask = 2 * mask + 1)
    end
    return a
end

randcycle!(a::Array{<:Integer}) = randcycle!(default_rng(), a)

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	## rand!(::BitArray) && bitrand
4
5	function rand!(rng::AbstractRNG, B::BitArray, ::SamplerType{Bool})	×
6	isempty(B) && return B	×
7	Bc = B.chunks	×
8	rand!(rng, Bc)	×
9	Bc[end] &= Base._msk_end(B)	×
10	return B	×
11	end
12
13	"""
14	bitrand([rng=default_rng()], [dims...])
15
16	Generate a `BitArray` of random boolean values.
17
18	# Examples
19	```jldoctest
20	julia> bitrand(Xoshiro(123), 10)
21	10-element BitVector:
22	0
23	1
24	0
25	1
26	0
27	1
28	0
29	0
30	1
31	1
32	```
33	"""
34	bitrand(r::AbstractRNG, dims::Dims) = rand!(r, BitArray(undef, dims))	×
35	bitrand(r::AbstractRNG, dims::Integer...) = rand!(r, BitArray(undef, convert(Dims, dims)))	×
36
37	bitrand(dims::Dims) = rand!(BitArray(undef, dims))	×
38	bitrand(dims::Integer...) = rand!(BitArray(undef, convert(Dims, dims)))	×
39
40
41	## randstring (often useful for temporary filenames/dirnames)
42
43	"""
44	randstring([rng=default_rng()], [chars], [len=8])
45
46	Create a random string of length `len`, consisting of characters from
47	`chars`, which defaults to the set of upper- and lower-case letters
48	and the digits 0-9. The optional `rng` argument specifies a random
49	number generator, see [Random Numbers](@ref).
50
51	# Examples
52	```jldoctest
53	julia> Random.seed!(3); randstring()
54	"Lxz5hUwn"
55
56	julia> randstring(Xoshiro(3), 'a':'z', 6)
57	"iyzcsm"
58
59	julia> randstring("ACGT")
60	"TGCTCCTC"
61	```
62
63	!!! note
64	`chars` can be any collection of characters, of type `Char` or
65	`UInt8` (more efficient), provided [`rand`](@ref) can randomly
66	pick characters from it.
67	"""
68	function randstring end
69
70	let b = UInt8['0':'9';'A':'Z';'a':'z']
71	global randstring
72
UNCOV 73	function randstring(r::AbstractRNG, chars=b, n::Integer=8)	×
UNCOV 74	T = eltype(chars)	×
UNCOV 75	if T === UInt8	×
UNCOV 76	str = Base._string_n(n)	×
UNCOV 77	GC.@preserve str rand!(r, UnsafeView(pointer(str), n), chars)	×
UNCOV 78	return str	×
79	else
80	v = Vector{T}(undef, n)	×
81	rand!(r, v, chars)	×
82	return String(v)	×
83	end
84	end
85
86	randstring(r::AbstractRNG, n::Integer) = randstring(r, b, n)	×
87	randstring(chars=b, n::Integer=8) = randstring(default_rng(), chars, n)	×
88	randstring(n::Integer) = randstring(default_rng(), b, n)	84✔
89	end
90
91
92	## randsubseq & randsubseq!
93
94	# Fill S (resized as needed) with a random subsequence of A, where
95	# each element of A is included in S with independent probability p.
96	# (Note that this is different from the problem of finding a random
97	# size-m subset of A where m is fixed!)
98	function randsubseq!(r::AbstractRNG, S::AbstractArray, A::AbstractArray, p::Real)	×
99	require_one_based_indexing(S, A)	×
100	0 <= p <= 1 \|\| throw(ArgumentError("probability $p not in [0,1]"))	×
101	n = length(A)	×
102	p == 1 && return copyto!(resize!(S, n), A)	×
103	empty!(S)	×
104	p == 0 && return S	×
105	nexpected = p * length(A)	×
106	sizehint!(S, round(Int,nexpected + 5*sqrt(nexpected)))	×
107	if p > 0.15 # empirical threshold for trivial O(n) algorithm to be better	×
108	for i = 1:n	×
109	rand(r) <= p && push!(S, A[i])	×
110	end	×
111	else
112	# Skip through A, in order, from each element i to the next element i+s
113	# included in S. The probability that the next included element is
114	# s==k (k > 0) is (1-p)^(k-1) * p, and hence the probability (CDF) that
115	# s is in {1,...,k} is 1-(1-p)^k = F(k). Thus, we can draw the skip s
116	# from this probability distribution via the discrete inverse-transform
117	# method: s = ceil(F^{-1}(u)) where u = rand(), which is simply
118	# s = ceil(log(rand()) / log1p(-p)).
119	# -log(rand()) is an exponential variate, so can use randexp().
120	L = -1 / log1p(-p) # L > 0	×
121	i = 0	×
122	while true	×
123	s = randexp(r) * L	×
124	s >= n - i && return S # compare before ceil to avoid overflow	×
125	push!(S, A[i += ceil(Int,s)])	×
126	end	×
127	# [This algorithm is similar in spirit to, but much simpler than,
128	# the one by Vitter for a related problem in "Faster methods for
129	# random sampling," Comm. ACM Magazine 7, 703-718 (1984).]
130	end
131	return S	×
132	end
133
134	"""
135	randsubseq!([rng=default_rng(),] S, A, p)
136
137	Like [`randsubseq`](@ref), but the results are stored in `S`
138	(which is resized as needed).
139
140	# Examples
141	```jldoctest
142	julia> S = Int64[];
143
144	julia> randsubseq!(Xoshiro(123), S, 1:8, 0.3)
145	2-element Vector{Int64}:
146	4
147	7
148
149	julia> S
150	2-element Vector{Int64}:
151	4
152	7
153	```
154	"""
155	randsubseq!(S::AbstractArray, A::AbstractArray, p::Real) = randsubseq!(default_rng(), S, A, p)	×
156
157	randsubseq(r::AbstractRNG, A::AbstractArray{T}, p::Real) where {T} =	×
158	randsubseq!(r, T[], A, p)
159
160	"""
161	randsubseq([rng=default_rng(),] A, p) -> Vector
162
163	Return a vector consisting of a random subsequence of the given array `A`, where each
164	element of `A` is included (in order) with independent probability `p`. (Complexity is
165	linear in `p*length(A)`, so this function is efficient even if `p` is small and `A` is
166	large.) Technically, this process is known as "Bernoulli sampling" of `A`.
167
168	# Examples
169	```jldoctest
170	julia> randsubseq(Xoshiro(123), 1:8, 0.3)
171	2-element Vector{Int64}:
172	4
173	7
174	```
175	"""
176	randsubseq(A::AbstractArray, p::Real) = randsubseq(default_rng(), A, p)	×
177
178
179	## rand Less Than Masked 52 bits (helper function)
180
181	"Return a sampler generating a random `Int` (masked with `mask`) in ``[0, n)``, when `n <= 2^52`."
182	ltm52(n::Int, mask::Int=nextpow(2, n)-1) = LessThan(n-1, Masked(mask, UInt52Raw(Int)))	×
183
184	## shuffle & shuffle!
185
186	"""
187	shuffle!([rng=default_rng(),] v::AbstractArray)
188
189	In-place version of [`shuffle`](@ref): randomly permute `v` in-place,
190	optionally supplying the random-number generator `rng`.
191
192	# Examples
193	```jldoctest
194	julia> shuffle!(Xoshiro(123), Vector(1:10))
195	10-element Vector{Int64}:
196	5
197	4
198	2
199	3
200	6
201	10
202	8
203	1
204	9
205	7
206	```
207	"""
208	function shuffle!(r::AbstractRNG, a::AbstractArray)	×
209	# keep it consistent with `randperm!` and `randcycle!` if possible
210	require_one_based_indexing(a)	×
211	n = length(a)	×
212	@assert n <= Int64(2)^52	×
213	n == 0 && return a	×
214	mask = 3	×
215	@inbounds for i = 2:n	×
216	j = 1 + rand(r, ltm52(i, mask))	×
217	a[i], a[j] = a[j], a[i]	×
218	i == 1 + mask && (mask = 2 * mask + 1)	×
219	end	×
220	return a	×
221	end
222
223	function shuffle!(r::AbstractRNG, a::AbstractArray{Bool})	×
224	old_count = count(a)	×
225	len = length(a)	×
226	uncommon_value = 2old_count <= len	×
227	fuel = uncommon_value ? old_count : len - old_count	×
228	fuel == 0 && return a	×
229	a .= !uncommon_value	×
230	while fuel > 0	×
231	k = rand(r, eachindex(a))	×
232	fuel -= a[k] != uncommon_value	×
233	a[k] = uncommon_value	×
234	end	×
235	a	×
236	end
237
238	shuffle!(a::AbstractArray) = shuffle!(default_rng(), a)	×
239
240	"""
241	shuffle([rng=default_rng(),] v::AbstractArray)
242
243	Return a randomly permuted copy of `v`. The optional `rng` argument specifies a random
244	number generator (see [Random Numbers](@ref)).
245	To permute `v` in-place, see [`shuffle!`](@ref). To obtain randomly permuted
246	indices, see [`randperm`](@ref).
247
248	# Examples
249	```jldoctest
250	julia> shuffle(Xoshiro(123), Vector(1:10))
251	10-element Vector{Int64}:
252	5
253	4
254	2
255	3
256	6
257	10
258	8
259	1
260	9
261	7
262	```
263	"""
264	shuffle(r::AbstractRNG, a::AbstractArray) = shuffle!(r, copymutable(a))	×
265	shuffle(a::AbstractArray) = shuffle(default_rng(), a)	×
266
267	shuffle(r::AbstractRNG, a::Base.OneTo) = randperm(r, last(a))	×
268
269	## randperm & randperm!
270
271	"""
272	randperm([rng=default_rng(),] n::Integer)
273
274	Construct a random permutation of length `n`. The optional `rng`
275	argument specifies a random number generator (see [Random
276	Numbers](@ref)). The element type of the result is the same as the type
277	of `n`.
278
279	To randomly permute an arbitrary vector, see [`shuffle`](@ref) or
280	[`shuffle!`](@ref).
281
282	!!! compat "Julia 1.1"
283	In Julia 1.1 `randperm` returns a vector `v` with `eltype(v) == typeof(n)`
284	while in Julia 1.0 `eltype(v) == Int`.
285
286	# Examples
287	```jldoctest
288	julia> randperm(Xoshiro(123), 4)
289	4-element Vector{Int64}:
290	1
291	4
292	2
293	3
294	```
295	"""
296	randperm(r::AbstractRNG, n::T) where {T <: Integer} = randperm!(r, Vector{T}(undef, n))	×
297	randperm(n::Integer) = randperm(default_rng(), n)	×
298
299	"""
300	randperm!([rng=default_rng(),] A::Array{<:Integer})
301
302	Construct in `A` a random permutation of length `length(A)`. The
303	optional `rng` argument specifies a random number generator (see
304	[Random Numbers](@ref)). To randomly permute an arbitrary vector, see
305	[`shuffle`](@ref) or [`shuffle!`](@ref).
306
307	# Examples
308	```jldoctest
309	julia> randperm!(Xoshiro(123), Vector{Int}(undef, 4))
310	4-element Vector{Int64}:
311	1
312	4
313	2
314	3
315	```
316	"""
317	function randperm!(r::AbstractRNG, a::Array{<:Integer})	×
318	# keep it consistent with `shuffle!` and `randcycle!` if possible
319	n = length(a)	×
320	@assert n <= Int64(2)^52	×
321	n == 0 && return a	×
322	a[1] = 1	×
323	mask = 3	×
324	@inbounds for i = 2:n	×
325	j = 1 + rand(r, ltm52(i, mask))	×
326	if i != j # a[i] is undef (and could be #undef)	×
327	a[i] = a[j]	×
328	end
329	a[j] = i	×
330	i == 1 + mask && (mask = 2 * mask + 1)	×
331	end	×
332	return a	×
333	end
334
335	randperm!(a::Array{<:Integer}) = randperm!(default_rng(), a)	×
336
337
338	## randcycle & randcycle!
339
340	"""
341	randcycle([rng=default_rng(),] n::Integer)
342
343	Construct a random cyclic permutation of length `n`. The optional `rng`
344	argument specifies a random number generator, see [Random Numbers](@ref).
345	The element type of the result is the same as the type of `n`.
346
347	Here, a "cyclic permutation" means that all of the elements lie within
348	a single cycle. If `n > 0`, there are ``(n-1)!`` possible cyclic permutations,
349	which are sampled uniformly. If `n == 0`, `randcycle` returns an empty vector.
350
351	[`randcycle!`](@ref) is an in-place variant of this function.
352
353	!!! compat "Julia 1.1"
354	In Julia 1.1 and above, `randcycle` returns a vector `v` with
355	`eltype(v) == typeof(n)` while in Julia 1.0 `eltype(v) == Int`.
356
357	# Examples
358	```jldoctest
359	julia> randcycle(Xoshiro(123), 6)
360	6-element Vector{Int64}:
361	5
362	4
363	2
364	6
365	3
366	1
367	```
368	"""
369	randcycle(r::AbstractRNG, n::T) where {T <: Integer} = randcycle!(r, Vector{T}(undef, n))	×
370	randcycle(n::Integer) = randcycle(default_rng(), n)	×
371
372	"""
373	randcycle!([rng=default_rng(),] A::Array{<:Integer})
374
375	Construct in `A` a random cyclic permutation of length `n = length(A)`.
376	The optional `rng` argument specifies a random number generator, see
377	[Random Numbers](@ref).
378
379	Here, a "cyclic permutation" means that all of the elements lie within a single cycle.
380	If `A` is nonempty (`n > 0`), there are ``(n-1)!`` possible cyclic permutations,
381	which are sampled uniformly. If `A` is empty, `randcycle!` leaves it unchanged.
382
383	[`randcycle`](@ref) is a variant of this function that allocates a new vector.
384
385	# Examples
386	```jldoctest
387	julia> randcycle!(Xoshiro(123), Vector{Int}(undef, 6))
388	6-element Vector{Int64}:
389	5
390	4
391	2
392	6
393	3
394	1
395	```
396	"""
397	function randcycle!(r::AbstractRNG, a::Array{<:Integer})	×
398	# keep it consistent with `shuffle!` and `randperm!` if possible
399	n = length(a)	×
400	@assert n <= Int64(2)^52	×
401	n == 0 && return a	×
402	a[1] = 1	×
403	mask = 3	×
404	# Sattolo's algorithm:
405	@inbounds for i = 2:n	×
406	j = 1 + rand(r, ltm52(i-1, mask))	×
407	a[i] = a[j]	×
408	a[j] = i	×
409	i == 1 + mask && (mask = 2 * mask + 1)	×
410	end	×
411	return a	×
412	end
413
414	randcycle!(a::Array{<:Integer}) = randcycle!(default_rng(), a)	×

JuliaLang / julia / #37999

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous