在JavaScript中实现队列时有很多选项。一种可能的实现是使用Array,使用Array.push向队列添加元素,并使用Array.shift将其从队列中删除。另一种可能的实现是使用链接列表并添加到尾部并从头部移除。
通过对Stacks实现的测试,我已经确定Array.push和Array.pop,无论数组的大小,都比向Linked List的尾部添加或删除元素快3-5倍。因此,在JavaScript中,使用链接列表来实现堆栈是没有意义的。但我想知道,在Queue的情况下,使用Array.shift从列表前面删除元素时,从数组前面删除元素时性能有何不同?
测试在Windows 10上的Chrome v63上运行。
收集50,000个或更少的元素 Array.shift比链接列表上的等效操作慢38%-40%。
超过50,000个元素的集合 Array.shift基本上比链接列表上的等效操作慢100%。
结论和建议 即使在小型数组上,Array.shift也比链接列表慢,但是如果您只需要做一些添加或删除操作,那么性能损失可能不足以保证实现链接列表。使用数组。另一方面,如果您有超过50k元素的集合或经常添加和删除大量项目,则可能值得实现链接列表。
有趣的是,V8显然在幕后应用了一些优化以使Array.shift更快,但是这种优化似乎只适用于大小为50,000或更小的数组。看看这个基准测试,很明显:https://jsperf.com/likedlistvsarray/1