跳到主要内容

webpack模块加载机制

· 阅读需 9 分钟

前端项目的规模越来越庞大,模块化开发已经是普遍需求。早期的打包工具将所有模块化的代码打包到一个bundle文件中,在一个简单的html文件中引入脚本。webpack允许输出为多个bundle文件,从而实现按需加载,更好的利用浏览器缓存,提升用户体验。

这里不讨论如何配置webpack,只说webpack如何加载模块。考虑一个多页面程序,有page1和page2两个页面,都用到一个工具模块util,page1直接引用util,而page2在页面加载后满足一定条件时动态加载util。

//util.js
console.log('util')
export function log(arg) {
console.log(arg)
}
//page1.js
import { log } from './util'
//...
log('page1')
//page2.js
//...
//条件满足时动态加载util
import('./util').then((util) => {
util.log('page2')
})

首先明确webpack中的两个概念:

  • module:一般是源代码中的一个文件,打包后被包裹在一个函数中,webpack模拟了模块环境
  • chunk:一个chunk即一个输出bundle文件,不考虑其它分割规则,每个入口将产出一个chunk。一个chunk包含若干module

假设我们已经配置好webpack,让它输出三个chunk:

0.js //util.js
page1.js //页面1
page2.js //页面2

下面从webpack的打包输出来分析webpack模块加载机制。

静态依赖

webpack中,一个js源文件作为一个模块(也可以是其他文件)。webpack将模块代码包裹在一个函数中,返回模块的导出内容。注意,每个模块最多仅被执行一次,第二次请求时会直接从缓存返回。

(打包后的)page1.js:

//立即执行函数初始化webpack运行时,然后加载入口模块
(function (modules) {
//modules是被打包到page1.js这个文件(chunk)中的模块列表,此处有page1和util两个模块
//已加载的模块的缓存
var installedModules = {};
// webpack require函数,用来加载模块
function __webpack_require__(moduleId) {
//检查模块是否已装载,是则返回缓存的模块
if (installedModules[moduleId]) {
return installedModules[moduleId].exports;
}
//将模块添加到缓存
var module = installedModules[moduleId] = {
i: moduleId, //模块ID
l: false, //模块是否已装载
exports: {} //模块的导出内容
};
// 执行模块初始化
modules[moduleId].call(
module.exports, //将模块代码的this指向其自己的exports
module, //相当于commonjs中的module,对模块自身的引用
module.exports, //相当于commonjs中的exports,模块的导出内容
__webpack_require__ //相当于commonjs中的require,提供加载同一chunk中其他模块的方法
);
// 将模块标识为已加载
module.l = true;
// 返回模块的导出内容
return module.exports;
}

//加载入口模块,即我们的page1.js
return __webpack_require__(__webpack_require__.s = "./src/page1.js");
})({
//page1模块
"./src/page1.js":
function (module, __webpack_exports__, __webpack_require__) {
let util = __webpack_require__('./src/util.js')
util.log('page1')
},

//util模块
"./src/util.js":
function (module, __webpack_exports__, __webpack_require__) {
function log (arg) {
console.log(arg)
}
//util模块导出log函数
__webpack_exports__['log'] = log
}
});

代码被我简化了一下,webpack有很多兼容性和安全性方面的考虑,我将那部分修改了让代码看起来清晰。

可以看到,util和page1被函数包围,模拟模块环境,然后作为参数传递给立即执行函数。注意,模块只有被加载时才会执行内部代码。

在立即执行函数中,先进行了webpack初始化,即提供核心的模块加载函数__webpack_require__函数,并在函数上配置一些静态字段记录必要的信息(如__webpack_require__.s为入口模块ID),然后装入入口模块,开始执行我们自己的逻辑代码。

按需加载

在page2中我们使用了动态import()方法来加载util模块。webpack足够智能,无需配置它也聪明的自动将util独立到单独的文件(chunk),在需要时再进行请求。

webpack通过jsonp机制加载不同chunk中的模块。

page2.js:

