java - 如何在 O(n) 时间内根据其在 Map 中的 Integer 值相对于其他值随机选择一个键？

Question

如果我们有一个 Map<T, Integer> ，假设 Integer 值表示“有多少”T。因此，我想根据它的 Integer 值统一选择一个 T。如果 map 包含“a”=4 和“b”=6 的字符串，那么我希望它有 40% 的时间选择“a”，60% 的时间选择“b”。

最重要的是，我希望在 O(n) 中做到这一点，在我之前的示例中 n 是二(而不是十)。我最初制作了一个 ArrayList，其中包含键的数量(并简单地返回任何随机索引)，但这个过程不仅非常慢，而且对于 Map<T, Integer> 的内容来说完全违反直觉。代表。

Answer 1

抱歉延迟，但我认为我有一个相对优雅的解决方案，O(n lg n) 构造时间和 O(lg n) fetch-a-随机元素时间。开始吧。

---

加权概率图:此类实现随机元素生成器。它是基于一个Iterable构建的；请参阅下面的 Test.java。

import java.util.Random;
import java.util.SortedMap;
import java.util.TreeMap;

class WeightedProbMap<EltType>  {
    private SortedMap<Integer, EltType> elts = new TreeMap<Integer, EltType>();
    private Random rand = new Random();
    private int sum = 0;

    // assume: each weight is > 0; there is at least one element;
    //         elements should not be repeated
    // ensure: this.elts maps cumulative weights to elements;
    //         this.sum is the total weight
    public WeightedProbMap(Iterable<Pair<Integer, EltType>> weights) {
        for (Pair<Integer, EltType> e : weights) {
            this.elts.put(this.sum, e.second);
            this.sum += e.first;
        }
    }

    // assume: this was initialized properly (cf. constructor req)
    // ensure: return an EltType with relative probability proportional
    //         to its associated weight
    public EltType nextElt() {
        int index = this.rand.nextInt(this.sum) + 1;
        SortedMap<Integer, EltType> view = this.elts.headMap(index);
        return view.get(view.lastKey());
    }
}

---

Pair.java:只是一个简单的 Pair 类。

class Pair<X, Y> {
    public Pair(X x, Y y) {
        first = x;
        second = y;
    }

    X first;
    Y second;
}

---

Test.java:这是用于 WeightedProbMap (WPM) 类的非常简单的测试工具。我们构建一个具有相关权重的元素的 ArrayList，使用它来构建 WPM，然后从 WPM 中获取 10,000 个样本以查看元素是否以预期的频率出现。

import java.util.ArrayList;

class Test {
    public static void main(String argc[]) {
        ArrayList<Pair<Integer, String> > elts = new ArrayList<Pair<Integer, String>>();
        elts.add(new Pair<Integer, String>(20, "Hello"));
        // elts.add(new Pair<Integer, String>(70, "World"));
        // elts.add(new Pair<Integer, String>(10, "Ohai"));

        WeightedProbMap<String> wpm = new WeightedProbMap<String>(elts);

        for (int i = 0; i < 10000; ++i) {
            System.out.println(wpm.nextElt());
        }
    }
}

---

测试这个:

1. 取消注释 Test.java 中的一个或两个 elts.add(...) 行。

2. 编译:

   $ javac Pair.java WeightedProbMap.java Test.java

3. 运行方式(例如，在 Unix 中):

   $ java 测试 | grep“你好” | wc -l

这将为您提供该特定执行的计数。

---

解释:

构造函数:WeightedProbMap (WPM) 类使用 java.util.SortedMap将累积权重映射到元素。图形说明:

The constructor takes weights...     ...and creates a mapping from the
      3 +---+                            number line:
        |   | 
  2 +---+   +---+ 2                   0      2         5      7
    |   |   |   |                     +------+---------+------+
    |   |   |   |                     |   X  |    Y    |   Z  |
  --+---+---+---+--                   +------+---------+------+
      X   Y   Z

nextElt():SortedMap 按键顺序存储其数据，这允许它廉价地提供 map 子集的“ View ”。特别是这条线

SortedMap<Integer, EltType> view = this.elts.headMap(index)

返回原始 map (this.elts) 的 View ，其中仅包含严格小于 index 的键。此操作 ( headMap) 是常数时间:view 需要 O(1) 时间来构建，如果您要更改 this.elts 稍后，更改也会反射(reflect)在 view 中。

一旦我们创建了小于随机数的所有内容的 View ，我们现在只需要找到该子集中的最大键。我们使用 SortedMap.lastKey() 来做到这一点，对于 TreeMap，它应该花费 \Theta(lg n) 时间。