V8的sort实现

## 前言 相信大家对sort的这个方法并不陌生,这就是数组的排序方法,众所周知,排序可以用很多种方法实现,插入排序,冒泡排序,快速排序等等,那V8内部用的是哪一种排序方法呢? ## Array.prototype.sort sort() 方法用原地算法对数组的元素进行排序,并返回数组。默认排序顺序是在将元素转换为字符串,然后比较它们的 UTF-16 代码单元值序列时构建的。 ::: hljs-right ————MDN ::: ```js const months = ["March", "Jan", "Feb", "Dec"]; months.sort(); console.log(months); // expected output: Array ["Dec", "Feb", "Jan", "March"] const array1 = [1, 30, 4, 21, 100000]; array1.sort(); console.log(array1); // expected output: Array [1, 100000, 21, 30, 4] ``` ## V8的sort ES规范没有指明sort具体使用哪一种排序算法,查资料显示V8在7.0版本之前,如果数组小于10,那么使用插入排序,否则使用快速排序 ::: hljs-center ![image.png](http://img.nanwayan.cn/image/png/image.png) ::: 测试后快速并没有插入快,原因可能是快速排序不是稳定的排序算法。 ps:稳定算法是指不会打乱原有顺序的排序算法,比如,排序后的0,1,2,3,8,8,8,这三个8有可能之前不是这么排列的,就好比两个商品价格相同,如歌按照价格排序,在不稳定的排序算法下就有可能将原有的顺序打乱。 于是V8采用了一个混合排序的算法:TimeSort ## What is TimSort? TimSort会利用数组本身的升序和降序特性来划分数组,比如对集合{7,4,2,1,1,3,5}进行排序。发现从第一个元素开始是一个降序。那么我把集合分割成下面两个字集合。{7,4,2,1}{1,3,5}。因为降序,第5个元素1,被划入后一个集合。就是分析待排序数据,根据其本身的特点,将排序好的(不管是顺序还是逆序)子序列的分为一个个run分区,之后将一个个run通过归并排序合并。 简易实现: ```js const arr = [ 3, 12, 4, 30, 8, 26, 27, 20, 29, 5, 11, 30, 21, 24, 7, 30, 5, 8, 4, 29 ]; function merge(left,right){ let result = [],iLeft = 0,iRight = 0 while(iLeft < left.length && iRight < right.length){ if(left[iLeft] < right[iRight]){ result.push(left[iLeft++]) }else{ result.push(right[iRight++]) } } while(iLeft < left.length){ result.push(left[iLeft++]) } while(iRight < right.length){ result.push(right[iRight++]) } return result } function timeSort(arr){ if(!arr || arr.length < 2)return arr let runs = [],sortedRuns = [],newRun = [],len=arr.length for(let i=1;i<len;i++){ if(arr[i]<arr[i-1]){ runs.push(newRun) newRun = [arr[i]] }else{ newRun.push(arr[i]) } if(len-1 == i){ runs.push(newRun) break } } for(let run of runs){ sortedRuns = merge(sortedRuns,run) } return sortedRuns } const timeSort2 = "timeSort" console.time(timeSort2) console.log(timeSort(arr)) console.timeEnd(timeSort2) ``` 只是简单实现,并没有提升很多。希望以后有机会可以真正理解并写出来timsort。 ## 参考资料 - [男科一梦(再续一集)-TimSort的实现](https://mp.weixin.qq.com/s?__biz=MzI2MTY0OTg2Nw==&mid=2247483816&idx=1&sn=079af3d70efcb68efa7400f09decb59c&chksm=ea56650cdd21ec1ace7c8fd168d62feb636e4b32f9a4d90329fe479489d8e7a70e612df8920b&token=2074049324&lang=zh_CN#rd) - [timsort是什么,如何用代码实现?](https://cloud.tencent.com/developer/article/1773970) - [讲下 V8 sort 的大概思路,并手写一个 sort 的实现](https://mp.weixin.qq.com/s/zrhwCosK4fi3uCA9Gms3Lg)

南浮宫魅影

2021-04-26 14:13:19 7次观看

一个页面卡顿的原因

# 一个页面卡顿其原因有哪些呢?有什么办法锁定原因并解决卡顿? 这个问题涉及到的东西很多,是一个非常广且有深度的问题,我还记得当初面试官问我这个问题我是这么回答的: 1. 因为现在的应用都是框架开发的,一般都是单页面,所以都会使用路由来决定展示哪些组件,我们可以找到发生卡顿问题的路由,再去查看当前路由涉及到的所有组件,将组件一一注释掉,直到页面不卡顿为止,就可以判断出页面卡顿是因为哪个组件而产生的了。 2. 或者查看一下网络是否请求过多,导致数据返回太慢,适当做一些缓存。 3. 也可能是打包后的某个文件过大,导致文件没有及时下载,渲染不及时,可以拆分文件。 4. 浏览器某一帧渲染的东西太多,导致卡顿,也有可能有太多的重绘回流。 其实还有最重要的一点就是长时间卡顿也有可能是内存泄漏导致的。 ## 1.那什么是内存泄漏呢 程序中动态分配的内存由于某种原因没有释放或者无法释放,造成系统内存的浪费,导致程序运行速度减慢甚至系统崩溃的严重后果。用我自己的话来说就是,不再用到的变量没有及时回收,就有可能造成内存泄漏。 ## 2.js中的内存存储 js中内存分为栈内存和堆内存,基本数据类型的变量放在栈内存中,比如`string`,`number`,`boolean`,`null`,`undefined`,`symbol`,`bigint`。而引用类型的变量是放在堆内存中的,`object`。简单说一下因为基本数据类型一般声明他的大小就是固定的所以放在栈内存中。而引用数据类型他的大小是不固定的,比如一个对象可以新增删除属性,所以放在堆内存中。 ## 3.GC 一些变量不再使用那么他就是垃圾,如果他一直保存在内存中,最终就有可能导致内存占用过多的情况,最终就会导致程序运行速度减慢或者崩溃。所以这些垃圾应该被程序回收掉,js就引入了垃圾回收机制。 js中的垃圾回收机制是自动回收,我们不需要关心为变量分配多大的内存,也不需要关心何时去释放掉,因为js内部会自动完成这些操作。但是我们仍然需要关心内存的管理,因为如果不合理的使用内存就会导致内存泄漏。 # 4.浏览器开发者工具查看内存情况 我们系拿来看看如何使用谷歌浏览器来查看js运行时的内存情况。 打开开发者工具,找到`Performance`这一选项,有一些按钮分别是,开始录制,刷新页面,清空记录,记录可视化内存,手动触发垃圾回收等等。 还有一个`memory`选项,主要记录某段时间内页面堆内存的具体情况以及js堆内存加载时间的分配情况。 ## 5.内存泄漏的场景 首先来列举几种常见的几种场景: 1. 过度依赖闭包 2. 意外引起的全局变量 3. 遗忘的定时器 4. 没有及时移除监听的事件 接下来来介绍一下各种情况 ### 闭包 ### 全局变量 ### 定时器 ### 监听事件

南浮宫魅影

2021-04-24 17:12:37 2次观看

GC