(function(modules) {
//模块加载函数,同page1。注意,此函数仅用于加载已被
function __webpack_require__(moduleId) {
//......
}

//可用的模块列表,包含本chunk中的模块和已经请求完毕的,来自其他chunk的模块
__webpack_require__.m = modules;
//基路径,用于拼接其他chunk的url
__webpack_require__.p = "";
//已装载的模块缓存,注意区分__webpack_require__.m,前者应该是后者的子集
var installedModules = {};
//这是相对page1中多出来的东西,用来记录其他chunk的加载情况
//值可能有3种:
// undefined, 即该chunk还没有被请求过
// 0, 该chunk中的模块已经正确的添加到__webpack_require__.m中,可以通过__webpack_require__加载了
// [resolve, reject, promise], chunk正在请求中。promise在chunk请求结束后才被resolve或reject
var installedChunks = {
"page2": 0 //page2即页面2的chunk自身,当然已经加载完成
};

//jsonp函数,chunk请求成功时由被请求的chunk调用。它的任务为将chunk中的模块加入可用模块列表
//data参数由被请求的chunk传过来,包含模块信息。这也是jsonp的核心部分
function webpackJsonpCallback(data) {
var chunkIds = data[0];
var moreModules = data[1];
var moduleId, chunkId, i = 0, resolves = [];
for(;i < chunkIds.length; i++) {
chunkId = chunkIds[i];
if(Object.prototype.hasOwnProperty.call(installedChunks, chunkId) && installedChunks[chunkId]) {
resolves.push(installedChunks[chunkId][0]);
}
//表示chunk已经加载好啦,下次不用去请求了
installedChunks[chunkId] = 0;
}
for(moduleId in moreModules) {
if(Object.prototype.hasOwnProperty.call(moreModules, moduleId)) {
//把chunk中的模块们加入可用列表(__webpack_require__.m == modules √)
modules[moduleId] = moreModules[moduleId];
}
}
//原数组的push函数,详见后文
if(parentJsonpFunction) parentJsonpFunction(data);
//resolve请求时创建的promise,执行回调
while(resolves.length) {
resolves.shift()();
}
};

//异步请求chunk
__webpack_require__.e = function requireEnsure(chunkId) {
var promises = [];
var installedChunkData = installedChunks[chunkId];
//检查chunk是否已经加载。0表示已加载
if(installedChunkData !== 0) {
//正在加载...有点不清楚为啥要重复记录一次promise?
if(installedChunkData) {
//installedChunkData[2]是之前请求的promise
promises.push(installedChunkData[2]);
} else {
//没有请求过,开始请求chunk
//标识chunkId这个chunk正在请求,并记录promise相关信息
var promise = new Promise(function(resolve, reject) {
installedChunkData = installedChunks[chunkId] = [resolve, reject];
});
promises.push(installedChunkData[2] = promise);
//现在installedChunks[chunkId] = [resolve, reject, promise]了
//用script标签加载chunk
var script = document.createElement('script');
var onScriptComplete;
script.charset = 'utf-8';
script.timeout = 120;
script.src = jsonpScriptSrc(chunkId);
//...请求错误处理...省略
//...超时处理
var timeout = setTimeout(function(){
}, 120000);
document.head.appendChild(script);
}
}
return Promise.all(promises);
};

//拼接被请求chunk的url
function jsonpScriptSrc(chunkId) {
return __webpack_require__.p + "" + ({}[chunkId]||chunkId) + ".js"
}
//通过window.webpackJsonp数组记录加载成功的chunk数据。其他chunk被加载后会将自己的chunk数据push到这个数组
var jsonpArray = window["webpackJsonp"] = window["webpackJsonp"] || [];
//注意,webpack覆盖了window.webpackJsonp数组的push函数。将原生的push函数替换成了webpackJsonpCallback
//在webpackJsonpCallback函数中我们看到有调用parentJsonpFunction,其实那个函数才是原来的数组的push函数
var oldJsonpFunction = jsonpArray.push.bind(jsonpArray);
jsonpArray.push = webpackJsonpCallback;
//理论上说这时jsonpArray应该是空的。。但如果不是空的就手动调用下webpackJsonpCallback装载chunk
//window["webpackJsonp"]已经被webpack污染啦,所以它复制了一下?
jsonpArray = jsonpArray.slice();
for(var i = 0; i < jsonpArray.length; i++) webpackJsonpCallback(jsonpArray[i]);
var parentJsonpFunction = oldJsonpFunction;

//加载入口模块
return __webpack_require__(__webpack_require__.s = "./src/page2.js");
})
({
//页面2
"./src/page2.js":
(function(module, exports, __webpack_require__) {
//我们的动态import()被webpack转化后大致代码
//先请求包含util的chunk
__webpack_require__.e(0)
//请求成功之后通过__webpack_require__加载util模块
.then(__webpack_require__.bind(null, 0))
//执行我们自己的逻辑代码
.then((util) => {
util.log('page2')
})
})
});

代码仍然有点长,不过已经删除和修改了很多边缘代码,并且调整了一下顺序,结构比较清晰了。代码中的注释解释了整个模块加载过程。先通过jsonp请求得到chunk数据,然后缓存chunk中的模块到可用列表(未装载),这时同步的模块加载已经可用,直接调用__webpack_require__加载相关模块,步骤就和page1一样了。

被加载的chunk结构就很简单了,只是简单的调用jsonp函数传入模块数据。

//0.js

//注意,前面说了,window["webpackJsonp"]数组的push函数被webpack重写了
//所以实际上这里调用了主模块那边定义的webpackJsonpCallback函数
//一个chunk可能包含多个模块,所以参数为 [moduleIds],moreModules
(window["webpackJsonp"] = window["webpackJsonp"] || []).push([[0], {
"./src/util.js":
(function (module, __webpack_exports__, __webpack_require__) {
"use strict";
__webpack_exports__['log'] = function (arg) {
console.log(arg)
}
})
}]);

总结

当项目规模增长到一定程度,模块化已是刚需。在ESModule标准制定之前广泛使用的模块化标准有commonjs,AMD,以及综合两者的UMD等。在ES6中模块化终于得到标准的支持,然而各平台对其的支持有限,暂时还难以替代传统解决方案。万幸,webpack提供了综合各种模块化标准的机制,让我们能够平稳的过渡。

LeetCode之旅——字母异位词分组(Group Anagrams)

· 阅读需 2 分钟

题目

给定一个字符串数组,要求将相同字母组成的字符串分组返回。字符串只由小写字母组成。

示例:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

思路一

将输入的每个字符串拆成字符排序,然后利用Map分组。

/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function(strs) {
const map = new Map()
for (let i = 0; i < strs.length; ++i) {
const key = strs[i].split('').sort().join()
map.has(key)
? map.set(key, map.get(key).concat(strs[i]))
: map.set(key, [strs[i]])
}
return Array.from(map.values())
};

思路二

由于字符串限定只由小写字母组成,可以构建一个长为26的“桶”,每一格存储对应的字母出现的次数。这样,每个字符串都被转化为一个这样的桶。然后把“桶”重新转为字符串,作为Map的键对原字符串数组进行分组。

/**
* @param {string[]} strs
* @return {string[][]}
*/
var groupAnagrams = function (strs) {
const list = []
for (const str of strs) {
//为每个字符串构造一个“桶”
const layer = []
for (const s of str) {
c = s.charCodeAt(0)
let value = layer[c - 0x60]
value = value ? value + 1 : 1
layer[c - 0x60] = value
}
list.push(layer.join(' '))
}
//把桶字符串化后作为key对原数组进行分组
const res = new Map()
for (let i = 0; i < list.length; ++i) {
res.has(list[i])
? res.set(list[i], res.get(list[i]).concat(strs[i]))
: res.set(list[i], [strs[i]])
}
return Array.from(res.values())
};

总结

思路一更简洁,但排序可能会消耗更多的时间。思路二利用了桶排序的思想,将排序复杂度降到了线性复杂度。在字符串较长时思路二应该会表现更好。

彻底搞懂JavaScript怪异函数——bind

· 阅读需 7 分钟

