4

リストanimalFilterNameを使用して、リストanimalSourceからリストanimalTargetにAnimalオブジェクトを移動する必要があります。リストanimalFilterNameに存在する名前を持つ Animal のみをanimalSource からanimalTargetに移動する必要が あります。パフォーマンスに関しては、以下で行うよりも良い方法があります。今のところサンプルデータのみを使用しています。

public class Animal {

    private String name;
    private String color;

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getColor() {
        return color;
    }
    public void setColor(String color) {
        this.color = color;
    }
}


public class MoveAnimal {

    /**
     * @param args
     */
    public static void main(String[] args) {

        List<Animal> animalSource = new ArrayList<Animal>();
        List<String> animalFilterName = new ArrayList<String>();
        List<Animal> animalTarget = new ArrayList<Animal>();

        animalFilterName.add("Name1");
        animalFilterName.add("Name2");

        Animal a1 = new Animal();
        a1.setColor("Color1");
        a1.setName("Name1");

        Animal a2 = new Animal();
        a2.setColor("Color2");
        a2.setName("Name2");

        Animal a3 = new Animal();
        a3.setColor("Color1");
        a3.setName("Name3");

        Animal a4 = new Animal();
        a4.setColor("Color1");
        a4.setName("Name4");

        Animal a5 = new Animal();
        a5.setColor("Color5");
        a5.setName("Name1");


        animalSource.add(a1);
        animalSource.add(a2);
        animalSource.add(a3);
        animalSource.add(a4);
        animalSource.add(a5);


        for(String s: animalFilterName) {
            for(Animal a: animalSource) {
                if(s.equals(a.getName())) {
                    animalTarget.add(a);
                }
            }
        }

    }

}
4

4 に答える 4

1

示されたアルゴリズムの複雑さは O(nxm) (2 つの入れ子になったループのため) です。ここで、n は最初のリストの要素の数で、m はフィルターの要素の数です。

n と m の値が大きい場合のパフォーマンスを向上させるためにアルゴリズムを改善するには、フィルター リストを HashTable に変換します。

このような：

 Hashtable<String, String> animalFilterName = new Hashtable<String, String>();
 animalFilterName.put("Name1", null);
 animalFilterName.put("Name2", null);

次に、二重 for ループは次のように簡略化できます。

for (Animal a: animalSource) {
    if (animalFilterName.containsKey(a.getName())) {
        animalTarget.add(a);
    }
}

複雑さが大幅に改善されました。ハッシュテーブルとしての O(n) は、O(1) の平均として動作します。ただし、n と m の数値が大きい場合にのみ違いに気付くでしょう。

于 2012-06-28T21:44:40.123 に答える
1

パフォーマンスを向上させるには、セットを使用することをお勧めします。m = animalSource.size() および n = animalFilterName.size() に対する O(m * n) 操作であると確信しています。ArrayLists のルックアップは n 番目 (リストのサイズに対して) であるためです。

セット内のルックアップ、挿入、および削除は、通常、(セットの実装の詳細に応じて) 償却された定数時間または対数時間 (セットのサイズに応じて) のいずれかであるため、最悪の場合、セットを使用すると、これが O(m * log (n)) 同じ m と n に対して。

Set<Animal> animalSource = ...;
Set<Animal> animalTarget = ...;
Set<String> animalFilterName = ...;

// add matching animals to new set
for (Animal a : animalSource)
    if (animalFilterName.contains(a.getName())) animalTarget.add(a);

// if you need to remove them from the first set, uncomment these lines
// for (Animal a : animalTarget)
//     animalSource.remove(a);

1行のifやループで改行を省いた方が見栄えが良くなると思います。個人的な好みですので、私のスタイルを真似する必要はありません。

編集：固定時間の複雑さ

別の編集: 移動と言うとき、一方のリストに追加し、もう一方のリストから削除することを意味しますか? それとも、1 つのリストに追加するだけですか?

3 番目の編集: 断片化された行を修正

于 2012-06-28T21:30:57.873 に答える
0

sourceAnimal リストで重複するエントリを許可しているという事実を尊重するために、次のことをお勧めします。

次の 2 つを追加します。

List 型の indexList

List<List<Integer>>

sourceAnimal リストに動物のインデックスを保持します。つまり、次の sourceAnimal リストがある場合

sourceAnimal: [ 0:"rabbit", 1:"dog", 2:"cat", 3:"horse", 4:"rabbit" ]

次の（新しい）indexListがあります。

indexList: [ 0: [0, 4], 1: [1], 2:[2], 3:[3] ]

これは、最後の追加ピースである HashTable を追加すると、すべて意味があります。

HashTable は、動物名を indexList 内の対応するインデックスにマップし、実際の sourceAnimal リスト内でその動物名が出現するすべての実際のインデックスを読み取ることができます。

それにより、次のようにタスクを処理します。

// Pseudo-Code !

foreach (animal: animalFilter) {

    if (hashtable.contains(animal) {

        int superIndex = hashtable.get(animal);

        foreach (int sourceAnimalIndex : indexList[superIndex]) {

            copy sourceAnimal[sourceAnimalIndex] to targetAnimal;
        }
    }

}

}

このアプローチの利点は、反復を回避することです (ただし、上記の例のように、「ウサギ」のインデックス 0 とインデックス 4 のように乗算を取得する動物のインデックスと、フィルター処理する動物の反復を除きます)。

もちろん、データ構造を追加したり、メンテナンスのオーバーヘッドを追加したりする必要があるという欠点もあります。

しかし、sourceAnimalList に多数のアイテムを格納している場合、すべての動物のリスト全体に対する「マスター反復」を防止することは非常に効率的です。

于 2012-06-28T21:45:25.503 に答える
0

2つのことが思い浮かびます

1) フィルターのリストを作成して反復するのではなく、一連のフィルターを作成して、動物の名前がセットに含まれているかどうかを確認できます。リアルタイムで高速かどうかは、実際のコレクションのサイズによって異なります。

2) ソートもランダム アクセスも行わない場合、LinkedList は ArrayList よりも効率的です。

public static void main(String[] args) {

    List<Animal> animalSource = new LinkedList<Animal>();
    Set<String> animalFilterName = new HashSet<String>();
    List<Animal> animalTarget = new LinkedList<Animal>();

    //Set-up

    for (Animal a : animalSource) {
        if (animalFilterName.contains(a.getName())) {
            animalTarget.add(a);
        }
    }
}
于 2012-06-28T21:31:25.337 に答える