dart - 我无法理解 Dart SDK 中算法的有效性

Question

我无法理解 Dart SDK 中算法的有效性。

这是算法(在 dart:core 中列出工厂，文件 list.dart)

factory List.from(Iterable other, { bool growable: true }) {
    List<E> list = new List<E>();
    for (E e in other) {
      list.add(e);
    }
    if (growable) return list;
    int length = list.length;
    List<E> fixedList = new List<E>(length);
    for (int i = 0; i < length; i  ) {
      fixedList[i] = list[i];
    }
    return fixedList;
  }

如 growable是 false然后将创建两个列表。

List<E> list = new List<E>();

List<E> fixedList = new List<E>(length);

但是在这种情况下创建列表 #1 是多余的，因为它是 Iterable other 的副本。 .它只会浪费 CPU 时间和内存。

在这种情况下，该算法将更有效，因为它不会创建不必要的列表 #1( growable 是 false)。

factory List.from(Iterable other, { bool growable: true }) {
    if(growable) {
      List<E> list = new List<E>();
      for (E e in other) {
        list.add(e);
      }
      return list;
    }        

    List<E> fixedList = new List<E>(other.length);
    var i = 0;
    for (E e in other) {
      fixedList[i++] = e;
    }
    return fixedList;
  }

还是我错了，错过了一些编程的微妙之处？

Answer 1

我们通常避免调用 length迭代器上的 setter/getter ，因为它可以具有线性性能和副作用。例如:

List list = [1, 2, 3];
Iterable iterable1 = list.map((x) {
  print(x);
  return x + 1;
});
Iterable iterable2 = iterable1.where((x) => x > 2);
var fixedList = new List.from(iterable2, growable: false);

如 List.from调用了 length getter 它将遍历所有元素两次( where 不缓存其结果)。它将进一步执行副作用(打印 1、2、3)两次。有关可迭代的更多信息，请查看 here .

最终我们要改变 List.from代码，以便我们避免第二次分配和复制。为此，我们需要将可增长列表转换为固定长度列表的(内部)功能。跟踪错误: http://dartbug.com/9459