STL中partial_sum算法的实际用途是什么/在哪里？
还有一些其他有趣/非平凡的例子或用例？
假设你有三个"选项" A,B和C.
您的算法必须选择并返回一个随机的算法.为此,将它们放入数组{A,B,C}并生成随机数(0,1或2)非常简单,该数字将是要返回的数组中元素的索引.
现在,这个算法有一个变化:假设A被选中的几率为40%,B20%和C40%.如果是这种情况,您可以采用类似的方法:生成数组{A,A,B,C,C}并使用随机数(0,1,2,3,4)来选择要返回的元素.
这样可行.但是,我觉得这是非常低效的.想象一下,将此算法用于大量选项.您将创建一个有点大的数组,可能有100个元素,每个元素代表1%.现在,这仍然不是很大,但假设你的算法每秒使用很多次,这可能会很麻烦.
我考虑过创建一个名为class的类Slot,它有两个属性:.value和.size.为每个选项创建一个插槽,其中.value属性是选项的值,并且该插槽.size等于数组中此类选项的出现次数.然后生成一个从0到总发生次数的随机数,并检查该数字落在哪个插槽上.
我更关心算法,但这是我对此的Ruby尝试:
class Slot
attr_accessor :value
attr_accessor :size
def initialize(value,size)
@value = value
@size = size
end
end
def picker(options)
slots = []
totalSize = 0
options.each do |value,size|
slots << Slot.new(value,size)
totalSize += size
end
pick = rand(totalSize)
currentStack = 0
slots.each do |slot|
if (pick <= …我正在寻找一个可以有偏见的随机数发生器.例如,假设我想要1-5之间的随机数,概率为:
1:上升20%的时间
2:上升10%的时间
3:上升40%的时间
4:上升25%的时间
5:上升5%的时间
标准库或其他库中是否有可以执行此操作的内容？或者,有没有一种有效的方法来做到这一点？
以下示例(ideone)在Windows 7上使用Visual Studio 2013时编译和工作,但在Ubuntu 13.10上不使用g ++ 4.8.1.
#include <cassert>
#include <cstdlib>
#include <array>
#include <iostream>
#include <numeric>
#include <utility>
// Wraps a std::array of TKey/TValue pairs and provides a method
// to randomly select a TKey with TValue bias.
template< typename TKey, typename TValue, std::size_t TSize >
class weights final
{
public:
using pair = const std::pair< const TKey, const TValue >;
using array = const std::array< pair, TSize >;
weights( array values )
: values_{ values } …我有一套物品。我需要随机挑选一个。问题是它们每个的权重都是1-10。权重为 2 意味着该商品被挑选的可能性是权重为 1 的两倍。权重为 3 则意味着该商品被挑选的可能性是权重的三倍。
我目前用每个项目填充一个数组。如果权重为 3，我将该项目的三个副本放入数组中。然后，我随机选择一个项目。
我的方法速度很快，但占用大量内存。我试图想出一种更快的方法，但什么也没想到。有人有解决这个问题的窍门吗？
编辑：我的代码...
显然，我没说清楚。我不想使用（或改进）我的代码。这就是我所做的。
//Given an array $a where $a[0] is an item name and $a[1] is the weight from 1 to 100.
$b = array();
foreach($a as $t)
$b = array_merge($b, array_fill(0,$t[1],$t));
$item = $b[array_rand($b)];
这要求我检查 $a 中的每个项目，并为数组使用 $a 内存的 max_weight/2*size 。我想要一个完全不同的算法。
此外，我在半夜用电话问了这个问题。在手机上输入代码几乎是不可能的，因为那些愚蠢的虚拟键盘简直太糟糕了。它会自动更正所有内容，破坏我输入的任何代码。
此外，我今天早上醒来时发现了一种全新的算法，该算法几乎不使用任何额外的内存，并且不需要检查数组中的每个项目。我将其作为答案发布在下面。
我需要对我用C++编写的我的俄罗斯方块游戏提供一些帮助,这是我的问题:
俄罗斯方块块列表有7种类型:{'我','J','L','S','Z','O','T'}
并且我需要选择上述字符中的一个,使得S和Z以每个概率1/12被选择,并且其他块以每个概率1/6被选择.
根据这些概率生成块的最佳方法是什么？
我想生成一个接近于零且具有一定范围的数字.例如,假设我要的号码落在下的时间为10 90%,但有一个小的机会,这将是15,20年甚至30数越高,接受它的机会越低.
我已经尝试用关键字"加权概率"寻找一些东西但找不到任何导致正确方向的东西.
更新:
我最终使用了Box-Muller变换(见接受的答案).这是我写的简单代码:
const E = 2.71828183;
function getRandomCurvedValue(temp.median, temp.density) {
return this.getCurvedValue(random(0, 1), temp.median, temp.density);
}
function getCurvedValue(temp.value, temp.median, temp.density) {
return temp.median + (temp.density * log(E, (temp.value / (1 - temp.value))));
}
如果有一个数字N确定达到更高数字或更低数字的可能性,你将如何实现从区间1..1000返回随机数的函数？
它应该表现如下:例如
很明显,生成的数字将为给定的N特定曲线创建.您能告诉我如何实现这一目标以及我可以创建哪些曲线？我有什么可能吗？你如何限制正面和负面因素等
谢谢你的帮助
我的代码花了40%的时间来搜索未分类的向量.更具体地,搜索功能my_search重复地接收单个未分类的长度矢量N,其中N可以取10到100,000之间的任何值.与每个元素相关联的权重具有相对小的方差(例如[0.8,0.81,0.85,0.78,0.8,0.7,0.84,0.82,...]).
该算法my_search首先对每个对象的所有权重求和,然后N用替换样本计算元素的平均值(与向量的长度一样多).该算法非常类似于
int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
if(rnd < choice_weight[i])
return i;
rnd -= choice_weight[i];
}
从这篇文章.
我可以在搜索之前对矢量进行排序,但是需要O(N log N)的顺序(取决于所使用的排序算法)并且我怀疑(但可能是错误的,因为我没有尝试过)我会获得很多时间特别是因为权重几乎没有变化.
另一种解决方案是存储在一系列点之前有多少重量的信息.例如,在对矢量求和时,每N/10个元素,我可以存储已经总和了多少权重的信息.然后,我可以首先与rnd这10个断点进行比较,并仅搜索向量总长度的十分之一.
N？