jakewilliami
commented
3 years ago Playing around with random search implementation
Attempt One
No better than the old one, as it ignores the first point in this issue.
Base.rand(𝒰::UniverseParameters) = rand(𝒰.Σ)
Base.rand(𝒰::UniverseParameters, C::AbstractArray) = rand.((C, 𝒰.Σ, 1:𝒰.n))
function replace_if_allowed!(C::AbstractArray, d::Integer, w, w′)
for c in C
if hamming_distance(c, w′) < d
return false
end
end
replace!(C, w => w′)
return true
end
replace_if_allowed(C::AbstractArray, d::Integer, w, w′) =
replace_if_allowed!(copy(C), d, w, w′)
function mutate_codeword(w::Union{Tuple{T}, NTuple{N, T}}, n::Integer, i::Integer, a::T) where {N, T}
w̲ = collect(w)
w̲[i] = a
return ntuple(j -> w̲[j], n)
end
C = get_codewords_greedy(𝒰, d)
for _ in 1:length(C)
# set/reset counter
j = 0
# try to mutate the code so that the new word fits (try up to m times)
for _ in 1:m
# choose a random word, letter, and position in the word
w, a, i = rand(𝒰, C)
# mutate a copy of the word
w′ = mutate_codeword(w, 𝒰.n, i, a)
# try to alter the code
replace_if_allowed!(C, d, w, w′) && break
# increment counter
j += 1
# if no viable option is found for a mutation, remove the word from the code.
isequal(j, m) && filter!(e -> e ≠ w, C)
end
end
return CAttempt Two
Garden of forking paths.
# choose random starting point
init_arr = rand(𝒰.Σ, 𝒰.n)
init_word = ntuple(j -> init_arr[j], length(init_arr))
# initialise array with random word
C = [init_word]
# iterate through words
for w in 𝒰
C′ = copy(C)
# find a word that will fit
for w′ in 𝒰
push_if_allowed!(C′, w′, d)
end
next_w = rand(𝒰.Σ, 𝒰.n)
C′ = nothing
push!(C, next_w)
end
return CAttempt Three
As we were previously, but the only random is the start.
# choose random starting point
init_arr = rand(𝒰.Σ, 𝒰.n)
init_word = ntuple(j -> init_arr[j], length(init_arr))
# initialise array with random word
C = [init_word]
# iterate through words
for w in 𝒰
push_if_allowed!(C′, w′, d)
end
return CAttempt Four
I found this solution entirely by accident, while I was following up an outdated lead for what I thought might have been a solution (Random.randperm). Thank God the people over at JuliaCollections put the hard work into this one... A strange problem it was indeed. The only limitation here I can think of is another dependency (namely, IterTools).
C = Tuple[]
for _ in 1:length(𝒰)
# https://github.com/JuliaCollections/IterTools.jl/blob/master/src/IterTools.jl#L610-L689
push_if_allowed!(C, nth(𝒰, rand(1:length(𝒰))), d)
end
return CNote
I suspect I know which one we will use (the cleanest one that is using pre-built functions as part of JuliaCollections, I suspect). However, I would like to request @dmipeck to review the current options, as he was the one who suggested mutating.
Using any of these methods is still considerably slower than the memory inefficient version. For example, consider the benchmarks of (respectively) the original and the fourth implementation of the random algorithms:
julia> @btime get_codewords_random(["a", "b", "c"], 4, 2); # original
86.998 μs (1988 allocations: 97.67 KiB)
julia> @btime get_codewords_random(["a", "b", "c"], 4, 3); # "memory efficient"
12.237 ms (89790 allocations: 2.45 MiB)
julia> @btime get_codewords_random(["a", "b", "c"], 6, 3); # original
4.225 ms (130948 allocations: 8.01 MiB)
julia> @btime get_codewords_random(["a", "b", "c"], 6, 3); # "memory efficient"
1.188 s (8633499 allocations: 272.82 MiB)
julia> @btime get_codewords_random(["a", "b", "c"], 8, 3); # original
377.728 ms (10969724 allocations: 836.81 MiB)
julia> @btime get_codewords_random(["a", "b", "c"], 8, 3); # "memory efficient"
100.025 s (738611869 allocations: 25.82 GiB)
Do NOT load into memory all codewords.Completed in 9a58d23, by @dmipeck.1Redone usingIterators.productin 993ec21.1 Edited and refined in 02d911c, 2f6e6c5, 3fff9d6, and 6546206. 2
The current plan is to have a kind of mutating code. The problem with the random "algorithm" (as it were) is to balance it with the first point in this issue; we do not want to load the universe into memory.See below. 3 After the bad performance with the memory efficient iterator method, we should work as much on performance (regarding time) as we can. This does not mean we need to change the algorithm, it just means we need to be careful. Edited and refined in cebcd76, a5b8d4a, 77ee159, 37f6886, 70dbc29, and 267f501. See below.