<commit_before># 当算法与前端相遇

> 前端需要了解算法吗？读了几章《算法导论》，结合一下项目实践试着以前端的视角来窥视一下算法的世界。

## 算法与前端

和一些同事闲聊过前端是否有必要研究算法，多数人给出了否定的答案，他们的理由是：

一、浏览器能调用的资源比较少，注定处理不了很多数据，算法优化效果不明显；

二、前端只处理页面逻辑，很少需要特别设计复杂的算法。

本着小马过河的精神早就想研究一下算法这个大宝贝儿，前段时间终于遇到了这样一个契机，由于工作的原因需要写一些稍微复杂一点的页面程序，写的感觉比较吃力，于是读了几章《算法导论》，觉得确实有必要拿出来分享一二。先给出前端有必要学习算法的三条理由：

一、资源少更需要优化；

二、前端承担的业务和交互会越来越复杂，做一些平台和组件的时候需要借助算法设计，下面会给出两个前端算法的例子；

三、熟悉算法的一些套路可以提高设计代码和读懂代码的速度，减少bug。

## 算法的概念

描述一个特定的计算过程来实现输入和输出关系。

## 算法设计

> 算法设计的目的是证明输入和输出满足某种关系，最常用的两种设计思路就是循环和分治。下面分别介绍设计技巧：

### 循环

先给一个经典的`插入排序`示例：

插入排序算法描述：

起始：从第二个开始；

保持：和前面元素作比较，如果比前面元素小就换互位置，一直到遇到不比自己小得元素终止，然后下一个；

终止：最后一个元素。

	// 插入排序核心代码
	for (var i = 1; i < array.length; i++) {
		var key = array[i];
		var j = i - 1;
		while (j >= 0 && array[j] > key) {
			array[j + 1] = array[j];
			j--;
		}
		array[j + 1] = key;
	}

[Demo](/articles/algorithms-1/demo/insertion-sort.html)

循环相对递归要简单一些，任何循环都能拆成上面三步，但是每一步中可能会包含另一个循环或递归，设计算法的时候可以先设计最外面的三步，然后推敲每一步的分支逻辑和设计每一步的具体实现(具体实现可能要嵌套其他算法设计)。

### 递归(分治)

递归是将原问题分解为几个更小但类似于原问题的子问题，然后递归解决这些子问题，最后合并这些子问题的解产生原问题的解。我们同样以一个示例最为开始 --- `快速排序`：

快速排序算法描述：

分解：将数组的最后一个元素作为分割元素，移动数组中的元素，使左边小于此元素右边大于此元素，将此元素的左右两部分视为新的数组；

解决：最后被分割而成的数组长度为0和1时直接返回，为2时排序；(为3时继续分解)

合并：无(由于数组是址引用，每次都是原址排序，搜易不需要单独的合并操作)。
	
	// 快速排序核心代码
	function quickSort(array, from, to) {
        // 参数容错，可使初始化不用做特殊处理
        from = from || 0;
        to = to === undefined ? (array.length - 1) : to;
        // to || (array.length - 1); 此种写法对 to=0 的情况会出问题
    
        if (from < to) {
    
            var markIndex = from - 1;  // 标记位
            var spaceItem = array[to]; // 默认最后一个
    
            // 找出分水岭的位置，并把大小数分列两侧
            for (var i = from; i <= to; i++) {
                if (array[i] <= spaceItem) {
                    markIndex++;
                    var temp = array[markIndex];
                    array[markIndex] = array[i];
                    array[i] = temp;
                }
            }
    
            arguments.callee(array, from, markIndex - 1);
            arguments.callee(array, markIndex + 1, to);
        }
        return array;
    }

在具体实现上我们采用一种`驱赶贪吃蛇`的策略来分解问题，`markIndex`作为贪吃蛇左起点的标记位，初始化时贪吃蛇没有长度，所以将标记位标记为`from - 1`(最开始时是-1，子问题也满足逻辑)；把数组(或数组的片段)最后一个元素当做分割元素`spaceItem`；然后从左到右遍历数组(或数组的片段)，如果当前数小于或等于`spaceItem`，那么将当前数和贪吃蛇的左边第一个数互换位置，使贪吃蛇向右移动一位，相应的`markIndex`也加1，如果当前数大于`spaceItem`，那么贪吃蛇向右涨一位。补充一下如果数组(或数组的片段)第一个元素小于`spaceItem`，会原位交换(`markIndex==i==0`)，这本身是没有意义的，但是如果加判断来消除这个逻辑分支，会带来两个问题，1、代码变复杂了，2、多数情况是非原位交换，每次都判断反而计算量更大。

[Demo](/articles/algorithms-1/demo/insertion-sort.html)

## 前端算法示例

### 将对象以表格的形式展现
	
使用上面的抽象方法，来描述两个示例...

