码农群里吹水的时候，有位前端在群里发了一道题目，说是鹅厂的面试题，要求用 JavaScript 实现。

写个函数实现

输入 [1,2,3]
返回 [1,2,2,3,3,3]

当输入是 [1,2,3,...10000] 的时候，保证性能，要怎么实现。

这题目乍一看好像没什么难度的样子，不就是跑个循环的事儿么，凭什么能够成为面试题呢？

但凡这种题目，无外乎在时间复杂度或者空间复杂度两个方向来优化。
两个循环这件事儿似乎没想到什么好办法来优化了，直觉上这题目是在考 JS 的坑。

搜索 “JavaScript 数组 底层实现”，果然不出所料，这里有坑。

JavaScript 的 Array 是个万能的结构，可数组，可栈，可队列，可字典。
这么万能，就决定了它的底层绝不简单。

大部分语言的数组，其实就是一段连续的内存空间，里面连续排列着各个数值。

但是这种结构并不能简单的实现 JavaScript 的 Array 所具备的万能功能，于是 JS 使用了一个较为复杂的机制来处理 Array 的实现，具体细节可以找一些文章来参考：

• 你所不知道的JavaScript数组 - 作者：小胡子哥 ( Barret Lee )
• Diving deep into JavaScript array – evolution & performance - Paul Shan
• [译] 深入 JavaScript 数组：进化与性能 - 文蔺

当然，更具体的实现可能需要去翻下 Chrome 或者 ff 的源码了，这里先不折腾。
从前面的资料中其实已经可以看到，JS 的 Array ，在某些情况下，很可能会退化为链表结构，而链表的遍历性能是惨不忍睹的。

好了，开始做题，其实不怎么会 JS，就用最朴素的写法：

// 生成测试数据
var qarr = new Array(10000)
for (var i = 1; i <= 10000; i++) {qarr[i-1] = i;}

console.time("All time");
var sum = 0;
for (var i = 0; i < qarr.length; i++) {
    sum += qarr[i];
}
var arr = new Array(sum);
var now = 0;
for (var i = 1; i <= qarr.length; i++) {
    for (var j = 1; j <= i; j++) {
        arr[now] = i;
        now += 1;
    }
}
console.timeEnd("All time");

执行的时候果然卡了一小下，执行时长 All time: 1857.407958984375ms

那么，如何优化呢？其实前面的参考文章里已经提到，类型化数组（Typed Arrays） 是可以开辟连续的内存空间的，那么简单修改一下代码试试看：

// 生成测试数据
var qarr = new Uint16Array(10000)
for (var i = 1; i <= 10000; i++) {qarr[i-1] = i;}

console.time("All time");
var sum = 0;
for (var i = 0; i < qarr.length; i++) {
    sum += qarr[i];
}
var arr = new Uint16Array(sum);
var now = 0;
for (var i = 1; i <= qarr.length; i++) {
    for (var j = 1; j <= i; j++) {
        arr[now] = i;
        now += 1;
    }
}
console.timeEnd("All time");

其实只做了非常简单的修改，把 new Array() 改成了 new Uint16Array() 就完了。
这时候再看看执行时长：All time: 163.51611328125ms

结论：
这道题目如果用其它语言来实现，简直就是 easy 级别，因为语言本身的数组就是连续的（当然，如果你非要用LinkedArray我也没话说）。

在我看来，这简直就是出题人的恶趣味，纯粹就是在吐槽 JavaScript 的 Array 实现，