2020.4.30
事实上存在new.target这个变量,在函数中会指向构造函数。如果不是以new操作符调用的构造函数,new.target为undefined。因此我们可以通过new.target判断函数是否是new操作符调用。不过各浏览器对bind的支持比对new.target要早,所以在bind函数的polyfill中使用new.target可能不太合适。


我们可能遇到过实现bind函数这样的题目,但似乎并不存在完美模拟原生bind函数的可能。ECMAScript 2015中将bind创建的函数称为exotic function object(怪异函数对象),这很适宜,因为它的确存在一些“怪异”之处。

在继续之前我们需要先了解bind函数。这可以参考MDN的解释:
bind() 方法创建一个新的函数,在 bind() 被调用时,这个新函数的 this 被指定为 bind() 的第一个参数,而其余参数将作为新函数的参数,供调用时使用。

另外还需要了解new操作符的实现,同样参考MDN的解释:

  1. 创建一个空的简单JavaScript对象(即{});
  2. 链接该对象(即设置该对象的构造函数)到另一个对象;
  3. 将步骤1新创建的对象作为this的上下文 ;
  4. 如果该函数没有返回对象,则返回this

第2步即为对象绑定隐式原型,将对象的__proto__属性指向构造函数的prototype,而函数默认的prototype拥有constructor属性指向构造函数,从而实现了所谓的“链接构造函数”。

这里约定一下,bind()方法的实现函数叫bind函数,创建的新函数叫做绑定函数,被封装的原函数叫做原函数

bind函数至少有这些特性:

  1. 除非是被new操作符调用,否则原函数执行环境中的this总是为bind函数被调用时传递的第一个参数;
  2. 绑定函数的prototype为undefined
  3. 通过new操作符调用绑定函数时,原函数执行环境的this仍为new操作符创建的新对象,即bind函数的this绑定被忽略;
  4. 通过new操作符调用绑定函数返回的对象是原函数的实例。即:
    function func() {}
    var fBound = func.bind({});
    var foo = new fBound();
    foo instanceof func; // true

MDN推荐的bind函数的Polyfill如下(部分):

Function.prototype.bind = function(that) {
var target = this; //原函数
var args = Array.prototype.slice.call(arguments, 1); //绑定参数
var bound; //绑定函数
//实际上binder才是绑定函数,bound将其再次包装后返回
var binder = function () {
if (this instanceof bound) {
//如果是通过new操作符调用的绑定函数,则绑定函数执行环境的this指向new操作符创建的新对象,而这个对象的隐式原型指向构造函数bound的prototype
//new操作符调用,忽略bind函数绑定的this,以实际执行环境this调用原函数
var result = target.apply(
this,
args.concat(arguments)
);
if (Object(result) === result) {
//如果构造函数返回的是一个对象,返回该对象
return result;
}
return this;
} else {
//非new操作符调用,使用绑定的this
return target.apply(
that,
args.concat(arguments)
);
}
};
//计算bind函数调用时提供的绑定参数数量
var boundLength = Math.max(0, target.length - args.length);
var boundArgs = [];
for (var i = 0; i < boundLength; i++) {
boundArgs.push('$' + i);
}
//相当于返回binder。之所以用函数再包一层,应该是为了使函数的length拥有正确的值
bound = Function('binder', 'return function (' + boundArgs.join(',') + '){ return binder.apply(this,arguments); }')(binder);

//调整原型链,使绑定函数的实例仍然是能通过原函数的原型链检测(因为绑定函数实例的隐式原型(__proto__)的隐式原型指向原函数的prototype)
//如果原函数没有prototype,则绑定函数具有默认prototype,且不会被外界访问到(除非通过绑定函数的prototype属性)
if (target.prototype) {
//构造一个临时的空函数,防止绑定函数的prototype直接引用原函数的prototype。因为原函数的prototype对外界可见,具有不确定性。如果绑定函数被调用时传递一个隐式原型指向原函数prototype的this参数,直接引用原函数就会造成误判为new操作符调用
var Empty = function Empty() {};
//绑定函数.prototype->空函数实例;空函数实例.__proto__->原函数prototype
//从而实现了,通过new得到的绑定函数实例的原型链上有原函数的prototype(文章开头的特性4),但隐式原型为原函数prototype的对象不是绑定函数的实例,因为绑定函数的原型是一个内部的对象(Empty实例),不太可能作为外部某对象的隐式原型(除非是绑定函数被当作了构造函数[new操作]),从而在前面的binder函数中,根据判断绑定函数执行环境的this是否是绑定函数的实例,正确的判断出是否为new操作符调用的绑定函数
//当然这里的漏洞是,绑定函数的prototype并不是完全不可访问的,因为绑定函数是公开的,从而绑定函数的prototype也就可访问了。但这一般不会出问题,除非你写一些奇怪的代码(后面有分析到)
Empty.prototype = target.prototype;
bound.prototype = new Empty();
Empty.prototype = null;
}
return bound;
};

上面的实现已经接近完美了,几乎也没有更好的实现方案了。我们来看看它实现了文章开头列出的哪些特性。

特性2,绑定函数的prototype为undefined。其实这个很容易实现,但为了实现识别new操作符,只好让绑定函数拥有prototype。幸运的是,这对实际使用几乎没有影响。

特性3,通过new操作符调用绑定函数时忽略bind函数绑定的this。OK,通过new调用时一定可以识别到。

特性4,new操作符调用绑定函数返回的对象是原函数的实例。已实现,虽然原型链上多了一个节点,但并不影响原型链判断。
原生bind函数实例的原型链:原函数prototype->Object.prototype->undefined
polyfill实现的bind函数实例的原型链:内部临时函数Empty.prototype->原函数prototype->Object.prototype->undefined

特性1就耐人寻味了,显然关键在于对new操作符调用的精确判断。如果是new操作符调用,显然绑定函数执行环境的this即绑定函数的实例,会被当做new操作符调用对待(忽略bind函数绑定的this)。但非new操作符调用的情况,是否一定能够被当作一般情况对待?考虑下面的代码:

