0

我需要找到最有效的方法来从最流行的类别中找到随机元素

从

4 Cheese
1 Olive
2 Mushroom
4 Ham
2 Chicken
4 Salad

我想要要么Cheese要么。如果有多个顶级类别，我不在乎我会从哪个类别中获得我的物品。HamSalad

在输入上我有Iterator<Foo>whereFoo实现

Interface Foo {
    int getCategory();
}

我当前的代码如下所示：

Foo getItem(Iterator<Foo> it) {
    Map<Integer, List<Foo>> categoryMap = new HashMap<Integer, List<Foo>>();
    while(it.hasNext()) {
        Foo foo = it.next();
        int category = foo.getCategory();

        List<Foo> l = categoryMap.get(category);
        if(l == null) {
            l = new ArrayList<Foo>();
            categoryMap.put(category, l);
        }

        l.add(foo);
    }

    int longest_list_size = 0;
    int longest_category_id = -1;

    Set<Integer> categories = categoryMap.keySet()

    for(Integer c:  categories ) {
        int list_size = categoryMap.get(c).size();
        if(list_size  > longest_list_size) {
           longest_list_size = list_size;
           longest_category_id = c;
        }
    }

    if(longest_list_size == 0)
        return null;

    int r = new Random().nextInt(longest_list_size);
    return categoryMap.get(c).get(r);
}
4

3 回答 3

1

拥有两张地图可能更快：

Foo getItem(Iterator<Foo> it) {
    Map<Integer, Foo> categoryToFoo = new HashMap<Integer, Foo>();
    Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
    int maxCount = 0;
    while(it.hasNext()) {
        Foo foo = it.next();
        int category = foo.getCategory();
        int categoryCount = 1;
        if ( ! categoryToFoo.contains( category ) ) {
            categoryToFoo.put( category, foo );
        }
        else {
            categoryCount = counts.get( category ) + 1;
        }
        counts.put( category, categoryCount );
        if ( categoryCount > maxCount ) {
            maxCount = categoryCount;
        }
    }

    List<Foo> possible = new ArrayList<Foo>()
    for ( Map.Entry entry : counts.entrySet() ) {
        if ( entry.getValue() == maxCount ) {
            possible.add( categoryToFoo.get( entry.getKey() ) );
        }
    }

    return possible.get( new Random().nextInt( possible.size() ) );
}

你可以在很多地方做进一步的优化，但你明白了。

于 2011-11-19T18:53:03.270 回答
1

这是我要做的：

  1. 创建一个List<Foo>从it
  2. 按类别对列表进行排序
  3. 从头开始遍历列表并存储相同类别的最长间隔的开始和结束索引
  4. 在开始和结束索引之间选择一个随机元素

我认为使用更少的代码会更快一些，但您的解决方案也很好。

如果您真的很关心性能，因为it可能有数百万个元素，那么您首先不应该使用它Iterator。在这种情况下，您可能应该将每个类别的流行度存储在一个Map中，并将相同项目的列表存储在另一个中Map，但我对其余代码一无所知。

于 2011-11-19T18:53:52.430 回答
1

好吧，实际上很难（如果不是不可能的话）改进你的方法，至少在复杂性方面是这样。我们来分析一下。你在做

  1. 插入地图 -> O(N)
  2. 计算最大值 -> O(N)

总计：O(N)

其他方法：

  1. 优先队列 -> O(N*log(N)) 插入所有元素 + O(1) 检索头部
  2. 按键排序初始映射 O(N*log(N)) + O(1) 检索第一个
  3. 如果您知道投票计数的间隔，例如 [0..K] 并且它小于或不高于 N，您可以在 O(K) + O(1) 中进行计数排序以获取最大值。

如果您只需要最大检索一次，那么您的方法就足够了，IMO。

于 2011-11-19T18:55:13.490 回答