说我有y不同的值,我想x随机选择它们.这样做的有效算法是什么？我可以打电话给rand() x时间,但如果很大x,表现会很差y.
请注意,此处需要组合:每个值应具有相同的概率,但结果中的顺序并不重要.当然,任何生成排列的算法都是合格的,但我想知道如果没有随机顺序要求,是否可以更有效地做到这一点.
如何有效地生成0和上限N之间的K个非重复整数的列表,涵盖了这种情况的排列.
我有一大块内存,比如256 KiB或更长.我想计算整个块中的1位数,或者换句话说:为所有字节添加"种群计数"值.
我知道AVX-512有一个VPOPCNTDQ指令,它计算512位向量中每个连续64位的1位数,而IIANM应该可以在每个周期发出其中一个(如果一个适当的SIMD向量寄存器是可用) - 但我没有任何编写SIMD代码的经验(我更像是一个GPU人).此外,我不是100%确定AVX-512目标的编译器支持.
在大多数CPU上,仍然没有(完全)支持AVX-512; 但AVX-2广泛可用.我无法找到类似于VPOPCNTDQ的低于512位的向量化指令,所以即使理论上我也不确定如何使用支持AVX-2的CPU快速计算位数; 也许这样的事情存在,我只是错过了它？
无论如何,对于两个指令集中的每一个,我都很欣赏一个简短的C/C++函数 - 使用一些内部包装库或内联汇编.签名是
uint64_t count_bits(void* ptr, size_t size);
笔记: