时间戳

首页 > 解决方案 > Julia 中更快的向量比较

performance - Julia 中更快的向量比较

问题描述

我尝试使用 Julia 以最快的方式构建和比较两个相同长度的 01 随机向量，每个向量具有相同数量的零和一。

这都是为了对以下概率问题进行蒙特卡罗模拟

我们有两个独立的骨灰盒，每个骨灰盒都有 n 个白球和 n 个黑球。然后我们拿一对球，每个瓮一个，每次都清空瓮。每对颜色相同的概率是多少？

我所做的是以下内容：

using Random
# Auxiliar function that compare the parity, element by element, of two 
# random vectors of length 2n
function comp(n::Int64)
  sum((shuffle!(Vector(1:2*n)) .+ shuffle!(Vector(1:2*n))).%2)
end

以上生成向量从 1 到 2n 的两个随机排列，逐个元素相加，对每个元素应用模 2，然后对剩余向量的所有值求和。然后我使用上面每个数字的奇偶性来模拟它的颜色：奇数黑白偶数。

如果最终总和为零，则两个随机向量具有相同的颜色，逐个元素。一个不同的结果表明这两个向量没有成对的颜色。

然后我设置了以下函数，它只是所需概率的蒙特卡罗模拟：

  # Here m is an optional argument that control the amount of random
  # experiments in the simulation
  function sim(n::Int64,m::Int64=24)
  # A counter for the valid cases
  x = 0
  for i in 1:2^m
    # A random pair of vectors is a valid case if they have the
    # the same parity element by element so
   if comp(n) == 0
    x += 1
   end
  end
  # The estimated value
   x/2^m
  end

现在我想知道是否有更快的方法来比较这些向量。我为随机向量尝试了以下替代构造和比较

shuffle!( repeat([0,1],n)) == shuffle!( repeat([0,1],n))

然后我相应地将代码更改为

comp(n)

通过这些更改，代码运行速度稍慢，这是我使用函数测试的@time。我所做的其他更改是将for语句更改为while语句，但计算时间保持不变。

因为我不是程序员（实际上就在昨天我学习了一些 Julia 语言，并安装了 Juno 前端），所以可能会是一种更快的方法来进行相同的计算。一些提示将受到赞赏，因为蒙特卡罗模拟的有效性取决于随机实验的数量，因此计算越快，我们可以测试的值越大。

标签： performancecomparisonjuliamontecarlo

解决方案

因此，这个问题的关键成本是shuffle!为了最大限度地提高您可以使用的模拟速度（我将其添加为答案，因为评论太长了）：

function test(n,m)
  ref = [isodd(i) for i in 1:2n]
  sum(all(view(shuffle!(ref), 1:n)) for i in 1:m) / m
end

与其他答案中提出的代码有什么区别：

  1. 您不必同时使用shuffle!两个向量；其中一个就足够了shuffle!，因为比较的结果对于两个向量在独立洗牌后的任何相同排列都是不变的；因此我们可以假设一个向量在随机排列之后被重新排序以使其trues在第一个n条目和falses最后一个n条目中都有
  2. 我shuffle!就地做（即ref向量只分配一次）
  3. 我all在向量的前半部分使用函数；这样，当我第一次点击时，检查就停止了false；如果我true在第一个n条目中全部命中，我不必检查最后一个n条目，因为我知道它们都是false所以我不必检查它们

推荐阅读