根据权重(宽度)从列表选取元素的算法是否有标准名称?
该权重区间匹配算法的通用名称是什么?
我有如下算法,以下是其简化版的类Rust伪代码:
fn foo<T>(elements: list<T>, weights: list<float>, offset: float) -> Option<T> { for i in 0..elements.length() { offset -= weights[i]; if (offset <= 0) { return Some(elements[i]); } } return None; }
简单来说,给定elements=["a", "b", "c"]和weights=[1, 3, 2],可将元素按权重作为宽度排列在一维轴上形成区域,offset为轴上的点,选取该点所在区域对应的元素:
![元素["a", "b", "c"]以权重[1, 3, 2]排列在轴上的示意图](https://i.sstatic.net/OQLpJ.png)
预期结果如下:
foo(elements, weights, 0.9) == Some("a") foo(elements, weights, 1.2) == Some("b") foo(elements, weights, 2.5) == Some("b") foo(elements, weights, 4.0) == Some("c") foo(elements, weights, 5.0) == Some("c")
即当offset在[0.0, 1.0)区间时返回"a",在[1.0, 4.0)区间时返回"b",在[4.0, 6.0)区间时返回"c",其他情况返回None。
这是一种常见的基础算法,我认为它应该有一个标准名称,但我并不知晓,也未能在网上搜索到。请问该算法是否有通用名称?
这个算法最常用的称呼是前缀和区间查找(Prefix Sum Interval Lookup),如果用于基于权重的随机抽样场景,它的核心逻辑就是轮盘赌选择法(Roulette Wheel Selection)的核心查找步骤——轮盘赌选择通常会先计算前缀和数组,再通过生成的随机值匹配对应区间,你写的实现就是该查找过程的直接落地。另外,在部分场景中它也被叫做权重区间匹配算法。
内容的提问来源于stack exchange,提问作者Slavfox
相关产品推荐
相关产品推荐

