4

我有三个列表，我需要使用列表animalFilterName将Animal对象从列表animalSource移动到列表animalTarget。只有 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

为了获得更好的性能，您可能需要使用 Sets。我很确定您正在做的是 m = animalSource.size() 和 n = animalFilterName.size() 的 O(m * n) 操作，因为 ArrayLists 中的查找顺序为 n（到列表大小）

Sets 中的查找、插入和删除通常是摊销的常数时间或对数时间（到集合的大小）（取决于集合实现的细节），所以最坏的情况下，使用集合会将其减少到 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);

我认为在一行 ifs 和循环中省略换行符会使它们看起来更整洁。这是个人喜好，你不必复制我的风格。

编辑：固定时间复杂度

另一个编辑：当您说移动时，您的意思是添加到一个列表并从另一个列表中删除吗？还是您只是指添加到一个列表中？

第三次编辑：固定碎片线

于 2012-06-28T21:30:57.873 回答
1

所示算法的复杂度为 O(nxm)（由于两个嵌套循环），其中 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 回答
0

想到两件事

1）您可以制作一组过滤器并检查动物的名字是否在集合中，而不是制作过滤器列表并对其进行迭代。这在大 O 方面更好，实时是否更快取决于实际的集合大小。

2）如果您既不排序也不进行随机访问，LinkedLists 比 ArrayLists 更有效。

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 回答
0

为了尊重您在 sourceAnimal 列表中允许重复条目的事实，我建议以下内容：

添加两件事：

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 将动物名称映射到其在 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 回答