刚学习Julia不久，同时也是算法菜鸟，求大神指点。
这个代码模拟100000000次随机实验，每次实验从整数1~1138中不重复地随机取出514个数作为一个数组，考察这个数组是否存在长度超过14的连续子序列（即连号）。
我运行代码，发现每次长度超过14的连号出现的几率都是0，不符合理论推算结果。另外，感觉算法写得也渣，不知如何优化，求指点。
using Distributed
addprocs()
@everywhere using Random
# 求给定数组中最大连续子序列的长度
@everywhere function maxlian(v::Vector{Int})
pk = 1
nk = 1
ptemp = 0 # 递增连续子序列的长度
ntemp = 0 # 递减连续子序列的长度
for i in 2:length(v)
if v[i] - v[i - 1] == 1
pk += 1
elseif v[i] - v[i - 1] == -1
nk += 1
else
if pk > ptemp
ptemp = pk
end
if nk > ntemp
ntemp = nk
end
pk = 1
nk = 1
end
end
return max(ptemp, ntemp)
end
num = 100000000 # 实验次数
@everywhere function ishave(result)
Int(maxlian(result) >= 14) # 数组result中的最大连续子序列长度是否大于14
end
k = @distributed (+) for i = 1:num
ishave(randperm(1138)[1:514]) # 从1:1138中不重复随机采样514个数作为数组，考察其最大连续子序列长度
end
println("14连号出现频率为：", k/num)
你第一个函数逻辑有点问题，多写点测试总没错
改一下就可以用了。
using Test
function max_seq_len(v::Vector{Int})
pk = 1
nk = 1
ptemp = 0 # 递增连续子序列的长度
ntemp = 0 # 递减连续子序列的长度
for i in 2:length(v)
if v[i] - v[i - 1] == 1
pk += 1
elseif v[i] - v[i - 1] == -1
nk += 1
else
pk = 1
nk = 1
end
if pk > ptemp
ptemp = pk
end
if nk > ntemp
ntemp = nk
end
end
return max(ptemp, ntemp)
end
max_seq_len(r::UnitRange) = max_seq_len(collect(r))
@test max_seq_len(1:10) == 10
@test max_seq_len(1:500) == 500
@test max_seq_len(vcat([500], 1:100)) == 100
@test max_seq_len(vcat([500, 0], 1:100, 6)) == 101
@test max_seq_len(vcat([500, 0], 100:-1:1)) == 100
@test max_seq_len(vcat([500, 0], 100:-1:1, 0)) == 101
另外你算的理论值概率是多少，我看连续出现的长度都很短
[max_seq_len(randperm(1138)[1:514]) for i=1:1000_000] |> maximum 一般就个位数
1 个赞
谢谢您的回复和指点，让我受到很大启发！
我昨晚躺着想了一下，发现跟理论推算出现差异的原因是没有对randper(1138)[1:514])进行排序。
另外，关于计算数组的最长连续子序列，我今早在Leetcode上发现了相关的代码，受益很大。
把代码更改如下：
using Distributed
addprocs()
@everywhere using Random
# 求给定数组中最大连续子序列的长度
@everywhere function longestConSq(v::Vector)
sort!(v)
longest = 1
current_length = 1
for i in 2:length(v)
if v[i] == v[i-1] + 1
current_length += 1
else
longest = max(longest, current_length)
current_length = 1
end
end
return max(longest, current_length)
end
num = 200000000 # 实验次数
@everywhere function ishave(result, n)
Int(longestConSq(result) >= n) # 数组result中的最大连续子序列长度是否大于14
end
k1 = @time @distributed (+) for i = 1:num
ishave(randperm(1138)[1:514], 14) # 从1:1138中不重复随机采样514个数作为数组，考察其最大连续子序列长度
end
println("14连号出现频率为：", k1/num)
k2 = @time @distributed (+) for i = 1:num
ishave(randperm(5141)[1:124], 6) # 从1:5141中不重复随机采样124个数作为数组，考察其最大连续子序列长度
end
println("6连号出现频率为：", k2/num)
输出结果为：
690.084621 seconds (1.43 M allocations: 72.773 MiB, 0.00% gc time)
14连号出现频率为：0.00830153
1304.065988 seconds (94.15 k allocations: 4.568 MiB)
6连号出现频率为：9.2e-7
这是来自《统计之美——人工智能时代的科学思维》第1.2.2节 “6连号和14连号“的一个实验。对应着 武汉经济适用房的6连号事件和老河口的14连号事件。
Julia的并行计算真是很强大！
谢谢！！！
另外，我将Leetcode上求解最长连续子序列的代码改成Julia，也在这里放出来供大家参考：
using Random
function longestConSq1(v::Vector{Int})
longest = 0
for num in v
current_num = num
current_length = 1
while current_num + 1 in v
current_num += 1
current_length += 1
end
longest = max(longest, current_length)
end
return longest
end
function longestConSq2(v::Vector)
sort!(v)
longest = 1
current_length = 1
for i in 2:length(v)
if v[i] == v[i-1] + 1
current_length += 1
else
longest = max(longest, current_length)
current_length = 1
end
end
return max(longest, current_length)
end
function longestConSq3(v::Vector)
longest = 0
for num in v
if ! in(num-1, v)
current_num = num
current_length = 1
while in(current_num + 1, v)
current_num += 1
current_length += 1
end
longest = max(longest, current_length)
end
end
return longest
end
arr = randperm(100000)[1:50000]
@time longestConSq1(arr)
@time longestConSq2(arr)
@time longestConSq3(arr)
运行结果为：
1.273514 seconds (11.68 k allocations: 548.685 KiB)
0.012754 seconds (22.15 k allocations: 1.177 MiB)
1.279665 seconds (16.04 k allocations: 742.550 KiB)