8

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

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

    Set<Coordinate> toSearch = new LinkedHashSet<Coordinate>();
    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 (ガベージ コレクション) への影響が最も少なく、最も高速に実行される可能性が最も高いでしょうか?

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

質問 (上からの繰り返し):

  1. toArray() と iterator() のどちらの手法が、GC (ガベージ コレクション) への影響が最も少なく、最も高速に実行される可能性が最も高いでしょうか?
  2. 渡される Set の実装がわからない場合 (HashSet または LinkedHashSet が最も可能性が高いと仮定)、 toArray() および iterator() メソッドのそれぞれでどのくらいのオーバーヘッドが発生しますか?
4

5 に答える 5

9

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

于 2010-12-04T23:57:19.467 に答える
1

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

private Set<Coordinate> floodFill(Value value, Coordinate start) {
    Set<Coordinate> result = new LinkedHashSet<Coordinate>();
    LinkedList<Coordinate> toSearch = new LinkedList<Coordinate>();
    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. LinkedListforを使用するtoSearchということは、要素を取得して一度に削除する簡単な方法があることを意味します。
  3. を使用する場合と比較して、をSet.add(...)返すという事実を使用してboolean、セット内のルックアップの数を取得できます。resultSet.contains()
  4. 塗りつぶしによって座標が追加された順序を知る必要がない限り、結果HashSetよりも使用する方がよいでしょう。LinkedHashSet
  5. ==インスタンスを比較するために使用することValueは、潜在的に少し危険です。
于 2010-12-05T13:28:06.757 に答える
1

私が見ることができるものから、あなたは幅優先検索を行っています

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

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

    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)時間でcontainsメソッドの問題を解決します。

乾杯

于 2010-12-05T00:11:01.893 に答える
0

Petro の応答の後、私はメソッドをコピーし、彼の提案に従って再実装しました。次のようになります。

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

    Queue<Coordinate> toSearch = new LinkedList<Coordinate>();
    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() メソッドの実装が、回答を返す前に内容の完全なスキャンを実行している可能性があることを懸念しています。それで、この方法を私が最初に投稿した方法と比較すると、どちらがより効率的である可能性が高いでしょうか (経験的なテストにかなりの時間を費やす前に)?

于 2010-12-05T01:10:56.917 に答える
0

以下は、toArray()[]-vs-interator().next() 競合を完全に排除することを含む、(主に Stephen、Cameron、Petro からの) フィードバックを取り入れた私の最新の実装です。そして、何が起こっているのか、なぜ起こっているのかをより正確に区別するために、コメントを散りばめました。また、Petro の最初の「トラッキング セットを使用する」というアドバイス (Cameron の支持) を具体的に実装した理由をより明確にするために。コード スニペットの直後に、他の提案されたソリューションと対比します。

private Set<Coordinate> floodFind3(Coordinate coordinate)
{
    Set<Coordinate> area = new LinkedHashSet<Coordinate>(); //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<Coordinate> checked = new LinkedHashSet<Coordinate>(); //every coordinate evaluated regardless of value
    checked.add(coordinate);
    Queue<Coordinate> candidates = new LinkedList<Coordinate>(); //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. 「is value」テストの前に「既に評価されているかどうかを確認する」テストの順序を変更して、すべての座標を 1 回だけ訪問するようにしました。これにより、隣接する !value 座標を複数回再訪することを回避できます。また、Stephen による Set add() メソッドの巧妙な二重使用も組み込まれています。これは、氾濫する領域がより迷路のようになる (蛇のような/クモのような) ようになると、非常に重要になります。
  4. 参照比較を強制する値をチェックするために「==」を保持しました。値は Java 1.5 Enum として定義されており、HotSpot に依存して .equals() メソッド呼び出しをインライン化し、それを参照比較に減らしたくありませんでした。Value が Enum から変更された場合、この選択は私を苦しめる可能性があります。これを指摘してくれた Stephen への Tyvm。

Petro と Stephan のソリューションは、value を含む座標を 1 回だけ訪れますが、!value を含む座標を 2 回以上再訪する必要があります。「長い迷路のようなトンネル」は病的なケースと見なされるかもしれませんが、この方法が必要な特定のドメインのより典型的なケースです。そして、私の「2番目」の試みた解決策（LinkedListのcontains（）呼び出しのパフォーマンスが低かった）は、本当の答えとして疑問でした（その答えについてStephenに{うなずきます）。

フィードバックをお寄せいただきありがとうございます。

次は、数億回の呼び出しにわたる単一のバリエーション/変更による多くの実証的テストです。今週末、この回答を詳細で更新します。

于 2010-12-07T04:54:51.783 に答える