function foo(name) {
this.name = name;
}
var obj = {};
var bar = foo.bind(obj);
const mock = Object.create(bar.prototype ? bar.prototype : null);
bar.call(mock, 'Jack');
console.log(obj.name);
var alice = new bar('Alice');
console.log(obj.name);
console.log(alice.name);
console.log(mock);

理想的输出是:

Jack
Jack
Alice
[Object: null prototype]

原生bind函数的输出符合预测,但polyfill实现的版本输出:

undefined
undefined
Alice
foo { name: 'Jack' }

bar.call(Object.create(bar.prototype), 'Jack')被当作了new操作符调用。因此绑定函数忽略了绑定的this,而使用了传入的this参数调用原函数,因此原函数中this.name = namethis指向mock,所以赋值操作发生在mock上而非obj

bind函数被成为怪异对象,怪异就怪异在其内部机制无法完全用合法的JavaScript逻辑模拟(至少我没有找到方法)。不过上面的实现已经可用了,最后的不一致行为其实属于“明知故犯”的怪癖代码,实际生产活动中完全可以杜绝。

参考

https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Function/bind

https://zhuanlan.zhihu.com/p/38968174

JavaScript微任务与宏任务(浏览器)

· 阅读需 3 分钟

问题描述

最近在用Ionic框架(基于Angular),有这么一个需求:
先调用history.go(-delta)返回到某个页面,再调用Angular的Router#navigate()导航到新的页面。

大致代码如下:

go(delta, url) {
history.go(delta)
this.router.navigateByUrl(url, { replaceUrl: true })
}

问题出来了,代码执行后只返回到了之前的页面,并没有正确导航到url参数指定的页面。

原因大概是,Angular监听了popstate事件以响应浏览器的回退操作。然而浏览器的事件触发是异步的,即history.go(delta)执行后,要等到下一轮事件循环Angular才能捕捉到回退事件,并渲染对应的组件。然而这时router.navigateByUrl()已经执行完毕,因此看到的是回退后的页面而不是希望导航到的新页面。

原理分析

JavaScript的事件循环主要是靠两个队列:宏任务(macro task)队列和微任务(micro task)队列。浏览器按下面的顺序执行队列中的任务:

macro task 1 micro task 1 micro task 2 micro task 3 ...... macro task 2 micro task 1 micro task 2 micro task 3 ......

即,在执行完宏任务后必须执行完当前的所有微任务才能执行下一个宏任务。而浏览器环境下,UI事件是宏任务,Promise#then()是微任务。

当go()函数被执行时,history.go(delta)执行后,popstate事件被推入宏任务队列,然后执行navigationByUrl()。Angular的路由导航也是异步的,但在没有路由守卫的情况下,navigateByUrl()函数发起的整个工作流程都只是微任务(可以认为是一连串立即被resolve的Promise),所以在下一个宏任务被读取之前,新页面的导航已经先于回退操作完成。

go函数执行过程如下:

go history.go() 宏任务队列推入popstate事件 navigateByUrl() 微任务队列推入NavigationStart ... ... 微任务队列弹出NavigationStart ... 微任务队列推入NavigationEnd ... 微任务队列弹出NavigationEnd,新页面导航完成 ... 微任务队列空 ... 宏任务弹出popstate事件,解析history.go()回退到的url 渲染回退到的页面

解决方法

知道了原理就好解决问题了。只需要等到下一次宏任务再执行新页面的导航就好了。

go(delta, url) {
history.go(delta)
setTimeout(() => {
this.router.navigateByUrl(url, { replaceUrl: true })
}, 0)
}

注意,setTimeout和setInterval函数创建的都是宏任务。另外,这里说的都是浏览器环境下的JavaScript,部分说法对nodejs并不适用。

Javascript的in操作符

· 阅读需 1 分钟

javascript的in操作符用于判断某个名称的属性是否存在于某个对象的原型链中。

语法:

prop in object

prop是string类型或Symbol类型,其他类型会被转化为string,返回值是布尔值,如果object.prop存在则返回true,否则返回false。

需要注意的是,object必须是一个对象。最容易被误用的场景是对字符串使用in操作符,这将直接抛出一个异常:

> 'length' in 'mystring' // Uncaught TypeError: Cannot use 'in' operator to search for 'length' in mystring

如果要判断字符串是否包含另一个字符串,请使用includes方法(ES6)。

参考:MDN Operator in

.NET 匿名函数引用局部变量导致的问题

· 阅读需 2 分钟

问题

写C#窗口程序,今天遇到的问题。在工作线程(非UI线程)要操作ListView,因此使用了跨线程调用方式。

for (int i = 0; i < videos.Count; ++i)
{
this.BeginInvoke(new Action(() =>
{
var item = lvwVideos.FindItemWithText(videos[i]);
if (item != null)
lvwVideos.Items.Remove(item);
}));
}

代码一跑给我抛出了异常,数组下标越界。原因分析如下。

分析

概念理解错误,C#的闭包环境并不会复制用到的局部变量。

.NET对闭包的实现是在编译阶段而不是运行阶段,事实上,匿名函数中的变量 i 和 for 循环中的i就是同一个变量,由于函数返回后变量还会被匿名函数使用,它会保存在堆中而不是调用栈——不管这个变量是值类型还是引用类型(如果是引用类型即对象和对象的引用都在堆中)。

因此,循环结束后 i 的值已经超出数组 videos 的下标范围。而BeginInvoke函数是不等待执行完毕的,因此很可能循环结束而匿名函数还没有执行完毕。这时匿名函数从堆中取到的 i 已经不是定义匿名函数时 i 的值了。

 
用下面的代码来说可能更清晰。

static void Main(string[] args)
{
int i = 1;
Action action = new Action(() =>
{
Console.WriteLine(i);
});
++i;
action(); // 2
}

action执行的时候访问的 i 和Main函数中的 i 是同一个,存储在堆中。

解决

使用Invoke

这里最简单的解决方法是将BeginInvoke改为Invoke。Invoke()会等待UI线程执行完毕才会继续执行,能够保证 i 值不会被工作线程改变。

