Java(1.5以降)で、Setから(任意の)要素を取得するための最良の実行方法は何ですか?

iterator java performance set toarray
Java(1.5以降)で、Setから(任意の)要素を取得するための最良の実行方法は何ですか?

以下のコードでは、toSearchから任意の要素を取得する必要がありました。 Setの単一の(ランダムですが、ランダムである必要はありません)メンバーを返すSetインターフェイス定義で便利なメソッドを見つけることができませんでした。 そこで、* toArray()[0] *テクニックを使用しました(以下のコードにあります)。

private Set floodFill(Value value, Coordinate coordinateStart)
{
    Set result = new LinkedHashSet();

    Set toSearch = new LinkedHashSet();
    toSearch.add(coordinateStart);
    while (toSearch.size() > 0)
    {
        Coordinate coordinate = (Coordinate)toSearch.toArray()[0];
        result.add(coordinate);
        toSearch.remove(coordinate);
        for (Coordinate coordinateAdjacent: getAdjacentCoordinates(coordinate))
        {
            if (this.query.getCoordinateValue(coordinateAdjacent) == value)
            {
                if (!result.contains(coordinateAdjacent))
                {
                    toSearch.add(coordinateAdjacent);
                }
            }
        }
    }

    return result;
}

私が議論した他のテクニックは、「(Coordinate)toSearch.toArray()[0] *」を「 toSearch.iterator()。next()*」に置き換えることです。 toArray()とiterator()のどちらの手法が、GC(ガベージコレクション)の影響を最小限に抑えて最も速く実行される可能性が最も高いでしょうか?

(この質問を構成した後の)私の直感では、イテレーターを使用する2番目の手法は、実行が高速で、GCのオーバーヘッドが低くなります。 渡されるSetの実装がわからない場合(HashSetまたはLinkedHashSetが最も可能性が高いと想定)、toArray()またはiterator()メソッドのそれぞれでオーバーヘッドが発生しますか? これに関する洞察は大歓迎です。

質問(上記から繰り返される):

  1. toArray()とiterator()のどちらの手法が最も可能性が高いか
    GC(ガベージコレクション)の影響を最小限に抑えて最も迅速に実行しますか?

  2. 渡されるSetの実装がわからない場合
    (最も可能性の高いHashSetまたはLinkedHashSetを想定)、toArray()およびiterator()メソッドのそれぞれでどのくらいのオーバーヘッドが発生しますか?

  8  1


ベストアンサー

`toSearch.iterator()。next()`はデータをコピーする必要がないため、より高速でメモリ消費が少なくなります。一方、 `toArray`はセットの内容を配列に割り当ててコピーします。 これは、実際の実装とは無関係です。`toArray`は、常にデータをコピーする必要があります。

9


あなたがやっていることを私が見ることができるものからhttp://en.wikipedia.org/wiki/Breadth-first_search[Breadth First Search]

以下は、toArrayを使用せずに実装する方法の例です。

    private Set floodFill(Value value, Coordinate coordinateStart) {
    final Set visitedCoordinates = new LinkedHashSet();
    final Deque deque = new ArrayDeque();

    deque.push(coordinateStart);

    while (!deque.isEmpty()) {
        final Coordinate currentVertex = deque.poll();
        visitedCoordinates.add(currentVertex);
        for (Coordinate coordinateAdjacent : getAdjacentCoordinates(currentVertex)) {
            if (this.query.getCoordinateValue(coordinateAdjacent) == value) {
                if (!visitedCoordinates.contains(coordinateAdjacent)) {
                    deque.add(coordinateAdjacent);
                }
            }
        }
    }

    return visitedCoordinates;
}

実施上の注意:

_
そして今、私は、LinkedListでのcontains()メソッドの実装が、回答を返す前にコンテンツのフルスキャンを実行しているのではないかと心配しています。
_

フルスキャン(別名線形検索)については正しいです。 それにもかかわらず、あなたの場合、既に訪れた頂点を追跡するための追加セットを持つことが可能です(ところで、実際にはあなたの結果です!)、それはO(1)時間で包含メソッドの問題を解決します。

乾杯

1


これを実装する方法は次のとおりです。

private Set floodFill(Value value, Coordinate start) {
    Set result = new LinkedHashSet();
    LinkedList toSearch = new LinkedList();
    toSearch.add(start);
    do {
        Coordinate coordinate = toSearch.removeFirst();
        if (result.add(coordinate)) {
            for (Coordinate ajacent: getAdjacentCoordinates(coordinate)) {
                if (this.query.getCoordinateValue(adjacent) == value) {
                    toSearch.add(adjacent);
                }
            }
        }
    } while (!toSearch.isEmpty());
    return result;
}

ノート:

  1. 考えてみると、 `toSearch`データ構造は必要ありません
    一意の要素が含まれます。

  2. 「toSearch」に「LinkedList」を使用すると、単純な
    要素を取得して一度に削除するメソッド。

  3. `Set.add(…​)`が `boolean`を返すという事実を使用して、
    `result`セット内のルックアップの数…​ `Set.contains()`を使用した場合と比較して。

  4. LinkedHashSet`ではなく HashSet`を使用した方が良いでしょう
    結果 …​ 塗りによって座標が追加された順序を知る必要がない限り。

  5. `==`を使用して `Value`インスタンスを比較するのは少し危険です。

