我有一个问题，我需要为常量键 i(也是整数，在某些范围内，比如 [1;M])存储变化的数据值 v_i(整数)。我需要能够快速绘制一个由值 v_i 加权的随机元素，即绘制 key k 的概率应该是 v_k/(sum(i=1...M) v_i)
我能想到的最好的想法是使用二叉树，并将以 k 为根的子树中的值的部分和存储为键 k 的值(仍在 [1;M] 范围内)。然后，每当一个值发生变化时，我需要更新它的节点和树中的所有父节点(需要 O(log M) 时间，因为键是固定的，因此二叉树是完美平衡的)。如上所述绘制随机元素也需要 O(log M) 时间(对于树的每一层，将范围 (0,1) 内的随机数与左子树、右子树和右子树的相对权重进行比较节点本身)并且比朴素算法快得多(取随机数 r，遍历元素以找到最小的 k 以便 sum(i=1...k) < r, sum(i=1...k +1) > r；花费 O(M) 时间)。
我现在的问题是如何优化树节点在内存中的放置，以最大限度地减少缓存未命中。由于所有键都是已知的并且保持不变，这基本上就是我应该为树节点分配内存的顺序。
谢谢!!
最佳答案
我不认为二叉树的最佳填充顺序除了前序、后序、顺序填充之类的东西？您的问题不是询问缓存通常如何工作吗？不幸的是，我自己并不知道，也许更简单的哈希数组在您的情况下会更有效？
关于algorithm - 二叉树的最佳填充顺序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5727197/