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

Question

如果我们有一个Map<T, Integer>,假设整数值代表"有多少"Ts.因此,我想根据其Integer值统一选择T. 如果地图包含"a"= 4且"b"= 6的字符串,那么我想要它,以便选择40%的时间"a"并选择60%的时间"b".

最重要的是,我在O(n)中喜欢这个,在我之前的例子中,n是两个(不是十个).我最初创建了一个包含键的ArrayList,它包含了多少个值(并且只返回任何随机索引),但是这个过程不仅非常慢,而且对于Map<T, Integer>代表的内容完全违反直觉.

Answer 1

很抱歉延迟,但我认为我有一个相对优雅的解决方案,包括O(n lg n)施工时间和O(lg n)取随机元素时间.开始.

WeightedProbMap: 此类实现随机元素生成器.它是基于一个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. 取消注释中的一行或两elts.add(...)行Test.java.

2. 编译:

   $ javac Pair.java WeightedProbMap.java Test.java

3. 运行(例如,在Unix中):

   $ java Test | grep "Hello" | 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(): A SortedMap按键顺序存储其数据,这样可以便宜地提供地图子集的"视图".特别是这条线

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

仅返回this.elts严格小于的键的原始map()视图index.此操作(headMap)是恒定时间:view需要O(1)时间来构建,如果您this.elts稍后要更改,则更改也会反映出来view.

一旦我们创建了view少于随机数的所有内容,我们现在只需找到该子集中的最大密钥.我们这样做SortedMap.lastKey(),对于a TreeMap,应该花\Theta(lg n)时间.

Answer 2

在这里。

我想出了一个优雅的解决方案！对于任何误解：我最初的想法是通过 ArrayList 中的值的数量来存储所有键，完全忽视了使用 Map 来存储“使用整数的键实例”的意义；任何类似的解决方案都会适得其反！假设地图是无序的，这是我的解决方案：

public T randomPick(Random r) {

        int randomValue = r.nextInt(size());
        int currentSum = 0;
        T lastElement = null;

        for (T t : map.keySet()){
            if (randomValue < currentSum + map.get(t)){
                return t;
            }
            currentSum+= map.get(t);
            lastElement = t;
        }
        return lastElement;
    }

它将random value与 a进行比较current sum + the current element's value。如果小于该值，我们返回当前密钥。否则，继续并将该值添加到总和中。如果是这样的情况，随机值永远不会小于任何值，我们返回lastElement.

希望这能解决问题。