chaijinsong / blog Goto Github PK
View Code? Open in Web Editor NEW博客
博客
BFC:块级格式化上下文,就是css渲染元素的一种方式,触发了BFC渲染方式的元素有以下几种特性
两个元素之间存在margin时,默认margin会重叠,并且最终的margin以较大的margin为主。如果想让margin不重叠,那么可以将之前的两个元素分别放在两个触发了BFC的元素中,这样就不会发生margin重叠了。
<div style="width:100px;height:100px;margin-bottom:20px"></div>
<div style="width:100px;height:100px;margin-top:30px"></div>
// 上面这两个div之间的margin最终为30px,而非30+20=50px;
// 解决方案:将上面两个div分别放在两个触发了BFC的元素中
<div style="overflow:hidden">
<div style="width:100px;height:100px;margin-bottom:20px"></div>
</div>
<div style="overflow:hidden">
<div style="width:100px;height:100px;margin-top:30px"></div>
</div>
// 上面用两个div将之前的元素包起来,并且两个外层的div都触发了BFC,(因为设置了overflow:hidden),此时两个元素之间的margin值为50
能够用来清除浮动,浮动的元素会脱离文档流,如果浮动元素的父元素没有触发BFC的话,那么父元素在视觉上并不会包含浮动元素,大小也不会包含浮动元素,出现子元素撑不开父元素的情况。此时如果触发父元素的BFC,那么浮动元素就能撑开父元素。
<div style="background-color: red;">
我是一串文字
<div style="float:left;width:200px;height:200px;background-color:pink;"></div>
</div>
// 上面的父元素没撑开,下面的父元素撑开了
<div style="background-color: red;overflow:hidden;">
我是一串文字
<div style="float:left;width:200px;height:200px;background-color:pink;"></div>
</div>
防止元素被浮动元素覆盖
<div style="float:left;width: 100px;height:100px;background-color:cyan;">
我是浮动的盒子
</div>
<div style="width:200px;height:200px;background-color:pink;">
我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子
</div>
// 上面的遮住,下面的没遮住
<div style="float:left;width: 100px;height:100px;background-color:cyan;">
我是浮动的盒子
</div>
<div style="width:200px;height:200px;background-color:pink;overflow:hidden;">
我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子,我是正常的盒子
</div>
上面是BFC常见的几种应用,下面是BFC触发的场景
涉及到的主要是AST相关的内容,AST(Abstract Syntax Tree)中文叫抽象语法树,是用来表示源代码语法的一种树形结构,树上的每个节点都代表源代码的一种结构。AST在我们日常应用中非常广泛,我们的代码高亮,代码检查等都是依靠的AST。
那么ES6转ES5的思路,其实就是在处理AST的过程中进行操作。转化代码的流程一般分为三步
现在一般使用的就是bable转ES6,具体的ES6转ES5在第二步中的逻辑,那就得看bable中转ES6的babel-preset-es2015
对AST进行操作的源码了
场景:electron打包后,发现子进程用不了,查看log发现是缺少一些包,但是子进程中的包在resource文件夹中都有之前的文章有介绍resource是干嘛的,为什么还会报包缺失呢?
排查错误
我们能够看到报了一个缺少 is-buffer
这个包,但是我在开发环境下没问题啊。关键点其实就是在打包的时候axios的依赖没有安装,导致打包完毕后需要用到axios的时候,axios自己的依赖没有安装,导致无法使用。
解决错误
如何解决?很简单,进入项目的node_modules
文件夹,进入子进程需要用到的包,检查该包下有没有安装依赖,如果没有则安装。
一个一个手动检查是否会太麻烦,如果子进程中用到的第三方包很多,那么一个个安装会很麻烦,有没有简便一些的方式呢?
直接写一个脚本给我们检查,在build之前执行脚本,检查指定的包下是否安装了依赖,没有的话就安装上,有的话就不忽略。
优化方案
选中的部分就是我们需要检查的包,所以我们只需要拿到这个数组,然后进入对应的目录去检查node_modules
文件夹就可以了
开始写代码
// checkPackage.js
const fs = require('fs');
const { exec } = require('child_process');
const path = require('path');
const config = require('./package.json');
const SPLIT_LENGTH = 1; // 路径中的文件夹路径切割符长度 '/' 的长度
checkPackage();
function checkPackage() {
let platform = ['mac', 'win', 'linux'];
let asarUnpackList = platform.map(name => {
return config.build[name].asarUnpack;
}).reduce((old, val) => {
return old.concat(val);
}, []);
asarUnpackList = Array.from(new Set(asarUnpackList));
let packageArr = asarUnpackList.map(item => {
let start = item.indexOf('node_modules') + 'node_modules'.length + SPLIT_LENGTH;
let tmpStr = item.substr(start);
let packageName = tmpStr.substr(0, tmpStr.indexOf('/'));
return packageName;
});
packageArr.forEach(item => {
console.log(`检查 ${item}`);
if (!fs.existsSync(`./node_modules/${item}/node_modules`)) {
console.log(`安装${item} 的依赖`);
// 在当前目录下的scripts文件夹里执行安装命令命令
exec('cnpm install', { cwd: path.join(process.cwd(), `node_modules/${item}`) }, (err, stdout, stderr) => {
if (err) {
console.log(err);
return;
}
console.log('执行了cnpm install', path.join(process.cwd(), `node_modules/${item}`));
console.log(`stdout: ${stdout}`);
});
}
});
}
就会得到如下结果(我提前将axios和archiver下的node_modules删除了):
这样就能够自动检查对应的包,不用手动去检查了。
相信很多人为了在webpack开发的时候使用 web-worker 而使用了 worker-loader 去进行处理,但是这个 loader 也存在一些问题,其实在webpack下不通过 worker-loader 也是可以使用的,仅仅需要非常简单的配置就可以。
背景:在多个worker中使用相同的包,最终build后,每个使用的worker中都集成了相同的第三方包,导致打包出来的 app.js 体积暴增,相同的第三方包无法抽离的情况。所以需要将这种方式剔除掉。并且该loader在github上的issue很多问题都没人解决,并不是很稳定。于是决定替换成web-worker原生方式
从上图可以看出,同一个 xlsx-populate.min.js
包,在worker中使用后,和worker的逻辑代码打包到了一起,在非 worker 中使用则被抽离到了 vendor
中,等于多打包了一次,如果多个worker都要用到这个包,那就每个worker都会打包一次。想想都可怕。。。
从上面打包后的结果来看 xlsx-populate
这个包已经不存在了,整个app.js 的体积明显减少。
解决思路: 既然使用原生 web-worker 方式,那么在worker中引入第三方包的话,就只能使用远程资源的方式了,相应的其他地方用到 这个包的时候,如果使用 import 方式引入,那么就需要设置 external 来解决
在抽离过程中出现的一些坑记录如下
配置 external
属性时,如下的方式配置会导致xlsx为undefined
// webpack 配置
externals: {
'xlsx-populate': 'xlsx-populate'
},
// 组件内使用
import xlsx from 'xlsx-populate';
正确配置如下:其中externals
中的value值,应该是引入该scripts后,该scripts在window上暴露出来的全局变量名称,在这里就是 XlsxPopulate
,全局变量不一定和包名相同。这一点在webpack的文档中虽然给了一个 jquery 设置 external 的例子,但是如果不注意很容易忽略掉。
// webpack 配置
externals: {
'xlsx-populate': 'XlsxPopulate'
},
// 组件内使用
import xlsx from 'xlsx-populate';
在 worker 中使用时, importScripts
并不是返回一个暴露出来的模块供我们使用,所以去哪找挂载在worker中的这个模块呢?其实这个模块被挂载在了 该worker的 self
对象上,self
就等于页面中的 windows
对象
importScripts('https://cdn-src.aiyunxiao.com/xlsx-populate/1.20.1/xlsx-populate.min.js');
const XlsxPopulate = self.XlsxPopulate;
// ... 使用 XlsxPopulate 做接下来的事
看一下最后上线后的结果:
页面中使用 script 标签引入 xlsx-populate
在导出 excel 时,直接使用的缓存的 xlsx-populate
文件,所以整体只加载一次。
不知道何时起,再也没有打开过手机QQ,更没有查看过QQ空间,顶多是打开一个TIM看一下有没有信息(事实证明并没有。。。)
这周刚换了个手机,今天晚饭后闲来无事便打开了QQ空间,翻看了一下之前朋友,同学的动态。看了之后,感觉每个人的生活都很丰富,有的从艺术学院刚毕业,有的在当老师,有的在读研究生,还有的出国旅游,坚持每天夜跑,也有每天加班的。突然感觉自己的生活并不是那么多姿多彩,为什么呢?
cookie原理解析
就是浏览器独有的一个特性,即每次发送请求都会在header中带上cookie这个请求头,所以可以用来保存一些信息,后端通过设置 Set-Cookie
请求头来给客户端设置cookie。
缺点:
代码实现:https://github.com/chaijinsong/node-study/tree/master/auth/cookie
session原理
由于cookie不能放敏感信息,并且存储空间不够大。所以可以考虑在后端存储,那么在cookie中存储的其实是一个key,后端接收到请求后通过cookie拿到key,然后去session对象中去拿对应的值。这样就在服务端保存了用户的状态信息,并且客户端也拿不到敏感信息。
缺点:
代码实现:https://github.com/chaijinsong/node-study/tree/master/auth/session
过程回顾
- 用户登录的时候,服务端生成一个token返回给客户端
- 客户端后续的请求都带上这个token
- 服务端解析token获取用户信息,并响应用户的请求
- token会有过期时间,客户端登出的时候也会废弃token,但是服务端不需要任何操作
代码实现:https://github.com/chaijinsong/node-study/tree/master/auth/token
eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJkYXRhIjoidGVzdCIsImV4cCI6MTU4NTQ5NjY0NCwiaWF0IjoxNTg1NDkzMDQ0fQ.Y2Vst5n9-wFXx_UhvEIsjRuMiDFOZF-ZqxdAICmA13I
其中令牌头和 payload 是固定的内容,后面的哈希值则是根据``令牌头 和 payload+
secret `生成的hash,所以在鉴权的时候,如果令牌头和 payload 被修改,那么和最后的hash值是不对应的,算是鉴权失败
过程:
- 用户访问app系统,app系统需要登录,此时用户没有登录
- 跳转到 sso 登录系统,sso登录系统也没有登录,此时弹出用户登录页面
- 用户填写用户名密码,sso系统认证后,将登录状态写入sso的session中,浏览器中写入sso域名下的cookie
- sso系统登录完成后生成一个 token,然后跳转到 app 系统。将token作为参数传给 app 系统
- app系统拿到 token 后,从后台向sso系统发送请求,验证 token 是否有效
- 验证通过后,app系统将登录状态写入session,并设置app域名下的cookie
至此,跨域单点登录就完成了,以后我们再次访问app系统时,app就是登录的。接下来看访问 app2系统时的流程
- 用户访问 app2 系统,app2 系统没有登录,跳转到 sso 系统进行登录
- 跳转到 sso 登录页面后,发现sso系统域名下存在cookie,说明sso系统已经处于登录状态了,不需要重新登录认证
- sso系统生成 token,浏览器跳转到 app2 系统,并将token作为参数传递给app2
- app2拿到token,后台访问 sso 验证token是否有效
- 验证成功后,app2将登录状态写入session,并且在app2域名下设置cookie
这样app2系统不需要走登录流程,就已经是登录状态了。
代码实现:https://github.com/chaijinsong/node-study/tree/master/auth/sso
以下内容总结自极客时间王争大佬的《数据结构与算法之美》课程,本文章仅供个人学习总结。
普通的测试一个算法运行的时间会收到很多因素的影响,比如一个i7处理器,一个i3处理器跑相同的代码,肯定i7更快。不同的输入得到的测试数据也不同,比如并不是所有的数据量用快速排序就会比插入排序快。所以我们需要去掉这些影响因素,得到一个相对公平的估算算法执行效率的方法。也就是时间、空间复杂度分析。
时间复杂度表达的是一种趋势,即随着输入的不同,代码运行时间的趋势是怎样的。所以我们通常会忽略掉常量和低阶系数,只需要关注最大阶的量级就可以了。所以分析算法复杂度的时候只需要关注循环执行次数最多的那一段代码就可以了。下面一个简单的例子。
function cal(n) {
let sum = 0;
for(let i = 1; i <= n; i++) {
sum = sum + i;
}
return sum;
}
我们很容易看到循环最多的是第3、4行代码,所以对这块进行重点分析,这两行代码被执行了n次,所以总的时间复杂度就为O(n)
接下来看一个稍微多一点的代码,分析进行分析
function cal(n) {
let sum_1 = 0;
for (let p = 1; p < 100; p++) {
sum_1 = sum_1 + p;
}
let sum_2 = 0;
for(let q = 1; q < n; q++) {
sum_2 = sum_2 + q;
}
let sum_3 = 0;
for (let i = 0; i <= n; i++) {
for (let j = 1; j < n; j++) {
sum_3 = sum_3 + i + j;
}
}
return sum_1 + sum_2 + sum_3;
}
代码分三部分,分别求 sum_1、sum_2、sum_3,我们一个一个分析。
求sum_1,循环了100次,因为100是个常量,和n没有任何关系。所以求sum_1的时间复杂度为O(1)
求sum_2,循环了n次,和n是有关系的,并且n是多少就循环多少次,所以求sum_2的时间复杂度为O(n)
求sum_3,看到有两个for循环,其中执行最多的代码有sum_3 = sum_3 + i + j;
外层的for循环执行了n次,内层的for循环在每次外层循环一次时会执行n次,所以最多执行了n*n次。所以sum_3的时间复杂度为O(n^2)
整体的时间复杂度为 O(1)、O(n)、O(n^2)的最大值,即O(n^2)
function cal(n) {
let ret = 0;
for (let i = 1; i <= n; i++) {
ret = ret + f(i);
}
}
function f(n) {
let sum = 0;
for (let i = 0; i <= n; i++) {
sum = sum + i;
}
return sum;
}
单独看cal()函数,假设f()是一个普通操作,那么cal()的时间复杂度就是O(n),但是f()不是一个简单的操作,f()的时间复杂度也是O(n),并且f()是嵌套在cal()的循环中,所以cal()函数的时间复杂度为O(n) * O(n) = O(n^2)
虽然代码千差万别,但是常见的复杂度也就那几种。按照复杂度的数量级进行排序如下:O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)、O(n^3)、O(n^k)、O(2^n)、O(n!)
上面的几种复杂度量级可以分为两种,一种是多项式级别和非多项式级别,上面的复杂度量级中 O(2^n)和O(n!)就是非多项式级别,随着n的增长,执行时间会极具增加,所以讨论这两种基本上没多大意义。我们常见的一些复杂度其实就是几种多项式级别的复杂度。
O(1): 并不是只执行了一行代码,而是代码的执行时间不随着n的增长而增长,那么时间复杂度就是O(1)。下面举个例子:
function cal(n) {
let sum = 0;
for (let i = 1; i <= 10000; i++) {
sum = sum + i + n;
}
}
不管n多大,整个代码都是执行10000次,这个函数的时间复杂度就是O(1)。
O(logn):这种的可能不大好直接说,我们直接上代码去分析
function cal(n) {
let i = 1;
while(i <= n) {
i = i * 2;
}
}
我们从代码中可以看到,i每次是乘2的,所以循环出来就是 2^1 2^2 2^3 ... 2^x = n,我们知道x的值是多少就知道运行了多少次,根据数学运算,x=log以2为底n的对数,所以时间复杂度为
现在再改一下代码
function cal(n) {
let i = 1;
while(i <= n) {
i = i * 3;
}
}
和上面的一样的套路,那么时间复杂度就是$O(log_3^n)$,实际上,不管是以2还是3或者10为底,我们都可以把所有对数阶的时间复杂度记为$O(logn)$,因为根据数学中的对数运算来说
同理,根据上面讲过的乘法法则,如果一段代码的时间复杂度为$O(logn)$,我们循环执行n遍,那么时间复杂度就成了
O(m + n)、O(m * n)
functin cal(m, n) {
let sum_1 = 0;
for (let i = 0; i < m; i++) {
sum_1 = sum_1 + i;
}
let sum_2 = 0;
for (let j = 0; j < m; i++) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
上面的代码,有两个输入,根据之前的标准,要找循环次数最多的代码作为时间复杂度,但是两个输入是不确定哪个大哪个小,无法忽略其中一个。所以整个代码的时间复杂度为O(m + n)
前面的时间复杂度讲的是执行时间与数据规模之间的增长关系,空间复杂度则是算法的存储空间和数据规模之间的增长关系。
function fn(n) {
let arr = new Array(n);
for (let i = 0; i < n; i++) {
arr[i] = i;
}
}
上面的第二行代码我们创建了一个长度为n的数组,和创建了一个i变量,但是i变量是常量级别的,和n没有关系所以可以忽略。剩下的除了一个长度为n的数组没有占用其他的空间,所以整个代码的空间复杂度为O(n)。
我们常见的空间复杂度O(1),O(n),O(n^2) ,像$O(logn)$,$O(nlogn)$ 这样的对数阶在空间复杂度中就基本上不会碰到。
用一张图来表示各个复杂度随着数据量的增长趋势,让我们能更直观的感受到不同算法之间的性能差异。一些基本的算法基本上复杂度都是图上的这几个。在看代码的时候,多思考,也可以多想想自己现在写的代码时间空间复杂度是多少,是否能够降低,长此以往,能够大大提升自己的代码质量和代码性能。
有人说,我们项目之前都会进行性能测试,再做代码的时间复杂度、空间复杂度分析,是不是多此一举呢?而且,每段代码都分析一下时间复杂度、空间复杂
度,是不是很浪费时间呢?你怎么看待这个问题呢?
- 性能测试和做代码的时间空间复杂度进行分析并不冲突,在开发的时候就考虑到时间复杂度和空间复杂度,能够降低后期维护的成本,性能测试一般是在开发完毕后,如果测试结果不达标,再去返工,会有更大的成本。
- 并不是一定要对每一行代码进行时间空间复杂度分析,一个项目动辄几万代码,一行一行的分析是不切实际也是没必要的,开发人员有了时间空间复杂度意识之后,在某些需要注意的地方去刻意注意一下时间空间复杂度,能够让项目性能更好。比如前端做一些复杂动画之类的操作的时候,就需要注重观察时间空间复杂度,否则动画就会卡顿。重要的是知道在什么时候需要复杂度分析,而不是对全部代码进行复杂度分析或者直接忽略复杂度分析。
本文章旨在能够为大家提供virtualDOM相关的**和如何去设计一个virtualDOM,并且如何能够将virtualDOM转化为真实的DOM,至于virtualDOM中的diff算法,由于涉及到的内容较多,我会放在下一周的博客中详细介绍virtualDOM的diff算法。
其基本思路如下:
输出一个div元素的所有属性看看
我们发现存在太多属性了,这就是DOM对象,我们如果想对DOM进行比较的话,如果使用原生的DOM比较的话,可能光遍历这些属性就非常慢了。所以我们现在使用js对象来作为一个DOM对象的映射,virtualDOM等价于是一个缓存,我们的所有的状态改变都在这个缓存中进行修改,然后修改完毕后,再应用到真实的DOM中。这样就避免了直接操作DOM。我们接下来就开始构建一个virtualDOM
一、使用js模拟一个DOM的结构
原理:
document.createElement
创建元素document.setAttribute
设置元素属性document.createTextNode
渲染文本appendChild
将创建的子元素插入到页面中原理基本就是上面几步,我们接下来使用代码实现:
class VNode {
// 构造函数
constructor(tag, attrs, children) {
this.tag = tag;
this.attrs = attrs || {};
this.children = children;
}
// 转化为DOM的方法
render() {
console.log(this.tag);
const el = document.createElement(this.tag); // 创建元素
let attrs = this.attrs;
for (var attr in attrs) { // 设置元素属性
var value = attrs[attr];
el.setAttribute(attr, value);
}
const children = this.children || [];
children.forEach(child => {
let childEl = (child instanceof VNode) // 判断子节点是否为VNode类型,如果是则继续render,否则视为文本节点
? child.render()
: document.createTextNode(child);
el.appendChild(childEl);
});
return el; // 返回最终的DOM
}
}
const tree = new VNode('div', {class: 'div'}, [
new VNode('h1', {style: 'color: pink;'},['我是文本']),
new VNode('ul', undefined, [
new VNode('li', undefined, ['1111']),
new VNode('li', undefined, ['2222']),
new VNode('li', undefined, ['2222']),
])
]);
let realDOM = tree.render();
console.log(realDOM);
document.body.appendChild(realDOM);
最后在浏览器中渲染出来的结果就是这样,我们也达到了使用virtualDOM渲染真实DOM的目的
通过上面的简单模拟,我们已经基本上知道了virtualDOM如何去渲染真实DOM的过程,其实最终肯定还是落实到真实的DOM操作上,并没有什么难点,主要就是一个**,为什么要这样去设计,有什么好处。当然上面的这个例子是比较简陋的,很多条件并没有进行处理,例如如何处理事件等。但是主要**需要理解。
通过HTTPS握手中的第二步获取到服务端给客户端的数字证书,先从系统(windows)或者浏览器内置的(firefox)检查证书链是否正确
验证失败则拦截
如果证书链验证成功,浏览器会尝试查CRL(证书吊销列表)和OCSP(在线证书检查),其中OCSP是用来代替CRL的,因为CRL的发布时间一般是7天(接收到新通知就是1天)并且很大不方便。但是考虑到老浏览器只能用CRL,并且CRL可以缓存本地对于网速差情况还是有用的,此外Firefox虽然支持OCSP但是可以手动关闭也是CRL存在的原因。
注意:CA(数字证书)不会直接暴露到外网的,如果需要访问CA服务器需要使用硬件Token并且多人在场录像,且只能远程访问。OCSP相当于证书数据库的备份而已,是直接暴露在外网的可以通过HTTP或者HTTPS访问
如果发现证书并没有被吊销或者过期则浏览器对EV证书会显示为绿色,对OV证书则是通过放行。否则弹出通知---该网站不可信(不同浏览器不同--Edge浏览器)
回顾一下HTTPS握手过程
<html>
<head>
<style>
.parent {
width: 100%;
height: 100px;
background: cyan;
display: flex;
justify-content: center;
align-items: center;
}
.son {
width: 20%;
height: 20%;
background: pink;
}
</style>
</head>
<body>
<div class='parent'>
<div class='son'></div>
</div>
</body>
</html>
<html>
<head>
<style>
.parent {
position: relative;
width: 200px;
height: 200px;
background: pink;
}
.son {
position: absolute;
left: 50%;
top: 50%;
margin-left: -25px;
margin-top: -25px;
width: 50px;
height: 50px;
background: yellow;
}
</style>
</head>
<body>
<div class='parent'>
<div class='son'></div>
</div>
</body>
</html>
<html>
<head>
<style>
.parent {
position: relative;
width: 200px;
height: 200px;
background: cyan;
}
.son {
position: absolute;
left: 0;
top: 0;
bottom: 0;
right: 0;
margin: auto;
width: 10%;
height: 10%;
background: yellow;
}
</style>
</head>
<body>
<div class='parent'>
<div class='son'></div>
</div>
</body>
</html>
<html>
<head>
<style>
.parent {
display: grid;
}
.son {
jusitify-self: center;
align-self: center;
}
</style>
</head>
<body>
<div class='parent'>
<div class='son'></div>
</div>
</body>
</html>
<html>
<head>
<style>
.parent {
display: table-cell;
vertical-align: middle;
text-align: center;
width: 100vw;
height: 90vh;
background-color: yellowgreen;
}
.son {
display: inline-block;
width: 200px;
height: 200px;
background-color: Indigo;
}
</style>
</head>
<body>
<div class='parent'>
<div class='son'></div>
</div>
</body>
</html>
<html>
<head>
<style>
.parent {
height: 100vh;
width: 100vw;
text-align: center;
background: #c0c0c0;
}
.parent:before {
content: "\200B";
display: inline-block;
height: 100%;
vertical-align: middle;
}
.son {
display: inline-block;
vertical-align: middle;
width: 200px;
height: 200px;
padding: 10px 15px;
background: #f5f5f5;
}
</style>
</head>
<body>
<div class="parent">
<div class="son"></div>
</div>
</body>
</html>
5 + 17 = 22
为例子
普通的加法运算分三步:
二进制的计算是否也符合上面的规则呢?
5的二进制 101 num.toString(2) => 十进制转二进制
17的二进制 10001
parseInt('10110', 2) => 二进制转十进制,得到22
所以也是符合的,那么我们可以吧上面计算二进制的加法用位运算来替换
function plus(num1, num2) {
if(num2 == 0)
return num1;
let sum = num1 ^ num2;
let carry = (num1 & num2) << 1;
return plus(sum, carry);
}
console.log(plus(19, 11));
给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9
我的心历路程:
碰到最少、最短这种字眼的话,现在我一开始想到的就是广度优先遍历 + 队列来解决这种类似问题。
“Talk is cheap. Show me the code.” --Linus Torvalds
/**
* 广度优先搜索,耗时严重,思路:
* 1. 计算出可能的完全平方数的数组
* 2. 设置一个数组,初始化元素为传入的正整数
* 3. 设置一个step为0
* 3. 循环这个数组,让数组中的每个元素都删除完全平方数中的每一个元素,第一个差为0的,说明就是最短路径
*/
var numSquares = function(n) {
let MaxSquare = Math.ceil(Math.sqrt(n));
function getAvailableSquareArr(num) {
let arr = [];
for (let i = 1; i<=num; i++) {
arr.push(Math.pow(i, 2));
}
return arr;
}
let squareArr = getAvailableSquareArr(MaxSquare); // 可能的完全平方数组成的数组
let squareLength = squareArr.length; // 完全平方数组长度
let subArr = [n]; // 用来存放每次减去完全平方数的数组,初始值为传入的正整数
let step = 0;
while(subArr.length) {
step++;
let len = subArr.length;
for (let j = 0; j < len; j++) {
let value = subArr.shift(); // 队首出队列
for (let i = 0; i < squareLength; i++) {
let sub = value - squareArr[i];
if (sub === 0) return step;
if (sub < 0) {
break;
}
if (!subArr.includes(sub)) {
subArr.push(sub);
}
}
}
}
return step;
};
上面的这种解法我们看一下执行耗时
竟然要解决6s的时间,可见这种方式固然能够求出结果,但是其计算的效率并不高。我们来分析一下他的时间复杂度是多少:
得到时间复杂度为O(n^3),这里时间复杂度我个人也不大确定是否为O(n^3),如果您知道怎么算,请在评论解惑。
所以我们需要一种更高效的方式来计算。于是引入了动态规划的方式解决该题。动态规划传送门
来自wiki百科:动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本**非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。
动态规划解决这个问题我也在leecode上看过解释,但是自己就是看不大懂。直到写文章的今天我也还是一知半解。所以使用动态规范解决的方式我现在的水平还讲不清楚,但是我先把动态规划解决的代码放在这,待日后补充具体的思路。各位大佬如果觉得能够讲清楚,也可以在留言处写下自己的思路。带带小弟我。
function numSquares(n) {
const dp = [0];
for (let i = 1; i <= n; i++) {
dp[i] = Number.MAX_VALUE;
for (let j = 1; j*j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i-j*j]+1);
}
}
return dp[n];
}
双向数据绑定是对表带元素使用v-model指令来实现双向数据绑定的,本质上是监听用户输入事件以更新数据,不通过mutation,直接修改值
vuex则规定了修改值值必须通过mutation进行修改
上面两者其实就已经冲突了,如果v-model绑定的是vuex中的值,由于v-model直接修改该值,vuex会报错。所以如果出现这种情况可以有两种方法来解决
不使用v-model,而是使用value来指定表单的值,并且监听表单的input或者change事件,通过mutation来修改值
<input :value="message" @input="updateMessage">
// ...
computed: {
...mapState({
message: state => state.obj.message
})
},
methods: {
updateMessage (e) {
this.$store.commit('updateMessage', e.target.value)
}
}
// ...
mutations: {
updateMessage (state, message) {
state.obj.message = message
}
}
使用v-model,但是v-model的值为一个计算属性,在这个计算属性的set方法中去调用mutation修改值,在get方法中去返回vuex中的state
<input v-model="message">
// ...
computed: {
message: {
get () {
return this.$store.state.obj.message
},
set (value) {
this.$store.commit('updateMessage', value)
}
}
}
以下内容总结自极客时间王争大佬的《数据结构与算法之美》课程,本文章仅供个人学习总结。
从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。
类比图书馆的书籍,我们如果想找一本书可以有很多种方法能找到这本书,可以从头一本一本找,也可以根据分类来缩小范围找。毫无疑问后一种耗时更少。这就是生活中的算法。
算法和数据结构是联系在一起的,特定的数据结构有特定的算法去操作,数据结构为算法提供服务,算法又依赖于特定的数据结构。比如广度优先遍历就可以作用在树或者图上,但是没有对数组进行广度优先遍历的。
数据结构是静态的,它只是组织数据的一种方式。如果不在它的基础上操作、构建算法,孤立存在的数据结构就是没用的。
3. 切记不要只是死记硬背,不要为了学习而学习,而是要学习它的“来历”“自身的特点”“适合解决的问题”以及“实际的应用场景”,多辩证地思考,多问为什么
“边学边练”这一招非常有用。建议你每周花1~2个小时的时间,集中把这周的三节内容涉及的数据结构和算法,全都自己写出来,用代码实现一遍。这样一定会比单纯地看或者听的效果要好很多!
学习最好的方法是,找到几个人一起学习,一块儿讨论切磋,写博客是一件可以交流和思考的很好的方式
每节课后都写一篇学习笔记或者学习心得,可以不用太长,但是一定要有思考。证明自己有进步
在学习的过程中,一定会碰到“拦路虎”。如果哪个知识点没有怎么学懂,不要着急,这是正常的。因为,想听一遍、看一遍就把所有知识掌握,这肯定是不可能的。学习知识的过程是反复迭代、不断沉淀的过程。 如果碰到“拦路虎”,可以请教他人,或者可以先沉淀一下,过几天再重新学一遍。所谓,书读百遍其义自见,我觉得是很有道理的!
思考学习数据结构与算法的方法。另外,你在之前学习数据结构和算法的过程中,遇到过什么样的困难或者疑惑吗?
主要是利用每天的通勤时间听大佬的课程,对照着讲义看,然后每次听完一节课些一篇总计记录下本节的内容和自己的思考,将自己的小节记录放在github上,能够促进自己坚持下去。
最近刷leecode就碰到了一个动态规划的问题,断断续续想了一周没有解决,代码很简单,但是自己对动态规划的思维方式有些不理解,导致卡顿。所以订了大佬的课程想系统的学习数据结构与算法。
DOCTYPE
是什么:是用来将特定的 SGML(标准通用标记语言) 文档 和 DTD(文档类型定义) 文件 相关联的指令,其中 DTD 就是 解析SGML 的一系列规则,HTML5以前的版本就是派生于 SGML ,但是最新的 HTML5 并不是基于 SGML 。
解决的问题:我们知道 HTML 也是有版本的,目前最新的 HTML 版本就是 HTML5。不同版本的 HTML 有不同的解析规则,如果不告诉浏览器用什么版本的规则去解析 HTML那么我们的标签和 CSS可能都不会正常工作,所以需要在 HTML 中明确告诉浏览器用什么规则去解析我们的 HTML 文档
如何使用:
上面说过最新的 HTML5 不再基于 SGML ,所以无需引用 DTD 文件 来告诉浏览器用什么规则解析 SGML ,所以 HTML5 中的 DOCTYPE只需要如下声明,浏览器就能正确渲染页面
<!DOCTYPE html>
HTML 4.0 版本则规定了三种 DTD文件,分别是 Strict
、Transitional
、Frameset
Strict
严格的DTD不允许使用已经废弃的元素如(font) 或者表现性元素(br)
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
"http://www.w3.org/TR/html4/strict.dtd">
Transitional
过渡DTD允许一些较旧的PUBLIC和已弃用的属性
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
Frameset
如果使用框架,则必须使用框架集DTD,允许废弃元素,表现性元素,以及frameset标签
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Frameset//EN"
"http://www.w3.org/TR/html4/frameset.dtd">
如果没有写 doctype
指令或者指令写错了,或者指令并不是写在第一行,那么浏览器会默认使用自己的 BackCompat 怪异模式,这种怪异模式会根据不同浏览器的不同展示不同的样式。
如果 doctype
写对了,那么就按照doctype指定的规则去解析。被称为 标准模式
标准模式和怪异模式可以通过 document.compactMode
来 判断,如果值为 CSS1Compat
说明是标准模式,如果值为 BackCompat
则为怪异模式
高级程序设计中写道new一个构造函数会经历以下步骤
- 创建一个新对象
- 将构造函数的作用域赋给新对象(因此this就指向了新对象)
- 执行构造函数中的代码(为新对象新增属性)
- 返回新对象
注意:实例._proto_ === 构造函数.prototype
function _new(fn, ...arg) {
const obj = Object.create(fn.prototype); // 因为实例的.__proto__ === 构造函数的.prorotype,所以第一步使用Object.create(fn.prototype)给新对象设置原型链
const ret = fn.apply(fn, arg); // 将2,3步都做了
return ret instanceof Object ? ret : obj; // 判断构造函数执行的返回值是什么,如果是对象就使用构造函数返回值,如果不是则使用创建的对象。一般来说构造函数都是没有返回值的。
}
数组从标准定义上来讲,是一串连续的内存地址,在C语言中定义数组时就得确定数组的长度,因为C语言是严格按照申请的内存地址来存储的,所以如果数组超出了申请的长度,就会出现数组越界的情况,因为C并不会进行动态扩容。在C中数组的寻址公式为:base + index * size,也就是基础地址 + 下标 * 每一个元素的大小,这样获取到指定下标的地址不需要循环,只需要计算一次就能够找到对应的值
在javascript中,数组定义可以不确定数组长度,基本上不会见到数组越界的问题,因为js中的数组会动态的扩容,而且js中的数组并不是一个连续的内存,所以上面的寻址公式在js中不起作用。在js中获取数组地址其实就是使用hash表的方式,每个下标对应的存储着一个地址,直接通过这个地址就能拿到元素的值,所以取第一个元素和取第10万个元素并没有什么区别。因为压根不需要循环。两者时间差可以忽略不计。
change事件在失去焦点的时候触发,input事件再value值修改的时候触发(输入中文过程中也会触发,所以会有问题)
一般情况下我们对输入进行防抖处理就是直接给input事件加上处理函数,并且将处理函数用防抖函数包裹起来
function debunce(fn, dealy) {
let timer;
return function(fn) {
clearTimeout(timer);
timer = setTimeout(function() {
fn.apply(this, arguments);
}, dealy);
}
}
由于需要对中文输入做处理,所以直接监听keyup会导致input中没内容但是事件处理函数多次触发,所以需要使用其他事件。目前element-ui使用的就是 compositionstart
compositionupdate
compositionend
这三个事件来处理中文输入问题。注意,当直接输入数字或者英文的时候,这三个事件是不会触发的,只有在其他输入情况下会触发,例如打汉字需要根据拼音选择文字之类的情况才会触发。
compositionstart
: 事件触发于一段文字的输入之前(类似于keydown)
compositionupdate
: 事件触发于字符被输入到一段文字的时候(这些可见字符的输入可能需要一连串的键盘操作、语音识别或者点击输入法的备选词)
compositionend
: 当文本段落的组成完成或取消时
在输入中文的时候:
compositionstart
和 compositionupdate
compositionupdate
compositionend
为了只写一个处理函数,监听input事件,如果是非输入汉字类情况,直接走input中的处理函数,如果是输入汉字类情况,那么在 compositionend
触发的时候主动去调input事件的处理函数。
17.45*0.9*3 = 47.115
,调换顺序后17.45*3*0.9 = 47.114999999999995
就算保留两位小数,那也不相等。所以需要保证两个地方的计算顺序一致打个比方,我们知道尺这个单位,一米等于三尺,如果我要买一尺红布,两尺黑布,那我需要把一米红布的三分之一拿出来,但是一米布的三分之一并不确定,因为他是一个无限循环的小数,所以只能取一个大概的值
两尺黑布同理也是一个不确定的值,这样当红布和黑布加在一起,并不一定就长一米,而是接近一米。
上面的例子就和我们0.1+0.2 != 0.3 一个道理,因为需要将0.1转化为二进制,将0.2转化为二进制,然后将两个二进制相加后再转为10进制,就在转化的过程中出现了偏差(类比尺和米的转化),所以导致结果并不是我们期望的那样,而是一个近似值。
解决方法:
(0.1*10 + 0.2*10) / 10 = 0.3
就是成立的了cookie:登陆后后端生成一个sessionid放在cookie中返回给客户端,并且服务端一直记录着这个sessionid,客户端以后每次请求都会带上这个sessionid,服务端通过这个sessionid来验证身份之类的操作。所以别人拿到了cookie拿到了sessionid后,就可以完全替代你。
token:登陆后后端返回一个token给客户端,客户端将这个token存储起来,然后每次客户端请求都需要开发者手动将token放在header中带过去,服务端每次只需要对这个token进行验证就能使用token中的信息来进行下一步操作了。
xss:用户通过各种方式将恶意代码注入到其他用户的页面中。就可以通过脚本获取信息,发起请求,之类的操作。
csrf:跨站请求攻击,简单地说,是攻击者通过一些技术手段欺骗用户的浏览器去访问一个自己曾经认证过的网站并运行一些操作(如发邮件,发消息,甚至财产操作如转账和购买商品)。由于浏览器曾经认证过,所以被访问的网站会认为是真正的用户操作而去运行。这利用了web中用户身份验证的一个漏洞:简单的身份验证只能保证请求发自某个用户的浏览器,却不能保证请求本身是用户自愿发出的。csrf并不能够拿到用户的任何信息,它只是欺骗用户浏览器,让其以用户的名义进行操作。
csrf例子:假如一家银行用以运行转账操作的URL地址如下: http://www.examplebank.com/withdraw?account=AccoutName&amount=1000&for=PayeeName
那么,一个恶意攻击者可以在另一个网站上放置如下代码:<img src="<http://www.examplebank.com/withdraw?account=Alice&amount=1000&for=Badman>">
如果有账户名为Alice的用户访问了恶意站点,而她之前刚访问过银行不久,登录信息尚未过期,那么她就会损失1000资金。
上面的两种攻击方式,如果被xss攻击了,不管是token还是cookie,都能被拿到,所以对于xss攻击来说,cookie和token没有什么区别。但是对于csrf来说就有区别了。
以上面的csrf攻击为例:
这是个人理解的为什么只劫持cookie不劫持token的原因。
为何不能修改:为了保证数据的单向流动,便于对数据进行追踪,避免数据混乱。官网有详细的信息 prop
所有的 prop 都使得其父子 prop 之间形成了一个单向下行绑定:父级 prop 的更新会向下流动到子组件中,但是反过来则不行。这样会防止从子组件意外改变父级组件的状态,从而导致你的应用的数据流向难以理解。
vue如何知道修改了父组件传来的props?
下面的代码就是实现Vue提示修改props的操作,在组件 initProps
方法的时候,会对props进行defineReactive操作,传入的第四个参数是自定义的set函数,该函数会在触发props的set方法时执行,当props修改了,就会运行这里传入的第四个参数,然后进行判断,如果不是root根组件,并且不是更新子组件,那么说明更新的是props,所以会警告
// src/core/instance/state.js 源码路径
function initProps (vm: Component, propsOptions: Object) {
const propsData = vm.$options.propsData || {}
const props = vm._props = {}
// cache prop keys so that future props updates can iterate using Array
// instead of dynamic object key enumeration.
const keys = vm.$options._propKeys = []
const isRoot = !vm.$parent
// root instance props should be converted
if (!isRoot) {
toggleObserving(false)
}
for (const key in propsOptions) {
keys.push(key)
const value = validateProp(key, propsOptions, propsData, vm)
/* istanbul ignore else */
if (process.env.NODE_ENV !== 'production') {
const hyphenatedKey = hyphenate(key)
if (isReservedAttribute(hyphenatedKey) ||
config.isReservedAttr(hyphenatedKey)) {
warn(
`"${hyphenatedKey}" is a reserved attribute and cannot be used as component prop.`,
vm
)
}
defineReactive(props, key, value, () => {
if (!isRoot && !isUpdatingChildComponent) {
warn(
`Avoid mutating a prop directly since the value will be ` +
`overwritten whenever the parent component re-renders. ` +
`Instead, use a data or computed property based on the prop's ` +
`value. Prop being mutated: "${key}"`,
vm
)
}
})
} else {
defineReactive(props, key, value)
}
// static props are already proxied on the component's prototype
// during Vue.extend(). We only need to proxy props defined at
// instantiation here.
if (!(key in vm)) {
proxy(vm, `_props`, key)
}
}
toggleObserving(true)
}
// src/core/observer/index.js
/**
* Define a reactive property on an Object.
*/
export function defineReactive (
obj: Object,
key: string,
val: any,
customSetter?: ?Function,
shallow?: boolean
) {
const dep = new Dep()
const property = Object.getOwnPropertyDescriptor(obj, key)
if (property && property.configurable === false) {
return
}
// cater for pre-defined getter/setters
const getter = property && property.get
const setter = property && property.set
if ((!getter || setter) && arguments.length === 2) {
val = obj[key]
}
let childOb = !shallow && observe(val)
Object.defineProperty(obj, key, {
enumerable: true,
configurable: true,
get: function reactiveGetter () {
const value = getter ? getter.call(obj) : val
if (Dep.target) {
dep.depend()
if (childOb) {
childOb.dep.depend()
if (Array.isArray(value)) {
dependArray(value)
}
}
}
return value
},
set: function reactiveSetter (newVal) {
const value = getter ? getter.call(obj) : val
/* eslint-disable no-self-compare */
if (newVal === value || (newVal !== newVal && value !== value)) {
return
}
/* eslint-enable no-self-compare */
if (process.env.NODE_ENV !== 'production' && customSetter) {
customSetter()
}
// #7981: for accessor properties without setter
if (getter && !setter) return
if (setter) {
setter.call(obj, newVal)
} else {
val = newVal
}
childOb = !shallow && observe(newVal)
dep.notify()
}
})
}
如果传入的props是基本数据类型,子组件修改父组件传的props会警告,并且修改不成功,如果传入的是引用数据类型,那么修改改引用数据类型的某个属性值时,对应的props也会修改,并且vue不会抱警告。
开始加密通信前,需要客户端和服务器需要先建立连接,交换参数,这个过程叫握手。a
握手过程分为5步:
canvas.toDataURL('image/png')
,此时图片的宽高就是canvas画布的宽高。他不受css宽高的影响,即使在页面上canvas可能是拉伸了的,但是最终生成的图片其实是正常比例的。scale(0.5, 0.5)
就是将宽高单位缩小为原有的0.5倍,scale(2,2)
就是将宽高单位放大为原来的2倍。这个属性可以用在兼容不同分辨率设备的场景以下内容总结自极客时间王争大佬的《数据结构与算法之美》课程,本文章仅供个人学习总结。
上一个文章主要是讲了几种计算时间复杂度的几个法则:
常见的时间复杂度,由低到高排序:
接下来介绍一下几种新的复杂度:
function find(array, n, x) {
let pos = -1;
for (let i = 0 ; i < n; ++i) {
if (array[i] === x) {
pos = i;
}
}
return pos;
}
上面的代码是用来在数组中寻找变量x出现的位置,如果没有找到就返回-1,我们一眼能看出代码的时间复杂度为$O(n)$。但是这个代码是可以优化的,因为可能中途就找到了这个元素,就不需要继续后面的循环了。所以我们改一下代码
function find(array, n, x) {
let pos = -1;
for (let i = 0 ; i < n; ++i) {
if (array[i] === x) {
pos = i;
break;
}
}
return pos;
}
修改完毕后,这个函数的时间复杂度还是$O(n)$吗?不一定把,因为都不一定会执行n次,可能数组的第一个元素就是x,也可能数组的第n个元素为x,那么这两种情况一个执行一次,一个执行n次。所以就有了最好时间复杂度、最坏时间复杂度,顾名思义就是最理想情况下的复杂度和最不理想下的时间复杂度,对应到上面的find函数,最好时间复杂度就是$O(1)$,数组第一个元素就是x,最坏时间复杂度为$O(n)$
最好时间复杂度和最坏时间复杂度都是极端情况下的代码复杂度,这种情况比较少,发生的概率并不大。为了更好的表示平均情况,于是有了平均时间复杂度。
平均时间复杂度的分析方式,还是以上面的例子分析。
function find(array, n, x) {
let pos = -1;
for (let i = 0 ; i < n; ++i) {
if (array[i] === x) {
pos = i;
break;
}
}
return pos;
}
要查找的变量x在数组中的位置有n+1种情况:0 ~ n-1 和不在数组中,将每一种情况需要循环的次数加起来,除以n+1就得到了平均需要遍历的元素个数。
化简后忽略低阶,常量、系数,得到平均时间复杂度为$O(n)$。虽然我们得到的$O(n)$看起来非常prefect,但是我们忽略了一点,就是每一种情况发生的概率是一样的吗?x在数组中和x在数组中第2个位置的概率是一样的吗?
很明显并不一样,我们假设x在数组中和不再数组中的概率55开,都为
最后化简得到的还是$O(n)$,这在概率论中叫期望值,所以平均时间复杂度又叫期望时间复杂度。
均摊时间复杂度
其实均摊时间复杂度个人理解是平均时间复杂度的一种,均摊时间复杂度分析起来更加简单,不需要像上面的平均时间复杂度那么复杂的计算,而是通过找规律直接计算出时间复杂度。怎么找规律呢?下面用一个例子来分析。
let array = new Array(n);
let count = 0;
function insert(val) {
if (count === array.length) {
let sum = 0;
for (let i = 0; i<array.length; i++) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
这段代码实现了一个往数组中插入数据的功能。当数组满了之后,也就是代码中的count == array.length时,我们用for循环遍历数组求和,并清空数组,将求和之后的sum值放到数组的第一个位置,然后再将新的数据插入。但如果数组一开始就有空闲空间,则直接将数据插入数组。
我们分析以下这段代码的时间复杂度
总结
一、复杂度分析的4个概念
1.最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。
2.最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。
3.平均时间复杂度:用代码在所有情况下执行的次数的期望值表示。
4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂 度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
二、为什么要引入这4个概念?
1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。
2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。
分析下面add函数的时间复杂度
let array = new Array(10);
let len = 10;
let i = 0;
function add(element) {
if(i >= len) {
// 申请两倍长度的数组空间
let new_array = new Array(len*2);
for(let j = 0; j < len; j++) {
// copy原来的array,到new_array中
new_array[j] = array[j];
}
// array大小为2倍len
array = new_array;
len = 2*len;
}
// element放在下标为1的位置,下标i加1
array[i] = element;
++i;
}
array[i]=element
, 此时最好时间复杂度为$O(1)$ES 是什么?
是一个开源的搜索引擎,建立在一个全文搜索引擎库(Apache Lucene)基础上。ES使用java对Lucene进行了封装,隐藏了Lucene的复杂性,取而代之是提供一套简单的 RESTful API。
面向文档
在应用程序中对象一般比较复杂,如果把这些对象存储在数据库中,使用关系型数据库的行和列来存储,那么必须将这个复杂对象扁平化,非常的麻烦。而ES是面向文档的,它存储整个对象或者文档,并且对每个文档的内容进行索引,使其能够被搜索到。这是ES支持复杂全文搜索的原因。我们搜索出来的一条数据就叫 文档
索引在ES中的不同含义
索引(名词):
一个 索引 类似于传统数据库中的一个 数据库 ,是存储关系型文档的地方
索引(动词):
索引 一个文档就睡存储一个文档到一个 索引(名词) 中,以便被检索和查询。
新增索引(名词)
下面给ES中新增雇员数据
PUT /megacorp/employee/1
{
"first_name" : "John",
"last_name" : "Smith",
"age" : 25,
"about" : "I love to go rock climbing",
"interests": [ "sports", "music" ]
}
路径 /megacorp/employee/1
包含了三部分信息:
megacorp
: 索引名词
employee
: 类型名称
1
: 特定雇员的ID
搜索指定ID的雇员
直接执行GET请求,指明文档的地址------ 索引库(索引名称)、类型和ID
GET /megacorp/employee/1
返回值为:
{
"_index" : "megacorp", // 索引库(索引名称)
"_type" : "employee", // 类型
"_id" : "1", // Id
"_version" : 1,
"found" : true,
"_source" : { // 存储的信息
"first_name" : "John",
"last_name" : "Smith",
"age" : 25,
"about" : "I love to go rock climbing",
"interests": [ "sports", "music" ]
}
}
搜索所有人
GET /megacorp/employee/_search
返回结果包含了所有的人的文档,放在数组 hits
中。一个搜索默认返回十条结果
{
"took": 6,
"timed_out": false,
"_shards": { ... },
"hits": {
"total": 1,
"max_score": 1,
"hits": [
{
"_index" : "megacorp", // 索引库(索引名称)
"_type" : "employee", // 类型
"_id" : "1", // Id
"_version" : 1,
"found" : true,
"_source" : { // 存储的信息
"first_name" : "John",
"last_name" : "Smith",
"age" : 25,
"about" : "I love to go rock climbing",
"interests": [ "sports", "music" ]
}
}
]
}
}
同理,搜索指定条件的文档(文档就是每个人的信息)
GET /megacorp/employee/_search?q=last_name:Smith
找出 last_name
为 Smith
的文档信息
上面的搜索,都是很简单的搜索,直接写在请求的url中,但在这种搜索不够灵活强大,所以ES提供了 DSL 支持更复杂的查询语句,上面的搜索Smith
的查询,使用DSL来写:
GET /megacorp/employee/_search
{
"query" : {
"match" : {
"last_name" : "Smith"
}
}
}
这里没有在url上写请求参数了,而是使用一个JSON格式的请求体替代,使用了 match
查询类型。
复杂的搜索
需求:搜索名字为 Smith
的员工,并且只需要年龄大于 30 的。此时多个条件我们就需要使用过滤器 filter
GET /megacorp/employee/_search
{
"query" : {
"bool": {
"must": {
"match" : {
"last_name" : "smith"
}
},
"filter": { // 满足大于30岁的才不会被过滤掉
"range" : {
"age" : { "gt" : 30 }
}
}
}
}
}
过滤器用来执行一个范围查询
全文搜索
上面的搜索都是比较简单的:单个姓名,通过年龄过滤。现在需要全文搜索,找出所有喜欢攀岩(rock climbing)的员工。
这种情况传统的SQL就没那么容易完成了。看一下之前插入的员工信息:
{
"first_name" : "John",
"last_name" : "Smith",
"age" : 25,
"about" : "I love to go rock climbing",
"interests": [ "sports", "music" ]
}
他的 about
属性中是 I love to go rock climbing
并不是 rock climbing
,所以传统SQL去搜索就不那么好搜了,但是在ES中搜索是很简单的:
GET /megacorp/employee/_search
{
"query" : {
"match" : {
"about" : "rock climbing"
}
}
}
得到的结果可能并不会一定包含 rock climbing
可能某个员工的 about
属性是 rock albums
,但是 ES 也会给我们返回出来,因为它觉得我们可能需要这个数据。但是他也会给数据进行排序,匹配程度高的在 hits
数组的前面。并且每个 文档 都会有一个 _score
属性,代表这个搜索出来的 文档 和搜索条件之间的一个 相关性 。就和google搜索一样,相关性更高的排在更上面
短语搜索
上面的全文搜索是找属性中的独立单词,例如上面会搜索出带 rock
或者 climbing
的文档,但是如果想要的结果是 rock climbing
两个单词连接起来才算匹配上的话,就需要使用短语查询。上面使用的是 match
查询,现在想实现短语查询就要使用 match_phrase
查询
GET /megacorp/employee/_search
{
"query" : {
"match_phrase" : {
"about" : "rock climbing"
}
}
}
高亮搜索
想在搜索结果中 高亮 部分文本片段,那么只需要多一个 highlight
参数就可以了。返回结果中会新增一个highlight
属性,该属性中返回的文本会加上 em
标签
搜索喜欢 攀岩的员工
GET /megacorp/employee/_search
{
"query" : {
"match_phrase" : {
"about" : "rock climbing"
}
},
"highlight": {
"fields" : {
"about" : {}
}
}
}
结果:
{
...
"hits": {
"total": 1,
"max_score": 0.23013961,
"hits": [
{
...
"_score": 0.23013961,
"_source": {
"first_name": "John",
"last_name": "Smith",
"age": 25,
"about": "I love to go rock climbing",
"interests": [ "sports", "music" ]
},
"highlight": { // 会将搜索的about属性中传入的字符串加上 em 高亮
"about": [
"I love to go <em>rock</em> <em>climbing</em>"
]
}
}
]
}
}
聚合(aggregations)
基于数据生成一些分析结果。聚合 于 SQL 中的 GROUP By
类似,但是更加强大
举个例子:挖掘出员工中最受欢迎的兴趣爱好
GET /megacorp/employee/_search
{
"aggs": {
"all_interests": {
"terms": { "field": "interests" }
}
}
}
返回值:aggregations.buckets
喜欢 music
的人最多,文档数(搜到喜欢music的人)为2
{
...
"hits": { ... },
"aggregations": {
"all_interests": {
"buckets": [
{
"key": "music",
"doc_count": 2
},
{
"key": "forestry",
"doc_count": 1
},
{
"key": "sports",
"doc_count": 1
}
]
}
}
}
这个最受欢迎的数据并不需要我们手动去算,而是ES在搜索过程中动态生成的
如果想进一步搜索指定姓名的人中最受欢迎的兴趣爱好可以构造一个组合查询
GET /megacorp/employee/_search
{
"query": {
"match": {
"last_name": "smith"
}
},
"aggs": {
"all_interests": {
"terms": {
"field": "interests"
}
}
}
}
上面的就是一些基础的语法,和概念。这些了解后,再后面的更复杂的搜索就更简单了。
let beforeUnloadTime = 0;
let gapTime = 0;
window.onbeforeunload = function() {
beforeUnloadTime = +new Date();
};
window.onunload = function() {
gapTime = +new Date() - beforeUnloadTime;
if (gapTime <= 5) {
// 页面关闭或者浏览器关闭
localStorage.removeItem('downLoadMap');
}
};
刷新和关闭都会触发onbeforeunload和onunload这两个方法,但是两者触发的事件间隔是有区别的,如果两个事件的时间间隔小于5则说明是关闭,否则是刷新。
window.onunload = function() {
window.sessionStorage.setItem('flag', '1');
};
if (!window.sessionStorage.getItem('flag')) {
localStorage.removeItem('downLoadMap');
}
使用sessionStorage来判断刷新还是关闭,因为sessionStorage在关闭页面时会清空,所以在onunload的时候设置一个sessionStorage值。每次进页面的时候先判断是否能拿到这个值,能拿到代表刷新,拿不到代表是关闭后再打开的本页面,于是清空localStorage
上面两种方法只是一部分解决方法,如果有更好的解决方案请评论出来,一起讨论学习
以下内容总结自极客时间王争大佬的《数据结构与算法之美》课程,本文章仅供个人学习总结。
你为什么要学习数据结构和算法呢?在过去的软件开发中,数据结构和算法在哪些地方帮到了你?
- 前端开发也需要数据结构与算法,在浏览器端,流畅度是很重要的,所以写的代码也需要简洁高效,完成一个动画或者需要一些循环的时候,使用数据结构和算法能够更少的耗时和更节省内存,保证流畅性。
- 作为一个程序员,不管是前端后端,大数据还是其他相关职业,数据结构与算法都是能够锻炼自己思维的东西。有了思维,不管是什么语言,做什么工作,都能够事半功倍。
比如 sleep(1000) 意味着等待1000毫秒,可从 Promise、Generator、Async/Await 等角度实现
// async
async function sleep(duration) {
console.log('sleep');
await new Promise((resolve, reject) => {
return setTimeout(() => {
resolve();
}, duration);
});
}
sleep(1000).then(() => {
console.log('async方式');
})
// Promise
function sleep(duration) {
return new Promise(resolve => setTimeout(resolve, duration))
}
sleep(1000).then(() => {
console.log('promise方式');
})
// generator
function * sleep(duration) {
yield new Promise((resolve) => {
setTimeout(resolve,duration);
});
}
sleep(1000).next().value.then(() => {
console.log('generator');
})
js中无法做到同步休眠,即无法实现如下写法,只能通过回调来实现,并且实现的sleep也并不精准,因为setTimeout本身就不能保证一定在指定时间后执行
sleep(1000);
console.log('sleep 1s 后执行的代码');
let person = { name: '张三' }
const handler = {
get(obj, prop) {
console.log('proxy get');
return obj[prop] || '默认值'
}
}
let p = new Proxy(person, handler);
Object.defineProperty(p, 'name', {
get() {
console.log('define get..')
return 'define p name'
}
})
Object.defineProperty(p, 'haha', {
get() {
console.log('define haha...')
return 'hahahaha'
}
})
p.name
// proxy get
// define get..
person.name
// define get..
p.haha
// define haha...
person.haha
// define haha...
能,通过上述实验能得出结论,
defineProperty
一个proxy
时,其实是拦截了proxy
的源对象person
出现场景:在迭代中有一个需求是将pdf文件名修改为所有班级的名称集合,出现的班级过多导致的文件名过长在linux下无法创建文件和文件夹的情况
解决方式:经过查证,linux中文件名最长为255字符,文件路径最大长度为4096字符。所以需要对班级名称进行截断,并且不仅仅是根据字符串长度截断,而是根据每一个字母或者汉字对应的字符来计算得到最后的文件名小于255个字符。
鉴于以上场景,于是进行稍微的深究,对字符编码相关的知识进行了一个深一步的学习
字符
简介:字符简单的来说就是我们日常生活中用到的一些字符,比如数字、汉字、标点符号等。专业的介绍可以参考百度百科
字节
简介:计算机中的一个计量存储容量的单位,常见的计算机中一个字节代表八位的二进制数
编码
简介:其实 编码 就是将字符转为二进制的规则,因为我们知道计算机是通过 高电平 和 低电平 来分别代表 1 和 0,想让计算机读懂我们的字符,就需要将 二进制数 和我们的字符建立一个映射关系,这个过程就叫编码。其实每个人都可以定义自己的编码规则,但是这样就乱套了。所以一些组织就制定了统一的编码规则。也就出现了我们常见的 ASCII 、unicode 等编码规则
字符集
ASCII(字符集):建立了128个字符对应的数字编号,仅支持英文字母、一些标点符号、以及一些不可显示的字符。
unicode (万国码 字符集):Unicode只是一个用来映射字符和数字的标准。它对支持字符的数量没有限制,也不要求字符必须占两个、三个或者其它任意数量的字节。Unicode并不涉及字符是怎么在字节中表示的,它仅仅指定了字符对应的数字。归根结底,unicode就是把世界上所有的字符都和一个数字做对应,但是具体到这个数字在计算机中如何表示,他是不管的。
关于Unicode的其它误解包括:Unicode支持的字符上限是65536个,Unicode字符必须占两个字节,这些都不正确。
Unicode字符是怎样被编码成内存中的字节这是另外的话题,它是被UTF(Unicode Transformation Formats)定义的。
unicode的问题:比如,汉字
严
的 Unicode 是十六进制数4E25
,转换成二进制数足足有15位(100111000100101
),也就是说,这个符号的表示至少需要2个字节。表示其他更大的符号,可能需要3个字节或者4个字节,甚至更多。这里就有两个严重的问题,第一个问题是,如何才能区别 Unicode 和 ASCII ?计算机怎么知道三个字节表示一个符号,而不是分别表示三个符号呢?第二个问题是,我们已经知道,英文字母只用一个字节表示就够了,如果 Unicode 统一规定,每个符号用三个或四个字节表示,那么每个英文字母前都必然有二到三个字节是
0
,这对于存储来说是极大的浪费,文本文件的大小会因此大出二三倍,这是无法接受的。于是出现了对unicode字符集的不同的编码方式
常见的编码规则
ASCII码的编码规则:每个二进制位(bit)有 0 1 两个状态,因此八个二进制位就能够组成 256 种不同的状态,也就是 00000000 - 11111111,由于ASCII字符集定义了128个字符,八个二进制位能够表达 256 个状态,所以肯定是够用了,所以在 ASCII 码中一个字符只占一个字节(一个字节 === 8 bit)
UTF-8:是一种unicode的编码方案,在UTF-8中,0-127号的字符用1个字节来表示,使用和US-ASCII相同的编码。这意味着1980年代写的文档用UTF-8打开一点问题都没有。只有128号及以上的字符才用2个,3个或者4个字节来表示。因此,UTF-8被称作可变长度编码,它可以使用1~4个字节表示一个符号,根据不同的符号而变化字节长度。
UTF-16:另一个流行的可变长度编码方案是UTF-16,它使用2个或者4个字节来存储字符。
javascript中的字符编码
js中用的编码方式不是UTF-8、UTF-16。而是 UCS-2,具体原因是因为javascript诞生的时候,还没有UTF-16,但是好在UCS的码点和unicode一致,所以他们是互相兼容的。**两者的关系简单说,就是UTF-16取代了UCS-2,或者说UCS-2整合进了UTF-16。**所以,现在只有UTF-16,没有UCS-2。
总结:
参考资料:
1. electron中弹窗的确认取消以及系统自带的叉号之间的关系
场景:在用户退出app时,需要提示用户是否确认退出,此时弹窗出现,如果点击确认就继续退出,执行回调,否则的话,不退出
问题:点击叉号的时候,回调中返回的值是0,由于代码中写的buttons顺序为['确认', '取消'],点击“确认”的时候对应的response也是0,就导致了点击“确认”和点击叉号的行为一致,这样的话是不正确的,点击叉号应该等同于取消退出。
// 问题代码,点击确认按钮会退出,点击右上角叉号也会退出
dialog.showMessageBox(mainWindow, { buttons: ['确认', '取消'] }, (response) => { if (reponse === 0) {
// 执行退出操作
}
});
// 修改后代码,点击确认退出,点击右上角叉号不退出
dialog.showMessageBox(mainWindow, { buttons: ['取消', '确认'] }, (response) => {
if (response === 1) {
// 执行确认退出操作
}
});
2. 打包后子进程中的代码没有执行的问题
场景:在本地开发过程中,使用子进程去下载资源,能够正常的下载,但是打包之后,发现下载不了,子进程中的事件没有执行。导致下载流程受阻
问题:electron中使用到子进程的时候,是把子进程当作一个外部依赖来做的,打包后并不会将子进程的代码打进到包中,需要额外进行配置。
解决方式:对子进程文件进行额外配置注:本项目脚手架基于electron-vue,配置文件和electron-vue保持相同
"mac": {
"icon": "build/icons/icon.icns",
"extendInfo": {
"CFBundleURLSchemes": [
"link"
]
},
"asarUnpack": [
"**/node_modules/electron-log/**/*",
"**/node_modules/unzipper/**/*",
"**/node_modules/axios/**/*",
"**/node_modules/archiver/**/*"
],
"extraResources": [
{
"from": "src/main",
"to": "app.asar.unpacked/download"
}
]
},
"win": {
"icon": "build/icons/icon.ico",
"asarUnpack": [
"**/node_modules/electron-log/**/*",
"**/node_modules/unzipper/**/*",
"**/node_modules/axios/**/*",
"**/node_modules/archiver/**/*"
],
"extraResources": [
{
"from": "src/main",
"to": "app.asar.unpacked/download"
}
],
"target": [
{
"target": "nsis",
"arch": [
"x64"
]
}
]
}
process.resoucesPath
: electron中定义的资源目录的路径,在打包后子进程js所在的路径。let isDev = process.env.NODE_ENV !== 'production';
let scriptPath = isDev ? path.join(__dirname, 'child_download_serial.js') : path.join(process.resourcesPath, 'app.asar.unpacked/download/child_download_serial.js');
上面两步做完了,打包完毕后可以在安装后的安装包下看到自己子进程的代码目录,此时说明配置成功,并且子进程和主进程能够正常通信了。
以上方案在windows下和mac下都适用
3. 子进程中的log输出不了
场景:想看一下子进程中输出的log,查看子进程的执行情况
问题:子进程的console在控制台中看不到,因为子进程和父进程是分开的,我们只能看到父进程的输出
解决方式:拿到子进程后,在父进程中监听子进程的stdout.on('data')事件,这样在子进程中的所有console.log在父亲进程中都会触发data事件,父进程可以输出子进程的console内容。注意fork的时候需要给一个silent:true的配置,如果为 true,则子进程的 stdin、stdout 和 stderr 将会被输送到父进程,否则它们将会继承自父进程。同理,也可以监听子进程的stderr的data事件,可以捕获到子进程的错误
childDownload = fork(scriptPath, [], { silent: true });
childDownload.stdout.on('data', data => {
console.log('子进程的console', data.toString());
});
4. electron闪退的问题
场景:在退出软件的时候,由于代码原因报了一个错误,然后软件成功关闭,但是当再次手动打开软件时,出现闪退情况
问题:主进程出错后,没有对错误进行捕获,导致再次打开软件依然有这个错误存在,软件打不开
解决方式:全局进行一个错误捕获,避免某些情况下的错误未捕获导致闪退打不开软件的问题
// 必要的全局错误捕获
process.on('uncaughtException', error => {
log.error(error.stack || JSON.stringify(error));
app.exit();
});
5. web端唤醒客户端覆盖问题
场景:错题本下载器安装后,再安装错题本logger工具,此时再web中点击唤醒下载工具,唤醒的是错题本logger工具
问题:再两者打包的时候,对应的appId都是相同的,导致后安装的软件将前安装的软件给顶替了,当再网页中唤醒的时候,就将替换后的软件唤醒了
解决方式:package.json中的appId保证唯一性
6.electron下使用子进程,找不到第三方包的问题
electron下使用子进程,找不到第三方包的问题
7.网页端唤醒应用,发现总会新开一个electron窗口
场景:网页端唤醒,然后本地启动项目,调试时,发现唤醒的并不是自己启动的electron项目,而是这种页面
解决方法:将本地的electron包卸载,重新安装一遍,就可以正常唤醒我们本地启动的项目了
a.b.c.d
性能比 a['b']['c']['d']
要高,因为a['b']
这种方式其实还需要考虑 []
中的内容作为一个变量的情况,所以多了对变量的计算。至于在ast层面上来看,两个表达式解析出来的结果前者会切割成7块,分别是a
.
b
.
c
.
d
, 而后者则需要匹配左右括弧,多出一些匹配操作,由于要考虑[]
中会存在变量的情况,还需要通过作用域链寻找变量。整体上来说就比a.b.c.d
要慢。
以下内容总结自极客时间王争大佬的《数据结构与算法之美》课程,本文章仅供个人学习总结。
数组,是日常开发中用到的最多的数据结构之一,自己一度认为数组太简单了,不就是通过下标拿元素,遍历数组,查找排序等操作。对数组的理解太浅显了,直到看了大佬对数组的介绍,才发觉自己真是坐井观天,今日就来聊一聊数组。
数组专业一点来说是属于“线性表”的一种,它用一组连续的内存空间来存储具有相同类型的数据。
常见的线性表结构有链表、数组、栈、队列,顾名思义线性表就是数据排列在一条线上,每个线性表上的数据最多只有前后两个方向。
非线性表结构则比线性表更复杂,非线性表上的数据并不是简单的前后关系,常见的非线性表数据结构有图、树、堆等。
通过上面的图,我们能明显看到线性表和非线性表的不同之处。线性表只有前后关系,非线性表则存在多种关系。
继续说数组,上面说到来数组是线性表的一种,并且数组是连续的内存空间,相同的数据类型,所以数组有通过下标“随机访问”的特性,但是这也带来了一些弊端,就是数组是连续的,导致删除和插入的时候为了保证连续性需要进行大量的数据迁移。
数据的访问,那到底数组是怎么通过下标随机访问元素的呢?
拿一个长度为10的int类型数组 int[] a = new int[10]; 计算机会给数组分配连续的内存空间 1000~1039,其中内存首地址为base_address = 1000;
我们知道计算机会给每个内存单元分配一个地址,计算机通过这个内存地址访问内存中的数据。数组中由于内存是连续的,所以我们可以通过基地址直接计算出对应的下标所在的内存地址。数组中计算某个下标元素的内存地址公示如下:
a[i]_address = base_address + i * data_type_size
在本例子中,数组中存储的是int类型数据(js中数组每个元素大小可以不同,是做了特殊处理,js中具体数组在内存中如何存储待研究,所以这里用java中的数组来讲),data_type_size为4个字节,所以如果要获取下标为2的元素的地址,通过上面的公式计算就得到来内存地址为1008,由于只计算一次就能获取到准确的内存地址,所以访问数组中某个元素的时间复杂度为$O(1)$
为什么说数组的“插入”和“删除”操作很低效呢?我们知道数组在内存中是连续的,如果进行插入或者删除操作的话,由于数组要保证内存数据的连续性,所以数据需要进行移动,来保证连续性。
下面举例说明:
插入:
插入操作:假设数组的长度为n,现在,如果我们需要将一个数据插入到数组中的第k个位置。为了把第k个位置腾出来,给新来的数据,我们需要将第k~n这部分的元素都顺 序地往后挪一位。那插入操作的时间复杂度是多少呢?我们可以分析一下。
分析:如果第k个位置是数组末尾,那么不需要移动数据,此时最好时间复杂度为$O(1)$。如果在数组的开头插入数据,则所有的数据都要往后移动一位,所以最坏时间复杂度为$O(n)$。因为我们在每个位置插入的元素的概率是一样的,所以平均时间复杂度为$(1+2+3+...+n)/n = O(n)$
通过上面的分析我们看到,插入操作的平均时间复杂度为$O(n)$,那么有没有能够优化的地方呢?其实是有的,但是只能针对特定的情况进行优化。比如当数组仅仅作为存储数据的集合而不在乎存储的数据的顺序时,我们可以直接将第k个元素放在数组最后,将要插入的元素放在第k个位置。这样就能做到时间复杂度为$O(1)$,这也是快排的**之一,但这也导致了快排是一个不稳定的排序算法关于排序算法稳定性的介绍
举个例子来看一下上面的优化方式:假设数组a[10]中存储了如下5个元素:a,b,c,d,e。 我们现在需要将元素x插入到第3个位置。我们只需要将c放入到a[5],将a[2]赋值为x即可。最后,数组中的元素如下: a,b,x,d,e,c。如下图所示
删除:
删除操作:存在长度为n的数组,现在需要删除第k个元素,删除第k个元素后为了保证数组中第k个位置不出现空洞导致数组内存不连续,所以需要将k~n的元素都要向前移动一位。我们依旧分析一下时间删除操作的时间复杂度。
分析:如果删除的是最后一个元素,则不需要移动,所以最好时间复杂度为$O(1)$,删除的是第一个元素,那么后面的k~n个元素都要向前移动一位,所以最坏时间复杂度为$O(n)$,在每个位置删除的概率是一样的,那么平均时间复杂度为$(1+2+3+...+n)/n = O(n)$
那么删除操作能否优化呢?其实也是可以的,我们通过上面的例子知道每删除一个元素就要移动后面的所有元素,那么我们能不能把多个删除操作放在一起,统一进行一次数据移动呢?
举个例子来看一下上面的优化方式:数组a[10]中存储了8个元素:a,b,c,d,e,f,g,h。现在,我们要依次删除a,b,c三个元素。
为了避免d,e,f,g,h这几个元素被移动三次,每次删除操作的时候并不去直接进行数据搬移,而是把要删除的元素标志为已删除,当数组中需要插入元素但是发现数组已经满了之后,再将标记为删除的元素真正的删除,这样就大大减少了删除操作导致的数据迁移。
如果你了解JVM,你会发现,这不就是JVM标记清除垃圾回收算法的核心**吗?没错,数据结构和算法的魅力就在于此,很多时候我们并不是要去死记硬背某 个数据结构或者算法,而是要学习它背后的**和处理技巧,这些东西才是最有价值的。如果你细心留意,不管是在软件开发还是架构设计中,总能找到某些算
法和数据结构的影子。 --王争
我们之前有计算过数组的内存寻址公式 a[i]_address = base_address + i * data_type_size
,如果从1开始的话,我们可以得到对应的内存寻址公式为 a[i]_address = base_address + (i - 1) * data_type_size
,每次随机访问一个元素都多了一个减法操作。
数组是一种很基础的数据结构,效率需要尽可能的高,所以为了减去一次减法操作,所以数组选择了从0开始编号而不是从1开始。
当然也并不是非0不可,有的语言甚至支持负数的下标,例如python。但是大多数都是从0开始编号,可能也和C语言以0作为下标有关,后面的语言或多或少的都借鉴了C语言。
我们今天学习了数组。它可以说是最基础、最简单的数据结构了。数组用一块连续的内存空间,来存储相同类型的一组数据,最大的特点就是支持随机访问,但 插入、删除操作也因此变得比较低效,平均情况时间复杂度为O(n),我们也了解到了一维数组的寻址公式,和插入和删除操作的优化方法。
一维数组寻址公式我们已经知道了a[i]_address = base_address + i * data_type_size
,那么二维数组的寻址公式呢?在留言处写下你的答案把!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.