SegmentFault 前端之路最新的文章
2021-11-22T17:22:02+08:00
https://segmentfault.com/feeds/blogs
https://creativecommons.org/licenses/by-nc-nd/4.0/
蚂蚁金服AntV-S2重磅发布
https://segmentfault.com/a/1190000040999121
2021-11-22T17:22:02+08:00
2021-11-22T17:22:02+08:00
Leon
https://segmentfault.com/u/leon07
0
<p><img src="/img/bVcWbTp" alt="" title=""></p><p>S2 是 AntV 团队推出的数据表可视化引擎,旨在提供高性能、易扩展、美观、易用的多维表格。不仅有丰富的分析表格形态,还内置丰富的交互能力, 帮助用户更好地看数和做决策。 </p><p>请猛击下方链接查看详情:<br><a href="https://link.segmentfault.com/?enc=wxMgaeo3tXye91j6v%2FnQWA%3D%3D.YoOfPthMfKccaxYxampITXhFKL5LH3sRGkQvdCZO1iOqBAW7pKIo0t7aLKT5b0EQ" rel="nofollow">Antv-S2</a></p>
实现antd的穿梭框
https://segmentfault.com/a/1190000040652757
2021-09-08T17:56:41+08:00
2021-09-08T17:56:41+08:00
Leon
https://segmentfault.com/u/leon07
0
<p>题目:实现<a href="https://link.segmentfault.com/?enc=yiP2neeyHaqQiY62RbKxRw%3D%3D.EVQmvBOg7vu2y%2B3SrLpjDOMJSXT0xldFMcqhcJ4vCjCZsp0ktbexkiEJWHLqnobp" rel="nofollow">antd穿梭框</a>的基本功能</p><p>antd的穿梭框实现有以下几个要点:</p><ol><li>数据分为两部分,source-左侧,target-右侧</li><li>选项在左右两个框中穿梭,实际上是对 source 和 target 这两个数组进行增删的数据维护</li></ol><p>下面是完整实现,线上<a href="https://link.segmentfault.com/?enc=OggTNxOqD3z2Yu6QfwiwcA%3D%3D.iOZzac%2Bxvgrkwjmx90%2FZIkWSn3wrL8pW4fNzxOjIYTMQt7sn5m%2FIqGaMXF1CWuBxUreMhz%2FckI0%2FhElQHsii6uye%2B7HsW%2FB%2B5dk4ConLIZiblp7%2F6PDQ5SQqaytpScG1" rel="nofollow">demo</a></p><pre><code class="javascript">import React, { useState } from "react";
import "./styles.css";
export default function Transfer(props) {
const [source, setSource] = useState(props.dataSource);
const [target, setTarget] = useState([]);
const [sourceSelectedKeys, setSourceSelectedKeys] = useState([]);
const [targetSelectedKeys, setTargetSelectedKeys] = useState([]);
const onSelectChange = (key, type, e) => {
if (type === "source") {
setSourceSelectedKeys([...sourceSelectedKeys, key]);
} else {
setTargetSelectedKeys([...targetSelectedKeys, key]);
}
};
const moveToRight = () => {
const dataSourceCpy = [...source];
const moveItem = dataSourceCpy.filter((item) =>
sourceSelectedKeys.includes(item.key)
);
const newSource = dataSourceCpy.filter(
(item) => !sourceSelectedKeys.includes(item.key)
);
setTarget([...moveItem, ...target]);
setSource(newSource);
setSourceSelectedKeys([]);
};
const moveToLeft = () => {
const targetCpy = [...target];
const moveItem = targetCpy.filter((item) =>
targetSelectedKeys.includes(item.key)
);
const newTarget = targetCpy.filter(
(item) => !targetSelectedKeys.includes(item.key)
);
setTarget(newTarget);
setSource([...moveItem, ...source]);
setTargetSelectedKeys([]);
};
const handleTransfer = (type) => {
if (type === "right") {
moveToRight();
} else {
moveToLeft();
}
};
return (
<div className="container">
<div className="dataSource">
{source.map((item) => {
return (
<div key={item.key}>
<input
type="checkbox"
name={item.title}
onChange={(e) => {
onSelectChange(item.key, "source", e);
}}
/>
<label htmlFor={item.title}>{item.title}</label>
</div>
);
})}
</div>
<div className="operation">
<button
onClick={() => {
handleTransfer("right");
}}
>
{">"}
</button>
<button
onClick={() => {
handleTransfer("left");
}}
>
{"<"}
</button>
</div>
<div className="target">
{target.map((item) => {
return (
<div key={item.key}>
<input
type="checkbox"
name={item.title}
onChange={(e) => {
onSelectChange(item.key, "target", e);
}}
/>
<label htmlFor={item.title}>{item.title}</label>
</div>
);
})}
</div>
</div>
);
}</code></pre><pre><code class="css">.container {
display: flex;
}
.dataSource {
border: 1px solid black;
width: 200px;
height: 300px;
}
.operation {
display: flex;
flex-direction: column;
}
.target {
border: 1px solid black;
width: 200px;
height: 300px;
}
</code></pre>
使用TypeScript校验运行时数据
https://segmentfault.com/a/1190000040652111
2021-09-08T17:18:54+08:00
2021-09-08T17:18:54+08:00
Leon
https://segmentfault.com/u/leon07
2
<h2>背景</h2><p>对于前端程序猿,常见的开发流程是:</p><ol><li>前后端约定接口</li><li>后端给出接口文档</li><li>根据接口编写 TypeScript 类型定义</li><li>开发完成进行联调</li></ol><p>虽然一切顺利,但是上线后还是翻车了,js 报错:<code>cannot read the property 'xx' of null</code>,很显然前端没有处理空值,接锅吧 TT。但回头一看接口文档,跟后端同学约定的返回对象,但实际返了 <code>null</code>,这锅不能一个人背。那么怎样才能尽早发现这种问题呢?一种解决方案是:</p><ol><li>将 TypeScript 类型定义转为 JSON Schema</li><li>利用 JSON Schema 校验数据正确性</li></ol><p>针对以上方案做了一个 <a href="https://link.segmentfault.com/?enc=f0gMg8F9kBBkm0Xh2GMFDg%3D%3D.HWuQ4EtnjVHPVJSOnkB4VJMFx5h684e2xTg8v8E1npIT91xxjM7KEVyT1qRPHJx3" rel="nofollow">demo</a></p><h2>JSON Schema</h2><p>JSON Schema 是一个 JSON 对象,用来描述和校验 JSON 对象的格式。比如下面这个 JSON Schema:</p><pre><code class="json">{
"type": "object",
"properties": {
"name": {
"type": "string"
},
"age": {
"type": "number"
},
"hobby": {
"type": "array",
"items": {
"type": "string"
}
}
},
"required": [
"age",
"hobby",
"name"
],
"$schema": "http://json-schema.org/draft-07/schema#",
}</code></pre><p>它描述了这样一个 JSON 对象:</p><ul><li>类型 - <code>type</code> 是<code>obeject</code></li><li><p>有四个属性 - <code>properties</code></p><ul><li><code>name</code>:类型为 <code>string</code></li><li><code>age</code>:类型为 <code>number</code></li><li><code>hobby</code>:类型为 <code>Array<string></code></li></ul></li><li>属性是否必须 - <code>required</code>:<code>name</code>,<code>age</code>,<code>hobby</code> 都为必须</li></ul><p>下面这个 JSON 对象就是满足这个 JSON Schema 的:</p><pre><code class="json">{
"name": "Tom",
"age": 1,
"hobby": ["coding"]
}</code></pre><p>可以看出 JSON Schema 还是很好理解的,但其描述语法还是有一定学习成本,这里强烈推荐通过 <a href="https://link.segmentfault.com/?enc=Mb7g3YZas7CDs6ZgnDm%2BWw%3D%3D.WRoF5Dux19jUbrZf%2BUUlIzlWFPiMNwuWn3eknAaAb2pKt87qiXsvvoIbUPaDAjkU" rel="nofollow">jsonschema</a> 库的 <a href="https://link.segmentfault.com/?enc=tMhB%2BlSD8iziUBzSi3Sl6A%3D%3D.Ros4lelpZNy6E9X%2F%2BNDaRkMeiftTsoSRIarGVQlNIVQnlOs7utD4KTDFUl8u%2F9i4kIIUV3UzPFpkL7pMHmZii9w3EsjGjJoKEPnCa8qtPMg%3D" rel="nofollow">example</a> 去学习相关语法,另外也可以看 <a href="https://link.segmentfault.com/?enc=gkLLDX9ecvXyQarpiM9kgA%3D%3D.B%2F2XVnP8nOxBKkC6bfJIYDH8Vtv9g9WbuHEXNoomFtWkaC%2B96yPMm9z%2FYqhErlS%2BTuB5JdZb%2B2MBTqaMtanXPQ%3D%3D" rel="nofollow">Understanding JSON Schema</a>。</p><p>有了 JSON Schema,怎么使用它校验 JSON 对象的合法性呢?这里就用到了刚刚提到的<a href="https://link.segmentfault.com/?enc=qWKyMHXZZ9Eczr5vlDuBfQ%3D%3D.ECRoONm53WCUD5z8xY5SuLGpnUavDGVoJgWgwa0Unz7mjgnzfQAawAYCDxLK8w8h" rel="nofollow">jsonschema</a> 库。简单使用示例如下:</p><pre><code class="javascript">var Validator = require('jsonschema').Validator;
var v = new Validator();
var instance = 4;
var schema = {"type": "number"};
console.log(v.validate(instance, schema));</code></pre><p>现在可以根据 JSON Schema 去校验后端返回数据的格式是否正确了,但是为每个接口手动编写 JSON Schema 是不现实的,我们自然会想到能不能将 TypeScript 的接口类型定义转为 JSON Schema?</p><h2>TypeScript Interface -> JSON Schema</h2><p>好在已经有 <a href="https://link.segmentfault.com/?enc=oVqxiH%2BPLvlPCbZcsulOTg%3D%3D.BZT1XpcwOMUloekMeDAF0vXk%2FPwPQ%2BGt5tz%2BotK%2F7flybFbu51VrTAropEzHKfAKqIH3v14iVkURY6ro7VMe7A%3D%3D" rel="nofollow">typescript-json-schema</a> 这个库帮我们解决了这个问题,下面给出简单的使用示例:</p><pre><code class="javascript">import path from "path";
import * as TJS from "typescript-json-schema";
const settings: TJS.PartialArgs = {
required: true
};
// optionally pass ts compiler options
const compilerOptions: TJS.CompilerOptions = {
strictNullChecks: true
};
// 解析接口定义文件:index.ts
const program = TJS.getProgramFromFiles(
[path.join(__dirname, './apis/index.ts')],
compilerOptions,
);
// 将"IApi1"这个interface转为schema,传入"*"将转换全部interface
let schema = TJS.generateSchema(program, "IApi1", settings) || {};</code></pre><p>一顿操作后就可以将下面这个 <code>interface</code> 转为文章开头给出的示例 JSON Schema:</p><pre><code class="typescript">interface IApi1 {
name: string;
age: number;
hobby: string[];
}</code></pre><p>然后再用 node 将刚刚得到的 schema 存成 json 文件:</p><pre><code class="javascript">fs.writeFileSync(path.join(__dirname, "./json-schema", "schema.json"), schema); </code></pre><p>接着就可以使用相应的 JSON Schema 对后端数据进行校验了:</p><pre><code class="javascript">import { Validator } from 'jsonschema'
const apiSchema = require('./json-schema/schema.json')
const v = new Validator();
Api1().then(res => {
const validateRes1 = v.validate(res, apiSchema)
console.log(validateRes1);
});</code></pre><p>完整的示例可以看:<a href="https://link.segmentfault.com/?enc=YMqHVWDqcxjtxF56GLoyyg%3D%3D.g6FoSJ18r0P%2Fro53Ak%2BwDsrfXwziNrDdrZmSLT7xLgjHfyHpFL4UoErBDk9q6lky" rel="nofollow">demo</a></p><h2>工程中的实践</h2><p>1、如何组织散落的接口类型定义?<br>我个人比较喜欢的方式是:在 <code>apis.ts</code> 文件中统一去写所有的接口定义和类型定义,这样在转换 JSON Schema 时去处理这一个文件即可。</p><p>2、怎样自动将类型定义转为 JSON Schema?<br>使用 <code>husky</code>,在 <code>pre-commit</code> 阶段去执行转换工作,进一步可以使用 <code>lint-staged</code> 判断当前提交是否涉及到接口定义文件的改动,有改动再执行转换。<br>关于脚本的编写:</p><ul><li><p>首先创建脚本</p><pre><code class="javascript">touch scripts/transfer.js</code></pre><p><code>transfer.js</code> 中去编写 TS 转为 JSON Schema 的逻辑</p></li><li><p><code>package.json</code> 中添加 <code>scripts</code>:</p><pre><code class="javascript">"scripts": {
"transfer": "node scripts/transfer.js"
}</code></pre><p>或者在 <code>pre-commit</code> 中去执行该脚本。</p></li></ul><p>3、何时校验数据?<br>这里我想到两个场景:</p><ul><li>生产上:对于一些关键接口,在接口返回数据后调用校验逻辑,如果校验有错,需要做两件事:第一是将错误数据转为正确的备用数据,以防页面挂掉;第二是上报错误;</li><li>测试时:写各种测试用例去测后端接口,校验返回数据的正确性,这样就不用人眼去校验数据是否正确了。</li></ul>
求数组中所有数字可拼出的最大整数
https://segmentfault.com/a/1190000040632816
2021-09-05T14:56:10+08:00
2021-09-05T14:56:10+08:00
Leon
https://segmentfault.com/u/leon07
0
<p>遇到这样一个题:实现一个函数,求数组中所有数字可拼出的最大整数。举例:</p><pre><code class="javascript">maxNum([0, 4, 19, 41, 70]) // 70441190
maxNum([3, 30, 34, 5, 9]) // 9534330
maxNum([539, 53]) // 53953
maxNum([]) // 0</code></pre><p>更新:<br>之前的方法太蠢了,其实很简单,在 <code>sort</code> 方法中将<code>a</code>,<code>b</code>两个数据交换前后顺序拼成两个数,相减就行了。</p><pre><code class="javascript">function maxNum(nums) {
function compare(a, b) {
const res1 = `${a}${b}`;
const res2 = `${b}${a}`;
return res2 - res1;
}
return +nums.sort(compare).join('');
}</code></pre><p>---------------以下是原答案---------------</p><p>这个题目实际上是对数组进行排序,排序的规则是让最大的数字排在高位,比如:70和41比较,7大于4,所以70应该放在41前;但是有特殊情况,如果两个数字前几位都相同该怎么办,比如539和53,5和3都相同,此时应该用539中的9和53的第一位5比较,9大于5,所以539应该放在前面。</p><p>实现的步骤为:</p><ol><li>将数字转为字符串,依次比较两个数字的每一位,将高位更大的数字排在前面;</li><li>如果两个数字 a, b 的长度分别为 n 和 n+m,且前 n 位都相同,那么用 a[0] 和 b[n] 进行比较;</li></ol><p>代码如下:</p><pre><code class="javascript">function maxNum(arr) {
function sortFn(num1, num2) {
num1 = `${num1}`;
num2 = `${num2}`;
let num1Len = num1.length;
let num2Len = num2.length;
let num1Index = 0;
let num2Index = 0;
while (1) {
if (num1[num1Index] === num2[num2Index]) {
num1Index++;
num2Index++;
// num1已遍历结束,num2未结束
if (num1Index === num1Len && num2Index < num2Len) {
return +num2[num2Index] - (+num1[0]);
}
// num2已遍历结束,num1未结束
if (num2Index === num2Len && num1Index < num1Len) {
return +num2[0] - (+num1[num1Index]);
}
// num1和num2都已遍历结束
if (num1Index === num2Len && num2Index === num2Len) {
return +num2[num2Index] - (+num1[num1Index]);
}
} else {
return +num2[num2Index] - (+num1[num1Index]);
}
}
}
return +arr.sort(sortFn).join('');
}
</code></pre>
Promise并发控制
https://segmentfault.com/a/1190000040573531
2021-08-25T17:16:48+08:00
2021-08-25T17:16:48+08:00
Leon
https://segmentfault.com/u/leon07
9
<h2>问题</h2><p>要求写一个方法控制 Promise 并发数量,如下:</p><pre><code class="javascript">promiseConcurrencyLimit(limit, array, iteratorFn)</code></pre><p><code>limit</code> 是同一时间执行的 promise 数量,<code>array</code> 是参数数组,<code>iteratorFn</code> 每个 promise 中执行的异步操作。</p><h2>背景</h2><p>开发中需要在多个promise处理完成后执行后置逻辑,通常使用<code>Promise.all</code>:</p><pre><code class="javascript">Primise.all([p1, p2, p3]).then((res) => ...)</code></pre><p>但是有个问题是,因为 promise 创建后会立即执行,也就是说传入到 <code>promise.all</code> 中的多个 promise 实例,在其创建的时候就已经开始执行了,如果这些实例中执行的异步操作都是 http 请求,那么就会在瞬间发出 n 个 http 请求,这样显然是不合理的;更合理的方式是:对 <code>Promise.all</code> 中异步操作的执行数量加以限制,同一时间只允许有 limit 个异步操作同时执行。</p><h2>思路 & 实现</h2><p>在背景中提到,promise 在创建后就会立即执行,所以控制并发的核心在于控制 promise 实例的生成。最开始只生成 limit 个 promise 实例,然后等待这些 promise 状态变更,只要其中某一个 promise 实例的状态发生变更,就立即再创建一个 promise 实例...如此循环,直到所有的 promise 都被创建并执行。</p><p>npm 上有很多库实现了此功能,个人觉得 <a href="https://link.segmentfault.com/?enc=0Ezv5BE3X9m0tfJjpnP5nQ%3D%3D.9e5JbYxb80l1mFas34QGIo1DLLmjWbRCKIy%2BTTnpHEperkxXUeKbl%2BFw1sbIa1gH" rel="nofollow">tiny-async-pool</a> 这个库比较好,因为它直接使用了原生的 Promise 实现了此功能,而其他库大多重新实现了 promise。其核心代码如下:</p><pre><code class="javascript">async function asyncPool(poolLimit, array, iteratorFn) {
const ret = []; // 用于存放所有的promise实例
const executing = []; // 用于存放目前正在执行的promise
for (const item of array) {
const p = Promise.resolve(iteratorFn(item)); // 防止回调函数返回的不是promise,使用Promise.resolve进行包裹
ret.push(p);
if (poolLimit <= array.length) {
// then回调中,当这个promise状态变为fulfilled后,将其从正在执行的promise列表executing中删除
const e = p.then(() => executing.splice(executing.indexOf(e), 1));
executing.push(e);
if (executing.length >= poolLimit) {
// 一旦正在执行的promise列表数量等于限制数,就使用Promise.race等待某一个promise状态发生变更,
// 状态变更后,就会执行上面then的回调,将该promise从executing中删除,
// 然后再进入到下一次for循环,生成新的promise进行补充
await Promise.race(executing);
}
}
}
return Promise.all(ret);
}</code></pre><p>测试代码如下:</p><pre><code class="javascript">const timeout = (i) => {
console.log('开始', i);
return new Promise((resolve) => setTimeout(() => {
resolve(i);
console.log('结束', i);
}, i));
};
(async () => {
const res = await asyncPool(2, [1000, 5000, 3000, 2000], timeout);
console.log(res);
})();</code></pre><p>代码的核心思路为:</p><ol><li>先初始化 <code>limit</code> 个 promise 实例,将它们放到 <code>executing</code> 数组中</li><li>使用 <code>Promise.race</code> 等待这 <code>limit</code> 个 promise 实例的执行结果</li><li>一旦某一个 promise 的状态发生变更,就将其从 <code>executing</code> 中删除,然后再执行循环生成新的 promise,放入<code>executing</code> 中</li><li>重复2、3两个步骤,直到所有的 promise 都被执行完</li><li>最后使用 <code>Promise.all</code> 返回所有 promise 实例的执行结果</li></ol>
基于vue2,eggjs,mysql的个人博客(正在更新)
https://segmentfault.com/a/1190000022458378
2020-04-24T17:27:44+08:00
2020-04-24T17:27:44+08:00
Leon
https://segmentfault.com/u/leon07
21
<p>简单做个博客。<br>功能点:注册、登录、cookie、权限控制、文章列表、文章详情、文章目录、点赞、评论、分页加载<br>整体架构:<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/0.png" alt="image.png" title="image.png"></p><p><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/Vue%E5%B7%A5%E7%A8%8B.png" alt="" title=""></p><h2>前端</h2><h3>使用vue-cli3创建项目</h3><pre><code class="JavaScript">npm install -g @vue/cli
vue create hello-world</code></pre><p>为了避开烦人的 eslint,选择了手动选择特性:<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/1.png" alt="image.png" title="image.png"><br>同时没有选择 Linter/Formatter,使用 vscode 中的插件 prettier 和 vetur 配合格式化代码。<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/2.png" alt="image.png" title="image.png"></p><h3>使用axios封装http请求方法</h3><p>参考了<a href="https://link.segmentfault.com/?enc=kj1TYUd6aqezoGgbJQN8mg%3D%3D.L4ou9hq3RzAHFTd%2FrKEU74I%2BBj4zJgiKj9Orm9QUKcTS%2FyhihUpCr7x%2BVdQ%2F41DX" rel="nofollow">vue中Axios的封装和API接口的管理</a>,对网络请求进行了发封装。<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/3.png" alt="image.png" title="image.png"><br>网络请求统一放在<code>/src/request</code>中,<code>config.js</code>中是基本配置信息:<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/4.png" alt="image.png" title="image.png"><br><code>http.js</code>中封装请求拦截、响应拦截、错误统一处理。<br><code>api.js</code>中是网站所有接口,将其导出后,挂载到 <code>vue.prototype.$api</code> 上,这样全局可以使用 <code>this.$api.xxx</code> 使用接口:<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/5.png" alt="image.png" title="image.png"><br>然后在<code>main.js</code>引入并挂载:<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/6.png" alt="image.png" title="image.png"></p><h3>cookie/session</h3><p>博客采用cookie/session的方式来记录会话状态,在<code>app.vue</code>的<code>created</code>生命周期函数中通过<code>checkLogin()</code>接口查询用户登录状态,具体的逻辑为:<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/7.png" alt="当当网流程图3.png" title="当当网流程图3.png"></p><h3>首页分页加载</h3><pre><code class="JavaScript"> let documentEle = document.documentElement
let needLoadMore =
documentEle.scrollTop + documentEle.clientHeight + 50 > documentEle.scrollHeight;
if (needLoadMore && !this.nomore) {
this.loadingMore = true;
//暂时不能再滚动加载数据
this.nomore = true;
this.loadMoreArticle();
}</code></pre><p><code>document.documentElement.scrollTop</code>:文档滚动的距离<br><code>document.documentElement.clientHeight</code>:文档在可视范围内的高度<br><code>document.documentElement.scrollHeight</code>:文档总高度</p><p>判断思路是:视口的高度 + 文档的滚动距离 >= 文档总高度,可以预留50的距离做预加载。前端每一次判断触底后,会向后端请求下一页数据,并返回 <code>nomore</code> 字段,表示是否还有未加载文章。这里有个细节是:每一次触底后手动将 <code>nomore</code> 设为 <code>true</code>,后端返回 <code>nomore</code> 后再修改其值,这样做的目的是防止在请求返回前再次发送请求。<br>参考:<a href="https://link.segmentfault.com/?enc=t9CwfFinsYGwPvTazJiCog%3D%3D.8qTCGFDMJeQUcIzk1QsCGooYOLNXl4W4%2BD1lyKOePq3stsyejnEwuWuAegzMyI9F" rel="nofollow">搞清clientHeight、offsetHeight、scrollHeight、offsetTop、scrollTop</a></p><h3>如何展示博文</h3><p>没有实际做博客之前,以为每一篇博文都是通过单独写html标签的方式排版的...然后通过别人的项目,发现了正确的做法是:<br>使用markdown/富文本编辑器编辑文章,生成<code>html</code>片段,在vue中使用<code>v-html</code>语法插入该<code>html</code>片段,文章便以<code>html</code>标签的形式渲染出来可。博客中使用的markdown编辑器是<a href="https://link.segmentfault.com/?enc=8I5jLgTy%2FKvfhzHU0hdHTQ%3D%3D.TJZ32Ji2C4kI7pw4X1EF3urtJc0Yq21b07cednzQ4kM25X6HXgQoZ4nL5EzUgsO0" rel="nofollow">mavonEditor</a>,另外使用<code>highlightjs</code>高亮代码。</p><pre><code class="JavaScript"><div v-html="articleInfo.contentHtml" class="article-container" ref="content"></div></code></pre><h3>提取目录</h3><pre><code class="JavaScript"> extractCatalog() {
let contentElementRef = Array.from(
this.$refs.content.querySelectorAll("h1,h2,h3,h4,h5,h6")
);
contentElementRef.forEach((item, index) => {
item.id = item.localName + "-" + index;
this.catalogList.push({
tagName: item.localName,
href: `#${item.localName}-${index}`,
text: item.innerText
});
});
}</code></pre><p>上一小节中,将文章的<code>html</code>片段渲染到了<code>div</code>容器元素中,接下来可以使用<code>querySelectorAll("h1,h2,h3,h4,h5,h6")</code>函数来找出文中所有的标题Dom节点,<code>querySelectorAll()</code>的好处在于它会按照传入参数的顺序进行查找,所以不用担心乱序。获取到目录后对各级目录编号,以便生成锚点进行跳转。</p><h3>判断对应节是否出现</h3><pre><code class="JavaScript"> watchPageScrollFunc() {
let contentElementRef = Array.from(
this.$refs.content.querySelectorAll("h1,h2,h3,h4,h5,h6")
);
for (let index = 0; index < contentElementRef.length; index++) {
const viewPortHeight =
window.innerHeight ||
document.documentElement.clientHeight ||
document.body.clientHeight;
const elementHeight = contentElementRef[index].clientHeight;
const el = contentElementRef[index];
const top =
el.getBoundingClientRect() &&
el.getBoundingClientRect().top + elementHeight;
if (top <= viewPortHeight && top > 0) {
this.firstVisibleElemetHref = this.catalogList[index].href;
break;
}
}
}
window.addEventListener("scroll", this.watchPageScrollFunc);</code></pre><p>判断方法:元素上边到视口上边的距离 + 元素自身高度 <= 视口高度 && 元素上边到视口上边的距离 + 元素自身高度 > 0<br>其中,获取元素到视口上边的距离用到:<code>getBoundingClientRect()</code>,某个元素相对于视窗的位置集合。集合中有top, right, bottom, left等属性:</p><pre><code class="javaScript">rectObject = object.getBoundingClientRect();
rectObject.top // 元素上边到视窗上边的距离;
rectObject.right // 元素右边到视窗左边的距离;
rectObject.bottom // 元素下边到视窗上边的距离;
rectObject.left // 元素左边到视窗左边的距离;
</code></pre><p>在整个文章的Dom结构中,使用<code>querySelectorAll("h1,h2,h3,h4,h5,h6")</code>去搜索所有标题类的Dom节点,每一次滚动都去依次动态检查这些标题元素距离视口上方的距离,找到第一个出现在视口中的Dom元素就返回。另外加上节流函数可优化性能。</p><p>参考:<a href="https://segmentfault.com/a/1190000017150136">如何判断元素是否在可视区域ViewPort</a></p><h3>评论的实现</h3><p>评论数据采用的数据结构如下,这里只做到了二级评论,数据结构定下来,具体的实现还是比较简单的。</p><pre><code class="JavaScript">let comments = [
{
author: "admin",
content: "留言1",
articleId: "9",
time: "2020-04-12 10:59",
id: "0",
replyList: [
{
author: "ghm",
content: "回复留言1",
articleId: "9",
replyTo: "admin",
time: "2020-04-12 10:59",
id: "0-0"
}
]
},
{
author: "admin",
content: "留言2",
articleId: "9",
time: "2020-04-12 10:59",
id: "1",
replyList: [
{
author: "ghm",
content: "回复留言2",
articleId: "9",
replyTo: "admin",
time: "2020-04-12 11:00",
id: "1-0"
}
]
}
];</code></pre><h4>可添加表情的输入框</h4><p>第一版的实现方式:在<code><input></code>中直接插入<code>emoji</code>的<code>unicode</code>,展示效果如下所示:<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/8.png" alt="image.png" title="image.png"><br>这样做的问题在于:展示效果没有图片好,并且在不同的浏览器中会展现出不同的效果。果断换用图片形式展示表情,但是<code><input></code>是不能插入<code><img></code>标签的,于是参考了掘金的实现方式,使用<code>contenteditable</code>这个css属性将普通Dom元素变为可编辑的Dom元素,这样就可以使用<code>appendChild()</code>的方式将<code><img></code>插入,最终的显示效果也是明显优于直接使用<code>emoji</code>的。</p><pre><code class="Html"> <div
class="textarea"
ref="inputContent"
contenteditable="true"
autocomplete="off"
:placeholder="placeholder"
draggable="false"
spellcheck="false"
></div></code></pre><p><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/9.png" alt="image.png" title="image.png"></p><h2>后端</h2><h3>数据库表的设计</h3><p>表1:文章列表:<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/10.png" alt="image.png" title="image.png"></p><p>表2: 文章详情:<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/11.png" alt="image.png" title="image.png"></p><p>表3:用户详情<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/12.png" alt="image.png" title="image.png"></p><h3>webServer</h3><p>使用了 eggjs 作为 web服务器,eggjs 的文档很完善,照着文档撸代码就够了。eggjs奉行约定优于配置,有以下优点:</p><ol><li>统一目录结构</li><li>统一分层设计:router-controller-service-model</li><li>全套安全、日志、测试方案</li><li>高扩展性的插件机制</li></ol><h4>初始化</h4><pre><code class="JavaScript">npm init egg --type=simple
npm i</code></pre><h4>目录结构</h4><p><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/13.png" alt="image.png" title="image.png"></p><h4>路由</h4><p>框架约定在<code>app/router.js</code>文件中统一配置所有路由</p><pre><code class="JavaScript">// app/router.js
module.exports = app => {
const { router, controller } = app;
router.get('/user/:id', controller.user.info);
};</code></pre><p>完整的理由定义如下:</p><pre><code class="JavaScript">router.verb('router-name', 'path-match', middleware1, ..., middlewareN, app.controller.action);</code></pre><p>注意事项:</p><ul><li>在 Router 定义中, 可以支持多个 Middleware 串联执行</li><li>Controller 必须定义在 <code>app/controller</code> 目录中。</li><li>一个文件里面也可以包含多个 Controller 定义,在定义路由的时候,可以通过 <code>${fileName}.${functionName}</code> 的方式指定对应的 Controller。</li><li>Controller 支持子目录,在定义路由的时候,可以通过 <code>${directoryName}.${fileName}.${functionName}</code> 的方式制定对应的 Controller。</li></ul><p>框架中一些常用的路由用法:</p><ul><li><p>获取查询参数</p><pre><code class="JavaScript">// curl http://127.0.0.1:7001/search?name=egg
ctx.query.name</code></pre></li><li><p>获取路径参数</p><pre><code class="JavaScript">// app/router.js
module.exports = app => {
app.router.get('/user/:id/:name', app.controller.user.info);
};
// app/controller/user.js
exports.info = async ctx => {
ctx.body = `user: ${ctx.params.id}, ${ctx.params.name}`;
};
// curl http://127.0.0.1:7001/user/123/xiaoming
</code></pre></li><li><p>post请求boby的获取</p><pre><code class="JavaScript">ctx.request.body</code></pre></li><li><p>重定向</p><pre><code class="JavaScript"> // 内部路由重定向
app.router.redirect('/', '/home/index', 302);
// 外部路由重定向
ctx.redirect(\`http://cn.bing.com\`);</code></pre></li></ul><h4>控制器(Controller)</h4><p>简单的说 Controller 负责解析用户的输入,处理后返回相应的结果。框架推荐 Controller 层主要对用户的请求参数进行处理(校验、转换),然后调用对应的service方法处理业务,得到业务结果后封装并返回:</p><ol><li>获取用户通过 HTTP 传递过来的请求参数。</li><li>校验、组装参数。</li><li>调用 Service 进行业务处理,必要时处理转换 Service 的返回结果,让它适应用户的需求。</li><li>通过 HTTP 将结果响应给用户。</li></ol><p>定义:<br>所有的 Controller 文件都必须放在 app/controller 目录下,可以支持多级目录,访问的时候可以通过目录名级联访问。</p><pre><code class="JavaScript">// app/controller/post.js
const Controller = require('egg').Controller;
class PostController extends Controller {
async create() {
const { ctx, service } = this;
const createRule = {
title: { type: 'string' },
content: { type: 'string' },
};
// 校验参数
ctx.validate(createRule);
// 组装参数
const author = ctx.session.userId;
const req = Object.assign(ctx.request.body, { author });
// 调用 Service 进行业务处理
const res = await service.post.create(req);
// 设置响应内容和响应状态码
ctx.body = { id: res.id };
ctx.status = 201;
}
}
module.exports = PostController;</code></pre><p>上面定义的<code>PostController</code>的方法可以通过文件名和方法名的方式使用。</p><pre><code class="JavaScript">// app/router.js
module.exports = app => {
const { router, controller } = app;
router.post('createPost', '/api/posts', controller.post.create);
}</code></pre><p>定义的 Controller 类,会在每一个请求访问到 server 时实例化一个全新的对象,而项目中的 Controller 类继承于 <code>egg.Controller</code>,会有下面几个属性挂在 <code>this</code> 上:<code>this.ctx</code>,<code>this.app</code>,<code>this.service</code>,<code>this.config</code>,<code>this.logger</code></p><h4>服务(Service)</h4><p>Service 就是在复杂业务场景下用于做业务逻辑封装的一个抽象层,提供这个抽象有以下几个好处:</p><ul><li>保持 Controller 中的逻辑更加简洁。</li><li>保持业务逻辑的独立性,抽象出来的 Service 可以被多个 Controller 重复调用。</li><li>将逻辑和展现分离,更容易编写测试用例</li></ul><p>使用场景:</p><ul><li>复杂数据的处理,比如要展现的信息需要从数据库获取,还要经过一定的规则计算,才能返回用户显示。或者计算完成后,更新到数据库。</li><li>第三方服务的调用,比如 GitHub 信息获取等。</li></ul><p>Service 文件必须放在 app/service 目录,可以支持多级目录,访问的时候可以通过目录名级联访</p><pre><code class="JavaScript">app/service/biz/user.js => ctx.service.biz.user</code></pre><p>由于它继承于 <code>egg.Service</code>,故拥有下列属性方便我们进行开发:<code>this.ctx</code>,<code>this.app</code>,<code>this.service</code>,<code>this.config</code>,<code>this.logger</code></p><h4>MySQL</h4><p>egg提供了 <code>egg-mysql</code>插件来访问 MySQL 数据库</p><p>安装插件:</p><pre><code class="JavaScript">$ npm i --save egg-mysql</code></pre><p>开启插件:</p><pre><code class="JavaScript">// config/plugin.js
exports.mysql = {
enable: true,
package: 'egg-mysql',
};</code></pre><p>最后在 <code>config/config.${env}.js</code> 配置各个环境的数据库连接信息</p><pre><code class="JavaScript">// config/config.${env}.js
exports.mysql = {
// 单数据库信息配置
client: {
// host
host: 'mysql.com',
// 端口号
port: '3306',
// 用户名
user: 'test_user',
// 密码
password: 'test_password',
// 数据库名
database: 'test',
},
// 是否加载到 app 上,默认开启
app: true,
// 是否加载到 agent 上,默认关闭
agent: false,
};</code></pre><h4>Sequelize</h4><p>Sequelize 是 nodejs 社区广泛使用的 ORM 框架,将关系数据库的表结构映射为对象,让开发者使用 js 语法完成数据库操作。另外Sequelize 提供了 Migrations,帮助开发者管理数据库的每一次变更,因此每一次库表的变动都应通过 Migrations 来实现。</p><p>egg 提供了集成 Sequelize 的脚手架:</p><pre><code class="JavaScript">npm init egg --type=sequelize</code></pre><h2>上线</h2><h3>配置服务器环境</h3><p>1.一台linux服务器<br>作者买的阿里云最便宜的ECS云服务器,配置为1核2G,1M带宽,作为学习使用完全够了,操作系统选择的CentOS。然后参照阿里云给出的教程在服务器上<a href="https://link.segmentfault.com/?enc=cdWsMdYlqnS3figHlNxYTw%3D%3D.C0rgiXzN6M%2BVRcXkoMIB1d7p4eJu%2FcM%2FUI3Tj4rpMGjxqVnv9ndfuZIj5NCpjRmNtqTJd7CKC%2BG4H%2BvUw0%2FnHfXYR%2BgHLR11JcryhSx7%2BsYngv7kGiE5KS6I7U7893iH%2BDvI9mlKbukTQYA64Devkw%3D%3D" rel="nofollow">部署NodeJs环境</a>,<a href="https://link.segmentfault.com/?enc=ECS%2FztHRWWIn5RIjNvbTXQ%3D%3D.WkBPgsRZaWwFkPHuyFamA1pMtJUDBjYMBDTsurFOGRdanTTg1%2BGvgUqoK9dfY3FRIzR9gdt3q%2FDaRfl%2Fq1dOOYrfVDvNgrsIocQ0mn9188U5Wa1dh%2Fyfh74kE5Ttig5T9ITM2P6bUQyrAfYebkIfesI2G%2FgNjOXt5G6aZxvi2OTE0PYrmyblcoiZpj1Zsdvl" rel="nofollow">部署mysql</a>。<br>2.购买域名<br>在阿里云上购买域名后,按照新手引导设置域名解析,同时设置 www 和 @,网站便可通过 www.xxx.com 和 xxx.com 访问。同时,想要使用域名访问网站,还需要对域名进行备案。<br>3.本地数据库迁移到云服务器<br>作者使用的数据库可视化工具是navicat,在navicat中对选中的数据库做转储SQL文件处理,再在云服务器的mysql中新建数据库,运行此SQL文件,便完成了数据库的迁移。<br><img src="https://dt-blog-images.oss-cn-hangzhou.aliyuncs.com/%E5%9F%BA%E4%BA%8Evue2%EF%BC%8Ceggjs%EF%BC%8Cmysql%E7%9A%84%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/14.png" alt="image.png" title="image.png"></p><h3>上传文件</h3><p>1.下载文件传输工具 Xftp<br>2.部署前端代码</p><pre><code class="JavaScript">npm run build</code></pre><p>打包好后,使用 Xftp 将 <code>dist</code> 文件夹上传到服务器中<br>3.部署后端代码<br>将后端代码 <code>git clone</code> 到服务器中</p><pre><code class="JavaScript">npm i
npm start</code></pre><h3>配置nginx</h3><p>1.安装nginx</p><pre><code class="JavaScript">yum install nginx</code></pre><p>安装好的 nginx 会在 <code>/etc/nginx</code> 中<br>2.使用 Xftp 修改 nginx 配置<br>找到<code>/etc/nginx</code>目录下的 <code>nginx.conf</code>文件,使用记事本打开编辑:</p><pre><code class="JavaScript">user root;
worker_processes 1;
events {
worker_connections 1024;
}
http {
include mime.types;
default_type application/octet-stream;
sendfile on;
keepalive_timeout 65;
server {
listen 80;
server_name localhost;
root /root/project/dt_blog/frontend/dist/;
index index.html;
add_header Access-Control-Allow-Origin *;
location /api {
proxy_pass http://127.0.0.1:7001;
proxy_set_header HOST $host;
}
location / {
try_files $uri $uri/ @router;
index index.html;
}
location @router {
rewrite ^.*$ /index.html last;
}
}
}</code></pre><p>其中这两个配置很重要:</p><pre><code class="JavaScript">location / {
try_files $uri $uri/ @router;
index index.html;
}
location @router {
rewrite ^.*$ /index.html last;
}</code></pre><p>网站部署好后,可以正常访问,但是打开二级页面后再刷新,就会404,原因是:v-router设置的路径并不是真实存在的路由,工程中的路由跳转都是通过 js 实现的,而将前端打包好的 <code>dist</code> 目录部署在服务器后,在浏览器中访问根路径会默认打到 index.html 中,但是直接访问其他路径,就没有一个真实的路径与其对应。(参考:<a>https://www.cnblogs.com/kevingrace/p/6126762.html</a>)</p><p>做好以上配置后,就可以通过 <code>服务器ip:80</code> 来访问部署好的网站了,但是一直通过 ip 地址访问网站不太合理,那么就需要给网站配置域名。</p><h3>配置域名</h3>
闭包理解
https://segmentfault.com/a/1190000016103385
2018-08-22T11:05:10+08:00
2018-08-22T11:05:10+08:00
Leon
https://segmentfault.com/u/leon07
47
<p>面试必问题目,但总觉得理解得不深入,索性写一篇文章慢慢梳理吧。</p>
<h2>什么是闭包</h2>
<p>红宝书上给出的定义是:<b>闭包是指有权访问另一个函数作用域中的变量的函数</b>,看到另外一个理解是:<b>函数和函数内部能访问到的变量(或者环境)的总合,就是一个闭包</b>。创建一个闭包最常见的方式就是在一个函数内部创建另一个函数。下面写一个例子:</p>
<pre><code>function f1() {
var a = 1;
function closure() {
console.log(++a);
}
return closure;
}</code></pre>
<p>上面例子中,<code>f1</code> 内部的匿名函数以及它能够访问到的外部函数的变量 <code>a</code> 合在一起,就形成了一个闭包。使用 <code>return</code> 将闭包返回的目的是让它可以被外部访问。下面看看它怎么使用:</p>
<pre><code>var f2 = f1(); // 执行外部函数,返回闭包
f2(); // 2
f2(); // 3
f2(); // 4</code></pre>
<p>第一句执行函数 <code>f1()</code> 后,闭包被返回并赋值给了一个全局变量 <code>f2</code>,以后每次调用 <code>f2()</code>,变量 <code>a</code> 的值就会加 <code>1</code>。通常函数执行完毕后,其作用域链和活动对象都会被销毁,为什么这里 <code>a</code> 并没有被销毁并且每次执行 <code>f2()</code> 还会被递增?原因是闭包有权访问外部函数的变量,进一步说,<b>闭包的作用域链会引用外部函数的活动对象</b>,所以<code> f2()</code> 在执行时,其作用域链实际上是:</p>
<ol>
<li>自身的活动对象;</li>
<li>
<code>f1()</code> 的活动对象;</li>
<li>全局变量对象。</li>
</ol>
<p>所以 <code>f1()</code> 执行完后,其执行环境的作用域链会被销毁,但活动对象仍然会留在内存中,因为闭包作用域链在引用这个活动对象(说白了就是闭包还需要使用外层函数的变量,不允许它们被销毁),直到闭包被销毁后,<code>f1()</code> 的活动对象才会被销毁。</p>
<p>上面例子中,是将返回的闭包赋值给了一个全局变量 <code>f2</code>,<code>var f2 = f1();</code>,<code>f2</code> 是不会被销毁的,每次执行完 <code>f2()</code>,闭包的作用域链不会被销毁,所以就会出现每次执行 <code>f2()</code>,<code>a</code> 递增。</p>
<p>但是换一种闭包的调用方式,情况会不同:</p>
<pre><code>f1()(); // 2
f1()(); // 2</code></pre>
<p>因为没有把闭包赋值给一个全局变量,闭包执行完后,其执行域链与活动对象都销毁了。</p>
<h2>闭包的作用</h2>
<h3>创建用于访问私有变量的公有方法</h3>
<p>其实构造函数中定义的实例方法,就是闭包:</p>
<pre><code>function Person(){
var name = 'Leon';
function sayHi() {
alert('Hi!');
}
this.publicMethod = function() {
alert(name);
return sayHi();
}
}</code></pre>
<p>构造函数 <code>Person</code> 中定义实例方法<code> publicMethod() </code>就是一个闭包,它可以访问外部函数的变量 <code>name </code>和 函数 <code>sayHi()</code>,为什么要这么做呢?因为我们想在构造函数中定义一些私有变量,让外部不能直接访问,只能通过定义好的公有方法访问,从而达到保护变量,收敛外部权限的目的。</p>
<p>而在普通函数中,把闭包 <code>return</code> 出去供外部使用,其实目的也就是:让函数内部的变量始终保持在内存中,同时保护这些变量,让它们不能被直接访问。</p>
<pre><code>function person(){
var name = 'Leon';
function sayHi() {
alert('Hi!');
}
function publicMethod() {
alert(name);
return sayHi();
}
return publicMethod;
}</code></pre>
<h3>闭包用于创建单例</h3>
<p>所谓单例,就是只有一个实例的对象。单例模式的好处在于:</p>
<ul>
<li>
<p>保证一个类只有一个实例,避免了一个在全局范围内使用的实例频繁创建与销毁。</p>
<ul><li>比如网页中的弹窗,点击 a 按钮弹出,点击 b 按钮隐藏,如果弹窗每一次弹出都需要新建一个对象,将会造成性能的浪费,更好的办法就是只实例化一个对象,一直使用。</li></ul>
</li>
<li>
<p>划分了命名空间,避免了与全局命名空间的冲突。</p>
<ul><li>比如在一个单例中可以定义很多方法,通过<code>单例.方法</code>来使用,避免了在全局环境中定义函数,造成函数名冲突。</li></ul>
</li>
</ul>
<p>下面逐步介绍下单例的创建方式,后两种方式将用到闭包。</p>
<h4>1. 对象字面量创建单例</h4>
<pre><code>var singleton = {
attr1: 1,
attr2: 2,
method: function () {
return this.attr1 + this.attr2;
}
}
var s1 = singleton;
var s2 = singleton;
console.log(s1 == s2) // true</code></pre>
<p>上面用字面量形式创建了一个单例,可以看到 <code>s1</code> 和 <code>s2</code> 是等同的。这种方式的问题在于外部可以直接访问单例的内部变量并加以修改,如果想让单例拥有私有变量,就需要使用模块模式,模块模式就是用了闭包。</p>
<h4>2. 模块模式</h4>
<p>JS 中的模块模式的作用是:为单例添加私有变量和公有方法。它使用立即执行函数和闭包来达到目的。</p>
<pre><code>var singleton = (function(){
// 创建私有变量
var privateNum = 1;
// 创建私有函数
function privateFunc(){
console.log(++privateNum);
}
// 返回一个对象包含公有方法
return {
publicMethod: function(){
console.log(privateNum)
return privateFunc()
}
};
})();
singleton.publicMethod();
// 1
// 2 </code></pre>
<p>这里首先定义了一个立即执行函数,它返回一个对象,该对象中有一个闭包 <code>publicMethod()</code>, 它可以访问外部函数的私有变量。从而这个被返回的对象就成为了单例的公共接口,外部可以通过它的公有方法访问私有变量而无权直接修改。总结一下就是两点:</p>
<ul>
<li>立即执行函数可以创建一个块级作用域, 避免在全局环境中添加变量。</li>
<li>闭包可以访问外层函数中的变量。</li>
</ul>
<h4>3. 构造函数+闭包</h4>
<p>上面提到的对象字面是用来创建单例的方法之一,既然单例只能被实例化一次,不难想到,在使用构造函数新建实例时,先判断实例是否已被新建,未被新建则新建实例,否则直接返回已被新建的实例。</p>
<pre><code>var Singleton = function(name){
this.name = name;
};
// 获取实例对象
var getInstance = (function() {
var instance = null;
return function(name) {
if(!instance) {
instance = new Singleton(name);
}
return instance;
}
})();
var a = getInstance('1');
console.log(a); // {name: "1"}
var b = getInstance('2');
console.log(b); // {name: "1"}</code></pre>
<p>这里将构造函数和实例化过程进行了分离, <code>getInstance()</code>中存在一个闭包,它可以访问到外部变量 <code>instance</code>,第一次 <code>instance = null</code>,则通过 <code>new Singleton(name) </code>新建实例,并将这个实例保存在<code>instance</code> 中,之后再想新建实例,因为闭包访问到的<code>instance</code>已经有值了,就会直接返回之前实例化的对象。</p>
关于NaN
https://segmentfault.com/a/1190000016088123
2018-08-21T11:30:30+08:00
2018-08-21T11:30:30+08:00
Leon
https://segmentfault.com/u/leon07
33
<p>昨天看到一个面试题:怎样实现 <code>isNaN()</code> 方法?</p>
<p>细细研究了一下 NaN,发现这个东西不常用,坑却异常多,颇有 “茴” 字有几种写法的感觉,这里记录下总结的东西吧。</p>
<h2>
<code>NaN</code> 是什么</h2>
<p><code>NaN</code> 即 <b>Not a Number</b>(非数值),但它是一个特殊的数值,所以:</p>
<pre><code>typeof(NaN) // "number"</code></pre>
<p>编码时很少直接使用 <code>NaN</code>,通常是在计算失败时,作为 <code>Math</code> 的某个方法的返回值出现的。</p>
<p>它有两个重要的性质:</p>
<ul><li>
<code>NaN</code>与任何值都不相等,包括<code>NaN</code>自身:</li></ul>
<pre><code>alert(NaN == NaN) // false
alert(NaN === NaN) // false</code></pre>
<ul><li>任何涉及 <code>NaN</code>的操作都会返回<code>NaN</code>。</li></ul>
<h3>哪些情况会产生<code>NaN</code>?</h3>
<h4>1. 计算</h4>
<p>JS 在进行加减乘除运算之前,会先调用 <code>Number()</code>方法,将非数值的运算项转化为数值,如果转换失败就返回<code>NaN</code>,比如:</p>
<pre><code>1-'a'; // NaN</code></pre>
<p>首先是执行<code>Number('a')</code>,不能成功转化为数值,返回<code>NaN</code>,再利用<code>NaN</code>的第二条性质:任何涉及 <code>NaN</code>的操作都会返回<code>NaN</code>,所以最终的结果是<code>NaN</code>。</p>
<h4>2. 类型转换</h4>
<p>当一个值不能被<code>Number</code>,<code>parseInt</code>,<code>parseFloat</code>成功转换为数值,就返回<code>NaN</code>,举例:</p>
<pre><code>Number('123.456abc'); // NaN
parseInt('123.456abc'); // 123
parseFloat('123.456abc'); // 123.456
Number('abc'); // NaN
parseInt('abc'); // NaN
parseFloat('abc'); // NaN
Number([]); // 0
parseInt([]); // NaN
parseFloat([]); // NaN
Number(''); // 0
parseInt(''); // NaN
parseFloat(''); // NaN
Number({}); // NaN
parseInt({}); // NaN
parseFloat({}); // NaN</code></pre>
<p>这里要注意三者之间的差异,我的理解是 <code>parseInt</code>,<code>parseFloat</code>会尽量将参数值转化为数值。</p>
<h2>关于<code>isNaN()</code>
</h2>
<p><code>isNaN</code>是<code>window</code>对象的一个方法,比较诡异的是:<code>isNaN(x)</code>并不是判断参数<code>x</code>本身是不是<code>NaN</code>,而是判断<code>Number(x)</code>是不是<code>NaN</code>。也就是说先用<code>Number()</code>去转化参数,再去判断转化的结果。返回的结果是一个布尔值。</p>
<pre><code>isNaN(NaN); // true
isNaN(123); // false
isNaN('abc'); //true
isNaN('123abc'); //true
isNaN({}); // true,因为Number({})=NaN
isNaN(''); // false, 因为Number('')=0
isNaN([]); // false,因为Number([])=0</code></pre>
<p>可以看到最后, 空字符串<code>''</code> 和 空数组<code>[]</code>显然是非数值,而<code>isNaN</code>返回了<code>false</code>,原因就是<code>Number</code>转换在作怪,这点还是很诡异的...所以我选择慎用...</p>
<p>那么<code>isNaN</code>是怎么实现的呢,原理就是利用<code>NaN</code>的第一条性质:<code>NaN</code>与任何值都不相等,包括<code>NaN</code>自身。</p>
<pre><code>var isNaNA = function(value) {
var n = Number(value);
return n !== n;
};</code></pre>
<p>先用<code>Number()</code>转换参数,再判断转换后的结果是不是不等于自身。</p>
<p>而 <a href="https://link.segmentfault.com/?enc=0uL008EOxpalqyizfH3zJw%3D%3D.%2BD0yAzKn4vkaStey7PP3BJswGInkSXxVD1DXRcAlD7kX5xTb40Ok6OV3upjfchR%2BH8Hqv0UNE4Si15S0w4eiv%2Bvg8TR8vUSNIcW06M0S%2Fbaq06Lt%2FNHUtFSVvbnP5nFR" rel="nofollow">MDN</a> 上给的实现方式是这样的:</p>
<pre><code>var isNaNB = function(value) {
var n = parseInt(value);
return n !== n;
};</code></pre>
<p>我觉得是有问题的,因为:</p>
<pre><code>isNaN('123abc'); // true
isNaNA('123abc'); // true
isNaNB('123abc'); // false</code></pre>
<h2><code>Number.isNaN()</code></h2>
<p>ES6 中的<code>Number.isNaN()</code>是一个判断<code>NaN</code>的升级版,和<code>isNaN()</code>不同的是,<code>Number.isNaN()</code>不会强制转化参数,直接对参数本身做判断,这样只有参数显示等于<code>NaN</code>,才会返回<code>true</code></p>
<pre><code>Number.isNaN(NaN); // true,其他情况都返回 false</code></pre>
<p>它的实现原理是:</p>
<pre><code>function isNaNC (value) {
return typeof(value) === "number" && isNaN(value);
}</code></pre>
<p>算了,还是不纠结了....</p>
<h2>参考</h2>
<p><a href="https://link.segmentfault.com/?enc=1dGX2mVM7i2ZrwYJlJB57Q%3D%3D.gfA5yZF5JA8ozW%2BdnTN%2BHyBcy%2Bfb7ZmSCbuX9UYujTpnwv8xZiHG8RxJHmvccwNMJc64KUv6PdXOy6jY0W68osYhx6CPb3COthvKpKDT1a2C7RNdV%2F9JZop6Vgf50DvH" rel="nofollow">MDN isNaN()</a><br><a href="https://link.segmentfault.com/?enc=k3GXH82TSQ9Gd0IMs6M4AQ%3D%3D.9bzrL5Lb%2BjvpZCY82QOBwr1XGVqkwWGdxe7WwLcnU%2BaZztrUQLknn3tUtrskNKcW" rel="nofollow">JavaScript中的 NaN 与 isNaN</a></p>
数组去重-Map实现
https://segmentfault.com/a/1190000015923301
2018-08-07T22:33:49+08:00
2018-08-07T22:33:49+08:00
Leon
https://segmentfault.com/u/leon07
30
<h2>问题由来</h2>
<p>遇到一道面试题:找到数组中第一个非重复的数。</p>
<blockquote>[ 1, 1, 2, 2, 3, 4, 4, 5 ]<br>第一个非重复的数为 3</blockquote>
<p>最简单的想法就是两层 <code>for</code> 循环遍历数组,这样的时间复杂度是 <code>O(n^2)</code>。而更高效的方式,是使用<code>hash Map</code>,可将时间复杂降为<code>O(n)</code>。</p>
<p>其实这个题目可以衍生出三个类似的问题:</p>
<ol>
<li>数组去重</li>
<li>找到数组中重复的数</li>
<li>找到数组中第一个非重复的数</li>
</ol>
<p>我准备用<code>ES6</code>中的 <code>Map</code>数据结构来解决这三个问题,在这之前有必要先梳理下Map的主要知识点。</p>
<h2>Map基础梳理</h2>
<p>JavaScript 的对象(Object),本质上是键值对的集合(Hash 结构),但是传统上只能用字符串当作键。这给它的使用带来了很大的限制。为了解决这个问题,ES6 提供了 <code>Map</code> 数据结构。它类似于对象,也是键值对的集合,但是“键”的范围不限于字符串,各种类型的值(包括对象)都可以当作键。也就是说,<code>Object </code>结构提供了“字符串—值”的对应,<code>Map</code> 结构提供了“值—值”的对应,是一种更完善的 Hash 结构实现。</p>
<p>例如Map构造函数接受一个数组作为其参数:</p>
<pre><code class="JavaScript">const map = new Map([
[1, '张三'],
[2, '李四']
]);
// 0:{1 => "张三"}
// 1:{2 => "李四"}</code></pre>
<p><code>Map</code>实例的属性和操作方法:</p>
<ul>
<li>
<code>size</code>:返回成员总数</li>
<li>
<code>set(key, value)</code>:添加新的键值</li>
<li>
<code>get(key)</code>:读取键对应的值</li>
<li>
<code>has(key)</code>:是否有某个键</li>
<li>
<code>delete(key)</code>:删除某个键</li>
<li>
<code>clear()</code>:清空</li>
</ul>
<p><code>Map</code>实例的遍历方法:</p>
<ul>
<li>
<code>keys()</code>:返回键名的遍历器。</li>
<li>
<code>values()</code>:返回键值的遍历器。</li>
<li>
<code>entries()</code>:返回键值对的遍历器。</li>
<li>
<code>forEach()</code>:遍历 Map 的所有成员。</li>
</ul>
<p>下面来通过代码解决三个问题:</p>
<h2>数组去重</h2>
<blockquote>去重前:[ 1, 1, 2, 2, 3, 4, 4, 5 ]<br>去重后:[ 1, 2, 3, 4, 5 ]</blockquote>
<p>主要思路:创建一个空<code>Map</code>,遍历原始数组,把数组的每一个元素作为<code>key</code>存到Map中,因为<code>Map</code>中不会出现相同的<code>key</code>值,所以最终得到的<code>Map</code>中的所有<code>key</code>值就是去重后的结果。</p>
<pre><code class="JavaScript">function arrayNonRepeatfy(arr) {
let hashMap = new Map();
let result = new Array(); // 数组用于返回结果
for (let i = 0; i < arr.length; i++) {
if(hashMap.has(arr[i])) { // 判断 hashMap 中是否已有该 key 值
hashMap.set(arr[i], true); // 后面的true 代表该 key 值在原始数组中重复了,false反之
} else { // 如果 hashMap 中没有该 key 值,添加
hashMap.set(arr[i], false);
result.push(arr[i]);
}
}
return result;
}
let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"];
console.log(arrayNonRepeatfy(arr)); // [ 1, 2, 3, 4, 5, 'a', 'b' ]</code></pre>
<p>上面最终产生的<code>Map</code>不仅可以达到去重的效果,而且对每一元素的重复性都做了标注,这样想找到找到数组中重复的数就很方便了:</p>
<pre><code>console.log(hashMap);
/*
0:{1 => true} {key: 1, value: true}
1:{2 => false} {key: 2, value: false}
2:{3 => true} {key: 3, value: true}
3:{4 => false} {key: 4, value: false}
4:{5 => true} {key: 5, value: true}
5:{"a" => true} {key: "a", value: true}
6:{"b" => false} {key: "b", value: false}
*/</code></pre>
<h2>找到数组中重复的数</h2>
<blockquote>[ 1, 1, 2, 2, 3, 4, 4, 5 ]<br>[ 1, 2, 4 ]<br>接上一节末尾,既然<code>hashMap</code>中记录了每一个元素的重复情况,找到重复的数就很简单了,遍历最终得到的<code>hashMap</code>,值为 <code>true</code> 对应的键就是重复的数:</blockquote>
<pre><code>function findRepeatNumInArray(arr) {
let hashMap = new Map();
let result = new Array();
for (let i = 0; i < arr.length; i++) {
hashMap.set(arr[i], hashMap.has(arr[i]))
}
// 得到 hashMap 后,对其进行遍历,值为 true,对应的键就是重复的数
for(let [key, value] of hashMap.entries()) {
if(value === true) {
result.push(key);
}
}
return result;
}
let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"];
console.log(findRepeatNumInArray(arr));</code></pre>
<h2>找到数组中第一个非重复的数</h2>
<blockquote>[ 1, 1, 2, 2, 3, 4, 4, 5 ]<br>3<br>代码与上一节的差不多,遍历最终得到的<code>hashMap</code>,第一个值为 <code>false</code> 对应的键就是第一个非重复数字:</blockquote>
<pre><code>function findFirstNonRepeat(arr) {
let hashMap = new Map();
for (let i = 0; i < arr.length; i++) {
hashMap.set(arr[i], hashMap.has(arr[i]))
}
// 找到第一个值为 false 的,就代表第一个非重复数,return 就好了
for(let [key, value] of hashMap.entries()) {
if(value === false) {
return key;
}
}
return "全部重复";
}
let arr = [1, 1, 1, 2, 3, 3, 4, 5, 5, "a", "b", "a"];
console.log(findFirstNonRepeat(arr));</code></pre>
<p>总结,三类问题的核心其实就是:利用 <code>Map </code>存储每一个数字的重复情况。</p>
JS面向对象编程之封装
https://segmentfault.com/a/1190000015843072
2018-08-01T11:45:58+08:00
2018-08-01T11:45:58+08:00
Leon
https://segmentfault.com/u/leon07
37
<p>我们所熟知的面向对象语言如 C++、Java 都有类的的概念,类是实例的类型模板,比如<code>Student</code>表示学生这种类型,而不表示任何具体的某个学生,而实例就是根据这个类型创建的一个具体的对象,比如<code>zhangsan</code>、<code>lisi</code>,由类生成对象体现了抽象模板到具体化的过程,这叫做<strong>基于类的面向对象方式</strong>,而 JavaScript 没有类的概念,是<strong>基于原型的面向对象方式</strong>(虽然 Es6 增加了 <code>class</code>,实质是对原型方式的封装)。总结起来就是以下两点:</p>
<ul>
<li>在基于类的面向对象方式中,对象(object)依靠类(class)来产生。</li>
<li>在基于原型的面向对象方式中,对象(object)则是依靠构造函数(constructor)和原型(prototype)构造出来的。</li>
</ul>
<p>面向对象语言的第一个特性毫无疑问是封装,在 JS 中,封装的过程就是把一些属性和方法放到对象中“包裹”起来,那么我们要怎么去封装属性和方法,或者说怎么去创建对象呢(后文统一说创建对象)?下面用逐步推进的方式阐述:</p>
<pre><code>对象字面量 --> 工厂模式 --> 构造函数 --> 原型模式 --> 构造函数+原型模式</code></pre>
<h2>对象字面量</h2>
<p>JS中创建对象最原始的方式有两种:</p>
<ul><li>对象字面量</li></ul>
<pre><code class="JavaScript">var person = {
name: "leon",
age: "20",
greeting: function() {
alert('Hi!');
}
}</code></pre>
<ul><li>为<code>Object</code>实例添加属性方法</li></ul>
<pre><code class="JavaScript">var person = new Object();
person.name = "leon";
person.age = "20";
person.greeting = function() {
alert('Hi!');
};
</code></pre>
<ul>
<li>优点:代码简单</li>
<li>缺点: 创建多个对象会产生大量的代码,编写麻烦,且并没有实例与原型的概念。</li>
<li>解决办法:工厂模式。</li>
</ul>
<h2>工厂模式</h2>
<p>工厂模式是编程领域一种广为人知的设计模式,它抽象了创建具体对象的过程。JS 中创建一个函数,把创建新对象、添加对象属性、返回对象的过程放到这个函数中,用户只需调用函数来生成对象而无需关注对象创建细节,这叫工厂模式:</p>
<pre><code class="JavaScript">function createPerson(name, age) {
var person = new Object();
person.name = name;
person.age = age;
person.greeting = function() {
alert('Hi!');
};
return person;
}
var person1 = createPerson("leon", "20");</code></pre>
<ul>
<li>优点:工厂模式解决了对象字面量创建对象代码重复问题,创建相似对象可以使用同一API。</li>
<li>缺点:因为是调用函创建对象,无法识别对象的类型。</li>
<li>解决办法:构造函数</li>
</ul>
<h2>构造函数</h2>
<p>JS 中构造函数与其他函数的唯一区别,就在于调用它的方式不同。任何函数,只要通过<code>new</code> 操作符来调用,那它就可以作为构造函数。来看下面的例子:</p>
<pre><code class="JavaScript">function Person(name, age) {
this.name = name;
this.age = age;
this.greeting = function() {
alert('Hi!');
};
// return this;
}
var person1 = new Person("leon", "20");
var person2 = new Person("jack", "21");</code></pre>
<p>通过构造函数<code>new</code>一个实例经历了四步:</p>
<ol>
<li>创建一个新对象;</li>
<li>将构造函数内的<code>this</code>绑定到新对象上;</li>
<li>为新对象添加属性和方法;</li>
<li>返回新对象(JS 引擎会默认添加 <code>return this;</code>)。</li>
</ol>
<p>而通过构造函数创建的对象都有一个<code>constructor</code>属性,它是一个指向构造函数本身的指针,因此就可以检测对象的类型啦。:</p>
<pre><code class="JavaScript">alert(person1.constructor === Person) //true
alert(person1 instanceof Person) // true</code></pre>
<p>但是仍然存在问题:</p>
<pre><code>alert(person1.greeting == person2.greeting) //false</code></pre>
<p>同一个构造函数中定义了<code>greeting()</code>,而不同实例上的同名函数却是不相等的,意味着这两个同名函数的内存空间不一致,也就是构造函数中的方法要在每个实例上重新创建一次。这显然是不划算的。</p>
<ul>
<li>优点:解决了类似对象创建问题,且可以检测对象类型。</li>
<li>缺点:构造函数方法要在每个实例上新建一次。</li>
<li>解决办法:原型模式。</li>
</ul>
<h2>原型模式</h2>
<p>终于讲到了原型模式,JS 中每个构造函数都有一个<code>prototype</code>属性,这个属性是一个指针,指向原型对象,而这个原型对象包含了这个构造函数所有实例共享的属性和方法。而实例对象中有一个<code><em>proto</em></code>属性,它指向原型对象,也就是<code>构造函数.prototype == 原型对象 == 对象._proto_</code>,那么对象就可以获取到原型对象中的属性和方法啦。同时,所有对象中都有一个<code>constructor</code>属性,原型对象的<code>constructor</code>指向其对应的构造函数。</p>
<p>使用原型,就意味着我们可以把希望实例共享的属性和方法放到原型对象中去,而不是放在构造函数中,这样每一次通过构造函数<code>new</code>一个实例,原型对象中定义的方法都不会重新创建一次。来看下面的例子:</p>
<pre><code class="JavaScript">function Person() {
}
Person.prototype.name = "leon";
Person.prototype.age = "20";
Person.prototype.greeting = function() {
alert('Hi!');
};
var person1 = new Person();
var person2 = new Person();
alert(person1.name); //"leon"
alert(person2.name); //"leon"
alert(person1.greeting == person2.greeting); //true</code></pre>
<ul>
<li>优点:与单纯使用构造函数不一样,原型对象中的方法不会在实例中重新创建一次,节约内存。</li>
<li>缺点:使用空构造函数,实例 person1 和 person2 的 <code>name</code>都一样了,我们显然不希望所有实例属性方法都一样,它们还是要有自己独有的属性方法。并且如果原型中对象中有引用类型值,实例中获得的都是该值的引用,意味着一个实例修改了这个值,其他实例中的值都会相应改变。</li>
<li>解决办法:构造函数+原型模式组合使用。</li>
</ul>
<p>另外 JS 中还定义了一些与原型相关的属性,这里罗列一下:</p>
<ul><li>
<code>Object.getPrototypeOf()</code>,取得实例的原型对象。</li></ul>
<pre><code>Object.getPrototypeOf(person1);</code></pre>
<ul><li>
<code>isPrototypeOf()</code>,判断是不是一个实例的原型对象。</li></ul>
<pre><code>Person.prototype.isPrototypeOf(person1);</code></pre>
<ul><li>
<code>hasOwnProperty()</code>,检测一个属性是否存在于实例中</li></ul>
<pre><code>person1.hasOwnProperty("name");</code></pre>
<ul><li>
<code>in</code>,判断一个属性是否存在于实例和原型中。</li></ul>
<pre><code>"name" in person1;</code></pre>
<h2>构造函数+原型模式</h2>
<p>最后一种方式就是组合使用构造函数和原型模式,构造函数用于定义实例属性,而共享属性和方法定义在原型对象中。这样每个实例都有自己独有的属性,同时又有对共享方法的引用,节省内存。</p>
<pre><code>function Person(name, age) {
this.name = name;
this.age = age;
}
Person.prototype = {
constructor: Person,
nationality: "China",
greeting: function() {
alert(this.name);
}
}
var person1 = new Person("leon", "20");
var person2 = new Person("jack", "21");
alert(person1.greeting == person2.greeting) //true</code></pre>
<p>上面代码中用对象字面量的形式重写了原型对象,这样相当于创建了一个新的对象,那么它的<code>constructor</code>属性就会指向<code>Object</code>,这里为了让它继续指向构造函数,显示的写上了<code>constructor: Person</code></p>
<p>这种构造函数与原型模式混成的模式,是目前在 JS 中使用最为广泛的一种创建对象的方法。</p>
Event Loop
https://segmentfault.com/a/1190000015832962
2018-07-31T17:07:14+08:00
2018-07-31T17:07:14+08:00
Leon
https://segmentfault.com/u/leon07
35
<p>本文主要参阅了以下两篇文章,对JS的Event Loop运行机制基础知识进行了整理。<br><a href="https://segmentfault.com/a/1190000012925872">从浏览器多进程到JS单线程,JS运行机制最全面的一次梳理</a><br><a href="https://link.segmentfault.com/?enc=UF0Mdpzncomzdhq4n%2FIKCQ%3D%3D.RXi1tRb%2BR%2FGI7F87Iz13hYCQXCJHQ9QjG%2Fc9SB5ZqC2xnWsZU0GfSKVg%2FUhhtk2l59zNzRaZSLLdAlvyaMoYtQ%3D%3D" rel="nofollow">JavaScript 运行机制详解:再谈Event Loop</a></p><h2>背景知识</h2><h3>进程与线程</h3><p>大家都知道JavaScript是单线程的,这就引申出一个问题,进程与线程是什么,他们的区别是什么?<br>先给出进程和线程的定义:</p><ul><li>进程是cpu资源分配的最小单位(是能拥有资源和独立运行的最小单位)</li><li>线程是cpu调度的最小单位(线程是建立在进程的基础上的一次程序运行单位,一个进程中可以有多个线程)<br>用工厂和工人的例子来形象阐述:</li></ul><pre><code>- 进程是一个工厂,工厂有它的独立资源 -> 系统分配的内存(独立的一块内存)
- 工厂之间相互独立 -> 进程之间相互独立
- 线程是工厂中的工人,多个工人协作完成任务 -> 多个线程在进程中协作完成任务
- 工厂内有一个或多个工人 -> 一个进程由一个或多个线程组成
- 工人之间共享工厂的资源 -> 同一进程下的各个线程之间共享进程的内存空间(包括代码段、数据集、堆等)</code></pre><p>补充:</p><ul><li>我们所说的单线程和多线程,是指一个进程内是单一线程还是多线程。</li><li>进程间的通信方式包括: 管道pipe、 命名管道FIFO、消息队列MessageQueue、共享存储SharedMemory、信号量Semaphore、套接字Socket、信号。</li></ul><h3>浏览器是多进程的</h3><p>关于浏览器进程问题可以简单基础三点:</p><ul><li>浏览器是多进程的。</li><li>浏览器之所以能够运行,是因为系统给它的进程分配了资源(cpu、内存)。</li><li>简单点理解,每打开一个Tab页,就相当于创建了一个独立的浏览器进程。</li></ul><p>平时 coding 接触到最多的一个浏览器进程是<strong>浏览器渲染进程</strong>(浏览器内核),它管理着页面渲染。脚本执行,事件处理等。要同时处理这么多事情,<strong>渲染进程显然是多线程的</strong>,它主要包括以下5个常驻线程:</p><ol><li>GUI渲染线程,负责渲染浏览器界面,解析HTML,CSS,构建DOM树和RenderObject树,布局和绘制等。</li><li>JS引擎线程,也称为JS内核,负责处理Javascript脚本程序,(例如V8引擎)。</li><li>事件触发线程,用来控制事件循环(可以理解为,JS引擎线程自己都忙不过来,需要浏览器另开线程协助)。</li><li>定时触发器线程,浏览器定时计数器并不是由JavaScript引擎计数的,(因为JavaScript引擎是单线程的, 如果处于阻塞线程状态就会影响记计时的准确),JS中常用的<code>setInterval</code>和<code>setTimeout</code>就归这个线程管理。</li><li>异步http请求线程,也就是<code>ajax</code>发出http请求后,接收响应、检测状态变更等都是这个线程管理的。</li></ol><p>我们常说的JavaScript是单线程的,其实就是说的JS引擎是单线程的,它仅仅是浏览器渲染进程种的一个线程。为什么呢?因为JavaScript的主要作用是与用户互动,以及操作<code>DOM</code>,如果JavaScript有两个线程,一个线程对一个<code>DOM</code>节点执行 A 操作,另一个线程这个<code>DOM</code>节点执行 B 操作,那么就会起冲突,所以JavaScript在前端的应用就注定了它是单线程的。</p><p>然而JavaScript的单线程特性就注定我们不用它去完成密集的 cpu 运算,因为密集 cpu 运算耗时过长,阻塞页面渲染。为了解决这个问题,HTML5提出 Web Worker 标准,允许JavaScript脚本创建多个线程,但是子线程完全受主线程控制,且不得操作<code>DOM</code>。</p><h2>浏览器中的Event Loop</h2><p>JavaScript 是单线程的带来的问题是:所有任务都必须同步执行,问题就出现了,很多 I/O 过程是非常耗时的(如http 请求数据),如果要等到 I/O 过程结束再执行后续任务,就会出现页面的卡顿、cpu 的闲置。于是异步的任务就出现了,异步任务是指挂起处于等待中的任务,继续执行同步任务,等到结果返回再去继续执行被挂起的任务。于是,JavaScript 的任务可以分为同步任务和异步任务。下面就引出 Event Loop 机制:</p><ul><li>所有同步任务都在主线程上执行,形成一个执行栈</li><li>主线程之外,事件触发线程管理着一个任务队列,只要异步任务有了运行结果,就在任务队列之中放置一个回调函数。</li><li>一旦执行栈中的所有同步任务执行完毕(此时JS引擎空闲),系统就会读取任务队列,将可运行的异步任务添加到执行栈中,开始执行。</li></ul><p><img src="/img/bV2J44" alt="clipboard.png" title="clipboard.png"></p><p>如上图所示,执行栈中的代码会调用一个异步的API,它们会在任务队列中添加各种事件(或者说回调函数),另外用户的操作如<code>click</code>、<code>mousedown</code>等都会在任务队列中添加事件。只要执行栈中的代码执行完毕,主线程就会去读取任务队列,将可执行的回调函数放到执行栈中执行。</p><p>总结一下:</p><pre><code>执行栈执行完毕 -> 主线程读取任务队列,并执行回调函数 -> 执行栈执行完毕 -> 主线程读取任务队列,并执行回调函数 ...
</code></pre><p>这个过程一直循环下去,所以就叫事件循环(Event Loop)。</p><h2>宏任务和微任务</h2><p>先看一道经典的面试题目:</p><pre><code class="javascript">console.log('script start');
setTimeout(function() {
console.log('setTimeout');
}, 0);
Promise.resolve().then(function() {
console.log('promise1');
}).then(function() {
console.log('promise2');
});
console.log('script end');</code></pre><p>输出结果为:</p><pre><code>script start
script end
promise1
promise2
setTimeout</code></pre><p>造成以上执行顺序的原因是Event Loop中的异步任务其实可以进一步细化为宏任务(macrotask)和微任务(microtask)。<br>常见的 macro-task 比如: setTimeout、setInterval、 setImmediate、 script(整体代码)、I/O 操作等。<br>常见的 micro-task 比如: process.nextTick、Promise、MutationObserver 等。<br>注意:script(整体代码)它也是一个宏任务;此外,宏任务中的 setImmediate、微任务中的 process.nextTick 这些都是 Node 独有的。</p><p>为了进一步区分,将第一小节中的任务队列细分为两个:宏任务队列和微任务队列。EventLoop的执行机制也可以进一步细化:</p><ul><li>所有同步任务都在主线程上执行,形成一个执行栈,每次执行栈执行的代码整体就是一个宏任务</li><li>执行栈中的同步代码执行过程中会产生新的宏任务和微任务,它们会被分别添加到宏任务队列和微任务队列中</li><li>执行栈中同步任务执行完后,会先取出微任务队列中的所有微任务,将其执行完;然后执行页面渲染;然后再从宏任务队列中取出一个宏任务放入执行栈执行</li></ul><p>大概步骤如下:</p><pre><code>执行栈执行完毕 -> 读取微任务队列所有任务,执行 -> 渲染 -> 读取宏任务队列中的一个宏任务,放入执行栈执行 -> 执行栈执行完毕 ->...
</code></pre><p>需要注意的点有两个:</p><ul><li>Event-Loop每次从宏任务队列中只会取出一个宏任务,而对于微任务队列则会将其清空</li><li>微任务的执行时机在渲染之前,宏任务的执行时机在渲染之后</li></ul><h2>setTimeout 和 setInterval</h2><p>前面提到了浏览器的定时触发器线程,它的主要作用就是计时,<code>setTimeout</code> 和 <code>setInterval</code> 就由它来控制,原理就是到达设置时间后,往任务队列中添加这两个函数中指定的回调函数。</p><p><code>setTimeout()</code> 方法用于在指定的毫秒数后调用函数或计算表达式。但是需要注意的是,实际是计时结束后定时触发器线程才会将回调函数放到任务队列中去,此时任务队列中这个回调之前可能已经有一些事件待处理,并且一定要执行栈的任务执行完后才会开始执行任务队列中的任务,所以 <code>setTimeout()</code> 中回调开始执行的时间是:<code>执行栈执行时间 + 任务队列前方回调执行时间 + 延迟时间</code></p><p><code>setInterval()</code> 方法可按照指定的时间间隔来周期性调用函数或计算表达式。它的问题在于:每次都精确的隔一段时间将一个回调放到任务队列中,并没有考虑到内部回调函数执行所需时间,这就会导致两种问题:</p><ul><li>回调函数执行需要时间,两个函数执行的时间间隔会小于设定值;</li><li>如果回调函数执行时间大于设定间隔,就会出现上一个加入任务队列中的回调还没执行完,下一个回调就被加入任务队列了,就会出现累计效应,即后面的回调会连续执行。</li></ul><h2>Node中的Event Loop</h2><p>浏览器的 Event-Loop 由各个浏览器自己实现;而 Node 的 Event-Loop 由 libuv 来实现。</p><p>Node中的Event Loop运行机制大致如下:</p><ol><li>执行全局的 Script 代码(与浏览器无差);</li><li>把微任务队列清空:注意,Node 清空微任务队列的手法比较特别。在浏览器中,我们只有一个微任务队列需要接受处理;但在 Node 中,有两类微任务队列:next-tick 队列和其它队列。其中这个 next-tick 队列,专门用来收敛 process.nextTick 派发的异步任务。在清空队列时,优先清空 next-tick 队列中的任务,随后才会清空其它微任务;</li><li>开始执行 macro-task(宏任务)。注意,Node 执行宏任务的方式与浏览器不同:在浏览器中,我们每次出队并执行一个宏任务;而在 Node 中,我们每次会尝试清空当前阶段对应宏任务队列里的所有任务(除非达到了系统限制);</li><li>步骤3开始,会进入 3 -> 2 -> 3 -> 2…的循环。</li></ol><p>这里有一个重要的区别,在node11之前,每一次Event-Loop中是尝试清空宏任务队列中的所有宏任务,而node11后的Event-Loop机制已经与浏览器趋同,都是每个循环都只执行宏任务队列中的一个任务,然后立即去执行微任务队列。如下题:</p><pre><code class="javascript">setTimeout(() => {
console.log('timeout1');
}, 0);
setTimeout(() => {
console.log('timeout2');
Promise.resolve().then(function() {
console.log('promise1');
});
}, 0);
setTimeout(() => {
console.log('timeout3')
}, 0)</code></pre><p>node11之前的输出为:</p><pre><code>timeout1
timeout2
timeout3
promise1</code></pre><p>而node11后和浏览器的输出为:</p><pre><code>timeout1
timeout2
promise1
timeout3</code></pre>
一张图理解Http缓存
https://segmentfault.com/a/1190000015816331
2018-07-30T14:55:28+08:00
2018-07-30T14:55:28+08:00
Leon
https://segmentfault.com/u/leon07
41
<p>参阅了一些浏览器缓存的资料,本文通过一张图来归纳总结其过程。</p>
<p>浏览器第一次向一个web服务器发起<code>http</code>请求后,服务器会返回请求的资源,并且在响应头中添加一些有关缓存的字段如:<code>Cache-Control</code>、<code>Expires</code>、<code>Last-Modified</code>、<code>ETag</code>、<code>Date</code>等等。之后浏览器再向该服务器请求该资源就可以视情况使用<b>强缓存</b>和<b>协商缓存</b>。</p>
<ul>
<li>强缓存:浏览器直接从本地缓存中获取数据,不与服务器进行交互。</li>
<li>协商缓存:浏览器发送请求到服务器,服务器判定是否可使用本地缓存。</li>
<li>联系与区别:两种缓存方式最终使用的都是本地缓存;前者无需与服务器交互,后者需要。</li>
</ul>
<p>下面假定浏览器已经访问了服务器,服务器返回了缓存相关的头部字段且浏览器已对相关资源做好缓存。通过下图来分析强缓存和协商缓存:</p>
<p><img src="/img/bVbewMT?w=983&h=680" alt="clipboard.png" title="clipboard.png"></p>
<h3>强缓存</h3>
<p>如图红线所示的过程代表强缓存。用户发起了一个<code>http</code>请求后,浏览器发现先本地已有所请求资源的缓存,便开始检查缓存是否过期。有两个http头部字段控制缓存的有效期:<code>Expires</code>和<code>Cache-Control</code>,浏览器是根据以下两步来判定缓存是否过期的:</p>
<ol>
<li>查看缓存是否有<code>Cache-Control</code>的<code>s-maxage</code>或<code>max-age</code>指令,若有,则使用响应报文生成时间<code>Date + s-maxage/max-age</code>获得过期时间,再与当前时间进行对比(<code>s-maxage</code>适用于多用户使用的公共缓存服务器);</li>
<li>如果没有<code>Cache-Control</code>的<code>s-maxage</code>或<code>max-age</code>指令,则比较<code>Expires</code>中的过期时间与当前时间。<code>Expires</code>是一个绝对时间。</li>
</ol>
<p><strong>注意</strong>,在HTTP/1.1中,当首部字段<code>Cache-Control</code>有指定<code>s-maxage</code>或<code>max-age</code>指令,比起首部字段<code>Expires</code>,会优先处理<code>s-maxage</code>或<code>max-age</code>。</p>
<p>另外下面列几个<code>Cache-Control</code>的常用指令:</p>
<ul>
<li>
<code>no-cache</code>:含义是不使用本地缓存,需要使用协商缓存,也就是先与服务器确认缓存是否可用。</li>
<li>
<code>no-store</code>:禁用缓存。</li>
<li>
<code>public</code>:表明其他用户也可使用缓存,适用于公共缓存服务器的情况。</li>
<li>
<code>private</code>:表明只有特定用户才能使用缓存,适用于公共缓存服务器的情况。</li>
</ul>
<p>经过上述两步判断后,若缓存未过期,返回状态码为<code>200</code>,则直接从本地读取缓存,这就完成了整个强缓存过程;如果缓存过期,则进入协商缓存或服务器返回新资源过程。</p>
<h3>协商缓存</h3>
<p>当浏览器发现缓存过期后,缓存并不一定不能使用了,因为服务器端的资源可能仍然没有改变,所以需要与服务器协商,让服务器判断本地缓存是否还能使用。此时浏览器会判断缓存中是否有<code>ETag</code>或<code>Last-Modified</code>字段,如果没有,则发起一个http请求,服务器根据请求返回资源;如果有这两个字段,则在请求头中添加<code>If-None-Match</code>字段(有<code>ETag</code>字段的话添加)、<code>If-Modified-Since</code>字段(有<code>Last-Modified</code>字段的话添加)。<strong>注意:</strong>如果同时发送<code>If-None-Match</code> 、<code>If-Modified-Since</code>字段,服务器只要比较<code>If-None-Match</code>和<code>ETag</code>的内容是否一致即可;如果内容一致,服务器认为缓存仍然可用,则返回状态码<code>304</code>,浏览器直接读取本地缓存,这就完成了协商缓存的过程,也就是图中的蓝线;如果内容不一致,则视情况返回其他状态码,并返回所请求资源。下面详细解释下这个过程:</p>
<h4>1.<code>ETag</code>和<code>If-None-Match</code>
</h4>
<p>二者的值都是服务器为每份资源分配的唯一标识字符串。</p>
<ul>
<li>浏览器请求资源,服务器会在响应报文头中加入<code>ETag</code>字段。资源更新时,服务器端的<code>ETag</code>值也随之更新;</li>
<li>浏览器再次请求资源时,会在请求报文头中添加<code>If-None-Match</code>字段,它的值就是上次响应报文中的<code>ETag</code>的值;</li>
<li>服务器会比对<code>ETag</code>与<code>If-None-Match</code>的值是否一致,如果不一致,服务器则接受请求,返回更新后的资源;如果一致,表明资源未更新,则返回状态码为<code>304</code>的响应,可继续使用本地缓存,要注意的是,此时响应头会加上<code>ETag</code>字段,即使它没有变化。</li>
</ul>
<h4>2.<code>Last-Modified</code>和<code>If-Modified-Since</code>
</h4>
<p>二者的值都是GMT格式的时间字符串。</p>
<ul>
<li>浏览器第一次向服务器请求资源后,服务器会在响应头中加上<code>Last-Modified</code>字段,表明该资源最后一次的修改时间;</li>
<li>浏览器再次请求该资源时,会在请求报文头中添加<code>If-Modified-Since</code>字段,它的值就是上次服务器响应报文中的<code>Last-Modified</code>的值;</li>
<li>服务器会比对<code>Last-Modified</code>与<code>If-Modified-Since</code>的值是否一致,如果不一致,服务器则接受请求,返回更新后的资源;如果一致,表明资源未更新,则返回状态码为<code>304</code>的响应,可继续使用本地缓存,与<code>ETag</code>不同的是:此时响应头中不会再添加<code>Last-Modified</code>字段。</li>
</ul>
<h4>3.<code>ETag</code>较之<code>Last-Modified</code>的优势</h4>
<p>以下内容引用于:<a href="https://link.segmentfault.com/?enc=wfa6WzE1kqU1aYIw8oMW8Q%3D%3D.plLCM0YP0CNj85wXf7RvedLMEh7a8qrj4qU6yeBWCfw9qmHSYtJ5FL1wSxj%2BxB0A" rel="nofollow">http协商缓存VS强缓存</a></p>
<p>你可能会觉得使用<code>Last-Modified</code>已经足以让浏览器知道本地的缓存副本是否足够新,为什么还需要<code>ETag</code>呢?<code>HTTP1.1</code>中<code>ETag</code>的出现主要是为了解决几个<code>Last-Modified</code>比较难解决的问题:</p>
<ul>
<li>一些文件也许会周期性的更改,但是他的内容并不改变(仅仅改变的修改时间),这个时候我们并不希望客户端认为这个文件被修改了,而重新<code>GET</code>;</li>
<li>某些文件修改非常频繁,比如在秒以下的时间内进行修改,(比方说1s内修改了N次),<code>If-Modified-Since</code>能检查到的粒度是s级的,这种修改无法判断(或者说<code>UNIX</code>记录<code>MTIME</code>只能精确到秒);</li>
<li>某些服务器不能精确的得到文件的最后修改时间。</li>
</ul>
<p>这时,利用<code>ETag</code>能够更加准确的控制缓存,因为<code>ETag</code>是服务器自动生成的资源在服务器端的唯一标识符,资源每次变动,都会生成新的<code>ETag</code>值。<code>Last-Modified</code>与<code>ETag</code>是可以一起使用的,但服务器会优先验证<code>ETag</code>。</p>
<h3>用户行为</h3>
<p>最后附一张图说明用户行为对浏览器缓存的影响:<br><img src="/img/bVbfafi?w=748&h=185" alt="clipboard.png" title="clipboard.png"></p>
Ajax基础知识梳理
https://segmentfault.com/a/1190000015668383
2018-07-17T20:25:07+08:00
2018-07-17T20:25:07+08:00
Leon
https://segmentfault.com/u/leon07
329
<p><code>Ajax</code>用一句话来说就是无须刷新页面即可从服务器取得数据。注意,虽然<code>Ajax</code>翻译过来叫异步<code>JavaScript</code>与<code>XML</code>,但是获得的数据不一定是<code>XML</code>数据,现在服务器端返回的都是<code>JSON</code>格式的文件。</p>
<h2>完整的<code>Ajax</code>请求过程</h2>
<p>完整的<code>Ajax</code>请求过程</p>
<blockquote><ol>
<li>创建<code>XMLHttpRequest</code>实例</li>
<li>发出<code>HTTP</code>请求</li>
<li>接收服务器传回的数据</li>
<li>更新网页数据</li>
</ol></blockquote>
<p>下面先看一个红宝书上给出的发起<code>Ajax</code>请求的例子,<code>API</code>的用法在后面章节给出。</p>
<pre><code class="JavaScript">var xhr = new XMLHttpRequest(); // 创建XMLHttpRequest实例
xhr.onreadystatechange = function(){
if (xhr.readyState == 4){ // 判断请求响应过程阶段,4 阶段代表已接收到数据
if (xhr.status >=200 && xhr.status < 300 || xhr.status == 304) { // 校验HTTP状态码
console.log(xhr.responseText); // 输出响应的文本
} else {
console.error(xhr.status, xhr.statusText); // 打印其他HTTP状态码
}
}
};
xhr.open('get', 'example.txt', true); // 初始化xhr实例,或者说启动请求
xhr.send(null); // 设置HTTP请求携带参数,null为不带参数</code></pre>
<h2>
<code> Ajax</code>请求过程详解</h2>
<h3>1. 创建<code>XMLHttpRequest</code>实例</h3>
<p>从上面的的代码可以看出,创建一个<code>XHR</code>实例方式为:</p>
<pre><code class="JavaScript">var xhr = new XMLHttpRequest();</code></pre>
<h3>2. 发出HTTP请求</h3>
<p>实例创建好后,首先需要启动一个<code>HTTP</code>请求,使用<code>XHR</code>的<code>open()</code>方法,<code>open</code>方法接受三个参数</p>
<pre><code class="JavaScript">XMLHttpRequest.open(method, url, isAsync)
// 例如
xhr.open('get', 'http://www.baidu.com', true)</code></pre>
<p>第一个参数为<code>http</code>请求使用方法,如('get','post'等),第二是参数是请求的<code>url</code>, 第三个参数代表是否异步发送请求(可选)。调用<code>open()</code>方法后会启动一个<code>http</code>请求,但它不会立即发送请求,处于待命状态。需要注意的是:请求的<code>url</code>必须要跟请求源域(origin)同域,也就是说协议、域名、端口号要一致,跨域请求要使用别的方法。接着调用<code>send()</code>方法就会发出这个<code>http</code>请求。</p>
<pre><code class="JavaScript">xhr.open('get', 'http://www.baidu.com', true)
xhr.send(null)</code></pre>
<p><code>send()</code>方法接受一个参数,为<code>http</code>请求发送的数据(通常用于'post'方法),如果为<code>null</code>,表示不发送数据。至此,一个异步的<code>http</code>请求就发送到了服务器。</p>
<h3>3. 接收服务器传回的数据</h3>
<h4>3.1 发送同步请求</h4>
<p>如果将<code>open</code>方法的第三个参数设为<code>false</code>,即为同步请求,当收到服务器的响应后,相应的数据会自动填充到<code>XHR</code>对象的属性中,主要包括以下四个:</p>
<ul>
<li>
<code>responseText</code>:作为响应主体被返回的文本。</li>
<li>
<code>responseXML</code>: 响应返回的<code>XML</code>文档,能接收到的前提是,响应的<code>Content-Type</code>字段的值为<br><code>text/xml</code>或者<code>application/xml</code>。</li>
<li>
<code>status</code>: <code>HTTP</code>状态码。</li>
<li>
<code>statusText</code>: <code>HTTP</code>状态码说明。</li>
</ul>
<p>当客户端收到以上信息后,首先要判断<code>HTTP</code>状态码来确认响应是否成功,状态码在200-300之间表示请求成功,同时304代表请求资源未被修改,可使用浏览器本地缓存。如果成功就可以获取响应报文主体中的数据了。</p>
<pre><code class="JavaScript">xhr.open('get', 'http://www.baidu.com', false)
xhr.send(null)
if (xhr.status >=200 && xhr.status < 300 || xhr.status == 304) { // 校验HTTP状态码
console.log(xhr.responseText); // 输出响应的文本
} else {
console.error(xhr.status, xhr.statusText); // 打印其他HTTP状态码
}</code></pre>
<h4>3.2 发送异步请求</h4>
<p>如果将<code>open</code>方法的第三个参数设为<code>true</code>,即为异步请求。那么就需要一个事件来通知程序异步请求的结果是否返回。<code>XHR</code>对象中的<code>readyState</code>属性,表示请求/响应整个过程所处的阶段,它有五个值分为对应五个阶段:</p>
<ul>
<li>0:未初始化。未调用<code>open()</code>方法。</li>
<li>1:启动。已经调用<code>open()</code>方法,但未调用<code>send()</code>方法。</li>
<li>2:发送。已调用<code>send()</code>方法,但未收到响应。</li>
<li>3: 接收。已经接收到部分响应数据。</li>
<li>4:完成。已经接受到全部响应数据。</li>
</ul>
<p><code>readyState</code>的值每变化一次,都会触发一次<code>readStatechange</code>事件,我们定义一个事件处理函数<code>onreadStatechange()</code>,并监听<code>readyState == 4</code>状态,就可以得知响应数据已全部收到,并进行下一步操作。那么就是文章开头给出的代码:</p>
<pre><code class="JavaScript">var xhr = new XMLHttpRequest(); // 创建XMLHttpRequest实例
xhr.onreadystatechange = function(){
if (xhr.readyState == 4){ // 判断请求响应过程阶段,4 阶段代表已接收到数据
if (xhr.status >=200 && xhr.status < 300 || xhr.status == 304) { // 校验HTTP状态码
console.log(xhr.responseText); // 输出响应的文本
} else {
console.error(xhr.status, xhr.statusText); // 打印其他HTTP状态码
}
}
};
xhr.open('get', 'example.txt', true); // 初始化xhr实例,或者说启动请求
xhr.send(null); // 设置HTTP请求携带参数,null为不带参数</code></pre>
<h2>补充XHR中三个有用的事件</h2>
<h3>
<code>timeout</code>事件</h3>
<p>当超出了设置时间还未收到响应,就会触发<code>timeout</code>事件,进而调用<code>ontimeout</code>事件处理程序。同时<code>timeout</code>也是<code>XHR</code>的一个属性,用于设置这个时间阈值。下面是用法:</p>
<pre><code class="JavaScript">xhr.ontimeout = function() {
alert('timeout!')
}
xhr.open('get', 'http://www.baidu.com', true)
xhr.timeout = 1000 // 时间阈值设为1秒
xhr.send(null)</code></pre>
<h3>
<code>load</code>事件</h3>
<p><code>load</code>事件用于简化对<code>readState</code>值的判断,响应数据全部接收完毕后(也就是<code>readState == 4</code>)会触发<code>load</code>事件,使用<code>onload</code>事件处理函数进行后续操作,<code>onload</code>会接收一个<code>event</code>对象,它的<code>target</code>属性等于<code>XHR</code>对象,当然我们在定义这个事件处理函数时也可以不传入这个参数,来看下面的用法:</p>
<pre><code class="JavaScript">var xhr = new XMLHttpRequest()
xhr.onload = function () {
if(xhr.status >=200 && xhr.status < 300 || xhr.status == 304) {
console.log(xhr.responseText); // 输出响应的文本
} else {
console.error(xhr.status, xhr.statusText); // 打印其他HTTP状态码
}
}
xhr.open('get', 'http://www.baidu.com', true)
xhr.send(null)</code></pre>
<p>这样就不用去关心<code>readyState</code>值的变化情况了。当然如果想在特定<code>readyState</code>值上做一些逻辑处理,还是要用之前的方法。</p>
<h3>
<code>progress</code>事件</h3>
<p>这个是很有用的一个事件,<code>progress</code>事件会在浏览器接收数据期间周期触发,代表整个请求过程的进度,它的事件处理程序<code>onprogress</code>接收一个<code>event</code>对象,<code>event.target</code>是<code>XHR</code>对象,另外<code>event</code>还有三个属性:</p>
<ul>
<li>
<code>lengthComputable</code>:Boolean值,进度信息是否可用。</li>
<li>
<code>position</code>:已经接收到的字节数。</li>
<li>
<code>totalSize</code>:总共要接收的字节数,被定义在响应报文的<code>Content-Length</code>字段中。</li>
</ul>
<p>如果响应报文中有<code>Content-Length</code>字段,那么我们就可以计算当前时刻响应数据的加载进度了,这也是之前看到的一个面试题。看下面的代码:</p>
<pre><code class="JavaScript">
xhr.onprogress = function(event) {
if(event.lengthComputable) {
console.log(`Received: ${(event.position/event.totalSize).toFixed(4)*100}%`);
}
}</code></pre>
<p>其他还有很多有用的API,如<code>FormData</code>表单序列化,<code>overrideMimeType()</code>重写<code>XHR</code>响应的<code>MIME</code>类型等等,后面慢慢更新。</p>
JS中的一些坑(持续更新)
https://segmentfault.com/a/1190000015490193
2018-07-05T13:20:15+08:00
2018-07-05T13:20:15+08:00
Leon
https://segmentfault.com/u/leon07
1
<h4>1. 基本类型与引用类型</h4>
<p>牛客网上的一个题:</p>
<pre><code class="JavaScript">var arr=[{a:1},{}];
arr.forEach(function(item,idx){
item.b=idx;
});</code></pre>
<p>执行完上面代码后,arr 的值是?</p>
<p>觉得 forEach 方法中的 item 参数是按值传递,所以不会改变原来的 arr,答案为:[{a:1},{}] 。正确答案是:[{a:1, b:0},{b:1}] 。这里忽略了一个重要的点,即函数参数虽然是按值传递,不是按引用传递,但是基本类型和引用类型本身的差别被忽略了。</p>
<p>基本类型占用的内存空间不大,所以把变量 a 赋给 b,是把 a 的值拷贝一份给b,a、b 所在的内存空间是独立的,所以修改 a 不会影响 b:</p>
<pre><code class="JavaScript">var a = 1;
var b = a;
a = 2;
a; // 2
b; // 1</code></pre>
<p>但是引用类型就不一样了,因为引用类型存储的内容可能很多,比如将对象 a 赋值给对象 b,如果是简单拷贝一遍内容,可能会带来很大的内存开销,所以这种情况,对象a 和 b 实际上指向同一个内存空间,赋值操作实际上是将 a 的内存地址复制一份给 b,所以 a 对象的属性改变也会影响到 b 对象:</p>
<pre><code class="JavaScript">var obja = {
a: 1,
b: 2
}
var objb = obja
obja.a = 2;
obja; // {a:2, b:2}
objb; // {a:2, b:2}</code></pre>
<p>那么就很好理解啦,forEach 中的参数 item 如果是一个引用类型,就要警惕啦,虽然是按值传递,但是传递的值是内存地址。</p>
<h4>2. NaN问题</h4>
<p><<JavaScript高级程序设计(第3版)>>第29页NaN部分写到:</p>
<blockquote>首先,任何涉及NaN的操作(例如 NaN/10),都会返回NaN。</blockquote>
<p>这一点写错了,加性操作符就是个特例:</p>
<pre><code class="JavaScript">console.log(NaN + 'A'); // "NaNA"
console.log(NaN + NaN); // NaN
console.log(NaN + 1); // NaN</code></pre>
<p>加性操作符中如果有一个操作数是字符串,即便有一个NaN,也会将其转为字符串进行拼接。</p>
<p>而对于减性操作符,书中所写是对的:</p>
<pre><code class="JavaScript">console.log(NaN - 'A'); // NaN
console.log(NaN - NaN); // NaN
console.log(NaN - 1); // NaN</code></pre>
从斐波那契数列看递归和动态规划
https://segmentfault.com/a/1190000015489981
2018-07-05T13:11:01+08:00
2018-07-05T13:11:01+08:00
Leon
https://segmentfault.com/u/leon07
3
<p>大名鼎鼎的斐波那契数列:<code>0,1,1,2,3,5,8,13,21...</code>使用数学归纳法可以看出其规律为:<code>f(n) = f(n-1) + f(n-2)</code>。</p>
<h3>递归</h3>
<p>下面首先直接使用递归(JavaScript实现)来求解第 n 项:<code>f(n)</code></p>
<pre><code class="JavaScript">// 直接使用递归
let num = 0; // 用来记录fib函数执行次数,执行一次加一
function fib(n) {
num ++;
if(n === 0) {
return 0;
}
if(n === 1) {
return 1;
}
return fib(n-1) + fib(n-2);
}
console.time("time used");
console.log(`result is: ${fib(40)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("time used");</code></pre>
<p>以 n = 40 为例,这里我们记录了 fib 函数总共调用的次数以及运算总共耗时,结果如下:</p>
<p><img src="/img/bVbc9NL?w=209&h=60" alt="clipboard.png" title="clipboard.png"></p>
<p>可以看出,即便仅仅是计算第 40 项,<code>fib</code> 函数调用的次数高达3亿多次,时间是2477ms。因为每一次 <code>fib</code> 函数的调用都会有两个子 fib 函数调用,那么时间复杂度是 O(2^n) ,呈指数级增长,这显然不是一个好算法。怎么优化呢?以一个简单的例子画图分析一下:</p>
<p><img src="/img/bVbc9N4?w=808&h=459" alt="clipboard.png" title="clipboard.png"></p>
<p>上图是 n = 5 时的递归树,可以看出虚线框中 f(2) 的计算用到了三次,同样的 f(3) 的计算用到了两次,显然我们执行了非常多的重复运算。那么很自然的想到,把每一个状态的计算结果都存起来,后面遇到相同的状态就可以直接使用了。</p>
<h3>记忆化搜索递归(自顶向下)</h3>
<p>代码如下,这里第三行 new 了一个长度为 n+1 的数组,用于存放 f(0) 到 f(n) 这 n+1 个状态的计算结果:</p>
<pre><code class="JavaScript">// 记忆化搜索,记录每次计算的结果
let num = 0; // 用来记录fib函数执行次数,执行一次加一
let totalnum = 40;
let memory = new Array(totalnum).fill(-1);
function fib(n) {
num++;
if(n === 0) {
return 0;
}
if(n === 1) {
return 1;
}
if(memory[n] === -1) {
memory[n] = fib(n-1) + fib(n-2); // 如果前面已经得到,直接使用
}
return memory[n];
}
console.time("timer");
console.log(`result is: ${fib(totalnum)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("timer");</code></pre>
<p>同样 n = 40,结果如下:</p>
<p><img src="/img/bVbc9Og?w=180&h=59" alt="clipboard.png" title="clipboard.png"></p>
<p>可以看处出优化是十分可观的,记录下每一次子调用的结果,让算法复杂度从 O(2^n) 变成了 O(n)。这其实就是动态规划的思想。什么是动态规划?</p>
<blockquote>Dynamic programming is when you use past knowledge to make solving a future problem easier.(动态规划是用已知项去更好的求解未知项)</blockquote>
<blockquote>Dynamic programming is a technique used to avoid computing multiple time the same subproblem in a recursive algorithm.</blockquote>
<blockquote>将原问题拆解成若干子问题,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。</blockquote>
<p>以上是我看到的两个很好的定义。记忆化搜索递归求斐波那契数列显然是使用了动态规划的思想,并且,这是一种自顶向下的求解方式(我们没有从最基本的问题开始求解,对于 <code>f(n) = f(n-1) + f(n-2)</code> ,先假定<code> f(n-1) </code>和 <code>f(n-2) </code>是已知的)。另外我们可以采用另一种自下向上的方式求解,即迭代,这也是一种动态规划的思想。</p>
<h3>迭代法(自下向上)</h3>
<p>代码如下,我们使用迭代,<code>f(2) = f(1) + f(0),f(3) = f(2) + f(1),...</code>,显然这是一种从基础问题开始的自下向上的解决方法:</p>
<pre><code class="JavaScript">let num = 0;
function fib(n) {
num++;
let memory = new Array(n);
memory[0] = 1;
memory[1] = 1;
for(let i = 2; i <= n; i++) {
memory[i] = memory[i-1] + memory[i-2];
}
return memory[n];
}
console.time("timer");
console.log(`result is: ${fib(40)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("timer");</code></pre>
<p>结果如下,显然使用迭代的方法复杂度也为 O(n):</p>
<p><img src="/img/bVbc9Ot?w=179&h=63" alt="clipboard.png" title="clipboard.png"></p>
<h3>小结</h3>
<p>动态规划就是:将原问题拆解成若干子问题,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。对于斐波那契数列的求解,有自顶向下的记忆化搜索递归和自下向上的迭代法,他们都使用了动态规划的思想。</p>
<p>参考链接:<br><a href="https://link.segmentfault.com/?enc=OOh5zVoHFyNOFbfHWdhN5Q%3D%3D.3Pdz9%2Bd3O3E3b%2Ft9vfMt%2BH4rD%2FSwkcuYh4pl%2BXdzrDRtoChw3CFL1hleDhrmSaz1sPYrUUpCPiGzq2rImycV5fmeu6mJX5FSlhwxnTdiqZA%3D" rel="nofollow">https://stackoverflow.com/que...</a></p>
JS实现希尔排序
https://segmentfault.com/a/1190000015489853
2018-07-05T12:58:08+08:00
2018-07-05T12:58:08+08:00
Leon
https://segmentfault.com/u/leon07
5
<p>希尔排序本质上是一种插入排序,但是对数列进行了等间隔分组处理,在每一组中做插入排序,这一优化使得时间复杂度降到了O(n^2)以下。</p>
<h3>基本思想</h3>
<p>希尔排序是按一定的间隔对数列进行分组,然后在每一个分组中做插入排序;随后逐次缩小间隔,在每一个分组中做插入排序...直到间隔等于1,做一次插入排序后结束。</p>
<p>那么问题来了,间隔应该取多大,怎么缩小?通常我们去取初始间隔为数列长度的一半:gap = length/2,以 gap = gap/2 的方式缩小,下面详细图解整个过程。</p>
<p>原始数组数组如下:</p>
<p><img src="/img/bVbc9Mc?w=475&h=61" alt="clipboard.png" title="clipboard.png"></p>
<hr>
<p>首先取间隔为 gap = length/2 = 4,将数组分为如下的4组,对每一组实施插入排序:</p>
<p><img src="/img/bVbc9Mj?w=486&h=175" alt="clipboard.png" title="clipboard.png"></p>
<hr>
<p>第一次排序,每一组较小的元素都移到了相对靠前的位置(这个状态可以叫 n-sorted,即以n为gap分组有序),可以想象相对有序的数组可能更有利于后面的排序。接着继续分组,gap = gap/2 = 2,对每一组实施插入排序:</p>
<p><img src="/img/bVbc9Mo?w=482&h=160" alt="clipboard.png" title="clipboard.png"></p>
<hr>
<p>继续对数组分组,gap = gap/2 = 1,即所有元素组成一组,做插入排序完成算法:</p>
<p><img src="/img/bVbc9Mr?w=476&h=128" alt="clipboard.png" title="clipboard.png"></p>
<p><img src="/img/bVbc9Mt?w=490&h=94" alt="clipboard.png" title="clipboard.png"></p>
<h3>代码实现</h3>
<p>内层循环使用的插入排序与普通的插入排序基本一致,只是每次移动的步长变为 gap 而不是 1:</p>
<pre><code class="JavaScript">// shellSort
function shellSort(arr) {
for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
// 内层循环与插入排序的写法基本一致,只是每次移动的步长变为 gap
for(let i = gap; i < arr.length; i++) {
let j = i;
let temp = arr[j];
for(; j> 0; j -= gap) {
if(temp >= arr[j-gap]) {
break;
}
arr[j] = arr[j-gap];
}
arr[j] = temp;
}
}
return arr;
}
// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
alert(shellSort(arr));</code></pre>
Git常用命令(持续更新)
https://segmentfault.com/a/1190000015489808
2018-07-05T12:51:28+08:00
2018-07-05T12:51:28+08:00
Leon
https://segmentfault.com/u/leon07
18
<ul>
<li>
<p>把文件存入本地暂存区:</p>
<ul>
<li>把新建文件、修改过的文件存入本地暂存区:<code>git add .</code>
</li>
<li>把修改过的文件、删除的文件存入本地暂存区:<code>git add -u</code>
</li>
<li>把新建文件、修改过的文件、删除的文件存入本地暂存区: <code>git add -A</code>,相当于上两条之和</li>
</ul>
</li>
<li>将本地暂存区的文件推送到本地库:<code>git commit -m '修改提示'</code>
</li>
<li>查看当前 git 状态:<code>git status</code>
</li>
<li>从 github 上克隆项目: <code>git clone <github url></code>
</li>
<li>
<p>将本地库文件的修改推送到绑定的 github: <code>git push</code></p>
<ul><li>
<code>git push <远程主机名> <本地分支名>:<远程分支名> </code><br> 比如我要将本地的wy分支推送到远程wy分支,使用: <br><code>git push origin wy:wy</code><br> 如果省略远程分支名,则表示将本地分支推送到与之存在"追踪关系"的远程分支(通常同名),如果该远程分支不存在,则会被新建。</li></ul>
</li>
<li>
<p>将远程库文件拉取到本地仓库:</p>
<ul>
<li>
<code>git pull</code>:会自动将本地版本与新版本<code>merge</code>。</li>
<li>
<code>git fetch</code>:不会自动将本地版本与新版本<code>merge</code>。</li>
</ul>
</li>
<li>
<p>分支:</p>
<ul>
<li>创建的新的分支:<code>git branch <branch-name></code>
</li>
<li>
<p>查看分支:<code>git branch</code></p>
<ul><li>在 git bash 中用此命令,按键盘下键查看未显示部分,输入 <code>q</code> 退出</li></ul>
</li>
<li>切换分支: <code>git checkout <branch-name></code>
</li>
<li>合并分支:<code>git merge origin/<branch-name> </code>合并之前要先切换到合并的目标分支上</li>
<li>删除分支:<code>git branch -d <branch-name></code>
</li>
</ul>
</li>
<li>
<p>版本回退:</p>
<ul>
<li>
<p><code>git log</code> 会显示最近的三个版本,head 指针指向最近的版本,输入 <code>q</code> 可以退出<code>git log</code>。回退之前,用<code>git log</code>确定要回退到哪个版本。</p>
<ul><li>加上<code>--pretty=oneline </code>会简化信息</li></ul>
</li>
<li>
<p>版本回退:</p>
<ul>
<li>
<code>git reset --hard HEAD^ </code>回退到上一个版本,上上是<code>HEAD^^</code>,往上一百个是<code>HEAD~100</code>
</li>
<li>直接回退到commit-id所对应版本,<code>git reset --hard commit-id</code>
</li>
</ul>
</li>
<li>
<code>git reflog </code>可以查看git 的历史操作,如果使用<code>git reset</code>回退错误,想要再次回到未来的版本,可以使用<code>git reflog </code>来查看回退之前的版本号。</li>
<li>
<code>git revert</code>是产生一次新的提交,不过这次提交的改动与之前的改动是相反的,也就是说利用新的提交去覆盖之前的修改。</li>
</ul>
</li>
<li>git 更改远程仓库地址:<code>git remote set-url origin <新的url></code>
</li>
<li>
<p>本地仓库整体上传到远程仓库</p>
<ol>
<li>首先在github新建一个仓库(最好不要初始化README.md,因为远程仓库和本地仓库不一样,首先要<code>git pull</code>同步,经常出问题...)。</li>
<li>将本地仓库与远程仓库连起来:<br><code>git remote add origin git@github.com:yourname/仓库名.git</code>
</li>
<li><code>git push -u origin master</code></li>
</ol>
</li>
<li>
<code>git diff</code>:查看当前代码的修改情况,<code>git diff HEAD -- readme.txt</code> 查看当前工作区和版本库最新版本之间的差别。</li>
<li>
<p><code>git</code>多人协作的工作模式通常是这样:</p>
<ol>
<li>在本地创建和远程分支对应的分支,使用<code>git checkout -b branch-name origin/branch-name</code>,本地和远程分支的名称最好一致</li>
<li>将本地分支推送到远程同名分支:<code>git push origin branch-name:branch-name</code>
</li>
<li>如果推送失败,说明远程分支内容比本地更新,需要先抓取并合并,<code>git pull</code>
</li>
<li>如果抓取也失败,可能是本地<code>dev</code>分支与远程<code>origin/dev</code>分支的未建立链接:<code>git branch --set-upstream-to=origin/dev dev</code>,再次使用<code>git pull</code>抓取合并</li>
<li>如果合并有冲突,则解决冲突,并在本地提交</li>
<li>再次推送:<code>git push origin wy:wy</code>
</li>
</ol>
</li>
<li>
<p>管理修改</p>
<ul>
<li>场景一:工作区的修改没有提交到暂存区(没有<code>git add</code>),使用<code>git checkout -- filename</code>,丢弃工作区的改动。</li>
<li>场景二:工作区的修改提交到了暂存区,使用<code>git reset HEAD -- filename</code> 回到场景一。</li>
<li>场景三:提交到了版本库(<code>git commit</code>),使用<code>git reset --hard commit-id</code> 回退版本。</li>
</ul>
</li>
<li>多人开发时,先<code>git add .</code> --> <code>git commit -m ''</code> --> <code>git push</code>(本地非最新) --> <code>git pull</code> --> <code>git push</code>,这样可能产生两条提交记录,一条是本地的修改记录,另一条的合并代码的记录。解决办法,本地修改文件后,先<code>git stash</code>将修改暂存起来,再<code>git pull</code>,更新本地代码,再<code>git stash pop</code>,将暂存的本地修改合并到拉取的版本中,可能会产生冲突,解决了冲突后,再执行<code>git add . -> commit -> push</code>的提交流程。</li>
<li>已提交commit后修改commit信息:<code>git commit --amend</code>,输入<code>i</code>后进入vim编辑,编辑好后,<code>Esc</code> 再 <code>:wq</code>保存退出</li>
</ul>
JS实现插入排序
https://segmentfault.com/a/1190000015489767
2018-07-05T12:48:36+08:00
2018-07-05T12:48:36+08:00
Leon
https://segmentfault.com/u/leon07
10
<p>直接插入排序的时间复杂度为 O(n^2) ,相较于复杂度为 O(nlogn) 的快速排序、归并排序、堆排序、希尔排序,插入排序可谓相形见绌。但是,插入排序真的一无是处吗? 答案是否定的,插入排序在实践中的使用频率是很高的,在一些场景下,甚至展现出完胜高级排序的效率。下面我们一起来看看。</p><p>由于插入排序的实现很简单,首先直接放出代码:</p><pre><code class="JavaScript">function insertSort(arr) {
let length = arr.length;
for(let i = 1; i < length; i++) {
let temp = arr[i];
let j = i;
for(; j > 0; j--) {
if(temp >= arr[j-1]) {
break; // 当前考察的数大于前一个数,证明有序,退出循环
}
arr[j] = arr[j-1]; // 将前一个数复制到后一个数上
}
arr[j] = temp; // 找到考察的数应处于的位置
}
return arr;
}
// example
let arr = [2,5,10,7,10,32,90,9,11,1,0,10]
console.log(insertSort(arr));</code></pre><p>插入排序的思路跟整理扑克牌是一样的,即每次拿到一张牌,按大小顺序将其插入到合适的位置。那么插入排序实际上就是:每次将一个数插入到有序的数组中去(初始一个数字自然有序)。</p><p><img src="/img/bVbc9Kl" alt="clipboard.png" title="clipboard.png"></p><p>下面以实例结合代码来分析一个插入排序的过程:</p><p><img src="/img/bVbc9Lk" alt="clipboard.png" title="clipboard.png"></p><p>由于第一个数 6 是自然有序的,所以我们从第二个数 5 开始考察, 将 5 取出与它的前一个数 6 比较,5 < 6, 将 6 复制到 5 的位置,5 向前移动继续比较,此时 5 已经处于数组第一位,第一次排序结束,将 5 放入当前位置;</p><p><img src="/img/bVbc9KR" alt="clipboard.png" title="clipboard.png"></p><hr><p>此时 [5, 6] 已经构成有序数组,考察 4,将 4 取出与它的前一个数 6 比较,4 < 6,将 6 复制到 4 的位置;4 向前移与 5 比较,4 < 5,将 5 复制到前一个 6 的位置,此时 4 处于数组第一位,第二趟排序结束。</p><p><img src="/img/bVbc9KV" alt="clipboard.png" title="clipboard.png"></p><p>后面的排序过程与前面分析的过程一致,总结一下就是:不断将大于当前考察对象的数后移一位,直到找到考察对象应该处于的位置。有一个需要注意的点是,考察对象不一定是要一直向前移动到数组第一个位置才结束一趟排序,如果中间找到了合适的位置,这趟排序是可以提前终止的。<br>举例:</p><p><img src="/img/bVbc9K3" alt="clipboard.png" title="clipboard.png"></p><p>这一点正是插入排序的精髓所在!如果对一个已经有序的数组使用插入排序,插入排序只会遍历数组一遍,时间复杂度退化为 O(n);可以想象,如果对一个接近有序的数组使用插入排序,其效率是非常可观的,而很多时候我们处理的数据是接近有序的,只需调整一些无序项,所以插入排序是很有用的。</p><p><a href="https://link.segmentfault.com/?enc=ui2KOS%2Fu%2BnkjJ4EgfOJTsg%3D%3D.ncOrHkQxNPvmqglwAWBfI4EOYU1ZMpG%2BLRFC9j2OwUqdkmAnRaqM5LacpQ2mWHYZD%2Fm3GjVpw5CMjbk1kwNUWtL77087%2BRUgb3KRV%2FBRRU1E%2B6x%2FtB5O6hbTkJL3kQuY" rel="nofollow">chrome v8</a>的 <code>Array.sort</code> 函数实现中(710行),当数组的长度小于等于22时,使用的就是插入排序,大于22使用的是快速排序。</p><blockquote>// In-place QuickSort algorithm.<br> // For short (length <= 22) arrays, insertion sort is used for efficiency.</blockquote>
JS实现归并排序
https://segmentfault.com/a/1190000015488807
2018-07-05T11:35:46+08:00
2018-07-05T11:35:46+08:00
Leon
https://segmentfault.com/u/leon07
8
<h3>递归的内存堆栈分析</h3>
<p>一直对递归理解不深,原因是递归的过程很抽象,分析不清内存堆栈的返回过程。偶然google到一篇博文<a href="https://link.segmentfault.com/?enc=aBZgvb4f0e%2FfopoTjz9VEA%3D%3D.CNI7afrSXSb1PYBjAcKtAk8AJfjKeYeh6CiunaJkOZhLEawaKPjoEzDnqVnKS8wt" rel="nofollow">递归</a>(不得不说,技术问题还是要多google),对递归过程的内存堆栈分析豁然开朗,下面先列出分析过程:</p>
<pre><code class="C++">// A C++ program to demonstrate working of recursion
#include<bits/stdc++.h>
using namespace std;
void printFun(int test)
{
if (test < 1)
return;
else
{
cout << test << " ";
printFun(test-1); // statement 2
cout << test << " ";
return;
}
}
int main()
{
int test = 3;
printFun(test);
}</code></pre>
<p>下面这个图准确的列出了整个递归的过程,以后遇到单次递归问题,完全可以用此方法分析(对于多次递归情况,尝试画了一下归并排序里的两次递归,实在没有办法整洁的排版,作罢。。)</p>
<p><img src="/img/bVbc9u7?w=1316&h=650" alt="clipboard.png" title="clipboard.png"></p>
<p>言归正传,下面分析归并排序。</p>
<h3>归并排序</h3>
<p>归并排序采用的是分治的思想,首先是“分”,将一个数组反复二分为两个小数组,直到每个数组只有一个元素;其次是“治”,从最小数组开始,两两按大小顺序合并,直到并为原始数组大小,下面是图解:</p>
<p><img src="/img/bVbc9vd?w=1014&h=855" alt="clipboard.png" title="clipboard.png"></p>
<p>观察下“治”的过程,可以看出,“治”实际上是将已经有序的数组合并为更大的有序数组。那么怎样将已经有序的数组合并为更大的有序数组?很简单,创建一个临时数组C,比较A[0],B[0],将较小值放到C[0],再比较A[1]与B[0](或者A[0],B[1]),将较小值放到C[1],直到对A,B都遍历一遍。可以看出数组A,B都只需遍历一遍,所以对两个有序数组的排序的时间复杂度为O(n)。</p>
<p>而“分”就是将原始数组逐次二分,直到每个数组只剩一个元素,一个元素的数组自然是有序的,所以就可以开始“治”的过程了。</p>
<p>时间复杂度分析:分的过程需要三步:log8 = 3,而每一步都需要遍历一次8个元素,所以8个元素共需要运行 8log8 次指令,那么对于 n 个元素,时间复杂度为 O(nlogn)。 </p>
<p>代码中运用了两次递归,十分抽象难懂,画了一整页堆栈调用图,才弄明白(太凌乱就不贴了),大家可以试试。</p>
<pre><code class="JavaScript">// 融合两个有序数组,这里实际上是将数组 arr 分为两个数组
function mergeArray(arr, first, mid, last, temp) {
let i = first;
let m = mid;
let j = mid+1;
let n = last;
let k = 0;
while(i<=m && j<=n) {
if(arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while(i<=m) {
temp[k++] = arr[i++];
}
while(j<=n) {
temp[k++] = arr[j++];
}
for(let l=0; l<k; l++) {
arr[first+l] = temp[l];
}
return arr;
}
// 递归实现归并排序
function mergeSort(arr, first, last, temp) {
if(first<last) {
let mid = Math.floor((first+last)/2);
mergeSort(arr, first, mid, temp); // 左子数组有序
mergeSort(arr, mid+1, last, temp); // 右子数组有序
arr = mergeArray(arr, first, mid, last, temp);
}
return arr;
}
// example
let arr = [10, 3, 1, 5, 11, 2, 0, 6, 3];
let temp = new Array();
let SortedArr = mergeSort(arr, 0 ,arr.length-1, temp);
alert(SortedArr);</code></pre>
JS实现快速排序
https://segmentfault.com/a/1190000015488549
2018-07-05T11:23:44+08:00
2018-07-05T11:23:44+08:00
Leon
https://segmentfault.com/u/leon07
15
<p>看了一篇通俗易懂的快排文章 <a href="https://link.segmentfault.com/?enc=jMvrpFIob7KRpbSCQc0y1g%3D%3D.cM40YU3r6opGfzqxuO4I9ysgQHQMBggi3%2FSUcj4%2BBeeqyMOJEkHKLauQNnlEQAY63CPeOtY2iJKfhVQJavzglQ%3D%3D" rel="nofollow">快排</a>,下面一步一步 实现整个过程。</p><h3>快排的基本思想</h3><p>上面链接的文章对快排的思路提出了一个很形象的概念:挖坑填数 + 分治法,分三个步骤实现:</p><ol><li>从数组中取出一个数作为基准(pivot)。</li><li>在原数组中进行移动,将大于基准的数放到基准右边,小于基准的数放到基准左边,在基准左右形成两个子数组。</li><li>在左右子数组中反复执行步骤1、2,直到所有子数组只剩下一个数。</li></ol><h3>详细步骤</h3><p>初始数组如下所示,取第一个数为基准,此时:i = 0, j = 9, pivot = arr[0] = 36,此时 i = 0 的位置就挖了一个坑,等待小于36的数来填这个坑。i 先不变,j-- 从后往前找小于基准的数:</p><p><img src="/img/bVbc9p4" alt="clipboard.png" title="clipboard.png"></p><hr><p>i= 0, j = 8 时,24 < 36,将 arr[8] 挖出,放入 arr[0] 的“坑中”(实际上在写程序时,是 arr[8] 与 arr[0] 交换)。接着arr[8] 的坑怎么填?调换顺序从前往后找比基准大的数(i++,j 不变):</p><p><img src="/img/bVbc9qk" alt="clipboard.png" title="clipboard.png"></p><hr><p>i= 3, j = 8 时,43 > 36,将 arr[3] 挖出,放入 arr[8] 的“坑中”。接着去找数填 arr[3] 的坑,调换顺序从后往前找比基准小的数:</p><p><img src="/img/bVbc9qz" alt="clipboard.png" title="clipboard.png"></p><hr><p>i= 3, j = 5 时,20 < 36,反向查找:</p><p><img src="/img/bVbc9s0" alt="clipboard.png" title="clipboard.png"></p><hr><p>i= j = 5 时,退出,第一趟排序完成,以 arr[5] = 36 为界分为左右两个子数组:</p><p><img src="/img/bVbc9q0" alt="clipboard.png" title="clipboard.png"></p><hr><p>接着在左右两个子数组中重复上面的排序过程,直到每个子数组的长度为1,排序结束!下面只给出每一步的执行结果:</p><p><img src="/img/bVbc9rf" alt="clipboard.png" title="clipboard.png"></p><p><img src="/img/bVbc9rn" alt="clipboard.png" title="clipboard.png"></p><hr><h3>JS代码</h3><pre><code class="JavaScript">// 快排
function quickSort(arr, i, j) {
if(i < j) {
let left = i;
let right = j;
let pivot = arr[left];
while(i < j) {
while(arr[j] >= pivot && i < j) { // 从后往前找比基准小的数
j--;
}
if(i < j) {
arr[i++] = arr[j];
}
while(arr[i] <= pivot && i < j) { // 从前往后找比基准大的数
i++;
}
if(i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot;
quickSort(arr, left, i-1);
quickSort(arr, i+1, right);
return arr;
}
}
// example
let arr = [2, 10, 4, 1, 0, 9, 5 ,2];
console.log(quickSort(arr, 0 , arr.length-1));</code></pre><p>有的书上是以中间的数作为基准数的,要实现这个方便非常方便,直接将中间的数和第一个数进行交换就可以了。</p><pre><code>function quickSort(arr, i, j) {
if(i < j) {
let left = i;
let right = j;
let mid = Math.floor((left+right)/2);
let temp = arr[left];
arr[left] = arr[mid];
arr[mid] = temp;
let pivot = arr[left];
while(i < j) {
while(arr[j] >= pivot && i < j) { // 从后往前找比基准小的数
j--;
}
if(i < j) {
arr[i++] = arr[j];
}
while(arr[i] <= pivot && i < j) { // 从前往后找比基准大的数
i++;
}
if(i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot;
quickSort(arr, left, i-1);
quickSort(arr, i+1, right);
return arr;
}
}</code></pre>
理解async/await
https://segmentfault.com/a/1190000015488033
2018-07-05T11:02:56+08:00
2018-07-05T11:02:56+08:00
Leon
https://segmentfault.com/u/leon07
45
<p>首先明确一个问题,为什么 <code>Node.js</code> 需要异步编程?</p>
<p><code>JavaScript </code> 是单线程的,在发出一个调用时,在没有得到结果之前,该调用就不返回,意思就是调用者主动等待调用结果,换句话说,就是必须等待上一个任务执行完才能执行下一个任务,这种执行模式叫:<strong>同步</strong>。<br><code>Node.js </code> 的主要应用场景是处理高并发(单位时间内极大的访问量)和 <code>I/O </code> 密集场景(ps: <code>I/O </code> 操作往往非常耗时,所以异步的关键在于解决 <code>I/O </code> 耗时问题),如果采用同步编程,问题就来了,服务器处理一个 <code>I/O </code> 请求需要大量的时间,后面的请求都将排队,造成浏览器端的卡顿。异步编程能解决这个问题。<br>所谓<strong>异步</strong>,就是调用在发出后,这个调用就直接返回了,调用者不会立即得到结果,但是不会阻塞,可以继续执行后续操作,而被调用者执行得到结果后通过状态、事件来通知调用者使用回调函数( <code>callback </code>)来处理这个结果。Node在处理耗时的 <code>I/O </code> 操作时,将其交给其他线程处理,自己继续处理其他访问请求,当 <code>I/O </code> 操作处理好后就会通过事件通知 Node 用回调做后续处理。<br>有个例子非常好:</p>
<blockquote>你打电话问书店老板有没有《分布式系统》这本书,如果是同步通信机制,书店老板会说,你稍等,”我查一下",然后开始查啊查,等查好了(可能是5秒,也可能是一天)告诉你结果(返回结果)。而异步通信机制,书店老板直接告诉你我查一下啊,查好了打电话给你,然后直接挂电话了(不返回结果)。然后查好了,他会主动打电话给你。在这里老板通过“回电”这种方式来回调。</blockquote>
<p>下面几种方式是异步解决方案的进化过程:</p>
<h3>CallBacks</h3>
<p>回调函数就是函数A作为参数传递给函数B,并且在未来某一个时间被调用。callback的异步模式最大的问题就是,理解困难加回调地狱(callback hell),看下面的代码的执行顺序:</p>
<pre><code class="JavaScript">A();
ajax('url1', function(){
B();
ajax('url2', function(){
C();
}
D();
});
E();</code></pre>
<p>其执行顺序为:<code>A => E => B => D => C</code>,这种执行顺序的确会让人头脑发昏,另外由于由于多个异步操作之间往往会耦合,只要中间一个操作需要修改,那么它的上层回调函数和下层回调函数都可能要修改,这就陷入了回调地狱。而 Promise 对象就很好的解决了异步操作之间的耦合问题,让我们可以用同步编程的方式去写异步操作。</p>
<h3>Promise</h3>
<p><code>Promise</code> 对象是一个构造函数,用来生成<code>promise</code>实例。<code>Promise</code> 代表一个异步操作,有三种状态:<code>pending,resolved</code>(异步操作成功由 <code>pending </code>变为 <code>resolved </code>),<code>rejected</code>(异步操作失败由 <code>pending </code>变为 <code>rejected </code>),一旦变为后两种状态将不会再改变。<code>Promise </code>对象作为构造函数接受一个函数作为参数,而这个函数又接受 <code>resolve</code> 和<code> reject</code> 两个函数做为参数,这两个函数是JS内置的,无需配置。<code>resolve</code> 函数在异步操作成功后调用,将<code>pending</code>状态变为<code>resolved</code>,并将它的参数传递给回调函数;<code>reject</code> 函数在异步操作失败时调用,将<code>pending</code>状态变为<code>rejected</code>,并将参数传递给回调函数。</p>
<ul><li><h4>Promise.prototype.then()</h4></li></ul>
<p><code>Promise</code>构造函数的原型上有一个<code>then</code>方法,它接受两个函数作为参数,分别是 <code>resolved</code> 状态和 <code>rejected</code> 状态的回调函数,而这两个回调函数接受的参数分别是<code>Promise</code>实例中<code>resolve</code>函数和<code>reject</code><strong>函数中的参数</strong>。 另外<code>rejected</code>状态的回调函数是可省略的。</p>
<p>下面是一个使用示例:</p>
<pre><code class="JavaScript">const instance = new Promise((resolve, reject) => {
// 一些异步操作
if(/*异步操作成功*/) {
resolve(value);
} else {
reject(error);
}
}
})
instance.then(value => {
// do something...
}, error => {
// do something...
})</code></pre>
<p>注意Promise实例在生成后会立即执行,而 <code>then </code>方法只有在所有同步任务执行完后才会执行,看看下面的例子:</p>
<pre><code class="JavaScript">const promise = new Promise((resolve, reject) => {
console.log('async task begins!');
setTimeout(() => {
resolve('done, pending -> resolved!');
}, 1000);
})
promise.then(value => {
console.log(value);
})
console.log('1.please wait');
console.log('2.please wait');
console.log('3.please wait');
// async task begins!
// 1.please wait
// 2.please wait
// 3.please wait
// done, pending -> resolved!</code></pre>
<p>上面的实例可以看出,Promise实例生成后立即执行,所以首先输出 <code>'async task begins!'</code>,随后定义了一个异步操作 <code>setTimeout</code>,1秒后执行,所以无需等待,向下执行,而<code>then</code>方法指定的回调函数要在所有同步任务执行完后才执行,所以先输出了3个<code>'please wait'</code>,最后输出<code>'done, pending -> resolved!'</code>。(此处省略了<code>then</code>方法中的<code>reject</code>回调,一般不在<code>then</code>中做<code>rejected</code>状态的处理,而使用<code>catch</code>方法专门处理错误,相当于<code>.then(null, reject)</code>)</p>
<ul><li>
<h4>链式调用 then 方法</h4>
<p><code>then </code> 方法会返回一个新的 Promise 实例,可以分两种情况来看:</p>
</li></ul>
<ol>
<li>指定返回值是新的 Promise 对象,如<code>return new Promise(...)</code>,这种情况没啥好说的,由于返回的是 <code>Promise</code>,后面显然可以继续调用<code>then</code>方法。</li>
<li>返回值不是Promise, 如:<code>return 1</code> 这种情况还是会返回一个 <code>Promise</code>,并且这个<code>Promise</code> 立即执行回调 <code>resolve(1)</code>。所以仍然可以链式调用<code>then</code>方法。(注:如果没有指定<code>return</code>语句,相当于返回了<code>undefined</code>)</li>
</ol>
<p>使用 then 的链式写法,按顺序实现一系列的异步操作,这样就可以用同步编程的形式去实现异步操作,来看下面的例子,实现隔两秒打一次招呼:</p>
<pre><code class="JavaScript">function sayHi(name) {
return new Promise((resolve, reject) => {
setTimeout(() => {
resolve(name);
}, 2000)
})
}
sayHi('张三')
.then(name => {
console.log(`你好, ${name}`);
return sayHi('李四'); // 最终 resolved 函数中的参数将作为值传递给下一个then
})
// name 是上一个then传递出来的参数
.then(name => {
console.log(`你好, ${name}`);
return sayHi('王二麻子');
})
.then(name => {
console.log(`你好, ${name}`);
})
// 你好, 张三
// 你好, 李四
// 你好, 王二麻子</code></pre>
<p>可以看到使用链式then的写法,将异步操作变成了同步的形式,但是也带来了新的问题,就是异步操作变成了很长的then链,新的解决方法就是<code>Generator</code>,这里跨过它直接说它的语法糖:<code>async/await</code>。</p>
<h3>async/await</h3>
<ul><li><h4>async</h4></li></ul>
<p><code>async/await</code>实际上是<code>Generator</code>的语法糖。顾名思义,<code>async</code>关键字代表后面的函数中有异步操作,<code>await</code>表示等待一个异步方法执行完成。声明异步函数只需在普通函数前面加一个关键字<code>async</code>即可,如:</p>
<pre><code>async function funcA() {}</code></pre>
<p><code>async</code> 函数返回一个Promise对象(如果指定的返回值不是Promise对象,也返回一个Promise,只不过立即 <code>resolve </code>,处理方式同 <code>then </code>方法),因此 <code>async </code>函数通过 <code>return </code>返回的值,会成为 <code>then </code>方法中回调函数的参数:</p>
<pre><code>async function funcA() {
return 'hello!';
}
funcA().then(value => {
console.log(value);
})
// hello!</code></pre>
<p>单独一个 <code>async </code>函数,其实与Promise执行的功能是一样的,来看看 <code>await </code>都干了些啥。</p>
<ul><li><h4>await</h4></li></ul>
<p>顾名思义, <code>await </code> 就是异步等待,它等待的是一个Promise,因此 <code>await </code>后面应该写一个Promise对象,如果不是Promise对象,那么会被转成一个立即 <code>resolve </code>的Promise。 <code>async </code>函数被调用后就立即执行,但是一旦遇到 <code>await </code>就会先返回,等到异步操作执行完成,再接着执行函数体内后面的语句。总结一下就是:<code>async</code>函数调用不会造成代码的阻塞,但是<code>await</code>会引起<code>async</code>函数内部代码的阻塞。看看下面这个例子:</p>
<pre><code class="JavaScript">async function func() {
console.log('async function is running!');
const num1 = await 200;
console.log(`num1 is ${num1}`);
const num2 = await num1+ 100;
console.log(`num2 is ${num2}`);
const num3 = await num2 + 100;
console.log(`num3 is ${num3}`);
}
func();
console.log('run me before await!');
// async function is running!
// run me before await!
// num1 is 200
// num2 is 300
// num3 is 400</code></pre>
<p>可以看出调用 <code>async func</code> 函数后,它会立即执行,首先输出了<code>'async function is running!'</code>,接着遇到了 <code>await </code>异步等待,函数返回,先执行<code>func()</code>后面的同步任务,同步任务执行完后,接着await等待的位置继续往下执行。可以说,<code>async</code>函数完全可以看作多个异步操作,包装成的一个Promise 对象,而<code>await</code>命令就是内部<code>then</code>命令的语法糖。</p>
<p>值得注意的是, <code>await </code> 后面的 Promise 对象不总是返回 <code> resolved </code>状态,只要一个 <code>await </code>后面的Promise状态变为 <code>rejected </code>,整个 <code>async </code>函数都会中断执行,为了保存错误的位置和错误信息,我们需要用 <code>try...catch</code> 语句来封装多个 <code>await </code>过程,如下:</p>
<pre><code class="JavaScript">async function func() {
try {
const num1 = await 200;
console.log(`num1 is ${num1}`);
const num2 = await Promise.reject('num2 is wrong!');
console.log(`num2 is ${num2}`);
const num3 = await num2 + 100;
console.log(`num3 is ${num3}`);
} catch (error) {
console.log(error);
}
}
func();
// num1 is 200
// 出错了
// num2 is wrong!</code></pre>
<p>如上所示,在 <code>num2 </code>处 <code>await </code>得到了一个状态为 <code>rejected </code>的Promise对象,该错误会被传递到 <code>catch </code>语句中,这样我们就可以定位错误发生的位置。</p>
<ul><li><h4>async/await比Promise强在哪儿?</h4></li></ul>
<p>接下来我们用<code>async/await</code>改写一下Promise章节中关于<code>sayHi</code>的一个例子,代码如下:</p>
<pre><code class="JavaScript">function sayHi(name) {
return new Promise((resolved, rejected) => {
setTimeout(() => {
resolved(name);
}, 2000)
})
}
async function sayHi_async(name) {
const sayHi_1 = await sayHi(name)
console.log(`你好, ${sayHi_1}`)
const sayHi_2 = await sayHi('李四')
console.log(`你好, ${sayHi_2}`)
const sayHi_3 = await sayHi('王二麻子')
console.log(`你好, ${sayHi_3}`)
}
sayHi_async('张三')
// 你好, 张三
// 你好, 李四
// 你好, 王二麻子</code></pre>
<p>与之前长长的then链和then方法里的回调函数相比,这样的写法看起来像是同步写法并且更加清爽,更加符合编程习惯。</p>
<h4>参考文章</h4>
<p><a href="https://segmentfault.com/a/1190000007535316">https://segmentfault.com/a/11...</a><br><a href="https://segmentfault.com/a/1190000006138882">https://segmentfault.com/a/11...</a><br><a href="https://link.segmentfault.com/?enc=%2BBtBYW0KbzyH8SYxN1V0tQ%3D%3D.RNJUy%2FJLikK3QlH5jyC5aTJZ4kucCg3iwqi2kdrGyyvmY7%2FUSxs3RO3PFg4yYFsr%2FbryxVGKue8eHHfxUwIUpw%3D%3D" rel="nofollow">https://www.zhihu.com/questio...</a></p>
JS实现堆排序
https://segmentfault.com/a/1190000015487916
2018-07-05T10:58:18+08:00
2018-07-05T10:58:18+08:00
Leon
https://segmentfault.com/u/leon07
26
<h3>堆的预备知识</h3>
<ul>
<li>堆是一个完全二叉树。</li>
<li>完全二叉树: 二叉树除开最后一层,其他层结点数都达到最大,最后一层的所有结点都集中在左边(左边结点排列满的情况下,右边才能缺失结点)。</li>
<li>大顶堆:根结点为最大值,每个结点的值大于或等于其孩子结点的值。</li>
<li>小顶堆:根结点为最小值,每个结点的值小于或等于其孩子结点的值。</li>
<li>堆的存储: 堆由数组来实现,相当于对二叉树做层序遍历。如下图:</li>
</ul>
<p><img src="/img/bVbc809?w=416&h=361" alt="clipboard.png" title="clipboard.png"></p>
<p><img src="/img/bVbc81e?w=700&h=116" alt="clipboard.png" title="clipboard.png"></p>
<p>对于结点 i ,其子结点为 2<em>i+1 与 2</em>i+2 。</p>
<h3>堆排序算法</h3>
<p><img src="/img/bVbc81P?w=452&h=429" alt="clipboard.png" title="clipboard.png"></p>
<p>现在需要对如上二叉树做升序排序,总共分为三步:</p>
<ol>
<li>将初始二叉树转化为大顶堆(heapify)(实质是从第一个非叶子结点开始,从下至上,从右至左,对每一个非叶子结点做shiftDown操作),此时根结点为最大值,将其与最后一个结点交换。</li>
<li>除开最后一个结点,将其余节点组成的新堆转化为大顶堆(实质上是对根节点做shiftDown操作),此时根结点为次最大值,将其与最后一个结点交换。</li>
<li>重复步骤2,直到堆中元素个数为1(或其对应数组的长度为1),排序完成。</li>
</ol>
<p>下面详细图解这个过程:</p>
<h4>步骤1:</h4>
<p>初始化大顶堆,首先选取最后一个非叶子结点(我们只需要调整父节点和孩子节点之间的大小关系,叶子结点之间的大小关系无需调整)。设数组为arr,则第一个非叶子结点的下标为:i = Math.floor(arr.length/2 - 1) = 1,也就是数字4,如图中虚线框,找到三个数字的最大值,与父节点交换。</p>
<p><img src="/img/bVbc82R?w=700&h=341" alt="clipboard.png" title="clipboard.png"></p>
<p>然后,下标 i 依次减1(即从第一个非叶子结点开始,从右至左,从下至上遍历所有非叶子节点)。后面的每一次调整都是如此:找到父子结点中的最大值,做交换。</p>
<p><img src="/img/bVbc83f?w=700&h=337" alt="clipboard.png" title="clipboard.png"></p>
<p>这一步中数字6、1交换后,数字[1,5,4]组成的堆顺序不对,需要执行一步调整。因此需要注意,每一次对一个非叶子结点做调整后,都要观察是否会影响子堆顺序!</p>
<p><img src="/img/bVbc83w?w=451&h=429" alt="clipboard.png" title="clipboard.png"></p>
<p>这次调整后,根节点为最大值,形成了一个大顶堆,将根节点与最后一个结点交换。</p>
<h4>步骤2:</h4>
<p>除开当前最后一个结点6(即最大值),将其余结点[4,5,3,1]组成新堆转化为大顶堆(注意观察,此时根节点以外的其他结点,都满足大顶堆的特征,所以可以从根节点4开始调整,即找到4应该处于的位置即可)。</p>
<p><img src="/img/bVbc836?w=700&h=337" alt="clipboard.png" title="clipboard.png"></p>
<p><img src="/img/bVbc84l?w=451&h=429" alt="clipboard.png" title="clipboard.png"></p>
<h4>步骤3:</h4>
<p>接下来反复执行步骤2,直到堆中元素个数为1:</p>
<p><img src="/img/bVbc84y?w=700&h=315" alt="clipboard.png" title="clipboard.png"></p>
<p><img src="/img/bVbc84L?w=451&h=429" alt="clipboard.png" title="clipboard.png"></p>
<p><img src="/img/bVbc84M?w=700&h=315" alt="clipboard.png" title="clipboard.png"></p>
<p>堆中元素个数为1, 排序完成。</p>
<h3>JavaScript实现</h3>
<pre><code class="JavaScript">// 交换两个节点
function swap(A, i, j) {
let temp = A[i];
A[i] = A[j];
A[j] = temp;
}
// 将 i 结点以下的堆整理为大顶堆,注意这一步实现的基础实际上是:
// 假设 结点 i 以下的子堆已经是一个大顶堆,shiftDown函数实现的
// 功能是实际上是:找到 结点 i 在包括结点 i 的堆中的正确位置。后面
// 将写一个 for 循环,从第一个非叶子结点开始,对每一个非叶子结点
// 都执行 shiftDown操作,所以就满足了结点 i 以下的子堆已经是一大
//顶堆
function shiftDown(A, i, length) {
let temp = A[i]; // 当前父节点
// j<length 的目的是对结点 i 以下的结点全部做顺序调整
for(let j = 2*i+1; j<length; j = 2*j+1) {
temp = A[i]; // 将 A[i] 取出,整个过程相当于找到 A[i] 应处于的位置
if(j+1 < length && A[j] < A[j+1]) {
j++; // 找到两个孩子中较大的一个,再与父节点比较
}
if(temp < A[j]) {
swap(A, i, j) // 如果父节点小于子节点:交换;否则跳出
i = j; // 交换后,temp 的下标变为 j
} else {
break;
}
}
}
// 堆排序
function heapSort(A) {
// 初始化大顶堆,从第一个非叶子结点开始
for(let i = Math.floor(A.length/2-1); i>=0; i--) {
shiftDown(A, i, A.length);
}
// 排序,每一次for循环找出一个当前最大值,数组长度减一
for(let i = Math.floor(A.length-1); i>0; i--) {
swap(A, 0, i); // 根节点与最后一个节点交换
shiftDown(A, 0, i); // 从根节点开始调整,并且最后一个结点已经为当
// 前最大值,不需要再参与比较,所以第三个参数
// 为 i,即比较到最后一个结点前一个即可
}
}
let Arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
heapSort(Arr);
alert(Arr);</code></pre>
<p>程序注释: 将 i 结点以下的堆整理为大顶堆,注意这一步实现的基础实际上是:假设 结点 i 以下的子堆已经是一个大顶堆,shiftDown函数实现的功能是实际上是:找到 结点 i 在包括结点 i 的堆中的正确位置。后面做第一次堆化时,heapSort 中写了一个 for 循环,从第一个非叶子结点开始,对每一个非叶子结点都执行 shiftDown操作,所以就满足了每一次 shiftDown中,结点 i 以下的子堆已经是一大顶堆。</p>
<p>复杂度分析:adjustHeap 函数中相当于堆的每一层只遍历一个结点,因为<br>具有n个结点的完全二叉树的深度为[log2n]+1,所以 shiftDown的复杂度为 O(logn),而外层循环共有 f(n) 次,所以最终的复杂度为 O(nlogn)。</p>
<h3>堆的应用</h3>
<p>堆主要是用来实现优先队列,下面是优先队列的应用示例:</p>
<ul>
<li>操作系统动态选择优先级最高的任务执行。</li>
<li>静态问题中,在N个元素中选出前M名,使用排序的复杂度:O(NlogN),使用优先队列的复杂度: O(NlogM)。</li>
</ul>
<p>而实现优先队列采用普通数组、顺序数组和堆的不同复杂度如下:</p>
<p><img src="/img/bVbc9oU?w=671&h=334" alt="clipboard.png" title="clipboard.png"></p>
<p>使用堆来实现优先队列,可以使入队和出队的复杂度都很低。</p>
如何理解 (object.getName = object.getName)() 这段代码?
https://segmentfault.com/a/1190000015486557
2018-07-05T10:05:42+08:00
2018-07-05T10:05:42+08:00
Leon
https://segmentfault.com/u/leon07
3
<blockquote>1.</blockquote>
<p>此段代码出自《JavaScript高级程序设计(第3版)》 p.183,代码片段如下:</p>
<pre><code class="JavaScript">var name = "The Window";
var object = {
name : "My Object",
getName: function(){
return this.name;
}
};
(object.getName = object.getName)(); //"The Window" </code></pre>
<p>理解此段代码,首先要明确一个点:赋值语句是有返回值的,返回值就是所赋的值(也就是‘=’右边的值)。</p>
<pre><code class="JavaScript">object.getName = object.getName ;</code></pre>
<p>上面这行代码的含义就是:将等号左边 object 对象的 getName 方法赋值为 object.getName。(刚看这段代码时犯了一个错误,即getName 方法后面是没有加括号的,也即是函数不执行,仅仅是传递了它的引用。)</p>
<p>那么上面这个赋值语句的返回值就是 object.getName 指向的函数体本身了:</p>
<pre><code class="JavaScript">function(){
return this.name;
}</code></pre>
<p>那么 (object.getName = object.getName)();其实就相当于:</p>
<pre><code class="JavaScript">(function(){
return this.name;
})();</code></pre>
<p>该段代码的调用者为 window,所以 this 指向window,最终结果为 "The Window"。</p>
<hr>
<blockquote>2.</blockquote>
<p>怎样理解红宝书182页这段代码。</p>
<pre><code class="JavaScript">var name = 'The Window';
var object = {
name : 'My Object',
getNameFunc : function() {
return function() {
return this.name;
};
}
};
alert(object.getNameFunc()());</code></pre>
<p>首先定义了一个全局变量 name = 'The Window';随后在 object 对象里又重新给 name 赋值为 'My Object',但是此时 name 为局部变量,object 对象还有一个方法 getNameFunc ,这个方法返回一个闭包。</p>
<p>object.getNameFunc()() 这一表达式其实可以分解为两步:</p>
<ul><li>var first = object.getNameFunc(),调用 getNameFunc 方法,那么就相当于:</li></ul>
<pre><code class="JavaScript">var first = function() {
return this.name;
};</code></pre>
<ul><li>var second = first(),调用第一步返回的闭包,相当于:</li></ul>
<pre><code class="JavaScript">var second = function() {
return this.name;
}();</code></pre>
<p>而此时是在全局作用域中调用 first 函数,所以里面的 this 对象等于 window,那么 返回的是:window.name,就是'The Window'。</p>