### 循环依赖的判断

这是从实际项目中抽象而出的一个例子(由于公司的保密规定具体项目信息就不方便透露了)，对处理一些任务依赖、前端模块依赖等问题上有一定的通用性，下面是一个依赖示意图：
	
	A --> B --> C --> D
	      ∧     |     |
	      |     ∨     | 
	G <-- F <-- E <───┘

描述节点的部分数据如下：

	[
        {
            "resourceId": "sid-E312C067",   // 节点标识
            "stencil": {
                "id": "start"
            },
            "outgoing": [
                {"resourceId": "sid-6A757572"}
            ]
        },
        {
            "resourceId": "sid-6A757572",
            "stencil": {
                "id": "bind"
            },
            "outgoing": [
                {"resourceId": "sid-C92FBDAE"}
            ]
        }
    ]    

第一个例子是较为简单的判断是否有依赖关系，下面是算法描述：

分解：首先找到开始节点，以开始节点为起点，路径记录为空数组，遍历当前节点 `outgoing` 属性中的元素，通过元素的`resourceId`查找节点进入子问题；

解决：记录当前节点从起始位置到当前节点之前的路径，如果当前节点的`resourceId`出现在了路径中，那么就出现了循环终止问题分解向上返回结果；如果当前节点的`resourceId`未出现在路径中，那么继续向下分解；

合并：如果出现“已出现循环”的结果，将此结果层层向上返回；否则遍历全部节点，向上层层返回默认值“未出现循环”。

[Demo，可在控制台查看代码](/articles/algorithms-1/demo/is-circular.html)。

### 递归的技巧

在设计递归算法和阅读递归的代码时，要把握的第一个关键就是怎样将入参转化为下一轮调用的入参，这个转换的逻辑就是将大问题转换成较小问题的逻辑；第二个关键点就是入参和出参的设计上，先不要管过程怎样实现将你需要的出参列出来，然后设计入参，在层级逻辑比较复杂的递归中入参最好设计为一个对象，除了要处理的数据本身还有一些上下级的逻辑关系需要传递下去。

### 一个问题要和大家讨论
	
合还是分，算两遍还是算一遍
	
技巧

## 时空复杂度

### 时间复杂度
	<commit_msg>调整算法示例的顺序<commit_after># 当算法与前端相遇

> 前端需要了解算法吗？读了几章《算法导论》，结合一下项目实践试着以前端的视角来窥视一下算法的世界。

## 算法与前端

和一些同事闲聊过前端是否有必要研究算法，多数人给出了否定的答案，他们的理由是：

一、浏览器能调用的资源比较少，注定处理不了很多数据，算法优化效果不明显；

二、前端只处理页面逻辑，很少需要特别设计复杂的算法。

本着小马过河的精神早就想研究一下算法这个大宝贝儿，前段时间终于遇到了这样一个契机，由于工作的原因需要写一些稍微复杂一点的页面程序，写的感觉比较吃力，于是读了几章《算法导论》，觉得确实有必要拿出来分享一二。先给出前端有必要学习算法的三条理由：

一、资源少更需要优化；

二、前端承担的业务和交互会越来越复杂，做一些平台和组件的时候需要借助算法设计，下面会给出两个前端算法的例子；

三、熟悉算法的一些套路可以提高设计代码和读懂代码的速度，减少bug。

## 算法的概念

描述一个特定的计算过程来实现输入和输出关系。

## 算法设计

> 算法设计的目的是证明输入和输出满足某种关系，最常用的两种设计思路就是循环和分治。下面分别介绍设计技巧：

### 循环

先给一个经典的`插入排序`示例：

插入排序算法描述：

起始：从第二个开始；

保持：和前面元素作比较，如果比前面元素小就换互位置，一直到遇到不比自己小得元素终止，然后下一个；

终止：最后一个元素。

	// 插入排序核心代码
	for (var i = 1; i < array.length; i++) {
		var key = array[i];
		var j = i - 1;
		while (j >= 0 && array[j] > key) {
			array[j + 1] = array[j];
			j--;
		}
		array[j + 1] = key;
	}

[Demo](/articles/algorithms-1/demo/insertion-sort.html)

循环相对递归要简单一些，任何循环都能拆成上面三步，但是每一步中可能会包含另一个循环或递归，设计算法的时候可以先设计最外面的三步，然后推敲每一步的分支逻辑和设计每一步的具体实现(具体实现可能要嵌套其他算法设计)。

### 递归(分治)

递归是将原问题分解为几个更小但类似于原问题的子问题，然后递归解决这些子问题，最后合并这些子问题的解产生原问题的解。我们同样以一个示例最为开始 --- `快速排序`：

快速排序算法描述：

分解：将数组的最后一个元素作为分割元素，移动数组中的元素，使左边小于此元素右边大于此元素，将此元素的左右两部分视为新的数组；

