求大神帮我优化下这段随机实验的代码

刚学习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)

京ICP备17009874号-2