V8 的垃圾回收策略是基于分代式垃圾回收机制。在所有垃圾回收的算法中,没有一种能胜任所有的场景。因为在我们的实际应用中,对象的生存周期长短不一,不同的算法只能针对特定的情况具有最好的效果。 因此目前的垃圾回收算法一般是按照对象的存活时间将内存进行分代,然后对不同的内存代采用不同的垃圾回收算法。 V8 的内存分代 在 V8 中主要将内存分为新生代和老生代,新生代中的对象存活时间较短,老生代中的对象存活时间较长或常驻内存,新生代中的对象有机会晋升到老生代。 新生代老生代表示 V8 堆整体的大小就是新生代的内存空间加上老生代的内存空间。在默认情况下,如果一直分配内存,在 64 位操作系统和 32 位操作系统下分别只能使用约 1.4 GB 和 0.7 GB 的大小。 对于新生代而言,在 64 位和 32 位操作系统下内存的最大值为 32MB 和 16MB;对于老生代而言,在 64 位和 32 位操作系统下内存的最大值为 1400MB 和 700MB V8 的主要垃圾回收算法 根据不同的分代,V8 在新生代中使用 Scavenge 算法进行垃圾回收,而在老生代中使用 Mark-Sweep 和 Mark-Compact 进行垃圾回收。 Scavenge 算法 Scavenge 算法是新生代中的对象进行垃圾回收的算法,其主要采用了 Cheney 算法,算法的核心思想是: 将堆一分为二,每一部分空间称为 semispace,然后采用复制的方式进行垃圾回收。在这两个 semispace 中,只有一个处于使用中,另一个处于闲置状态。处于使用中的空间称为 From 空间,处于闲置中的空间称为 To 空间。当我们在分配对象的时候,首先在 From 空间中进行分配。当进行垃圾回收的时候,检查 From 空间中的存活对象,将存活对象复制到 To 空间,而非存活对象的空间将会被释放。完成复制之后,From 空间变为 To 空间, To 空间变为 From 空间,即进行角色互换。 Scavenge 算法的优点是时间效率较高,缺点是只能利用一半的内存。由于该算法只复制存活的对象,因此对于生存周期较短的场景(新生代),存活的对象较少,非常适合应用该算法进行垃圾回收。 当一个对象在新生代中经过多次复制依然存活,它将被认为是生存周期较长的对象。这些生命周期较长的对象会被移动到老生代中,采用新的算法进行管理。对象从新生代移动到老生代称为晋升。 因此我们在将 From 空间的对象移动到 To 空间之前需要进行检查,在一定条件下需要将存活周期较长的对象移动到老生代中,也就是完成对象晋升。 对象晋升的主要条件有两个: 对象是否经历过 Scavenge 回收 在默认情况下, V8 的对象分配主要集中在 From 空间,对象从 From 复制到 To 空间的时候,会检查它的内存地址来判断该对象是否经历过一次 Scavenge 回收。如果经历过,会将该对象复制到老生代空间中;否则复制到 To 空间。 To 空间的内存占比超过 25% 当要从 From 空间复制一个对象到 To 空间的时候,如果 To 空间已经使用了超过 25%,则这个对象直接晋升到老生代空间中。 Mark-Sweep 和 Mark-Compact 对于老生代中的对象,由于存活对象占比较大,再采用 Scavenge 算法会造成两个问题: 存活对象较多,复制存活对象的效率将会很低 浪费一半的空间 因此 V8 在老生代中主要采用 Mark-Sweep 和 Mark-Compact 相结合的方法进行垃圾回收。 Mark-Sweep 实际上就是标记清除的意思,它分为标记和清除两个阶段。该算法会遍历堆中的所有对象,并标记存活的对象,在随后的清除过程中,清除未被标记的对象。可以看出 Scavenge 中只复制活着的对象,而 Mark-Sweep 中只清理死亡的对象。活对象在新生代中占较少一部分,死亡对象在老生代中占较少一部分,这是两种回收方式能高效处理的原因。 如图所示,黑色部分标记为死亡的对象。 标记清除 Mark-Sweep 算法最大的问题是,在进行一次垃圾回收之后,内存空间会出现不连续的状态。这种内存碎片会对后续的内存分配造成问题。例如我们要给一个大对象分配内存的时候,这时所有的碎片空间都无法完成此次分配,就会提前触发垃圾回收机制,而这次回收是没有必要的。 因此,为了 Mark-Sweep 解决内存碎片的问题,Mark-Compact 算法被提出来了。Mark-Compact 是标记整理的意思,是在 Mark-Sweep 的基础上演变而来的。Mark-Compact 在标记对象为死亡之后,在整理的过程中,将活的对象往一端移动,移动完成之后直接清理掉边界外的内存。 由于 Mark-Compact 需要移动对象,因此它的执行效率不可能很快,所以在取舍上, V8 主要采用 Mark-Sweep 算法,在空间不足以给从新生代中晋升过来的对象分配空间的时候才使用 Mark-Compact。 Incremental Marking 为了避免出现 JS 应用逻辑与垃圾回收器看到的不一致的情况,垃圾回收的三种基本算法都需要将应用逻辑暂停下来,待执行完回收之后再恢复应用程序的执行,这被称为”全停顿“。 在 V8 的分代式垃圾回收中,一次小垃圾回收只收集新生代,由于新生代默认配置较小,且其中存活的对象较少,所以即使它是全停顿也影响不大。但是在老生代中,空间配置较大,存活对象较多,全堆垃圾回收的标记、清理、整理等操作所造成的停顿就会较大,需要设法改善。 为了降低全堆垃圾回收带来的停顿时间,V8 采用了增量标记,也就是将原本需要一口气完成标记的过程拆分为许多小步进行,每做完一小步就让 JS 应用逻辑执行一小会,标记与应用程序交替执行直到标记完成。