模仿JS

将上面的代码稍作修改:

static void Main(string[] args)
{
int i = 1;
Action action = null;
new Action<int>((n) =>
{
action = new Action(()=>
{
Console.WriteLine(n);
});
})(i);
++i;
action(); // 1
}

这相当于将 i 复制了一遍。

基于Go语言的命令行即时聊天工具——StormChat

· 阅读需 7 分钟

简介

  前段时间心血来潮想学习最近的明星编程语言Golang。于是想做个聊天小程序实践一下。程序基于TCP协议通信,更详细的设计见设计思路

  用Golang实现了服务端程序,同时代码抄抄改改做了个Golang客户端,又由于输出问题,用C++写了个Windows控制台的简陋的输出控制库,于是客户端在Windows上能看了(不过朋友说很丑>_<)。

  在朋友(@Billows)的鼓励下,我们决定用C#写一个客户端程序,正好他在学习WPF编程,于是界面采用了WPF编写。我负责后台数据交互,他负责前台界面逻辑。

  C#客户端还使用到了JSON格式化库Newtonsoft.Json,特此说明。

github地址:https://github.com/mattuylee/stormchat

设计思路

通信流程

  1. 发送方(客户端或者服务器)发送数据包;
  2. 接收方(服务器或者客户端)处理数据;
  3. 如果需要反馈,接收方发送反馈数据包;
  4. 发送方处理反馈数据(如果有)。

通信数据包结构

数据通信基于TCP协议,每次通信的数据包应包含【包头域+数据域】。包头域总是JSON格式、UTF-8编码的字符串,数据域由包头决定,可以为空。通信数据包结构如图。

stormchat通信规则

HEAD(包头域)至少包含两个参数:

  • Toekn
  • Operation

Token参数是一次通信的标识文本,由请求方随机生成,处理方返回数据包的Token参数应和请求方的Token参数一致(如果有返回数据)。

Operation参数指定本次通信的请求。它决定了数据包的其他数据。Operation具体行为定义见这里

本来做了设计图表,不过第一次用starUML,画了一半才发现完全是鬼画桃符,没有掌握正确的作图方式,也没什么热情重新画了。因此这里不展示完整的设计文件了(本来也不完整),上面的链接是截取的关键部分(才知道starUML可以导出html文档)。

哦,还有服务器端的数据库结构,见文件stormchat-server/res/stormchat.sql

环境配置

  1. 开发环境

    服务器端:Windows/Linux Golang 1.11
    客户端-Go:Windows x64,C++,Golang 1.11
    客户端-C#:Windows,.NET4.0,WPF,Newtonsoft.Json for .NET4.0

  1. 运行环境

    服务器端:Linux/Windows, MySQL5.5+/MariaDB10.0+
    客户端:Windows10 x64(其他平台没测试过)

程序配置

由于懒癌发作,一些参数设置只能在编译时指定好,没有运行中指定参数的功能。

Go语言的部分(服务器程序和golang客户端程序)这块都在control.go文件中,C#客户端这边也没什么可配置的,也就是连接服务器的地址和端口。下面列出部分配置参数:

服务器端

  • serveMode
    服务(后台)模式。如果此参数为true,日志输出到str_log_file参数指定的文件中,且Debug()函数将不输出内容。如果为false,日志输出和Debug()函数都将直接向控制台或终端输出。

  • max_head_length
    最大包头长度,单位字节,如果包头长度超过此参数将被抛弃。

  • max_message_length
    最大消息长度,单位字节,如果消息长度超过此参数将被抛弃。

  • max_photo_size
    最大头像大小,单位字节,如果头像数据长度超过此参数将被抛弃。

  • timeout_message
    客户端连接最大数据等待时间,单位秒。如果超过此时间客户端没有数据到达则断开连接(此参数当前未启用)。

  • str_log_file
    日志文件。仅在serveMode为true时有效。注意,程序并不会自动清理此文件。

  • str_db_conn_str
    MySQL数据库连接字符串。

客户端(Go)

  • server_addr
    服务器地址和端口。

