我有一个工作线程池,我在其中根据百分比向它们发送请求。例如,工作人员 1 必须处理总请求的 60%,工作人员 2 必须处理总请求的 31%,最后工作人员 3 必须处理 9%。我需要从数学上知道如何缩小数字并保持比率,这样我就不必向线程 1 发送 60 个请求,然后开始向工作线程 2 发送请求。这听起来像是“线性比例”数学方法。无论如何,我们感谢有关此问题的所有意见
思考这个问题的一种方法使其与在基于像素的显示器上绘制斜线的问题非常相似,这可以通过布雷森纳姆算法 http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm.
首先,为简单起见,我们假设只有 2 个工作人员,并且他们应该获取传入请求的一小部分 p(对于工作人员 1)和 (1-p)(对于工作人员 2)。想象一下,“发送到工作程序 1 的请求”是图表的水平轴,“发送到工作程序 2 的请求”是图表的垂直轴:我们想要做的是在该图表中绘制一条从 (0, 0) 并且具有斜率 (1-p)/p (即,向右每前进 p 个单位,向上前进 (1-p) 个单位)。当新的请求到来时,就会绘制一个新的像素。这个新像素将始终紧邻前一个像素的右侧(如果我们将作业分配给工作人员 1)或紧邻其上方(如果我们将其分配给工作人员 2),因此它不太像 Bresenham 的算法,其中对角线移动是有可能,但也有相似之处。
对于传入的每个新请求,我们必须将该请求分配给其中一个工作人员,对应于从前一个像素向右或向上绘制下一个像素。我建议选择正确方向的一个好方法是选择一个最小化误差函数。最简单的方法是获取 (0, 0) 与 2 个可能选择中的每一个所产生的点之间的直线的斜率,并将这些斜率与理想斜率 (1-p)/p 进行比较;然后选择产生最小差异的一个。这将导致绘制的像素尽可能接近地“跟踪”理想线。
为了将其推广到二维以上(工人),我们不能直接使用斜率。如果有W个工人,我们需要提出一些函数error(X,Y),其中X和Y都是W维向量,一个代表理想的方向(分配请求的比率,类似于前面的斜率 (1-p)/p),另一个表示候选点,并返回一些表示它们方向差异程度的数字。幸运的是,这很容易:我们可以采取两个向量之间的角度的余弦通过划分他们的点积 http://en.wikipedia.org/wiki/Dot_product#Geometric_definition通过它们的大小的乘积,这很容易计算。如果它们的方向相同,则为 1,否则小于 1,因此当新请求到达时,我们需要做的就是为每个工作人员 1
[EDIT]
这个程序也会适应理想方向的变化。但就目前情况而言,它试图(尽其所能)使迄今为止分配的每个请求的总体比率跟踪理想方向,因此如果程序运行了很长时间,那么即使目标方向进行很小的调整也可能会导致较大的“波动”以进行补偿。在这种情况下,当调用 error(X, Y[i]) 时,最好使用最新像素(请求分配)与某个 k 个(例如 k=100)步中的像素之间的差异来计算第二个参数前。 (在原始算法中,我们隐式减去起始点 (0, 0),即 k 尽可能大。)这仅需要您保留最后 k 个选择的端点。选择 k 太大意味着您仍然可以获得较大的波动,而选择 k 太小可能意味着“线”偏离路线,有些工作人员根本没有选择过,因为每个任务都会极大地改变方向。您可能需要进行实验才能找到合适的 k。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)