我以为我很聪明,我实现了一个排序器,该排序器不使用比较函数,该函数仅在每次迭代时重新计算比较元素的排序分数,而是计算一次分数(我称它们为键)并缓存它们。对我而言,这似乎与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倍。怎么了?

最佳答案

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

您的实现还通过不必要地使用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;
}

关于sorting - 为什么Dart的默认排序实现击败了我的键排序器?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/24143977/

10-12 12:23
查看更多