小编Dan*_*zes的帖子

问题

我需要在不同的机器和编译器上生成相同的(伪)随机数序列.如果我使用相同的内核,似乎g ++中的mersenne twister(MT)的实现效果很好:无论我是在新机器上编译我的程序,使用g ++ 4.9或4.7,我都得到相同的随机数.但是如果我使用较旧的内核或者我改用Visual Studio的编译器,我会得到不同的.没关系,因为没有保证可以mersenne_twister_engine::seed将内部状态设置为不同的编译器.

我已经尝试过的

我认为应用于operator<<发生器会产生一个独特的结果,可以用来设置其他机器上的发生器operator>>,但是如果mt19937它似乎不起作用.为了说清楚,在计算机上AI有代码

mt19937 generator1A;
uniform_int_distribution<int> distribution(0, 1000);

cout << "Generating random numbers with seed 1000" << endl;

generator1A.seed(1000);
generator1A(); //to advance the state by one so operator>> will give a longer output; this is not necessary indeed
ofstream test("testseed1000.txt");
test << generator1A << endl;

for (int i = 0; i < 10; ++i)
    cout << distribution(generator1A) << endl;

它产生252,590,893,......和一个长文件.我将文件传输到另一台机器B,并运行以下代码:

mt19937 generator1B, generator2B;
uniform_int_distribution<int> distribution(0, 1000); …

我想提高我在分形分析中使用的盒子计数方法的速度性能.

关于任务

我有一个整数流(大约n = 2 ^ 24长),我必须计算流中有多少不同的值.没有上限,允许负值(但负值的数量可能小于sqrt(n)).流中存在小的相关性,即实际元素可能与前一个元素相等或不太远.在许多情况下,我在整个范围内有很多相等的值.

方法我已经尝试过了

矢量,排序,uniqe

我的第一个实现是将所有元素放入向量中,然后我应用std :: sort然后应用std :: unique.

这种方法的复杂性是O(n*log(n)),我认为任何其他算法在扩展时都不会更快.但我确信一个代码必须存在比这更快但具有相同的缩放属性 - 只有一个常数因子才能更快.原因是:

1. 我在向量中存储了很多相等的值,因此排序不是那么有效,向量过大
2. 在这种方法中,我不使用实际元素和前一个元素彼此接近的信息
3. 我不需要有关这些唯一值的信息,我只需要不同元素的数量

设置,插入,大小

为了消除第一个无效点,我将每个元素放入set :: insert的集合中.最后我用set :: size计算了元素的数量.

我的期望是这段代码必须更快,因为只有唯一值存储在集合中,并且它不必比较具有大量相等值的新元素.但不幸的是,这种方法比前一种方法慢1.5倍.

set,emplace_hint,size

为了消除第二个无效点,我不仅将每个元素放入一个集合中,而且使用函数set :: emplace_hint.每当一个提示将新元素放在前一个元素旁边时.最后,我用set :: size询问了set的大小

我的期望是这个代码必须比前一代码更快,因为我可以猜出新元素的价值,它总比没有好.但不幸的是,这种方法比前一种方法慢了5倍.

这个问题

您能否建议任何可以计算流中不同元素(int)数量的有效方法？如果知道的话,你能优化代码吗？

1. 数字中存在可测量的相关性
2. 有些数字是重复出现的

目标体系结构是现代x86或x86-64 PC处理器(使用sse,sse2),只有单线程代码是合适的.我不喜欢使用boost而是使用c ++ 11.

解决方案

首先,感谢许多建议,耐心和理解,我很抱歉,我无法测试所有方法,我也确信有效性取决于我没有提供的整数流的细节.但是我分享了VS2013编译器的结果.(代码在gcc4.7下测试但未测量.)这个主题值得花很多时间去研究,但我有一个符合我需求的解决方案.

关于方法:

• bool的矢量:DieterLücking的BitVector解决方案
• 二进制查找:Tony D建议的方法
• unordered set:将所有元素简单地放入std :: unordered_set,然后询问其元素的数量,如Ixanezis所示
• 矢量插入排序:使用DieterLücking的Sorted Vector方法
• set insert:我在问题表单中描述的方法
• 基数排序:Ixanezis的建议,在向量上使用流行的排序算法
• set emplace提示:使用问题表单中描述的std :: emplace_hint

我尝试使用选项C++ 14 编译代码:

#define X static_cast<double>(2)
#include <algorithm>
// if you change the two lines, no error occurs

int main()
{
    return 0;
}

但是我在X之后得到错误:

错误:预期','或'...'

我没有选择C++ 98的错误.使用我的gcc版本4.8.4,我没有得到错误,但我用5.4.0.这是一个错误吗？我做错了吗？

如果没有提供明确的种子值，Python 如何为内置随机库中使用的梅森扭曲伪随机数生成器提供种子？它以某种方式基于时钟吗？如果是，那么在导入随机模块或首次调用随机模块时是否找到了种子？

Python的文档似乎没有给出答案。

我想让访问者能够对使用 python-sphinx 从 RST 生成的 HTML 页面中的表格中的单元格进行排序。假设我有一个这样的表：

.. list-table:: A fancy name table
   :header-rows: 1
   
   * - Family name
     - Given name
   * - Smith
     - Samuel
   * - Johnson
     - John

这可以很好地呈现并按输入顺序显示名称。现在我想生成一个 HTML 输出，并为用户提供将名称重新排序为字母顺序的可能性。有独立的示例和库来实现这一点，我想知道哪种解决方案已经在 Sphinx 中实现（如果有）。最好的方法是包含一个最小的扩展并修改所有表（或只是我希望能够排序的表）的属性以包含此功能。

您能否建议扩展以及如何做到这一点的最佳实践？我更愿意自己进行尽可能少的 CSS 和 JS 代码/文件操作。