问题标签 [montecarlo]

我经常*发现自己需要一个具有以下属性的数据结构：

• 可以用 O(n) 中的 n 个对象数组初始化。
• 可以在 O(1) 中获得一个随机元素，在此操作之后，将拾取的元素从结构中删除。（无需更换）
• 可以在 O(p) 中撤消 p '不替换的拾取'操作
• 可以从 O(log(n)) 中的结构中删除特定对象（例如通过 id）
• 可以在 O(n) 中获取当前结构中的对象数组。

其他操作（例如插入）的复杂性（甚至可能性）并不重要。除了复杂性之外，它对于少量的 n 也应该是有效的。

谁能给我实施这种结构的指导方针？我目前实现了一个具有上述所有属性的结构，除了元素的选取需要 O(d) 和 d 过去选取的数量（因为我明确检查它是否“尚未选取”）。我可以找出允许在 O(1) 中选择的结构，但这些结构至少在其他操作之一上具有更高的复杂性。

顺便说一句：请注意，上面的 O(1) 意味着复杂性与#earlier 选择的元素无关，也与总的#elements 无关。

*在蒙特卡罗算法中（从 n 个元素的“集合”中迭代选择 p 个随机元素）。

我知道时间对于随机数生成来说是一个不安全的种子，因为它有效地减小了种子空间的大小。

但是说我不关心安全。例如，假设我正在为纸牌游戏进行蒙特卡洛模拟。但是，我确实关心尽可能接近真正的随机性。时间作为种子会影响我输出的随机性吗？在这种情况下，我认为 PRNG 的选择比种子更重要。

我正在尝试将我的数据从 XML 数据组织成字典格式。这将用于运行蒙特卡罗模拟。

下面是 XML 中的几个条目的示例：

我当前的数据集只有两个变量，类型可以是 3 中的 1 或可能的 4 离散类型。对两个变量进行硬编码不是问题，但我想开始处理具有更多变量的数据并自动执行此过程。我的目标是自动将此 XML 数据导入字典，以便以后能够进一步操作它，而无需在数组标题和变量中进行硬编码。

这是我所拥有的：

我得到一个 KeyError @thisList = masterDictionary[thisKey]

我也在尝试创建一个类来处理 xml 的其他一些元素：

然后我可以使用以下内容检查值吗：

任何和所有的帮助表示赞赏

更新

感谢约翰的帮助。缩进问题是我的草率。这是我第一次在 Stack 上发帖，只是复制/粘贴不正确。else: 之后的部分实际上缩进为 for 循环的一部分，并且该类在我的代码中缩进了四个空格——这只是一个糟糕的帖子。我会牢记大写约定。您的建议确实有效，现在使用以下命令：

产量：

这些确实是我的两个变量，并且值与顶部列出的 xml 同步。

更新 2

好吧，我以为我已经解决了这个问题，但我又粗心了，事实证明我还没有完全解决这个问题。之前的解决方案最终将所有数据写入我的两个字典键，以便我有两个相等的所有数据列表，分配给两个不同的字典键。这个想法是将不同的数据集从 XML 分配给匹配的字典键。这是当前代码：

当我输入：

两个键（'stock' 和 'inflation'）的结果是相同的：

XML 文件中有 27 件物品带有股票标签，29 件物品带有通货膨胀标签。如何使分配给字典键的每个列表仅在循环中提取特定数据？

更新 3

它似乎适用于 2 个循环，但我不知道它如何以及为什么它不能在 1 个单循环中工作。我不小心管理了这个：

我已经尝试了大量的排列以使其在一个循环中发生，但没有运气。我可以将所有数据列在两个键中——所有数据的相同数组（不是很有帮助），或者将数据正确排序到两个键的 2 个不同数组中，但只有最后一个数据条目（循环覆盖自身每次只在数组中留下一个条目）。

任何人都可以请建议执行以下操作的最佳方法吗？

我有三个变量（X、Y 和 Z）和四个组（1、2、3 和 4）。我一直在 SPSS 中使用判别函数分析来预测已知分组数据的组成员资格，以用于未来的未分组数据。

理想情况下，我希望能够对越来越多的数据子集进行随机抽样，以查看需要多少次观察才能达到所需的正确分类百分比。

但是，我知道这可能很困难。因此，我正在寻找这样做的手段。

例如，假设变量 X 对于第 1 组的平均值为 141。这个平均值可能是根据 2000 次观察计算得出的。但是，平均值可能出现在 700 次观察中。我希望能够计算出我的数据中平均水平的观察/案例数量。例如，可能从 10 次观察开始并随机重复 50 或 100 次，然后增加到 20 次观察......等等。

我知道这是蒙特卡罗测试的一种形式。我可以访问 SPSS 15、17 和 18 以及 excel。我还可以访问 minitab 15 & 16 和 amos17 并下载了“R”，但我不熟悉这些。我的经验是使用 SPSS 和 excel。我已经在 SPSS Modified from this..http://pages.infinit.net/rlevesqu/Syntax/RandomSampling/Select2CasesFromEachGroup.txt 中尝试了一些语法，但这对我来说输入子集号等仍然很耗时。

希望有人可以提供帮助。

谢谢阅读。

安迪