南浮宫魅影

2021-04-03 19:46:55 5次观看
面试
面试题

Vue 的奇淫技巧

当我们需要导入很多组件时是不是要这么写 ```js import lineChart from "@/widgets/lineChart"; import StackedAreaChart from "@/widgets/StackedAreaChart"; import DataTable from "@/widgets/DataTable"; import BarChart from "@/widgets/BarChart"; import XyBarChart from "@/widgets/XyBarChart"; import StackBarChart from "@/widgets/StackBarChart"; import HorizontalBar from "@/widgets/horizontalBar"; import PieChart from "@/widgets/PieChart"; import RoseChart from "@/widgets/RosePie"; import BasicRadarChart from "@/widgets/BasicRadarChart"; ``` 而现在有一种批量导入的方法,而且支持动态导入,岂不是很香 ```js const path = require("path"); const files = require.context("@/widgets", false, /.vue$/); // console.log("files: ", files.keys()); const modules = {}; files.keys().forEach((key) => { const name = path.basename(key, ".vue"); modules[name] = files(key).default || files(key); }); ``` 之后只需要在`compoments`加入即可 ```js components{ ...modules } ``` 如此一来这个文件夹下的所有vue文件都将被导入进来了

南浮宫魅影

2021-02-26 22:04:58 18次观看
javascript
vue

手写专题

::: hljs-center **在此开启一个手写篇章** ::: # 数组 ## 扁平化 ```js function flatten(arr) { let result=[] for (let i=0,len=arr.length;i<len;i++) { if (Array.isArray(arr[i])) { result=result.concat(flatten(arr[i])) } else { result=[...result,arr[i] } } return result } ``` ## 去重 ```js //方法1 遍历 function unique(arr){ let res = [] arr.forEach(item=>{ if(!res.includes(item)){ res.push(item) } }) return res; } //方法2 Set function unique (arr) { // return [...new Set(arr)] return Array.from(new Set(arr)) } //方法3 双层for循环 function unique(arr){ for(var i=0;i<arr.length;i++){ for(var j =i+1;j<arr.length;j++){ if(arr[j]===arr[i]){ arr.splice(j,1); j-- } } } return arr; } //方法4 对象属性不相同 如果对象的属性名没有这个i,就把i放入 function unique(arr) { var arrry= []; var obj = {}; for (var i = 0; i < arr.length; i++) { if (!obj[arr[i]]) { arrry.push(arr[i]) obj[arr[i]] = 1 } } return arrry; } ``` # 对象 ## 拷贝 ### 浅拷贝 ```js function copy(obj) { let result=Array.isArray(obj)?[]:{} Object.keys(obj).forEach(key=>result[key]=obj[key]) return result } otherStar={...star} Object.assign({},star) ``` ### 深拷贝 ```js function deepCopy(obj, cache = new WeakMap()) { if (!obj instanceof Object) return obj // 防止循环引用 if (cache.get(obj)) return cache.get(obj) // 支持函数 if (obj instanceof Function) { return function () { obj.apply(this, arguments) } } // 支持日期 if (obj instanceof Date) return new Date(obj) // 支持正则对象 if (obj instanceof RegExp) return new RegExp(obj.source, obj.flags) // 还可以增加其他对象,比如:Map, Set等,根据情况判断增加即可,面试点到为止就可以了 // 数组是 key 为数字素银的特殊对象 const res = Array.isArray(obj) ? [] : {} // 缓存 copy 的对象,用于处理循环引用的情况 cache.set(obj, res) Object.keys(obj).forEach((key) => { if (obj[key] instanceof Object) { res[key] = deepCopy(obj[key], cache) } else { res[key] = obj[key] } }); return res } //递归实现 function deepClone(val) { if (typeof val !== "object" || val == null) return val let newObj = ({}).toString.call(val) === "[object Object]" ? {} : []; Reflect.ownKeys(val).forEach(key=>newObj[key]= deepClone(val[key])) return newObj } ```

南浮宫魅影

2020-12-05 17:07:13 11次观看
javascript
算法
  • 1
  • 2
  • 3
  • 4
  • 9