8

特定のセットをバラバラのサブセットに分割するコードを書きたいと思っています。たとえば、サッカー選手のセットを、所属するチームに応じて分割します。最後に、代表者のリスト、つまり各チームから 1 人のプレーヤーが必要です。

すべてのサッカー選手は、チームの他のすべての選手を知っています。これは、複雑さに非常に関連しています。したがって、これを行う方法に関する私の現在の考えは次のとおりです（set現在の場所は ですLinkedHashSet<T>）：

while (!set.isEmpty()) {
    E e = set.iterator().next();
    makeRepresentative(e);
    set.remove(AllPlayersOnSameTeamAs(e));
}

ただし、while ループのすべてのステップで新しい反復子を作成するのは奇妙に感じます。LinkedHashSet は、(LinkedList の動作のために) 内部で何らかのfirstElement()機能を持っているはずですが、何らかの理由でこれを行う方法が見つかりません。代わりに foreach ループも試しましたが、java.util.ConcurrentModificationException.

これを正しく行うにはどうすればよいですか？

4

2 に答える 2

1 
while (!set.isEmpty()) {    
    Collection<E> toBeRemoved = new ArrayList<E>();
    E first = set.iterator().next();
    doSomethingWith(e);
    for (E e : set) {
        if (similar(first, e)) toBeRemoved.add(e);
    }
    set.removeAll(toBeRemoved);
}

編集を読んで理解を深めた後、次の解決策をお勧めします。

Collection<E> processed = new ArrayList<E>();
for (E e1 : set) {
    boolean similar = false;
    for (E e2 : processed) {
        if (similar(e1, e2)) similar = true;
    }
    if (!similar) {
        doSomethingWith(e1);
        processed.add(e1);
    }
}
set.clear();

「類似」の定義についてこれ以上何も知らなくても、この問題は本質的に二次問題であることに注意してください。線形または準二次にする唯一の方法は、類似の要素を同じキーにハッシュする方法があった場合です。その場合、上記の 2 番目の戦略を使用できますが、processed構造と以前の類似要素をチェックする部分をより効率的に変更することができます (現在、そのステップは類似グループの数で線形であり、総要素で線形である可能性があります)。 .

さらに、準二次的なものはすべて、確実に一定以上のメモリを使用します。一定のメモリが必要な場合は、これが最善の方法です (これは間違いなく 2 次時間です)。

while (!set.isEmpty()) {
    Iterator<E> iter = set.iterator();
    E first = iter.next();
    doSomethingWith(first);
    while (iter.hasNext()) {
        if (similar(first, iter.next())) iter.remove();
    }
}

iter.remove() を使用すると、以前に発生した同時変更の問題が修正されることに注意してください。

于 2012-09-12T00:18:21.080 に答える