好的，所以我们希望我们的机器人 - roomba（漂亮的真空吸尘器）知道它在给定房间中的位置。这意味着我们有房间的地图，机器人被放置在某个地方，需要在短时间内知道它的位置。我们看到了很多算法——其中最相关的一个是用于空间机器人定位的 MCL（蒙特卡罗算法）。我们害怕它对我们来说太大了，不知道从哪里开始。我们想在 MATLAB 中编写代码。因此，如果有人知道我们可以在哪里找到代码 - 我们会非常感激。我们对算法持开放态度 - 因此，如果您有更好的算法或可能有用的东西，那就太好了。这与我们编写它的语言有关。

谢谢。里龙。

我正在编写一个程序，试图复制本文开头讨论的算法，

http://www-stat.stanford.edu/~cgates/PERSI/papers/MCMCRev.pdf

F 是从 char 到 char 的函数。假设 Pl(f) 是该函数的“合理性”度量。算法是：

从对函数的初步猜测开始，比如说 f，然后是一个新的函数 f*——

• 计算 Pl(f)。
• 通过对 f 分配给两个符号的值进行随机转置来更改为 f*。
• 计算 Pl(f*)；如果这大于 Pl(f)，则接受 f*。
• 如果没有，则掷一枚 Pl(f)/Pl(f*) 硬币；如果出现正面，接受 f*。
• 如果抛硬币出现反面，则留在 f。

我正在使用以下代码实现这一点。我正在使用 c#，但试图使其对每个人都更加简化。如果有更好的论坛请告诉我。

我的问题基本上是这看起来是否是实现该算法的最佳方法。尽管实施了这种方法，但似乎我可能会陷入一些局部最大值/局部最小值。

编辑- 这是 Transpose() 方法背后的基本内容。我使用类型为 << char, char >> 的字典/哈希表，候选函数使用它来查看任何给定的 char -> char 转换。因此，转置方法只是交换字典中指示函数行为的两个值。

请记住，使用底层字典的候选函数基本上只是：

这是计算 Pl(f) 的函数：

蒙特卡洛方法和进化算法之间有什么关系？从表面上看，它们似乎是用于解决复杂问题的不相关的模拟方法。哪种问题最适合？他们能解决同样的问题吗？两者之间有什么关系（如果有的话）？

下面的类解析一个非常大的字符串（整个文本小说）并将其分解为连续的 4 个字符的字符串，这些字符串存储为一个元组。然后可以根据计算为每个元​​组分配一个概率。我将其用作蒙特卡罗/遗传算法的一部分来训练程序仅基于语法（仅字符转换）来识别语言。

我想知道是否有更快的方法来做到这一点。查找任何给定的 4 字符元组的概率大约需要 400 毫秒。相关方法 _Probablity() 位于类的末尾。

这是与我的另一篇文章相关的计算密集型问题：计算函数的合理性的算法/蒙特卡洛方法

最终，我想将这些值存储在 4d 矩阵中。但鉴于字母表中有 26 个字母，这将是一项艰巨的任务。（26x26x26x26）。如果我只取小说的前 15000 个字符，那么性能会提高很多，但我的数据没有那么有用。

这是解析文本“源”的方法：

这是 _Probability 方法：

编辑- 我正在提供更多细节来解决问题，

1）严格来说，到目前为止我只使用过英语，但确实必须考虑不同的字母表。目前我只希望程序识别英语，类似于本文中描述的内容：http ://www-stat.stanford.edu/~cgates/PERSI/papers/MCMCRev.pdf

2）我正在计算 n <= 4 的字符元组的概率。例如，如果我正在计算字符串“that”的总概率，我会将其分解为这些独立的元组并计算每个元组的概率首先单独：

[吨][小时]

[t][h][a]

[那]

[t][h] 的权重最大，然后是 [t][h][a]，然后是 [t][h][a][t]。由于我不只是将 4 字符元组视为一个单元，因此我无法仅将文本中 [t][h][a][t] 的实例除以总数。接下来是 4 元组。

分配给每个 4 元组的值不能过拟合文本，因为偶然许多真正的英语单词可能永远不会出现在文本中，它们不应该得到不成比例的低分。强调一阶字符转换（2 元组）可以改善这个问题。移动到 3 元组，然后 4 元组只是细化了计算。

我想出了一个字典，它简单地计算元组在文本中出现的频率（类似于 Vilx 建议的），而不是重复相同的元组，这会浪费内存。这让我从每次查找约 400 毫秒到每次约 40 毫秒，这是一个相当大的改进。但是，我仍然需要研究其他一些建议。

我需要编写 MATLAB 代码，该代码将使用 Monte Carlo 在 R^5 超立方体上进行积分。当我有一个通用函数时，我有一个基本算法。但我需要集成的功能是：

∫dA

A是R^5的一个元素。

如果我有 ∫f(x)dA，那么我认为我的算法会起作用。

这是算法：

我有一个蒙特卡洛模拟器，它有一个计算函数，它在一个循环中调用了很多次（数百万次或更多次）。为了加快速度，我想将其拆分为对模拟器的多个并行线程调用。IE。如果我想总共运行 100 万次，请将其拆分为 4 - 250,000 次并行运行。每个线程都使用相同的变量名，我该如何处理才不会发生冲突？我是否必须使用不同命名的变量创建 4 个单独版本的模拟器？

我已经开始使用 Python 线程模块编写一个版本，但可以肯定变量仍然存在问题。

有什么建议么？

谢谢你的时间。

凯尔