相关疑难解决方法(0)

在JavaScript中,是否可以从另一个数字生成一个随机数？

我正在尝试为我的一个分形地形生成器实现一个可预测的随机数生成器.我已经知道可以使用Math.random()生成一个随机数,但我想创建一个随机数生成器,为每个输入生成一个输出.(例如,predictableRandomGenerator(1)总是会产生相同的结果,这不一定与输入相同.)

那么是否可以从另一个数字生成一个随机数,其中每个输入的输出总是相同的？

我正在努力将MATLAB仿真移植到C++中.为此,我试图复制MATLAB的randsample()函数.我还没有想出一个有效的方法来做到这一点.

所以我问你们所有人,如何在0 + n-1(n> k)范围内随机抽样k数而不用C++替换？

我考虑过以下伪代码(受到cppreference.com上的第三个例子的启发),但我觉得它有点像hacky:

initialize vect<int> v of size n
for i = 0 to n-1
    v[i] = i
shuffle v
return v[0 to k-1]

这里的缺点也是首先要构建一个大规模阵列的要求.这似乎是缓慢/笨重的矫枉过正.

如果你能提供帮助,我会喜欢这里的方向.我对理论不太感兴趣(算法很有趣,但现在与我的需求无关),而不是在C++中实现它的最佳方法.

提前致谢!

这是Knuth乘法散列的正确实现吗？

int hash(int v)
{
    v *= 2654435761;
    return v >> 32;
}

乘法中的溢出会影响算法吗？

如何提高这种方法的性能？

在/O2(发布)模式下查看由Visual Studio(2015U2)生成的程序集时,我看到这个"手动优化"的C代码被转换回乘法:

int64_t calc(int64_t a) {
  return (a << 6) + (a << 16) - a;
}

部件:

  imul        rdx,qword ptr [a],1003Fh  

所以我想知道这是否真的比按照它的编写方式更快,类似于:

  mov         rbx,qword ptr [a]  
  mov         rax,rbx  
  shl         rax,6  
  mov         rcx,rbx  
  shl         rcx,10h  
  add         rax,rcx  
  sub         rax,rbx  

我总是觉得乘法总是比几个班次/加法慢？现代英特尔x86_64处理器不再是这种情况吗？

使用除法的散列意味着 h(k) = k mod m 。我读到了

m 不应该是 2 的幂。这是因为如果 m = 2^p，h 就变成 k 的 p 个最低位。通常我们选择 m 作为一个不太接近 2 的幂的素数。

有人可以用一个小例子来解释最低阶位部分吗？我认为所有 (mod m) 所做的就是将结果包裹在范围 m 周围。如果 m 是 2 的幂，不知何故看不到问题。

我正在构建一个应用程序，在我的一个函数中，我需要生成随机且唯一的 4 位数代码。显然，从 0000 到 9999 的范围是有限的，但每天整个列表都会被擦除，每天我都不需要超过可用数量的代码，这意味着每天都有可能有唯一的代码。实际上，我每天可能只需要几百个代码。

我现在编码的方式是简单的暴力方式，即生成一个随机的 4 位数字，检查该数字是否存在于数组中，如果存在，则生成另一个数字，如果不存在，则返回生成的数字。

由于它是 4 位数字，所以运行时间并不算太疯狂，而且我每天主要生成几百个代码，因此不会出现生成 9999 个代码并且我不断随机生成数字来查找最后一个代码的情况剩下一张。

如果可以让问题变得更容易的话，也可以在其中包含字母而不仅仅是数字。

除了我的蛮力方法之外，还有什么更有效的方法呢？

谢谢你！

我试图将大约6400万个64位唯一无符号整数散列到1.28亿个桶(27位宽地址).我尝试了Bob Jenkin的HashLittle和Murmur哈希(这些哈希函数都提供了32位哈希值,我将其屏蔽以获得27位地址).在这两种情况下,它导致大约22%的碰撞,最终只占据了37%的水桶.这是预期还是我做错了什么？我期待更少的碰撞和更好的铲斗占领.

这个问题是关于我们如何将整数与常数相乘.那么让我们看一个简单的函数:

int f(int x) {
    return 10*x;
}

如何最佳地优化该功能,尤其是在内联到呼叫者时？

方法1(由大多数优化编译器生成(例如,在Godbolt上))

    lea    (%rdi,%rdi,4), %eax
    add    %eax, %eax

方法2(使用clang3.6和更早版本,使用-O3生成)

    imul   $10, %edi, %eax

方法3(使用g ++ 6.2生成,无需优化,删除存储/重新加载)

    mov    %edi, %eax
    sal    $2, %eax
    add    %edi, %eax
    add    %eax, %eax

哪个版本最快,为什么？主要对英特尔Haswell感兴趣.

我在x86-64汇编中开发了一个程序，该程序需要通过相同的操作进行多次迭代：

IMUL rdx, 3   # rdx is always different

但是，我需要使运行时更快，因此我从上面想到了对该特定行的优化：

MOV rcx, rdx
SHL rdx, 1
ADD rdx, rcx

现在我问你们：这种修改会改善程序的运行时间（减少时钟），还是我应该坚持使用该IMUL命令？

我想要生成大量 (10 TB) 看似随机但可预测的数字。生成速度应该超过快速SSD，所以我想要3000 MB/s到4000 MB/s。

文件写入后，将再次读取数字并重新生成，以便进行比较。整个程序应该检查磁盘。

目前我正在考虑哈希。为了可预测性，要散列的数据只是一个 8 字节数字 ( ulong)。所以在二进制文件中它看起来像这样

<32 bytes of SHA256(0)> <32 bytes of SHA256(1)> ...

我不认为我可以使用带种子的随机数生成器，因为我无法告诉随机数生成器生成第n个数字。但我可以告诉 SHA256 算法计算 SHA256(n)。

我使用 SHA256 算法对 128 MB 数据进行了测试，如下所示：

Parallel.For(0, 128 * 1024 * 1024 / 32,     // 128 MB / length of the hash
    a => {
        var sha = SHA256.Create();
        sha.Initialize();
        var ba = new byte[8];
        ba[0] = (byte)((long)a >> 0 & 0xFF);
        ba[1] = (byte)((long)a >> 8 & 0xFF);
        ba[2] = (byte)((long)a …