Posts

JavaScript对象的浅拷贝与深拷贝

Manan
概述 在JavaScript中对象的类型可以分为值类型和引用类型两种,值类型有:number,string,boolean,null,undefined,symbol等。引用类型有:object,function等。 JavaScript的对象为引用类型,所以对象变量作为右值赋值的操作实际上是引用的拷贝操作,即两个变量引用同一块内存区域。值类型的变量在作为右值赋值给一个左值变量时是对内存区域的拷贝。由此也就引出了JavaScript中对象的拷贝问题。 浅拷贝是指只拷贝对象中值类型变量,引用类型的变量依然采用引用拷贝。深拷贝是讲变量所有的内容重新拷贝一份到新的内存区域中,无论是值类型还是引用类型。 浅拷贝 JavaScript对象的浅拷贝实现有多种方式,常用的有 迭代对象 Object.assign 对象展开 1. 迭代对象 function shadowCopy(src) { const dst = new src.constructor(); for (const [prop, val] of Object.entries(src)) { dst[prop] = val; } return dst; } 这里采用构造函数去实例化对象,而不是采用对象字面量{}来创建的原因是保留对象的原型链信息。 2. Object.assign function shadowCopy(src) { const dst = new src.constructor(); return Object.assign(dst, src); } 3. 对象展开 function shadowCopy(src) { return { ...src }; } 深拷贝 在有浅拷贝作为前置知识的情况下,深拷贝很容易实现。 深拷贝主要要解决问题时完成对对象中引用类型属性的复制,当属性为值类型时,直接执行对象的浅拷贝,当遇到一个引用类型的属性时,可以递归按照之前设计的对象浅拷贝逻辑进行。 function doDeepCopy(src, dst) { for (const [prop, val] of Object.

旅行家问题和遗传算法

Manan
旅行家问题 旅行家问题(Travelling salesman problem 以下简称TSP)是一个NP难题,其内容为给定一系列城市,每个城市只访问一遍,然后回到起点城市,在所有可能的路径中长度求解最短的一条。 可以看出旅行家问题是组合问题与最短路径问题的结合,最短路径问题的求解算法有很多,常规的有“迪杰斯特拉算法”和“弗洛伊德算法“。但这些算法都无法完美的应用于旅行家问题,针对此问题较为有效的算法有”遗传算法“、”粒子群算法“、”蚁群算法“这类智能群算法。 本文将用”遗传算法”来求解旅行家问题。 遗传算法 遗传算法的发展 1965年,Holland首次提出了人工遗传操作的重要性,并把这些应用于自然系统和人工系统中。 1967年,Bagley在他的论文中首次提出了遗传算法这一 术语,并讨论了遗传算法在自动博弈中的应用。 1970年,Cavicchio把遗传算法应用于模式识别中。第 一个把遗传算法应用于函数优化的是Hollstien。 1975年是遗传算法研究的历史上十分重要的一年。这一 年,Holland出版了他的著名专著《自然系统和人工系 统的适应性》该书系统地阐述了遗传算法的基本理论和 方法,并提出了对遗传算法的理论研究和发展极为重要 的模式理论(schemata theory),该理论首次确认了 结构重组遗传操作对于获得隐并行性的重要性。 遗传算法的基本思想 遗传算法的基本思想是将问题的解编码为染色体,这是十分重要的环节,在算法中便是一个按照特定方式编码的串。 将问题的解编码之后,按照自然进化论的观点,生成一定数目的个体(染色体),然后按照自然选择,染色体交叉,染色体变异的流程不断地繁衍迭代。 种群经过不断地繁衍发展,最终最适应环境的一些个体会保留下来,这些最适应环境地个体也将是在遗传算法背景下待求解问题的最优解。 遗传算法的要素 通过上述对遗传算法的思想的阐述,可以得知遗传算法包含许多要素,其中最重要的便是染色体即问题的解。 染色体:编码之后的问题的解 种群:一定数目个体(染色体)组成的集合 自然选择算子:对种群中适应度较高的个体筛选的算法 染色体交叉算子:染色体之间进行交叉的方式 染色体变异算子:染色体变异的方式 PM:代表种群中染色体变异的概率 PC:代表种群中染色体之间交叉的概率 N:种群的规模,在不断迭代中种群的规模一般保持不变 在用遗传算法求解问题时,这些要是都是必备的。但是针对于不同的问题要素的表现形式有所不同。例如染色体的编码方式就有二进制编码和真值编码两类,对于不同的问题要选择合适的要素形式。 遗传算法对TSP的建模 染色体编码方式 针对TSP的描述,需要先将城市编号,如1, 2, ... n。TSP的解途径各个城市的顺序也就是路径可以表示为:1 -> 3 -> ... n,因此可以采用真值编码的方式对路径进行编码。 染色体表示为:1.3.2.5.6.4其中.为分隔符。 除此之外也可以选择二进制编码,将城市编号转变为特定长度的二进制数字。这种编码方式在染色体交叉和变异中会比较方便,但是针对于问题规模,编码的长度需要改变,同时染色体交叉过程中容易产生不合理的解(交叉过程中产生了一个不存在的城市编号)。 染色体交叉算子定义 交叉算子多种多样,分别适用于不同的问题。其中常见的算子有: Partial Mapped Crossover (PMC) Order Crossover (OX) Position Based Crossover(PBC) Order Based Crossover (OBX) Cycle Crossover(CX) Subtour Exchange Crossover 除此之外,还有针对于TSP优化的交叉算子”贪心交叉算子“等等,本文采用Order Crossover作为交叉算子。

博弈树的启发式搜索

Manan
概述 博弈树是一种基于与或图的启发式搜索算法。博弈主要分为两类,一是机遇性博弈,还有就是完备性博弈。机遇性博弈中参与博弈的玩家之间信息是不完备的,并且博弈中事件的发生具有概率性,日常中大部分的博弈都是机遇性博弈。完备性博弈是指参与博弈的玩家之间都掌握着博弈对手的完整信息,基于已掌握的信息对博弈进程进行推演。完备性博弈是一种理想的博弈,通常出现在棋牌类的游戏中。 对于一种博弈的游戏,参与者可能会有多个。基于与或图的博弈树启发式搜索只能应用于双人完备信息博弈。这种搜索算法也称为Max-Min搜索(极大极小搜索)。 与或图也称为与或树,是一种特殊的树结构。与或树是多叉树,每个节点的类型要么是与节点,要么是或节点。通常可以将与或树应用于问题求解上,对于一个问题可以将其归约为许多子问题的求解。这样的一个问题归约的过程就可以用与或树进行表示。其中原命题为与或树的跟节点,分解出的子命题为与或树的孩子节点。如果分解出子命题中一个命题有解就可以导致原命题有解,就把原命题所在节点命名为或节点,反之若需要所有子命题都有解才能导致原命题有解,那么这个节点就是与节点。 极大极小搜索 双人完备信息博弈中,假设博弈一方是MAX,另一方是MIN。对于MAX来说自己可选的行动方案都是或的关系,因为主动权掌握在MAX手中。而对手MIN所作出的所有决策在MAX看来都是与的关系,因为当主动权掌握在MIN手中后,MAX不得不考虑到MIN所有可能的决策结果,这样MAX才能作出对于自己最有利的决策。 基于如上的假设与考量结合双人完备信息博弈游戏的特点,可以总结出博弈树有如下特征: 博弈过程必须有立场,要么站在MAX的立场上,要么站在MIN的立场上。 博弈树中与节点与或节点是逐层交替出现的,其中根节点是或极点。或节点代表MAX所面临的博弈状态(MIN决策之后的博弈状态),与节点代表MIN所面临的博弈状态(MAX决策之后的博弈状态)。

JavaScript ZX——用JS写Shell脚本

Manan
ZX库简介 zx是Google推出的一个运行在Node.js环境下的方便开发人员编写命令行脚本程序的类库。 命令脚本程序是基于特定操作系统,方便完成的一系列批处理工作的脚本程序。在Unix-like的操作系统,通常是使用shell脚本。在Windows系统中使用的则是bat脚本。 这类批处理脚本都有一个共同的特点——语法晦涩不好编写。对于开发人员来说,掌握shell编程的收益并不大。好在Google推出了一款可以在Node运行时环境中进行shell编程的工具类库zx zx的Github项目地址为https://github.com/google/zx,此项目在笔者写下这篇文章时就已经有23k左右的star了,可见这个库确实解决了开发人员的一个痛点。 ZX库的安装 安装ZX之前,需要确保本机具有Node的运行时环境。如果没有安装,可以去NodeJS官网下载,地址为:https://nodejs.org/en/。 NodeJS的安装完毕后,你就可以使用npm(Node Package Manager)来安装zx了。 sudo npm install -g zx 使用ZX写一段shell脚本 zx提供了许多封装好的函数方便你进行shell编程。 例如:question函数,对readline进行了封装,可以更方便的接收shell的输入。同时zx还提供了fetch函数,可以更好的进行网络数据的请求。 在zx中以$符号开头的代表这是一个shell命令,它会立即执行并返回一个Promise,这个Promise被定义为 class ProcessPromise<T> extends Promise<T> { readonly stdin: Writable readonly stdout: Readable readonly stderr: Readable readonly exitCode: Promise<number> pipe(dest): ProcessPromise<T> kill(signal = 'SIGTERM'): Promise<void> } ProcessPromise的返回值为: class ProcessOutput { readonly stdout: string readonly stderr: string readonly exitCode: number toString(): string } 其中如果shell命令执行成功,那么exitCode字段将被设置为0。同时shell命令执行后的输出将会被保存在stdout中。如果执行失败,那么exitCode将为一个非零的整数,命令的输出将会被保存在stderr中。 同时你也可以对shell命令执行后的输出进行重定向: $`git pull`.pipe(streamVar) Demo:自动提交当前代码 #!/usr/bin/env zx // 注意$返回的是一个Promise let { exitCode } = await $"git add .

Java Swing类库汇总

Manan
Swing类库汇总 🌸Look And Feel 外观 BeautyEye L&F(国人开发) 🏠 HomePage: http://docs.52im.net/extend/docs/src/beautyeye3/ 🛒 Github: https://github.com/JackJiang2011/beautyeye 📦 Maven Repository: ❎ Flat L&F 🏠 HomePage: https://www.formdev.com/flatlaf/ 🛒 Github: https://github.com/JFormDesigner/FlatLaf 📦 Maven Repository: ✅ Dark L&F 🏠 HomePage: https://weisj.github.io/darklaf-docs/ 🛒 Github: https://github.com/bulenkov/Darcula 📦 Maven Repository: ✅ Substance L&F 🏠 HomePage: ❌ 🛒 Github: https://github.com/kirill-grouchnikov/radiance 📦 Maven Repository: ✅ Web L&F 🏠 HomePage: http://weblookandfeel.com/ 🛒 Github: https://github.com/mgarin/weblaf 📦 Maven Repository: ✅ 🛠实用工具类库

将Java编译为本地代码

Manan
将Java编译为本地代码 通常Java程序的执行流程为:将Java代码编译为Byte Code(字节码),然后JVM执行引擎执行编译好的Byte Code。这是一种中间语言的特性,它的好处就是可以做到平台的无关性,一份代码可以在任意的平台上运行。而且JVM语言采用了JIT(Just In Time)即时编译技术,会将执行中的热点代码(字节码)编译为本地代码运行,提高代码执行性能。 虽然Java的这种中间语言+即时编译的技术有很多优点,同时也有很多缺点。比如JVM执行引擎执行会比较占用资源,而且JIT有热加载的问题,所以执行的性能发挥不太稳定。对于软件的发布来说,我们通常会将JRE连同我们的应用程序一同发布,这样虽然能解决用户PC上JRE版本与要求版本不一致问题,但是也增大了软件包的体积。 针对上述JVM存在的问题,Oracel公司推出了一个名为GraalVM的项目,这个项目可以将Java字节码编译为本地代码。编译生成的本地代码无须JVM,可以直接在目标机器上运行。而且这种AOT(Ahead Of Time)的编译方式并不会对性能造成太大的影响,同时它还能够减少运行时的内存占用与CPU资源消耗。具体的其他特性,可以查看GraalVM官网。 GraalVM安装(OSX) GraalVM JDK可以与你本机的JDK互补的存在,GraalVM并没有提供相应的安装程序,而是以压缩的包的形式进行发布,你可以从Github上进行下载:https://github.com/graalvm/graalvm-ce-builds/releases/tag/vm-21.0.0.2 下载完毕后解压缩至相应目录即可。 安装完毕GraalVM之后,你可以安装native-image本地代码编译工具,这个工具需要依赖于GraalVM,所以在安装这个工具前,请先安装GraalVM。native-image本地代码编译工具也可以在上文中的Github仓库中进行下载,它也是压缩包的形式进行发布的,下载下来解压即可。但是与GraalVM不同的是这个工具并不是开箱即用,而是需要一些配置。 sudo xattr -r -d com.apple.quarantine /path/to/GRAALVM_HOME <GraalVM安装目录>/Contents/Home/bin/gu install native-image 执行完这个命令后,native-image就会安装到GraalVM的bin目录下。 测试编译本地代码 Java源代码: public class Test { public static void main(String... args) { System.out.println("Hello world"); } } 将源代码编译为字节码: javac Test.java 将字节码编译为本地代码: native-image Test

哈夫曼树与哈夫曼编码

Manan
概述 哈夫曼树(Huffman Tree)也是一种树,与其他树不同的是哈夫曼树的构造方式。在哈夫曼树的构造过程中有一个参考指标——带权路径长度。 路径是指从树中一个节点出发到另一个节点之间的分支,分支的数目称为路径长度。带权路径长度是考虑到节点之间的权重大小之后的一个指标参数,数值上它等于路径长度与该路径上所有节点的权重乘积。 $$ WPL = \sum_{i = 1}^{n} W_i \times L_i $$ 哈夫曼树是带权节点集合中构造出的WPL最小的二叉树。Huffman树本质上也是一种二叉树,同时由于其WPL最小,所以也称之为最优二叉树。 哈夫曼编码是在哈夫曼树这种数据结构基础之上的一种编码方式。常见的编码方式主要分为两种——等长编码和变长编码。 等长编码是指将待编码数据全部映射为长度大小一致的二进制序列,这样的编码编解码都很方便,也容易实现。但是缺点也很明显,这样的编码得到的字节序列会较大,在存储与传输过程中比较消耗资源。比较常见的ASCII码就是一种等长度编码的形式。 变长编码是指将待编码数据由一定规则指定编码为长度不一致的二进制序列,变长编码的优势在于能够实现对数据的无损压缩(相较于等长度编码,变长编码后的体积更小而且不损伤数据的完整性),但是编解码比较困难。 哈夫曼树的构造 哈夫曼树的构造算法需要所有带权节点构成森林(树节点的集合)作为输入,集合中每个树节点的左子树与右子树均为空。 从集合中选择一个权重最小的节点M0和权重次小的节点M1。 构造一个新的节点N0,N0左子树为M0,右子树为M1。 N0节点的权重大小为M0的权重加上M1的权重。 将M0和M1从集合中删除,并将新构造的N0节点放入集合中。 重复步骤1,直至集合中只剩下一个节点 哈夫曼树的特点 从哈夫曼树的构造中可以看出,哈夫曼树有以下特点: 叶子节点存储有效信息。 哈夫曼树中不存在出度为1的节点,即每个节点要么没有左右子树,要么都有左右子树。 若初始森林中树节点的个数为N,则哈夫曼树中的节点个数为2N - 1。 哈夫曼编码 哈夫曼树构造完成之后,就已经确定了对特定数据的哈夫曼编码。 数据的编码由该数据在哈夫曼树中的路径确定,具体形式为:从根节点出发,沿左子树行走为0,沿右子树行走为1。如图所示,节点A的路径为{left, left, left},故其编码为000。节点B的路径为{left, left, right},故其编码为001。 从图中便可看出哈夫曼编码属于变长编码,数据的编码长度并不相同。 哈夫曼解码 数据经过编码之后可以得到一串由0,1组成的二进制序列。解码就是将这串二进制序列重新变为原始数据的过程。解码的过程中需要用到将数据编码的哈夫曼树,其具体的操作流程为: 遍历二进制序列,遇到0则沿哈夫曼树向左走,遇到1则沿哈夫曼树向右走。 若哈夫曼树的当前节点为叶子节点,则完成了一个数据的解码。将解码数据保存,重新回到哈夫曼的的根节点。 重复步骤1,2直到序列被遍历完。 附录A——哈夫曼节点定义 class HuffmanNode<T>( var left: HuffmanNode<T>?

8086字符串操作

Manan
概述 8086关于字符串的五种操作指令: MOVS (MOVE BYTE OR WORD STRING) CMPS (COMPARE BYTE OR WORD STRING) SCAS (SCAN BYTE OR WORD STRING) LODS (LOAD BYTE OR WORD STRING) STOS (STORE BYTE OR WORD STRING) 从指令的全称中可以看到,8086对于字符串的操作既可以对字节进行操作,也可以对字进行操作。 上述指令的寻址方式均为隐含寻址,若SRC在存储器中,则数据地址由DS:SI提供,若SRC在寄存器中,则对字节操作时数据在AL中,对字操作时数据在AX中。若DST在存储器中,则数据地址必须由 ES:DI确定。若DST在寄存器中,则对字节操作时数据在AL中,对字操作时数据在AX中。

8086寻址方式

Manan
概述 一条汇编指令包含了操作码和操作数两部分,而操作数又分为目的操作数(DST)和源操作数(SRC)两种。汇编指令就是操作码与操作数的结合,有的操作码需要两个操作数(即DST和SRC)有的只需要一个操作数(例如PUSH),还有的不需要操作数(例如CLI)。 这种差异性便是寻址方式的不同造成的,所谓寻址便是确定如何寻找操作数的过程。 不管指令需要结合多少个操作数,指令执行过程中数据的流向是唯一的,那就是从SRC -> DST。并且在数据传递的过程中必须保障SRC和DST长度大小明确且一致。 指令系统的寻址主要包括两类: 数据的寻址方式:寻找指令所操作数据的方式 转移地址的寻址方式:寻找转移指令所需的程序地址 数据的八种寻址方式: 立即数寻址 寄存器寻址 存储器寻址 直接寻址 寄存器间接寻址 寄存器相对寻址 基址变址寻址 基址变址寻址且相对寻址 隐含寻址 立即数寻址 MOV AX, 100H ; 十六进制立即数 MOV BX, 1010 ; 十进制立即数 MOV AX, 12Q ; 八进制立即数 MOV AX, 0101B ; 二进制立即数 立即数只能作为源操作数(SRC)使用,无法作为目的操作数。立即数所占据的内存大小由目的操作数决定。且立即数本身长度不得超出目的操作数长度。 MOV AL, 10H ; 10H占据一个Byte的空间 MOV AX, 10H ; 10H占据一个Word的空间 MOV AL, 1010H ; ❌ 1010H占据一个Word的空间无法放入一个Byte的寄存器中 MOV 1010H, AX ; ❌ 立即数无法作为DST 注:CS寄存器在立即数寻址过程中无法作为目的操作数使用。

后缀表达式与基于栈VM

Manan
后缀表达式 算术运算表达式有三种形式,分别为“中缀表达式”,“后缀表达式”和“前缀表达式”。 中缀表达式是让数据结合在算符的两侧,例如a * (b + c) - d。这种表达式也是我们使用最多,最符合人类思考方式的算术运算表达形式。 前缀表达式与后缀表达式类似,后缀表达式是将算符置于数据之后,例如a b c + * d -。前缀表达式是将运算符置于数据之前,例如+ * a b c - d。 最常使用的中缀表达式可以通过一定的算法转换为后缀或者前缀表达式。 通过观察不难发现,后缀表达式在计算时是有序的,所谓有序就是我们只需遍历整个表达式就能得到表达式的结果,无需考虑运算符之间的优先级顺序(中缀表达式显然需要考虑算符之间的优先级顺序,而后缀表达式是已经按照运算符顺序进行排好序的表达式序列)。 后缀表达式的计算 算法准备 后缀表达式 数据栈 算法阐述 遍历后缀表达式字符串 如果字符串是数字,转换为数字并压入数据栈 如果是支持的算符,根据算符的数据结合性(一元算符结合一个数据,二元算符结合两个数据,不考虑算符的左结合和右结合)从栈中弹出指定数量的数据 将弹出的数据按照算符计算规则进行计算,并重新压入栈 Java代码实现 ArrayDeque<Double> operatorNumberStack = new ArrayDeque<>(); for (String token : tokenStream) { if (isSupportedOperator(token.charAt(0))) { double a, b = 0.