解决：最后被分割而成的数组长度为0和1时直接返回，为2时排序；(为3时继续分解)

合并：无(由于数组是址引用，每次都是原址排序，搜易不需要单独的合并操作)。
	
	// 快速排序核心代码
	function quickSort(array, from, to) {
        // 参数容错，可使初始化不用做特殊处理
        from = from || 0;
        to = to === undefined ? (array.length - 1) : to;
        // to || (array.length - 1); 此种写法对 to=0 的情况会出问题
    
        if (from < to) {
    
            var markIndex = from - 1;  // 标记位
            var spaceItem = array[to]; // 默认最后一个
    
            // 找出分水岭的位置，并把大小数分列两侧
            for (var i = from; i <= to; i++) {
                if (array[i] <= spaceItem) {
                    markIndex++;
                    var temp = array[markIndex];
                    array[markIndex] = array[i];
                    array[i] = temp;
                }
            }
    
            arguments.callee(array, from, markIndex - 1);
            arguments.callee(array, markIndex + 1, to);
        }
        return array;
    }

在具体实现上我们采用一种`驱赶贪吃蛇`的策略来分解问题，`markIndex`作为贪吃蛇左起点的标记位，初始化时贪吃蛇没有长度，所以将标记位标记为`from - 1`(最开始时是-1，子问题也满足逻辑)；把数组(或数组的片段)最后一个元素当做分割元素`spaceItem`；然后从左到右遍历数组(或数组的片段)，如果当前数小于或等于`spaceItem`，那么将当前数和贪吃蛇的左边第一个数互换位置，使贪吃蛇向右移动一位，相应的`markIndex`也加1，如果当前数大于`spaceItem`，那么贪吃蛇向右涨一位。补充一下如果数组(或数组的片段)第一个元素小于`spaceItem`，会原位交换(`markIndex==i==0`)，这本身是没有意义的，但是如果加判断来消除这个逻辑分支，会带来两个问题，1、代码变复杂了，2、多数情况是非原位交换，每次都判断反而计算量更大。

[Demo](/articles/algorithms-1/demo/insertion-sort.html)

## 前端算法示例

### 循环依赖的判断

这是从实际项目中抽象而出的一个例子(由于公司的保密规定具体项目信息就不方便透露了)，对处理一些任务依赖、前端模块依赖等问题上有一定的通用性，下面是一个依赖示意图：
	
	A --> B --> C --> D
	      ∧     |     |
	      |     ∨     | 
	G <-- F <-- E <───┘

描述节点的部分数据如下：

	[
        {
            "resourceId": "sid-E312C067",   // 节点标识
            "stencil": {
                "id": "start"
            },
            "outgoing": [
                {"resourceId": "sid-6A757572"}
            ]
        },
        {
            "resourceId": "sid-6A757572",
            "stencil": {
                "id": "bind"
            },
            "outgoing": [
                {"resourceId": "sid-C92FBDAE"}
            ]
        }
    ]    

第一个例子是较为简单的判断是否有依赖关系，下面是算法描述：

分解：首先找到开始节点，以开始节点为起点，路径记录为空数组，遍历当前节点 `outgoing` 属性中的元素，通过元素的`resourceId`查找节点进入子问题；

解决：记录当前节点从起始位置到当前节点之前的路径，如果当前节点的`resourceId`出现在了路径中，那么就出现了循环终止问题分解向上返回结果；如果当前节点的`resourceId`未出现在路径中，那么继续向下分解；

合并：如果出现“已出现循环”的结果，将此结果层层向上返回；否则遍历全部节点，向上层层返回默认值“未出现循环”。

[Demo，可在控制台查看代码](/articles/algorithms-1/demo/is-circular.html)。

### 将对象以表格的形式展现
	
使用上面的抽象方法，来描述两个示例...

### 递归的技巧

在设计递归算法和阅读递归的代码时，要把握的第一个关键就是怎样将入参转化为下一轮调用的入参，这个转换的逻辑就是将大问题转换成较小问题的逻辑；第二个关键点就是入参和出参的设计上，先不要管过程怎样实现将你需要的出参列出来，然后设计入参，在层级逻辑比较复杂的递归中入参最好设计为一个对象，除了要处理的数据本身还有一些上下级的逻辑关系需要传递下去。

### 一个问题要和大家讨论
	
合还是分，算两遍还是算一遍
	
技巧

## 时空复杂度

### 时间复杂度
	
{'fraction_non_alphanumeric': 0.1338193178859672, 'fraction_numerical': 0.012236396771674042, 'mean_word_length': 3.054353562005277, 'pattern_counts': {'":': 20, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2867240', 'n_tokens_mistral': 5371, 'n_tokens_neox': 6174, 'n_words': 338}