假设我有一个项目列表，每个项目都有一个重量，我想选择一个随机项目。实现这一点的最简单方法是保留项目列表和按总和排序的权重的运行总和。然后从最大权重中选择一个随机整数并进行二进制搜索以找到与随机值匹配的项目。做起来不难。
问题是有比二分搜索更优化的选择项目的方法吗？
在我的情况下，我有 50,000 个项目，并且权重的大小（整数）相似，这排除了简单地按重量时间复制项目，这使得选择一个简单的数组参考。
我不需要知道如何做到这一点我只是想知道是否有更快的算法？我可能想做很多这些，所以速度可能有用，但内存不是无限的。
在这种情况下，我使用的是 C++，但不必使用任何特定语言。