为什么数字数组,更多数据排序比对象数组更快,Javascript数据更少？

Question

对于我在node.js中的应用程序,我必须根据一些数值(即数字等级)按降序对数组的元素进行排序.由于我的应用程序对性能至关重要,因此我决定构建我的数据结构,以便优化排序.我假设我的数组中每个元素包含的数据越少,排序就越快.为了测试我的假设,我在三个长度为10000的不同数组上运行了以下命令:

编辑:伙计们,我的原始测试似乎有些瑕疵.第一次测试所需的时间明显长于后续测试.因此,我修改了我的测试代码,以便在实际排序之前进行"缓冲"排序.此外,我将测试的顺序轮换为固定数量的试验,以减少测试本身排序可能导致的任何偏差.我相应地修改了结果.

完整来源:https://raw.githubusercontent.com/youngrrrr/js-array-sort-bench-test/master/arraySortTest.js

var buffer = [781197, ... ];
var sparseArray = [781197, ... ];
var sparseArray2 = [{'a' : 781197}, ...];
var denseArray = [{'a' : 781197, 'b': ['r', 'a', 'n', 'd', 'o', 'm'] }, ...];

/* buffer : for some reason, the first test always takes significantly longer than the others. I've added this to try to remove whatever bias there was before... */
console.time('buffer');
random.sort(compareSparse);
console.timeEnd('buffer');
console.log(buffer[0]); // prints "58"


/* sparseArray : an array whose elements are numbers */
console.time('sparse');
sparseArray.sort(compareSparse);
console.timeEnd('sparse');
console.log(sparseArray[0]); // prints "58"

/* sparseArray2 (not an accurate name, just got lazy) :
   an array whose elements are objects with a single key-value pair mapping
   an arbitrary name 'a' to a number (which we sort on) */
console.time('sparse2');
sparseArray2.sort(compareDense);
console.timeEnd('sparse2');
console.log(sparseArray2[0]); // prints "{ a: 58 }"

/* denseArray : an array whose elements are objects with two key-value
   pairs mapping an arbitrary key 'a' to a number (which we sort on) and
   another arbitrary key 'b' to an array (which is just supposed to be 
   extra data for the purpose of my hypothesis) */
console.time('dense');
denseArray.sort(compareDense);
console.timeEnd('dense');
console.log(denseArray[0]); // prints "{ a: 58, b: [ 'r', 'a', 'n', 'd', 'o', 'm' ] }"

function compareSparse(a, b) {
    if (a < b) {
        return -1;
    } else if (a > b) {
        return 1;   }
    else {
        return 0;
    }
}

function compareDense(a, b) {
    if (a.a < b.a) {
            return -1;
        } else if (a.a > b.a) {
            return 1;   }
        else {
            return 0;
        }
    }
}

老测试:

经过25次试验(我知道,样本量很小,但我手动完成了这一切)我得到了以下平均排序时间:

• sparseArray:(24 + 23 + 21 + 23 + 21 + 22 + 22 + 22 + 22 + 22 + 21 + 20 + 22 + 24 + 24 + 21 + 22 + 22 + 25 + 23 + 24 + 23 + 21 + 21 + 23)/ 25 = 22.32ms
• sparseArray2:(4 + 4 + 4 + 4 + 4 + 5 + 5 + 5 + 5 + 4 + 6 + 5 + 5 + 4 + 5 + 4 + 4 + 4 + 5 + 6 + 4 + 5 + 4 + 4 + 5)/ 25 = 4.56ms
• denseArray:(5 + 5 + 4 + 5 + 5 + 5 + 5 + 5 + 5 + 6 + 5 + 5 + 4 + 4 + 5 + 5 + 5 + 4 + 5 + 5 + 6 + 5 + 5 + 5 + 4)/ 25 = 4.88ms

新测试:

经过25次试验(我知道,样本量很小,但我手动完成了这一切)我得到了以下平均排序时间:

• sparseArray:(4 + 4 + 4 + 4 + 3 + 4 + 4 + 4 + 4 + 4 + 4 + 4 + 3 + 4 + 4)/ 15 = 3.867ms
• sparseArray2:(4 + 4 + 4 + 6 + 5 + 4 + 4 + 4 + 4 + 5 + 5 + 4 + 5 + 5 + 5)/ 15 = 4.533ms
• denseArray:(4 + 4 + 4 + 5 + 5 + 4 + 4 + 4 + 4 + 5 + 5 + 4 + 5 + 5 + 5)/ 15 = 4.466ms

所以我得出以下结论:

• 数字数组比值为数字的对象数组排序更快.这在直觉上是有道理的.
• 出于某种原因,并且矛盾的是,特定元素中的更多数据导致比较少数据更快的排序(如sparseArray2与denseArray运行时所证明的那样).

我想知道的是:

• 这些结论是否得到了我测试以外的任何文档/其他内容的支持？那就是,我得出了正确的结论吗？
• 为什么？为什么数字数组比对象数组排序更快(直观地说,但是这背后的解释是什么,如果有的话)？不仅如此,为什么包含MORE数据的数组似乎比包含较少数据的数组排序更快？

请注意,我没有嫁给这些结论或任何东西.样本量很小,我的测试之前证明是有缺陷的,所以我的结果很可能只是测试不好的结果.此外,似乎有各种因素,我没有意识到这可能会影响结果(正如Ryan O'Hara在我之前的文章中指出的那样).这篇文章的重点是发现任何基于事实的Javascript排序行为解释.

谢谢阅读!

Answer 1

除了我的测试之外，这些结论是否有任何文档/其他内容支持？也就是说，我得出的结论是否正确？

.sort()任何规范都没有要求具体如何实现，因此.sort()只能通过对浏览器中感兴趣的数据集或感兴趣的 JS 实现进行性能测试来发现其性能方面。几乎所有性能问题都可以通过在对您重要的特定环境下进行测试来得到最好的答案。除此之外的概括很容易产生误导或错误，并且不一定适用于所有配置。

为什么？为什么数字数组的排序速度比对象数组快（直观上是有道理的，但是这背后的解释是什么（如果有的话））？不仅如此，为什么包含更多数据的数组似乎比包含更少数据的数组排序更快？

使用自定义比较函数的给定排序的性能将由以下几项决定：

1. 数组的长度。较长的数组将需要更多的排序比较。
2. 内部排序算法的智能可以尽可能减少排序比较的次数
3. 自定义排序函数的性能（执行给定排序比较需要多长时间）。

因此，如果您保留自定义排序函数和.sort()使用常量的实现以及数组常量中的数据，则较长的数组将需要更长的时间来排序。

但是，如果您同时更改上面的 1. 和 3.（一个朝有利的方向，一个朝不太有利的方向），就像您从对数字数组进行排序到按特定属性值对对象数组进行排序时所做的那样，那么速度的增量将取决于净变化是正还是负，这取决于在非常具体的实现和数据集以及大量测试之外很难预测的几件事（换句话说，它可以是方式）。

有关对数字数组进行排序与​​对对象数组中的属性进行排序的一些测试信息，请参阅http://jsperf.com/sort-value-vs-property。毫不奇怪，对数字数组进行排序会稍微快一点，尽管速度不是很多。