I feel like I’ve just gone through some serious Jedi mind training so I just want to thank all the Yoda’s for providing such an amazing education. Not only the code itself but the philosophy behind it is really invaluable to someone who doesn’t know what they are doing…yet. So thank you! Just in case anyone’s understanding requires as much assistance as I did, I’m posting a walkthrough of the fastest solution (@stevengj 's neighbors5c) and the simplest solution (@RobertGregg 's neighbors6c). (Sorry it’s taking me so long to work through the code, I just saw @rocco_sprmnt21 solution and I still have to work through that one.) My intention is just to provide a reference for any novice still working through the Julia manual, but if I end up inadvertently lowering the collective Julia IQ with this post please let me know and I’ll remove it.
fast solution @stevengj 's neighbors5c
As a reminder C is a f x r array where size(C,1) is the number of permutations possible given size(C,2) entries. E.g. given 6 entries size(C,2) == 6, size(C,1) == 2^6. For benchmarking purposes C = 2^20x 20
@benchmark neighbors5c(C)
BenchmarkTools.Trial: 747 samples with 1 evaluation.
Range (min … max): 5.863 ms … 15.767 ms ┊ GC (min … max): 0.00% … 59.38%
Time (median): 6.413 ms ┊ GC (median): 0.00%
Time (mean ± σ): 6.685 ms ± 1.347 ms ┊ GC (mean ± σ): 3.99% ± 9.96%
█▇▃
▄▁▇███▄▁▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄▁▁▁▅▄▅▅▁▁▅▄▄▅▁▅▅▁▅ ▇
5.86 ms Histogram: log(frequency) by time 14 ms <
Memory estimate: 8.00 MiB, allocs estimate: 2.
function neighbors5c(C::AbstractMatrix)
firstindex(C,1) == firstindex(C,2) == 1 || throw(ArgumentError("1-based array required"))
# I may be wrong here but I think this is to check that C is a two dimensional array with
# 1 based indexing.
c = zeros(Int, size(C,1))
# This creates an array of zeros to tally the number of entries with different neighbors in
# each permutation. The values in the array will be of type Int.
# The length of the array is the number of possible permutations given n # of neighbors, i.e. size(C,1).
local j::Int
# local j declares a new local variable in this scope, regardless of whether
# there is already a variable named j in an outer scope. `::` defines j to be type Int.
for outer j in 1:4:size(C,2)-3
# unroll column loop by 4 to combine column comparisons
# generally in julia you can only shadow an existing local variable
# (i.e. create a new variable with the same name as an existing variable)
# by explicitly stating `local` as shown above.
# A for loop or comprehension iteration variable however is always a new variable.
# So even if `j` were used again it would be a new variable rather than the `j` defined above.
# "for outer" re-use's the existing local variable j as the iteration variable.
# 1:4:size(C,2)-3 counts from 1:size(C,2)-3, in increments of 4. Incidentally size(C,2) == size(C)[2]
# Because ghost columns aren't being used, he defines who is considered a neighbor in the following manner
jm1 = j > 1 ? j-1 : size(C,2)
# a ? b:c is shorthand for if a, evaluabe b otherwise c i.e.
# if j > 1 then jm1 = the neighbor on your left, if you are the first element in the array
# then j would ==1, and the neighbor to your left is the last element in the array.
jp1 = j < size(C, 2) ? j+1 : 1
# if j < number of entries, then the neighbor to the right = j + 1, for the last element in the array the neighbor to the right = the first element.
jp2 = j+2 ≤ size(C, 2) ? j+2 : j+2 - size(C, 2)
# likewise here if j+2 < = number of entries, then two players to the right = j+2,
# otherwise say you are n - 1, then 2 players to the right of you is = 1 == j + 2 - n
jp3 = j+3 ≤ size(C, 2) ? j+3 : j+3 - size(C, 2)
jp4 = j+4 ≤ size(C, 2) ? j+4 : j+4 - size(C, 2)
# @inbounds eliminates bounds checking to improve performance.
@inbounds for i = 1:size(C,1)
c1 = C[i,j] != C[i,jp1] # if j != to right neighbor, c1 == 1
c2 = C[i,jp1] != C[i,jp2] # if j's right neighbor != to his right neighbor, c2 == 1
c3 = C[i,jp2] != C[i,jp3]
c4 = C[i,jp3] != C[i,jp4]
c[i] += ((C[i,jm1] != C[i,j]) & c1) + (c1&c2) + (c2&c3) + (c3&c4)
# Here we tally all the times we have differing neighbors into the array we created above.
# `(C[i,jm1] != C[i,j])` will yield a 1 for true and 0 for false the `&` here means bitwise &.
# A bitwise & B converts A and B to binary numbers and compare the bits of each number to its counterpart
# when inputs A and B are true, output is true; otherwise output is false
# A B A & B
# -------------
# 0 | 0 | 0
# 0 | 1 | 0
# 1 | 0 | 0
# 1 | 1 | 0
# now suppose you have an array of 6 values. c1 == 1 != 2, c2 == 2 != 3, c3 == 3!=4, c4 == c4 !=5
# `(C[i,jm1] != C[i,j]& c1)` checks if the 1st element is different from the 2nd and last element i.e. 6 != 1 & 1 !=2
# likewise (c1&c2) checks 2 for different neighbors, (c2&c3) checks 3 for differing neighbors, (c3&c4) checks 4 for differing neighbors
end
end
# in the above example where size(C,2) == 6 the above loop would check values 1:4 for differing neighbors. So we still
# have to check the remaining players in the same manner as above.
for j in j+4:size(C,2)
jm1 = j > 1 ? j-1 : size(C,2)
jp1 = j < size(C, 2) ? j+1 : 1
@inbounds for i = 1:size(C,1)
c[i] += (C[i,jm1] != C[i,j]) & (C[i,j] != C[i,jp1])
end
end
return c
end
simple solution @RobertGregg 's neighbors6c. This one is very cool because it accomplishes all of the above in only three lines of code but it takes a bit longer for large n.
@benchmark neighbors6c(E)
BenchmarkTools.Trial: 110 samples with 1 evaluation.
Range (min … max): 43.807 ms … 57.498 ms ┊ GC (min … max): 0.00% … 13.07%
Time (median): 44.483 ms ┊ GC (median): 0.00%
Time (mean ± σ): 45.474 ms ± 3.067 ms ┊ GC (mean ± σ): 1.11% ± 3.62%
▁▄█▅▄
██████▁▇▆▁▁▁▁▁▁▅▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▅▁▁▁▅▁▁▁▅▅▁▁▁▅▁▁▁▁▁▁▅▁▁▅▅▁▅ ▅
43.8 ms Histogram: log(frequency) by time 57.3 ms <
Memory estimate: 13.01 MiB, allocs estimate: 16.
function neighbors6c(A)
center = 1:size(A,2)
# create an array counting the number of entries
left = circshift(center, 1)
# rotate the array 1 to the left
right = circshift(center, -1)
# rotate the array 1 to the right
return @views sum(A[:,left] .≠ A[:,center] .≠ A[:,right], dims=2)
# since the indexes are shifted this compares A[1:1] !=A[1,2] != A[1,size(A,2)]
# the `.` proceeding the `!=` indicated an element wise operator
# @stevengj has a really great post about @views here https://discourse.julialang.org/t/could-you-explain-what-are-views/17535/2
end