客户端(C#)

资源定义在StormChat解决方案,Interact项目的属性->资源中。

  • RemoteServerAddr
    服务器地址。

  • RemoteServerPort
    服务器端口。

如何编译

首先安装git和golang,这一步请自行解决;

克隆项目到本地:

git clone -b master https://github.com/mattuylee/stormchat.git

假设项目已克隆到本地DIR目录,命令行切换到stormchat目录:

cd DIR/stormchat

  1. 服务器端

切换到服务器端工程目录:

cd stormchat-server

克隆mysql操作库

Go标准库里是没有数据库操作的库的,因此先添加mysql操作库到项目中。创建目录sotormchat-server/src/github.com/go-sql-driver/,然后克隆MySQL操作库:

cd src/github.com/go-sql-driver
git clone https://github.com/go-sql-driver/mysql.git

配置环境变量GOPATH

Windows下:
如果环境变量GOPATH存在,则在GOPATH后添加 ";DIR/stormchat/stormchat-server"(不含引号,注意分号),如果不存在添加GOPATH环境变量并将其设置为DIR/stormchat/stormchat-server即可,注意把DIR换成git仓库所在目录。
Linux下:
先查看GOPATH环境变量的值,再添加项目目录到GOPATH:

echo $GOPATH
如果值为空:
export GOPATH=DIR/stormchat/stormchat-server
如果值不为空:
export GOPATH=$GOPATH:DIR/stormchat/stormchat-server

编译程序

切换到stormchat-server/src/stormchat/目录,然后编译:

cd DIR/stormchat/stormchat-server/src/stormchat
go build

配置MySQL

登录mysql:

mysql -uroot -p

为stormchat创建数据库:

CREATE DATABASE stormchat CHARSET=UTF8;

导入数据库结构:

SOURCE DIR/stormchat/stormchat-server/res/stormchat.sql;

创建用户并授权:

CREATE USER 'stormchat'@'localhost' IDENTIFIED BY 'stormchat';
GRANT ALL ON stormchat.* TO 'stormchat'@'localhost';
FLUSH PRIVILEGES;

启动服务器程序

Linux下执行下列命令以守护进程运行:

nohup ./stormchat &

Windows请自行探索。

  1. 客户端-Go

cd DIR/stormchat/stormchat-client-golang/src
go build

注意,客户端运行时需要conctrl_x64.dll在运行目录下,此文件在stormchat-client-golang/res/目录下。

  1. 客户端-C#

Visual Studio 2015以上版本打开项目,直接编译即可。

注意事项

  • 没有设计注册账户的API,只能在强插数据库。emmmm,这个坑懒得填了。
  • 服务器端的日志文件不会自动清除(反正也没什么日志要写)。
  • 其他的,想到再补充。

目录结构(主要部分)

stormchat │ .gitattributes │ .gitignore │ LICENSE //许可证 │ README.md //此帮助文件 │ ├─design //设计文件 │ message.png │ operations.svg │ stormchat.zip //starUML设计文件 │ │ ├─stormchat-server //服务器端工程目录 │ ├─res │ │ stormchat.sql //数据库结构 │ │ │ └─src //代码文件 │ └─stormchat │ control.go │ err.go │ main.go │ message.go │ session-deprecated.go //已不推荐使用的接口 │ session.go │ storm-server.go │ user.go │─stormchat-client-golang //Go客户端工程目录 │ ├─res │ │ conctrl_x64.dll //Winodws控制台输出库 │ │ icon.ico //客户端图标 │ │ │ └─src │ control.go //参数控制 │ main.go │ session.go │ stormchat-client.syso //资源文件(图标资源) │ user.go │ win-console.go //输出控制,调用conctrl库 │ └─stormchat-client-csharp //C#客户端工程目录 ├─Interact //数据交互模块 │ │ Interact.csproj //Visual Studio项目文件 │ │ Newtonsoft.Json.dll //JSON格式化库 │ │ AttrNames.cs //一些字符串常量 │ │ Client.cs //提供给数据表现模块的静态类 │ │ Client-Fields.cs //部分类,定义内部字段 │ │ Client-Handle.cs //部分类,处理服务器数据的方法 │ │ Client-Read.cs //部分类,接收服务器数据的方法 │ │ Client-Send.cs //部分类,向服务器发送数据的方法 │ │ Exception.cs │ │ jsonObject.cs //定义一些内部使用的结构,用于JSON格式化 │ │ Message.cs //定义一些数据结构,用于数据交换 │ │ User.cs //定义用户 │ │ │ └─Properties //项目属性和资源 │ AssemblyInfo.cs │ Resources.Designer.cs │ Resources.resx │ └─StormChatWPF //数据表现和用户交互模块*

使用截图

Golang客户端

stormchat使用截图
stormchat使用截图

源代码

github地址:https://github.com/mattuylee/stormchat

AVL树的C语言实现

· 阅读需 6 分钟
// 2018-12-08
// By Mattuy
// AVL树的C语言实现
// 实现对AVL树节点的增删改查
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int DataType; //树的数据域

//定义AVL树
typedef struct SearchTree
{
int height; //树的深度,空树(NULL)的深度为-1
DataType value;
struct SearchTree* left;
struct SearchTree* right;
} TreeNode, SearchTree;

TreeNode* SingleRotateWithLeft(TreeNode* grandpa); //左左单旋转
TreeNode* SingleRotateWithRight(TreeNode* grandpa); //右右单旋转
TreeNode* DoubleRotateWithLeft(TreeNode* grandpa); //左右双旋转
TreeNode* DoubleRotateWithRight(TreeNode* grandpa); //右左双旋转
TreeNode* Remove(SearchTree* tree, TreeNode* node); //删除节点
void Assign(TreeNode* dest, DataType* value); //将一个节点的值赋给另外一个节点
TreeNode* Find(SearchTree* tree, DataType value); //查找节点

//获取树高度
int getHeight(SearchTree* tree);
//删除同时有左右孩子的节点时寻找子合适的子节点来顶替被删除节点
TreeNode* findExtreamNode(TreeNode* node);
//中序遍历输出AVL树
void output(SearchTree* tree);

//左左单旋转
TreeNode* SingleRotateWithLeft(TreeNode* grandpa)
{
//将祖父变为父亲的右儿子,父亲原来的右儿子变为祖父的左儿子(祖父原来的左儿子就是父亲,关系已断开)
TreeNode* parent = grandpa->left;
grandpa->left = parent->right;
parent->right = grandpa;
//新的关系是,原来的孙子和祖父变成父亲的左右儿子(孙子位置没动)。
//原祖父(现父亲右儿子)的深度取决于原父亲的右儿子和原祖父的右儿子
//父亲的深度取决于孙子和祖父(现右儿子),因此须先计算祖父(右儿子)的深度
grandpa->height = max(getHeight(grandpa->left), getHeight(grandpa->right)) + 1;
parent->height = max(getHeight(parent->left), grandpa->height) + 1;
//返回新的根节点(原来是祖父,现在是父亲)
return parent;
}
//右右单旋转
TreeNode* SingleRotateWithRight(TreeNode* grandpa)
{
TreeNode* parent = grandpa->right;
grandpa->right = parent->left;
parent->left = grandpa;
grandpa->height = max(getHeight(grandpa->left), getHeight(grandpa->right)) + 1;
parent->height = max(getHeight(parent->right), grandpa->height) + 1;
return parent;
}
//左右双旋转
TreeNode* DoubleRotateWithLeft(TreeNode* grandpa)
{
grandpa->left = SingleRotateWithRight(grandpa->left);
return SingleRotateWithLeft(grandpa);
}
//右左双旋转
TreeNode* DoubleRotateWithRight(TreeNode* grandpa)
{
grandpa->right = SingleRotateWithLeft(grandpa->right);
return SingleRotateWithRight(grandpa);
}

//插入节点,返回插入后的根节点
TreeNode* Insert(SearchTree* tree, DataType value)
{
if (tree == NULL)
{
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
if (!temp)
{
return NULL;
} //申请内存失败
temp->left = temp->right = NULL;
temp->value = value;
temp->height = 0;
return temp;
} //插入新节点

if (value < tree->value)
{
tree->left = Insert(tree->left, value);
//当平衡被破坏时调整
if (getHeight(tree->left) - getHeight(tree->right) == 2)
{
//插入的节点在哪边就旋转哪边
if (value < tree->left->value)
tree = SingleRotateWithLeft(tree);
else
tree = DoubleRotateWithLeft(tree);
}
}
else if (value > tree->value)
{
tree->right = Insert(tree->right, value);
if (getHeight(tree->right) - getHeight(tree->left) == 2)
{
if (value > tree->right->value)
tree = SingleRotateWithRight(tree);
else
tree = DoubleRotateWithRight(tree);
}
}
else
return NULL; //不允许插入值相同的节点
tree->height = max(getHeight(tree-> left), getHeight(tree->right)) + 1;
return tree;
}

//删除节点
TreeNode* Remove(SearchTree* tree, TreeNode* node)
{
if (!tree || !node)
return NULL;
if (node == tree)
{
if (tree->left && tree->right)
{
//找到一个合适的子节点来替换被删除的节点
TreeNode* leaf = findExtreamNode(tree);
//记录是在左子树找的子节点还是右子树
bool doesLeft = true;
if (leaf->value > tree->value)
doesLeft = false;
//用子节点的值替代要删除节点的值
Assign(tree, leaf->value);
//删除子节点。因为现在tree节点的值和子节点一样,所以不能直接传tree节点作为参数
if (doesLeft)
tree->left = Remove(tree->left, leaf);
else
tree->right = Remove(tree->right, leaf);
tree->height = max(getHeight(tree->left), getHeight(tree->right)) + 1;
return tree;
} //被删除的节点有两个儿子
else if (!tree->left && !tree->right)
{
free(tree);
return NULL;
} //被删除的是叶子节点
else if (tree->left || tree->right)
{
TreeNode* temp = tree->left ? tree->left : tree->right;
free(tree);
return temp;
} //被删除的节点只有一个儿子
} //当前节点为待删除节点
else if(node->value > tree->value)
{
tree->right = Remove(tree->right, node);
//如果删除节点后破坏平衡,调整以重新平衡
//从右子树删除节点后进行左旋转
//如果左孩子有左孩子则进行单旋转,否则进行双旋转
if (abs(getHeight(tree->left) - getHeight(tree->right)) == 2)
tree = tree->left->left ? SingleRotateWithLeft(tree) : DoubleRotateWithLeft(tree);
} //待删除节点在右子树
else
{
tree->left = Remove(tree->left, node);
//从左子树删除节点后进行右旋转
//如果右孩子有右孩子则进行单旋转,否则进行双旋转
if (abs(getHeight(tree->left) - getHeight(tree->right)) == 2)
tree = tree->right->right ? SingleRotateWithRight(tree) : DoubleRotateWithRight(tree);
} //待删除节点在左子树
tree->height = max(getHeight(tree->left), getHeight(tree->right)) + 1;
return tree;
}

//为节点赋值
void Assign(TreeNode* dest, DataType* value)
{
dest->value = value;
}

//查找
TreeNode* Find(SearchTree* tree, DataType value)
{
TreeNode* cur = tree;
while (cur != NULL)
{
if (cur->value == value)
break;
cur = value > cur->value ? cur->right : cur->left;
}
return cur;
}

//获取树高度
int getHeight(SearchTree* tree)
{
return tree ? tree->height : -1;
}
/**
* 当被删除节点有左右孩子时找出左子树的最右节点或右子树的最左节点。务必保证传入的参数为被搜索的节点,
* 函数将根据其左右子树的深度来决定返回左孩子的最右子树还是右孩子的最左子树。
* 此函数仅应被Remove函数调用
*/
TreeNode* findExtreamNode(TreeNode* node)
{
if (node->right->height > node->left->height)
{
TreeNode* cur = node->right;
while (cur->left)
cur = cur->left;
return cur;
}
else
{
TreeNode* cur = node->left;
while (cur->right)
{
cur = cur->right;
}
return cur;
}
}
//中序遍历输出
void output(SearchTree* tree)
{
if (!tree) return;
output(tree->left);
printf("value = %d, height = %d\n", tree->value, tree->height);
output(tree->right);
}

//测试
int main()
{
SearchTree* tree = NULL;
for (int i = 1; i <= 8; i++)
tree = Insert(tree, i);
tree = Remove(tree, Find(tree, 6));
output(tree);
system("pause");
}

LeetCode之旅——Two Sum,哈希表的应用

· 阅读需 2 分钟

今天做的题叫Two Sum,简单题,给定一个整形数组和一个整数target,存在唯一的两个成员相加等于target,要求返回这两个成员的位置。

示例:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

解决方案

1. 暴力算法

最简单的当然是暴力算法,一个嵌套的for循环搞定。标准答案如下:

public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
}

