49

アルゴリズムの可能な結果の組み合わせを多数計算しています。この組み合わせを並べ替えるには、double 値で評価し、PriorityQueue に保存します。現在、そのキューには約 200k のアイテムがあり、かなりメモリを消費します。実際には、リスト内のすべてのアイテムの中で最高の 1000 または 100 を言うだけで済みます。そこで、Java で固定サイズのプライオリティ キューを使用する方法があるかどうかを自問し始めました。私は次のように振る舞うべきです: そのアイテムはすでに保管されているものよりも優れていますか? はいの場合は、適切な位置に挿入し、評価が最も低い要素を捨てます。

誰にもアイデアはありますか？どうもありがとうございました!

マルコ

4

7 に答える 7

42 
que.add(d);
if (que.size() > YOUR_LIMIT)
     que.poll();

または私はあなたの質問を誤解しましたか？

編集：これを機能させるには、各サイクルで最も優先度の高いものを破棄するため、おそらく comparTo 関数を反転する必要があることに言及するのを忘れました。(a が「より良い」場合、b を比較すると (a, b) は肯定的な数値を返す必要があります。

最大数を保持する例は、次のようなものを使用します。

public int compare(Double first, Double second) {
            // keep the biggest values
            return first > second ? 1 : -1;
        }
于 2009-12-04T14:12:22.597 に答える
14

MinMaxPriorityQueue、Googleグアバ

コレクションの最大サイズを超えるアイテムを追加するときに、アイテムを比較して削除するアイテムを見つけ、それによって部屋を作成するキューを維持するためのクラスが実際にあります:バージョン 8 のGoogle GuavaMinMaxPriorityQueueで見つかりました。

EvictingQueue

ちなみに、オブジェクトの値を比較せずに最も古い要素を削除するだけの場合は、Google Guava 15 がEvictingQueueクラスを獲得しました。

于 2014-02-11T10:39:51.963 に答える
5

Apache Lucene には固定サイズの優先キューがあります: http://lucene.apache.org/java/2_4_1/api/org/apache/lucene/util/PriorityQueue.html

私のテストに基づいて優れたパフォーマンスを発揮します。

于 2009-12-04T18:37:14.320 に答える
2

poll()最小要素が現在の要素よりも小さい場合 (あなたの場合、評価が悪い場合) はキューだけです。

static <V extends Comparable<? super V>> 
PriorityQueue<V> nbest(int n, Iterable<V> valueGenerator) {
    PriorityQueue<V> values = new PriorityQueue<V>();
    for (V value : valueGenerator) {
        if (values.size() == n && value.compareTo(values.peek()) > 0)
            values.poll(); // remove least element, current is better
        if (values.size() < n) // we removed one or haven't filled up, so add
            values.add(value);
    }
    return values;
}

Comparableこれは、組み合わせを評価で比較する を実装するある種の組み合わせクラスがあることを前提としています。

編集：明確にするために、Iterable私の例では事前に入力する必要はありません。たとえば、が表すことができるIterable<Integer>すべての自然数を与える は次のとおりです。int

Iterable<Integer> naturals = new Iterable<Integer>() {
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            int current = 0;
            @Override
            public boolean hasNext() {
                return current >= 0;
            }
            @Override
            public Integer next() {
                return current++;
            }
            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
};

ご覧のとおり、メモリ消費は非常に控えめです。20 億を超える値の場合、2 つのオブジェクト (IterableとIterator) と 1 つの が必要intです。

もちろん、コードを使用しないように簡単に変更することもできますIterable。シーケンスを表すエレガントな方法であるため、これを使用しました (また、Python と C# を使いすぎていました☺)。

于 2009-12-04T12:25:58.760 に答える
2

SortedSet を使用します。

SortedSet<Item> items = new TreeSet<Item>(new Comparator<Item>(...));
...
void addItem(Item newItem) {
    if (items.size() > 100) {
         Item lowest = items.first();
         if (newItem.greaterThan(lowest)) {
             items.remove(lowest);
         }
    }

    items.add(newItem);   
}
于 2009-12-04T12:12:14.050 に答える
0

より良いアプローチは、プログラムの実行中にキューにあるものを削除したり追加したりして、キューにあるものをより厳密に管理することです。アイテムをキューに追加する前に、いくつかのアイテムを除外する余地があるようです。いわば車輪の再発明よりも簡単です。

于 2009-12-04T11:05:36.757 に答える
-1

アイテムを追加するたびにトップ 1000 を保持するのは当然のことのように思えますが、PriorityQueueそれを優雅に達成するためのものは何も提供していません。を使用する代わりにPriorityQueue、メソッドで次のようなことを行うことができます。

List<Double> list = new ArrayList<Double>();
...
list.add(newOutput);
Collections.sort(list);
list = list.subList(0, 1000);
于 2009-12-04T11:55:52.053 に答える