sorting - 为什么Dart的默认排序实现击败了我的键排序器？

Question

我以为我很聪明，我实现了一个排序器，该排序器不使用比较函数，该函数仅在每次迭代时重新计算比较元素的排序分数，而是计算一次分数(我称它们为键)并缓存它们。对我而言，这似乎与dart默认实现(或就此而言，也就是Java实现)相反。

无论如何，这是我的实现:

class KeySorter<V, K extends Comparable> {

  List<V> list;

  KeySorter(this.list);

  List<V> sort(K keyFn(V)) {
    Map<V, K> keys = {};
    list.sort((e1, e2) {
      var e1Key = keys.putIfAbsent(e1, () => keyFn(e1)),
          e2Key = keys.putIfAbsent(e2, () => keyFn(e2));
      return e1Key.compareTo(e2Key);
    });

    return list;
  }
}

这就是基准:
https://gist.github.com/Gregoor/547c0451c4fa527dd85c

默认实现比我的实现高出4倍。怎么了？

Answer 1

如注释中所述，仅当创建和查找缓存的时间少于从头计算结果的时间时，缓存才有意义。

您的实现还通过不必要地使用putIfAbsent来人为减慢缓存的查找速度。将其替换为初始缓存填充，然后进行直接键查找，可以将性能差异降低到仅2倍:

List<V> sort(K keyFn(V)) {
  Map<V, K> keys = {};
  list.forEach((e) => keys[e] = keyFn(e));
  list.sort((e1, e2) {
    return keys[e1].compareTo(keys[e2]);
  });

  return list;
}