Posts

JavaScript学习总结 基础语法 js基础的语法和C/C++等众多语言类似，有8种基本类型： string number boolean null undefined object symbol bigint 以及流程控制和循环语句等： if switch for for .. in for .. of while do .. while JS Object 在js中，除了几个基本类型，其他基本都可以当成是Object。而Object这个对象就是JS中最基本的Object, 除了使用Object.create(null)创建的对象，其他对象都会默认使用Object.prototype作为自己的[[Prototype]]。如下是JS中几种主要Object的导图： Function JS中的function也是Object, 只不过是可以“执行”的Object。要注意的是，js中的this变量的处理与其他语言不太一样，this指向的是调用该函数的对象，比如a.hi()，调用hi()的时候，this指向的是a这个object, 而用b.hi()时则是指向b这个object。 This 在JS中，当调用Object里面的函数时，并不能用变量名直接访问对象的其他property，而是必须通过this变量。一般情况下，this就是指向调用对象的一个指针。 Arrow function JS的箭头函数() => xxx除了是简化的函数外，还有一点比较特殊：没有this，所以箭头函数会直接使用调用环境下的this。 Closure JS中闭包其实就是上下文或者说Environment的复制（估计解释型语言应该都是这样）再加上JS的垃圾回收机制（一个对象没有任何引用或者一组与Global无关的对象才会被自动回收）。Environment就是执行时的层级，其中记录了当前Block下的各种变量。比如： function a(){ let count = 0; return function(){ count++; } } let b = a(); 当如上代码执行时，会先创建一个a的Environment，然后再创建被返回的那个匿名函数的Environment，因为匿名函数被b引用，而a的Environment会被匿名函数引用，便形成了一个闭包。 Prototype JS中的prototype是Object的一个特殊的属性，当访问Object的属性或者函数时，如果没有找到相应的，则会去prototype中寻找，因此我们可以用prototype来实现继承关系。因为prototype本身也是一个Object，所以可以有很多层的继承。实例的__proto__属性是真正的prototype的一个setter/getter，对于真正的prototype，一般用[[Prototype]]表示。 在函数和Class中，有一个prototype的属性，注意这个属性并不是上面所讲的prototype。函数和Class的prototype属性是用来给实例的__proto__或者说[[Prototype]]赋值的，需要使用new操作符。比如： function User(){ this.name = "John"; } User.prototype = { name: "IIa" } let user = new User; console.log(User.prototype == user.__proto__); Class Class是JS为OOP设计的一个结构，跟其他OOP语言一样有成员、方法，可以继承，有静态变量和方法，但是如下特性还只在最近的浏览器版本中部分实现： 静态成员 私有成员或函数(#) JS的Class本质上也是一个Function, 只不过把constructor体现的更明显，其中super关键字也可以在普通Object中使用。 ...

红黑树(C++) 红黑树性质 每个节点只能是红色或者黑色 根节点是黑色 叶子节点是黑色 红色节点的子节点必须是黑色 任一节点到其子树叶子节点的所有简单路径具有相同数量的黑色节点 插入 共6种情况，其中33对称，实际上就3种 删除 共8种情况，其中44对称，实际上就4种 代码实现 #include <algorithm> #include <iostream> using namespace std; enum Color { RED, BLACK }; template<typename T> class Node { public: Node *parent, *left, *right; T key; Color color; Node(T key, Color color = RED) : key(key), color(color) { parent = nullptr; left = nullptr; right = nullptr; } Node() : Node(0) { } }; template<typename T> class RBT { private: Node<T> *nil; Node<T> *root; public: RBT() { nil = new Node<T>(0, BLACK); root = nil; } void leftRotate(Node<T> *x) { Node<T> *y = x->right; x->right = y->left; if (y->left != nil) { y->left->parent = x; } y->parent = x->parent; if (x->parent == nil) { root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } void rightRotate(Node<T> *y) { Node<T> *x = y->left; y->left = x->right; if (y->left != nil) { y->left->parent = x; } x->parent = y->parent; if (y->parent == nil) { root = x; } else if (y->parent->left == y) { y->parent->left = x; } else { y->parent->right = x; } x->right = y; y->parent = x; } void insert(Node<T> *z) { Node<T> *y = nil; Node<T> *x = root; while (x != nil) { y = x; if (z->key < x->key) x = x->left; else x = x->right; } z->parent = y; if (y == nil) { root = z; } else if (z->key < y->key) { y->left = z; } else { y->right = z; } z->left = nil; z->right = nil; z->color = RED; insert_fixup(z); } void insert_fixup(Node<T> *z) { while (z->parent->color == RED) { if (z->parent == z->parent->parent->left) { Node<T> *y = z->parent->parent->right; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->right) { z = z->parent; leftRotate(z); } z->parent->color = BLACK; z->parent->parent->color = RED; rightRotate(z->parent->parent); } } else { Node<T> *y = z->parent->parent->left; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->left) { z = z->parent; rightRotate(z); } z->parent->color = BLACK; z->parent->parent->color = RED; leftRotate(z->parent->parent); } } } root->color = BLACK; } void transplant(Node<T> *u, Node<T> *v) { if (u->parent == nil) root = v; else if (u->parent->left == u) u->parent->left = v; else u->parent->right = v; v->parent = u->parent; } Node<T> *minimum(Node<T> *u) { while (u != nil && u->left != nil) u = u->left; return u; } void remove(Node<T> *z) { Node<T> *y = z, *x; Color origin_y = y->color; if (z->left == nil) { x = z->right; transplant(z, z->right); } else if (z->right == nil) { x = z->left; transplant(z, z->left); } else { y = minimum(z->right); origin_y = y->color; x = y->right; if (y->parent == z) x->parent = z; else { transplant(y, y->right); y->left = z->left; y->left->parent = y; y->color = z->color; } transplant(z, y); y->left = z->left; y->left->parent = y; y->color = z->color; } if (origin_y == BLACK) { remove_fixup(x); } } void remove_fixup(Node<T> *x) { while (x != root && x->color == BLACK) { if (x == x->parent->left) { Node<T> *w = x->parent->right; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; leftRotate(x->parent); w = x->parent->right; } if (w->left->color == BLACK && w->right->color == BLACK) { w->color = RED; x = x->parent; } else { if (w->right->color == BLACK) { w->left->color = BLACK; w->color = RED; rightRotate(w); w = x->parent->right; } w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; leftRotate(x->parent); x = root; } } else { Node<T> *w = x->parent->left; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rightRotate(x->parent); w = x->parent->left; } if (w->left->color == BLACK && w->right->color == BLACK) { w->color = RED; x = x->parent; } else { if (w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; leftRotate(w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rightRotate(x->parent); x = root; } } } x->color = BLACK; } }; // test for number 1-100 int main() { auto *nodes = new Node<int>[100]; for (int i = 0; i < 100; ++i) (nodes + i)->key = i + 1; RBT<int> T; for (int i = 0; i < 100; ++i) { T.insert(nodes + i); } for (int i = 0; i < 95; ++i) T.remove(nodes + i); return 0; }

题龙阳县青草湖 [作者] 唐温如 [朝代] 元 西风吹老洞庭波，一夜湘君白发多。 醉后不知天在水，满船清梦压星河。 无题 [出自] 风云 倚楼听风雨,淡看江湖路. 但见泪痕湿,不知心恨谁! 春夜喜雨 [作者] 杜甫 [朝代] 唐 好雨知时节，当春乃发生。 随风潜入夜，润物细无声。 野径云俱黑，江船火独明。 晓看红湿处，花重锦官城。 和董传留别 [作者] 苏轼 [朝代] 宋 粗缯大布裹生涯，腹有诗书气自华。 厌伴老儒烹瓠叶，强随举子踏槐花。 囊空不办寻春马，眼乱行看择婿车。 得意犹堪夸世俗，诏黄新湿字如鸦。 大德歌·冬景 [作者] 关汉卿 [朝代] 元 雪粉华，舞梨花，再不见烟村四五家。 密洒堪图画，看疏林噪晚鸦。 黄芦掩映清江下，斜缆着钓鱼艖。 清平乐·春归何处 [作者] 黄庭坚 [朝代] 宋 春归何处？寂寞无行路。 若有人知春去处，唤取归来同住。 春无踪迹谁知？除非问取黄鹂。 百啭无人能解，因风飞过蔷薇。 送别 长亭外 [作者] 李叔同 长亭外 古道边 芳草碧连天， 晚风拂柳笛声残 夕阳山外山， 长亭外 古道边 芳草碧连天， 晚风拂柳笛声残 夕阳山外山， 天之涯 地之角 知交半零落， 一壶浊酒尽余欢今宵别梦寒， 长亭外 古道边 芳草碧连天， 问君此去几时来 来时莫徘徊， 天之涯 地之角 知交半零落， 人生难得是欢聚 惟有别离多， 天之涯 地之角 知交半零落， ...

为什么要Windows + Linux 其实主要是因为N卡和CUDA，不然直接macOS就行了 (x) 探索经历 Arch + i3wm + kvm 众所周知，Arch是最好的发行版(x)，配上i3wm的便捷操作，效率确实能提高不少，但是最终还是放弃了这个方案。放弃的原因并不是因为软件的问题，主要还是因为硬件的问题，一是主板不支持vt-d，不能直通显卡给KVM，而windows和macOS都是比较吃显卡的，二是新换的Intel AX200在Linux固件上还有点问题，不过这个问题是personally。 Windows10 + Hyper-v 最终还是选择了这个方案，主要是因为Linux可以不吃显卡，有图形化的需求可以直接在Windows上跑一个X Server。 Hyper-v安装Arch 安装过程都是傻瓜式的，因为我笔记本上刚好有两块SSD，索性就直接把Arch装在256G的PM961上了，然后Switch用的就是默认的Switch。 Arch安装Hyper-v Integration Service 微软提供了一套服务来让宿主机和Hyper-v VM交互，包括文件传输、状态监控、获取IP等等，只需要安装hyperv这个包就行了，然后开启如下三个daemon: hv_kvp_daemon hv_vss_daemon hv_fcopy_daemon 不过启动这3个service后再重启VM，马上就会发现问题：这3个Service启动时有很大的可能会失败。然后看了一下Service的内容: [Unit] xxx ConditionPathExists=/dev/vmbus/hv_xxx 失败的原因是ConditionPathExists不满足，但是奇怪的是重启登录后这个设备是存在的，手动启动是可以成功的，于是开始Google(期间因为网络问题错过了标准答案，还好后来archlinuxcn群里有人帮忙找到了答案)。在Redhat的论坛里有一篇15年的帖子讨论 了这个问题，然后我看了一下日志发现现在2020年了，hyper-v的这个设计还是一样毫无变化。主要的原因就是hyper-v的这个vmbus是通过netlink挂载上去的，而网络传输是存在延迟的，所以就会导致在Integration Service启动的时候vmbus还没有挂载上，不过解决的办法也很简单，就是自己添加一个udev的rule，在vmbus成功挂载时再次启动相应的service： SUBSYSTEM=="misc",KERNEL=="vmbus/hv_kvp",TAG+="systemd",ENV{SYSTEMD_WANTS}+="hv_kvp_daemon.service" 那么Integration Service启动失败的问题就差不多解决了(期间因为把==写成了=，找了好几个小时 TwT)。 Windows Terminal的配置 Windows Terminal是微软官方发布的一款terminator，目前还在preview，不过已经0.9了，估计可能20H1就要发布正式版了。 第一步当然是要先换字体和配色，字体很简单，用fontFace配置就行了，然后配色，刚好自带了Solarized(目前最喜欢的配色)，不过如果是Powershell最好换用其他颜色，因为PS的语法亮尚会和Solarized冲突。(感谢这些愿意无私奉献的艺术家们) 接下来就是配置ssh登录Arch，因为Default Switch的IP range是dynamic的(为什么不用Static IP?因为之前试过几次都不稳定，不是突然变了就是突然连不了Internet了)，所以需要动态获取Arch的IP，好在Powershell提供了很多操作命令，实现起来很简单： function arch_addr { $addr = (Get-VMNetworkAdapter Arch).ipaddresses[0] return $addr } 同时为了支持转发X，需要配置端口转发，因为Windows Terminal中直连貌似不行，完整的代码如下： $arch_switch="Default Switch" function arch_addr { $addr = (Get-VMNetworkAdapter Arch).ipaddresses[0] return $addr } function arch_switch_addr { return (Get-NetIPAddress | Where-Object {$_.InterfaceAlias -like "*($arch_switch)*" -and $_.AddressFamily -eq "IPv4"}).ipaddress } function arch { $addr = arch_addr $switch_addr = arch_switch_addr $x_port = 6000 ssh -R $switch_addr`:$x_port`:localhost`:$x_port mt@$addr -i C:\Users\RMT\.ssh\arch } 同时需要手动在Arch中设置DISPLAY，然后就可以转发X了，Windows10用的是VCXSRV。 ...

虽然知道了有理数集是可数的，但一直都不知道该如何定义一个有理数序列，使得每个有理数都在其中出现至少一次。今天看书的时候了解到了一种构造方法，所以记录一下。 有理数的可数性证明 众所周知，有理数都可以写成$ \frac{p}{q} $的形式，其中p和q都是自然数。对于一个大于1的正整数x，将x表示为$x=p + q$共有$x-1$种表示 方式。对于所有的$x=2,3,4,\dots$，我们将p和q构造成分数$\frac{p}{q}$，并按照p从小到大排列，则可以得到如下序列(忽略p和q有大于1的公因数的情况)： $$\frac{1}{1},\frac{1}{2},\frac{2}{1},\frac{3}{1},\frac{1}{3},\frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1},\frac{1}{5},\frac{5}{1},\frac{1}{6},\frac{2}{5}\dots$$ 或许从这里还看不出这个序列已经包含了所有大于0的有理数，那么可以看如下的规律： 对于$p=1,2,3,4,\dots$，其分母都包括了所有的自然数。对于负有理数，vice versa.

因为最近要写一篇GPU方面的论文，所以找了一些资料慢慢看 参考：GPU Technology Trends and Future Requirements 虽然是多年前的文章，不过讲得很细～ GPU的发展 GPU的基本功能是处理图形，从最初单一的pipeline发展到现在，已经能够完成很多通用的计算任务，而且拥有远超CPU的并行计算能力。 GPU基本知识 GPU接受的数据应该是一系列的Vertex(保存坐标信息)和Attributes(保存颜色、亮度等信息)，Vertex由专门的vertex shader处理，Attribute由pixel shader处理，shader就是GPU中的一个子程序。经过一系列的shaer处理后，最初的几何数据便会成功最终的像素合并到Frame Buffer中。 GPU基础架构 从架构图可以比较容易看出，基本的工作方式就是通过BUS传输数据，然后GPU中一些shader讲计算任务分发给各个TPC。至于其中各个组件的作用，见下面的MindMap。