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