0

n 個のアイテムのサブセットを共有する可能性のある m 個の入札がある場合、入札間の競合を保存し、2 つの入札が競合しているかどうか (つまり、少なくとも 1 つのアイテムを共有している) をチェックする最善の方法を見つけたいと考えています。これまでのところ、最適ではない次元 mxm の行列を試しました。私の問題には数千の入札がある可能性があるため、正方行列の実装を使用すると、「Java がメモリ領域不足です」というエラーが頻繁に発生します。次に、(元の競合行列が対称であるため) 三角行列を試してみましたが、メモリの問題を取り除くことはできませんでした!

もっと良いアイデアはありますか？

コーディングする最良の方法は？

ありがとう。

4

1 に答える 1

0

1 つの解決策は、Guava を使用して、すべての入札を含むTableと組み合わせることです。List<Bid>注: 以下のコードでは、多くの Guava の利点を使用しています。

final List<Bid> allBids = Lists.newArrayList();
final Table<Bid, Bid, Void> conflicts = HashBasedTable.create();

新しい入札を保存するときは、次のことを行います (これは、を返すメソッドがあることを前提としbidています)。.items()Set<Item>

for (final Bid bid: allBids)
    if (!Sets.intersection(newBid.items(), bid.items()).isEmpty())
        conflicts.put(newBid, bid, null);
allBids.add(newBid);

次に、2 つの入札間の競合を検出する場合:

return table.contains(bid1, bid2) || table.contains(bid2, bid1);

Void代わりに値をSet<Item>s に置き換えて、競合するアイテムを保存し、その中に結果を入れることもできますSets.intersection()。

// Table becomes Table<Bid, Bid, Set<Item>>
Sets.SetView<Item> set;
for (final Bid bid: allBids) {
    set = Sets.intersection(newBid.items(), bid.items())
    if (!set.isEmpty())
        conflicts.put(newBid, bid, set.immutableCopy());
}
allBids.add(newBid);
于 2013-07-11T09:45:38.477 に答える