在JavaScript中实现队列时有许多选项。一种可能的实现是使用数组,使用Array.push将元素添加到队列中,并使用Array.shift将它们从队列中移除。另一个可能的实现是使用链接列表并添加到尾部并从头部移除。
通过对堆栈实现的测试,我确定无论数组的大小如何,Array.push和Array.pop都比向链接列表的尾部添加或删除元素快3-5倍。因此,在JavaScript中,使用链接列表来实现堆栈是没有意义的。但我想知道,在队列中,使用Array.shift从数组前面删除元素与从列表前面删除元素时,性能有什么不同?
发布于 2018-01-02 16:05:25
测试在Chrome v63上运行,在Windows 10上运行。
50,000个元素或更少的集合
Array.shift比链接列表上的等效操作慢38%-40%。
50,000多个元素的集合
Array.shift基本上比链接列表上的等效操作慢100%。
结论和建议
即使是在小数组上,Array.shift也比链接列表慢,但是如果您需要做的只是到处添加或删除一些操作,那么性能影响可能还不够大,不足以保证实现链接列表。和阵列一起去。另一方面,如果您有一个超过50k元素的集合,或者经常添加和删除大量的项,那么实现一个链接列表可能是值得的。
有趣的是,V8显然在幕后应用了一些优化以使Array.shift更快,但这种优化似乎只应用于大小为50,000或更小的数组。看看这个基准测试,很明显:https://jsperf.com/likedlistvsarray/1
https://stackoverflow.com/questions/48064134
复制相似问题