2. 哈希表

第一种方法的时间复杂度是O(n2),空间复杂度O(1)。另一个更快的解决方案是利用哈希表。遍历数组并将成员其插入哈希表,再查询[target - 成员]是否在表中(不能等于自身),如果在则结果已产生。至于是一次遍历实现还是两次遍历个人认为区别不大。
标准答案如下:

public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[] { i, map.get(complement) };
}
}
}

总结

哈希表最大的优势在于查询。理想的哈希表可以以O(1)的时间复杂度处理查询。此题的微妙之处在于,需要将数组索引作为表的值而数组成员作为键。而思维惯性可能让人一时转不过弯。

哈希表虽然高效,但却不是任何时候都适用。它的空间复杂度是O(n),但其常数因子并不小,可能花费甚至浪费很大的空间。另外冲突处理也会一定程度降低哈希表的性能。

因此哈希表并不总是比暴力解法好。如果你的空间足够,数据量大,查询频度高,我认为使用哈希表是合理的选择。

C++实现贪吃蛇

· 阅读需 4 分钟

注意,编译前源文件字符编码必须为GB2312/GBK。否则填充字符会出现异常。

编译时需要指定按C++11标准编译,为了支持结构体字面量的语法。
g++ -std=c++11 -o gluttonous-snake.exe ./source.cpp