1


Petroの応答後、メソッドをコピーし、彼の提案に従って再実装しました。 それはこのように見えます:

private Set floodFind2(Value value, Coordinate coordinateStart)
{
    Set result = new LinkedHashSet();

    Queue toSearch = new LinkedList();
    toSearch.add(coordinateStart);
    while (!toSearch.isEmpty())
    {
        Coordinate coordinate = toSearch.remove();
        result.add(coordinate);
        for (Coordinate coordinateAdjacent: getAdjacentCoordinates(coordinate))
        {
            if (getCoordinateValue(coordinateAdjacent).equals(value))
            {
                if (!result.contains(coordinateAdjacent))
                {
                    if (!toSearch.contains(coordinateAdjacent))
                    {
                        toSearch.add(coordinateAdjacent);
                    }
                }
            }
        }
    }

    return result;
}

SetからQueueに移動することで、効率の質問は、追加しなければならなかった新しい条件チェック「* if(!toSearch.contains(coordinateAdjacent))*」に移行しました。 Setインターフェースを使用して、重複を追加することを静かに止めました。 Queueインターフェイスを使用して、重複を追加していないことを確認する必要があります。

そして今、私は、LinkedListでのcontains()メソッドの実装が、回答を返す前にコンテンツのフルスキャンを実行しているのではないかと心配しています。 だから、この方法を私が最初に投稿した方法と比較すると、より効率的である可能性が高い(経験的テストを行うのに十分な時間を費やす前に)?

0


OK そして、何が起こって何が起こっているのかをより正確に区別するためにコメントを振りかけました。 そして、私が具体的にPetroのオリジナルの「トラッキングセットを使用する」アドバイス(Cameronに続く)を具体的に実装した理由をより明確にするために。 そして、コードスニペットの直後に、他の提案されたソリューションと比較します。

private Set floodFind3(Coordinate coordinate)
{
    Set area = new LinkedHashSet(); //includes only area of value (which is the same as at coordinate)

    area.add(coordinate);
    Value value = getCoordinateValue(coordinate); //value upon which to expand area
    Set checked = new LinkedHashSet(); //every coordinate evaluated regardless of value
    checked.add(coordinate);
    Queue candidates = new LinkedList(); //coordinates evaluated, were of value, and are queued to iterate through their adjacents
    candidates.add(nordinate);
    while (!candidates.isEmpty())
    {
        for (Nordinate coordinateAdjacent: this.query.getNordinates().getAdjacent(candidates.remove()).getOrthogonal())
        {
            if (checked.add(coordinateAdjacent)) //only expands containing value and !value
            {
                if (getCoordinateValue(coordinateAdjacent) == value)
                {
                    area.add(coordinateAdjacent); //only expands containing value
                    candidates.add(coordinateAdjacent); //expands and contracts containing value
                }
            }
        }
    }

    return area;
}

メソッドをいくつかの重要な方法で更新しました。

  1. メソッドパラメーターが1つ少ない:派生可能であったため、パラメーターを削除しました
    検索から、開始座標が!valueを含む場所を指しているという論理的な問題を排除しました。

  2. 3つのコレクションが検索を追跡します。エリア(設定)、チェック(設定)および
    候補(キュー)。 コードのコメントは、それぞれの特定の用途を明確にします。 LinkedHashSetを使用して、バグやパフォーマンスの問題を追跡しながら信頼性の高い再現性を実現しました(http://stackoverflow.com/questions/2704597/iteration-order-of-hashset)。 安定したら、より高速なHashSet実装に戻ります。

  3. 「既に評価済みかどうかを確認する」テストの順序を「
    値」テストでは、すべての座標を1回だけ訪問します。 これにより、!value隣接座標を複数回再確認する必要がなくなります。 また、Step addのSet add()メソッドの巧妙な二重使用も取り入れました。 これは、洪水のエリアが迷路のようになる(蛇のような/くすんだ)ので、非常に重要になります。

  4. 参照比較を強制する値をチェックするために「==」を保持しました。 値
    Java 1.5列挙型として定義されており、.equals()メソッド呼び出しのインライン化と参照比較への削減の両方をHotSpotに依存したくありませんでした。 ValueがEnumから変更された場合、この選択は私に噛み付くように戻ってきます。 これを指摘してくれたStephenへのTyvm。

PetroとStephanのソリューションは、値を含む座標を1回だけアクセスしますが、!valueを含む座標を複数回再確認する必要があります。これにより、長い迷路のようなトンネルで構成されるエリアのかなりの数の重複フェッチ/値チェックが発生する可能性があります。 「長い迷路のようなトンネル」は病理学的なケースと考えられるかもしれませんが、この方法が必要な特定のドメインのより典型的なものです。 そして、私の “2番目の”試みられた解決策(LinkedList contains()呼び出しのパフォーマンスが低かった)は、本当の答えとして疑わしかった(そのためのStephenに対する\ {うなずき))。

ご意見ありがとうございます。

次に、何億もの呼び出しを経た単一のバリエーション/変更を伴う多くの実証的テスト。 今週中にこの回答を詳細に更新します。

0


タイトルとURLをコピーしました