0

最も人気のあるカテゴリからランダムな要素を見つけるための最も効率的な方法を見つける必要があります

から

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

CheeseまたはHamまたはのいずれかが必要Saladです。上位のカテゴリが複数ある場合は、どのカテゴリからアイテムを取得するかは関係ありません。

私が持っている入力についてはIterator<Foo>、Foo

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

おそらく2つのマップがある方が速いでしょう：

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、そもそもこれを使用しないでください。この場合、各カテゴリの人気を1つ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）でカウントソートを実行して最大値を取得できます。

最大の検索を1回だけ行う必要がある場合は、IMOの方法で十分です。

于 2011-11-19T18:55:13.490 に答える