性能与内存：列表

Question

什么方法更好？

假设我们有一个名为mainClass的类，它具有一个包含List<Foo>foos和List<BigClass>的成员变量。 Foo本身具有一个List<Boo>。

如果目标是为了能够获得foos中所有元素的Boo。那么，是将另一个List<Boo>保存在BigClass中，并在用户将新的Foo插入foos时，插入相应的Boo元素，比较好？

还是说每次用户请求此列表时，从BigClass内生成整个Boo列表更好？

主要问题在于，你必须在性能和内存之间做出选择。

PS. 对不起，标题过于宽泛，我无法准确描述这个问题。

- Koen Demonie

---

使用最容易理解的方法。这是首要考虑的问题。不要担心性能或内存，除非出现问题，因为可能不会出现。 - Mike Dunlavey

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - JB Nizet

@MikeDunlavey，如果你每次遇到问题都要搜索那些可以释放更多内存或提高性能的函数，这种方法不是很“慢”、“冗余”吗？ - Koen Demonie

@Koen：我已经编程半个世纪了 - 那我知道什么呢？首先要做对。然后，如果有问题，修复问题。如果你想知道我如何找到性能问题，这里有一个视频[here]（https://www.youtube.com/channel/UCGwyNGICQ4RHmcYcQIG9gxw），以及许多在线讨论。 - Mike Dunlavey

@KoenDemonie 即使做得正确，维护仍然更加困难。代码不断演进。实现复杂的解决方案以获得几毫秒的优势，当简单的解决方案已经足够快时，这并不是一个好主意。 - JB Nizet

Answer 1

您可以使用单一实现来同时实现这两种行为。只需在mainClass中创建自己的List实现（可能是一个名为FooList的内部类，或者甚至是一个匿名内部类）。让FooList的方法以透明的方式将所有单独的Foo列表呈现为单个列表。例如，FooList.iterator()的实现将透明地依次在每个单独的Foo列表上实例化一个迭代器，以便它看起来像是在遍历一个大的列表。

- Peter Headland

Answer 2

如果您需要获取所有Boo并且还要保持Boo分组（即属于某个Foo的Boo），那么我建议最好返回一个视图，其中包含BigClass中包含的所有Boo，无论它们属于哪个Foo。

要实现这一点，您可以使用Google Guava Iterables或Java 8 Stream.flatMap()，具体取决于您的Java版本。

使用Google Guava：

class BigClass {

    List<Foo> foos = new LinkedList<Foo>();

    public Iterable<Boo> allBoos() {
        return Iterables.concat(this.foos);
    }
}

class Boo {
    final int a;

    Boo(int a) {
        this.a = a;
    }

    @Override
    public String toString() {
        return String.valueOf(this.a);
    }
}

class Foo
    implements Iterable<Boo> {

    List<Boo> boos = new LinkedList<Boo>();

    @Override
    public Iterator<Boo> iterator() {
        return this.boos.iterator();
    }
}

public class Sample {
    public static void main(String[] args) {

        Boo b1 = new Boo(1);
        Boo b3 = new Boo(3);
        Boo b5 = new Boo(5);

        Boo b2 = new Boo(2);
        Boo b4 = new Boo(4);
        Boo b6 = new Boo(6);

        Foo odd = new Foo();
        odd.boos.addAll(Arrays.asList(b1, b3, b5));

        Foo even = new Foo();
        even.boos.addAll(Arrays.asList(b2, b4, b6));

        BigClass b = new BigClass();
        b.foos.add(odd);
        b.foos.add(even);

        System.out.println(b.allBoos()); // [1, 3, 5, 2, 4, 6]
    }
}

这种方法的最大优点是Guava返回的Iterable是惰性的，这意味着不会创建任何新的集合或列表，并填充任何元素。相反，返回的Iterable是一个视图，其Iterator从第一个Iterable中消耗元素，当用尽时，“跳转”到下一个Iterable并消耗其元素，然后“跳转”到下一个，依此类推，直到消耗掉最后一个Iterable的最后一个元素。

使用Java 8：

class BigClass {

    List<Foo> foos = new LinkedList<Foo>();

    public Iterable<Boo> allBoos() {
        Stream<Boo> s = this.foos.stream().flatMap(
            f -> f.getBoos().stream());
        return s::iterator;
    }
}

class Boo {
    final int a;

    Boo(int a) {
        this.a = a;
    }

    @Override
    public String toString() {
        return String.valueOf(this.a);
    }
}

class Foo {

    List<Boo> boos = new LinkedList<Boo>();

    public List<Boo> getBoos() {
        return this.boos;
    }
}

public class Sample {
    public static void main(String[] args) {

        Boo b1 = new Boo(1);
        Boo b3 = new Boo(3);
        Boo b5 = new Boo(5);

        Boo b2 = new Boo(2);
        Boo b4 = new Boo(4);
        Boo b6 = new Boo(6);

        Foo odd = new Foo();
        odd.boos.addAll(Arrays.asList(b1, b3, b5));

        Foo even = new Foo();
        even.boos.addAll(Arrays.asList(b2, b4, b6));

        BigClass b = new BigClass();
        b.foos.add(odd);
        b.foos.add(even);

        List<Boo> list = new ArrayList<>();
        b.allBoos().forEach(boo -> list.add(boo));

        System.out.println(list); // [1, 3, 5, 2, 4, 6]
    }
}

这里也适用于“懒惰”方面的考虑。

- fps

---

这看起来非常不错，因为（据我所知）它不会消耗任何额外的内存。但是，每次调用获取所有“boo”的时候，它都必须一遍又一遍地迭代，对吗？ - Koen Demonie

@Koen 不，它是一个视图。换句话说，它是每个 Foo 中所有 Boo 列表的包装器。这是一个 O(1) 操作。 - fps

@Koen 为了明确起见：当返回的 List 迭代时，元素最终被遍历。 - fps

基本上它不会消耗额外的内存，也不会显著降低性能速度吗？ - Koen Demonie

非常好。只是有点奇怪，我从来没有听说过这个……谢谢。 - Koen Demonie