代码

#include <cstdlib>
#include <conio.h>
#include <deque>
#include <iostream>
#include <time.h>
#include <windows.h>
//定义一次步进
typedef struct {
//是否纵向移动
bool virticle = false;
//移动步长
int offset = 0;
}Step;
//定义'成长礼包'类型
enum GiftType {
//礼物,增加长度
GIFT_GIFT = FOREGROUND_GREEN,
//陷阱,减少长度
GIFT_TRAP = FOREGROUND_GREEN | FOREGROUND_BLUE,
//利剑,直接死亡
GIFT_SWORD = FOREGROUND_RED
};
//定义移动区域。窗口宽度应为width的两倍,因为ansi字符宽度仅高度的1/2。
#define FACTORY_WIDTH 64
#define FACTORY_HEIGHT 36

//定义蛇身颜色
#define SNAKE_BODY_COLOR (FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE)
using namespace std;
//控制台输出句柄
HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
//蛇身数据容器。
deque<COORD> snakeBody;
//死亡标记
bool dead = false;
//'成长礼包'
COORD gift, trap, sword;


//判定点是否在蛇身上
bool inSnake(COORD point) {
if (snakeBody.size() == 0)
return false;
deque<COORD>::iterator iter = snakeBody.begin();
while (iter != snakeBody.end()) {
if (point.X == (*iter).X && point.Y == (*iter).Y)
return true;
++iter;
}
return false;
}
//生成'成长礼包'
COORD createGift(GiftType color) {
//统计递归调用次数
static int count = 0;
++count;
COORD point;
srand(rand());
point.X = rand() % FACTORY_WIDTH * 2;
srand(rand());
point.Y = rand() % FACTORY_HEIGHT;
if (inSnake(point)) {
return createGift(color);
}
else {
SetConsoleCursorPosition(hOutput, point);
SetConsoleTextAttribute(hOutput, color);
cout << "█";
SetConsoleTextAttribute(hOutput, SNAKE_BODY_COLOR);
dead = count > 12 ? true : false;
count = 0;
return point;
}//连礼包都没地方放了,死了算了
}
//初始化
void init() {
system("cls");
snakeBody.clear();
srand(time(NULL));
snakeBody.push_front({ 0, 0 });
snakeBody.push_front({ 2, 0 });
snakeBody.push_front({ 4, 0 });
deque<COORD>::iterator iter = snakeBody.begin();
while (iter != snakeBody.end()) {
SetConsoleCursorPosition(hOutput, *iter);
cout << "█";
++iter;
}
sword = createGift(GIFT_SWORD);
trap = createGift(GIFT_TRAP);
gift = createGift(GIFT_GIFT);
}
//步进
void stepOnece(Step step) {
COORD head = snakeBody.front();
(step.virticle ? head.Y : head.X) += step.offset;
//死亡
if (inSnake(head)
|| snakeBody.size() == 0
|| (head.X == sword.X && head.Y == sword.Y)
|| head.X < 0 || head.X >= FACTORY_WIDTH * 2
|| head.Y < 0 || head.Y >= FACTORY_HEIGHT) {
dead = true;
return;
}
snakeBody.push_front(head);
SetConsoleCursorPosition(hOutput, head);
cout << "█";

int count;
if (head.X == trap.X && head.Y == trap.Y) {
count = 2;
trap = createGift(GIFT_TRAP);
}//陷阱,变短
else if (head.X == gift.X && head.Y == gift.Y) {
count = 0;
gift = createGift(GIFT_GIFT);
}//礼物,增长
else
count = 1;
for (int i = 0; i < count; i++) {
COORD back = snakeBody.back();
SetConsoleCursorPosition(hOutput, back);
printf(" ");
snakeBody.pop_back();
if (snakeBody.size() == 0) {
dead = true;
break;
}
}
}
//控制循环
void gameLoop() {
Step curStep = { false, 2 };
Step step = curStep;
while (!dead) {
for (int i = 0; i < 200; i++) {
Sleep(1);
if (!_kbhit())
continue;
char cmd;
bool breakdown = true;
cmd = _getch();
switch (cmd) {
case 'w':
step.virticle = true;
step.offset = -1;
break;
case 's':
step.virticle = true;
step.offset = 1;
break;
case 'a':
step.virticle = false;
step.offset = -2;
break;
case 'd':
step.virticle = false;
step.offset = 2;
break;
default:
breakdown = false;
break;
}
//禁止当前方向反方向步进
if (step.virticle == curStep.virticle && step.offset * curStep.offset < 0)
continue;
else
curStep = step;
if (breakdown)
break;
}
stepOnece(curStep);
}
}
int main() {
//设置缓冲区大小
SMALL_RECT rect = { 0, 0, 10, 10 };
SetConsoleWindowInfo(hOutput, true, &rect);
SetConsoleScreenBufferSize(hOutput, { FACTORY_WIDTH * 2, FACTORY_HEIGHT });
//设置窗口大小
rect = { 0, 0, FACTORY_WIDTH * 2 - 1, FACTORY_HEIGHT - 1 };
SetConsoleWindowInfo(hOutput, true, &rect);
//设置窗口样式
SetConsoleTextAttribute(hOutput, SNAKE_BODY_COLOR);
CONSOLE_CURSOR_INFO cursorInfo = { 1, false };
SetConsoleCursorInfo(hOutput, &cursorInfo);
//规则介绍
cout << "使用W、S、A、D控制方向,吃到绿色礼包长度增加,吃到黄色礼包时长度减短,"\
"吃到红色礼包直接死亡。您也可以按CTRL + C退出游戏。按任意键开始游戏。" << endl;
system("pause");
//开始游戏
while (true) {
init();
gameLoop();
system("cls");
SetConsoleCursorPosition(hOutput, { 0, 0 });
printf("You has dead! Retry? (y/n)");
char cmd;
cin >> cmd;
if (cmd != 'y')
break;
else
dead = false;
}
}