为什么数组数组,更多的数据sorting比对象数组更快,在Javascript中的数据更less?

对于我在node.js中的应用程序,我必须根据某个数值(即数字级别)以降序排列数组的元素。 由于我的应用程序对性能至关重要,因此我决定构build我的数据结构,以便优化sorting。 我假设数组中每个元素所包含的数据越less,sorting的速度就越快。 为了testing我的假设,我运行了三个不同的长度为10000的数组:

编辑 :伙计们,似乎有什么东西与我原来的testing有瑕疵。 第一个testing比以下testing花费的时间要长得多。 因此,我已经修改了我的testing代码,在实际sorting之前有一个“缓冲区”sorting。 此外,为了减lesstesting本身的sorting可能导致的任何偏差,我将testing的顺序进行了固定数量的试验。 我已经修改了相应的结果。

完整的源代码在这里: 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 (aa < ba) { return -1; } else if (aa > ba) { return 1; } else { return 0; } } } 

旧testing:

经过25次试验(我知道,样本量很小,但我手动做了这一切),我平均sorting时间有以下几个时间:

  • 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
  • (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

新的testing:

经过25次试验(我知道,样本量很小,但我手动做了这一切),我平均sorting时间有以下几个时间:

  • 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
  • (4 + 4 + 4 + 5 + 5 + 4 + 4 + 4 + 4 + 5 + 5 + 4 + 5 + 5 + 5)/ 15 = 4.466ms

所以我得出了以下结论:

  • 数组数组的sorting速度快于数组对象的数组。 这很直观。
  • 出于某种原因,矛盾的是,特定元素中的更多数据导致比less数据更快的sorting(如sparseArray2与denseArray运行时所certificate的那样)。

我想知道的是:

  • 这些结论是否支持任何文档/除了我的testing之外的东西? 也就是说,我得出了正确的结论吗?
  • 为什么? 为什么数组的sorting比对象的数组sorting要快(直观上有意义,但是如果有的话,这个解释是什么)? 不仅如此,为什么包含更多数据的数组似乎比包含更less数据的数组sorting更快?

而且,请注意,我并没有娶这些结论或任何东西。 样本量很小,我的testing已经certificate是有缺陷的,所以我的结果可能只是testing不当的结果。 另外,似乎有很多因素,我没有意识到这可能会影响结果(正如Ryan O'Hara在我以前的文章中指出的那样)。 这篇文章的重点是要发现任何基于事实的解释sorting行为在Javascript中。

谢谢阅读!

Solutions Collecting From Web of "为什么数组数组,更多的数据sorting比对象数组更快,在Javascript中的数据更less?"

这些结论是否支持任何文档/除了我的testing之外的东西? 也就是说,我得出了正确的结论吗?

实现.sort()的具体细节并不是任何规范所要求的,因此.sort()的性能方面只能通过在浏览器或感兴趣的JS实现中testing有趣的数据集来进行性能testing。 几乎所有的性能问题都可以通过在对您很重要的特定情况下进行testing来得到最好的回答 除此之外的概括很容易引起误解或错误,并不一定适用于所有configuration。

为什么? 为什么数组的sorting比对象的数组sorting要快(直观上有意义,但是如果有的话,这个解释是什么)? 不仅如此,为什么包含更多数据的数组似乎比包含更less数据的数组sorting更快?

具有自定义比较函数的给定types的性能将由以下项目来pipe理:

  1. 数组的长度。 较长的数组将需要更多的sorting比较。
  2. 内部sortingalgorithm的智能,以尽可能减lesssorting比较的数量
  3. 自定义sorting函数的性能(执行给定sorting比较需要多长时间)。

所以,如果你保存自定义sorting函数和.sort()实现你使用的常量和数组中的数据常量,那么较长的数组将需要更长的时间来sorting。

但是,如果你从一个数组中sorting数组到一个特定的属性值对数组进行sorting,就像你正在做的那样,同时改变上面的1和3(一个在一个有利的方向,另一个在一个不太有利的方向) ,那么三angular洲的速度将取决于净变化是正面的还是负面的,这取决于在一个非常具体的实现和数据集以及很多testing之外很难预测的几件事情(换句话说,办法)。

有关对数组进行sorting的一些testing信息,还是从对象数组中sorting属性,请参阅http://jsperf.com/sort-value-vs-property 。 毫不奇怪,对数字sorting虽然不是很多,但稍微快一点。

我相信这与JavaScript中的sorting方式有关。 如果没有提供比较函数,则在sorting之前将数字转换为string ,这需要一些时间。