Posts

前言 我利用github pages作为平台搭建我的博客，我开始选择将博客内容和部署分成两个仓库存放，但这显然造成了复杂性的提升。在阅读 mdbook 的官方文档时，我发现他部署 book 的一个方式是利用一个新的分支进行部署，这样可以将内容和页面放在不同的分支上共同保存，同时有好的规整感。 原理 在 github 仓库的 Settings/Pages 下可以选择利用哪一个分支进行部署。 利用 github worktree 可以将当前分支绑定到一个新建的 worktree 目录上，并通过新的目录进行分支操作。 使用 新建分支 deploy 和 /tmp/blog 目录，利用github worktree 将目录 deploy 分支绑定到目录下。 将生成的页面文件（我这里在public文件夹中），拷贝到 /tmp/blog 目录下 在 /tmp/blog 下利用 git 操作，添加并提交到远程 deploy 分支中。 设置 github pages，用 deploy 分支作为 github pages 部署分支。 现在你可以将内容提交到 main 分支，而将部署提交到 deploy分支。 为什么使用临时目录 使用临时目录的样例来自 mdbook 的文档。因此我只是当一个黑盒来使用。我的想法是为了不破坏其他数据，不过有了解的朋友也欢迎来给我答疑解惑。 我的 Makefile 文件 .PHONY: deploy .PHONY: clean .PHONY: build .PHONY: commit clean: rm -rf public deploy: public @echo "====> deploying to github" -mkdir /tmp/blog git worktree prune -git worktree add /tmp/blog deploy rm -rf /tmp/blog/* cp -rp public/* /tmp/blog/ cd /tmp/blog && \ git add -A && \ git commit -m "deployed on $(shell date)by ${USER}" && \ git push origin deploy cd - build: hugo commit: git add Makefile config....

目标 对这个 网页中的数据集进行数据处理,选择一列 找出最大值和最小值, 选择其中两列求出差值并求和. 步骤 对于html, 可以使用wget或curl读入. 处理html内容可以采用pup工具来实现. 下载网页到本地 wget https://stats.wikimedia.org/EN/TablesWikipediaZZ.htm -O pra.html 对网站元素进行查看 最好的方法是使用浏览器的审查元素方式进行查看, 能够较快的找到自己所需的内容. 可以看到我们所需的数据表格在table中,id为table1.更近一步观察可以看到位于tbody中.可以通过pup过滤并 输出内容. 数据处理 通过pup获取html中第一个表格的数据 cat pra.html | pup 'table#table1 tbody td next{}' 此时内容如图 去除头部和尾部部分行 对于表格文件,我只关心表格中间的数据，而忽略表头和表尾，这里采用head和tail进行过滤. 删除尾部30行,删除头部208（209-1）行. head -n -30 tail -n +209 将列变为行，以空格分割 相对于一列，我更喜欢处理以整行数据,这样就可以利用awk的$获取分割. 通过tr命令进行替换 tr '\n' ' ' awk awk是一种善于处理文本的编程语言,他太强大了,以至于我们可以用awk完成其余的所有操作. awk '{sum = 0;max = 0; min = 65536;for(i = 2;i < 4302; i+=20) {if(max < $i) max = $i; if(min > $i) \ min = $i; if($i > $(i+1)) sum += $i - $(i+1); if($i <= $(i+1)) sum += $(i+1) - $i;}print max; print \ min; print sum } 正如我们所说，awk是一种编程语言，代码块中，$0 表示整行的内容，$1 到 $n 为一行中的 n 个区域，区域的 分割基于 awk 的域分隔符（默认是空格，可以通过-F来修改）。...

前言 最近一直在做一生一芯，跟着做了些PA的项目，感觉自己之前很多所学都有了很多欠缺，也越发发现学校在培养计 划上的自己认为的一些不合理地方，在此记录下:自己如果回到大一，可能会如何开始学习（顺带考虑一下培养计划）。 大一上 应该在大一上学到一门导论课，去知道自己大学四年应该学什么，可以学什么，同时可以将这些知识进行一个简单的串联， 未必要将每一个知识点学的很深，但希望可以覆盖到每一个知识点。 程序设计基础肯定要有，但课设（挺想把C语言课设搬到大一上的，这里一并说了）希望可以有一个培养为上，内容次之的 过程。 现在的课设很多开始已经是报告要卷，内容要卷的状态了。什么数据库，前端，GUI，一些“卷王”做出了很多远超于 课设本身内容的事情。 希望课设是将课上所学实践起来。而不是在各种内容之外的地方去竞争。也希望未来的学弟学妹都能够真正自己思考,动手 写出课设，而不是在网上copy代码。 可以让学生多学一些工具，比如利用git进行团队协作（老实说这个我现在都还没做好），通过make工具链编译。未必要成为 课设加分项，但也可以让学生开始接触一些试试（我现在就在被makefile折磨）。 这里点赞一下我们的实验课老师，他实验课的开始就让我们体会了一些git的用法，据说现在学弟学妹还可以在CG平台实验了。 大一下 学会工具使用！学会工具使用！学会工具使用！ 一定需要一门课来教一些工具的使用了，命令行，shell，版本控制，文本编辑…。狂吹The missing semester of your CS education 。 如果说大一上已经开始接触git了，你可能感受到（或没有）他的便利，如果没有，尝试继续在日常使用。 如果你没有开始，用qq，U盘传文件的方式已经让你感到麻烦，开始git吧，找寻一种更高效（开始可能不）的方法。 学会使用这些工具未必能让你立刻觉得你付出的时间会有回报，但他们一定会穿插在你学习计算机的每一个时刻。 对于C++，老师上课第一件要说的就是：学的是面向对象程序设计，只是用C++来教学，因此将更多实时间放在面向对象 上应该是个好主意。 装一台虚拟机，装上linux（颇有私货），但从无到有掌握linux确实能提高很多你的能力（包括查阅文档）。 建议 老师的PPT很老，对于教学来讲足够了，但对于计算机前沿来讲显得过于陈旧。可以多上网冲浪看一看，现代计算机发展到了哪一个阶段。 多实践，多敲键盘，学会计算机的最好办法。 查阅手册，查看代码，搜索网页。解决问题的最好办法 结语 祝你早日成为计算机科学家

介绍 Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。 算法主要通过维护结点集合S。通过从结点集V-S中选择最短路径最小的结点u,将其加入进S中，并对所有从u发出可到达V-S集合中结点的边进行松弛操作。 对邻接表进行操作 松弛操作：对于一条从 顶点u指向 顶点v的边 u–>v来说，如果满足 d[u]+w(u,v)<d[v],就更新 d[v],使得 d[v]=d[u]+w(u,v)；这就是对 边uv的一次松弛操作； 其中，w(u,v)表示边的权重，d(u)表示顶点u到达源s的最短距离(目前已知) 因此我们可以将算法理解为三个操作： 找到V-S集合中距离S集合最小结点 将结点加入S集合中 对V-S中剩余结点进行松弛操作。 算法描述 解释 算法的主要逻辑为while循环。Q始终为Q=V-S。每一次通过EXTRACT-MIN(Q)取出Q中距离最小值u。并将u放入S集合中。之后在for循环中对Q中剩余结点进行松弛操作。 对距离进行更新。 分析 算法通过每次从Q中找出距离最小的一个结点插入到S中，并将Q中剩余的结点距离进行松弛，直到Q中没有结点结束。因为Q中初始结点一共有V个，因此一定会有一次O(V)操作(全部插入)。 注意到我们每次只需要松弛刚插入结点连接到的表，由于采用邻接表操作，我们对每一个边只会松弛一次，因此一共会执行|E|次。 找到最小结点的操作可以有多种方式实现，下面介绍三种。 利用一次遍历实现(常通过维护数组) 我们每一次都通过遍历Q中全部结点找到最小值，这时候需要对一次插入结点都需要执行一个O(V)操作。算法的时间复杂度为 $$ O(V^2 + E) = O(V^2) $$ 利用二叉堆实现 显然，如果我们每一次都要找到最小值，可以通过使用二叉堆实现优先队列来优化寻找最小值的算法。这样我们可以将查找最小值的操作优化到O(lgV) 而对于二叉堆，每一次修改距离并加入到二叉堆都需要一次更新，因此复杂了松弛操作，时间复杂度为 $$ O((V+E)lgV) $$ 即每一次删除Q中一个结点和将结点距离松弛化都需要lgV时间 因此，是否优于第一种需要考虑E的范围，即图是稀疏图还是稠密图 利用斐波那契堆 斐波那契堆的对于找到最小值并进行删除需要的时间与二叉堆一样，都是O(lgV)，但对松弛操作，斐波那契堆的摊还代价是O(1),因此可以实现更好的优化，他的时间复杂度为 $$ O(VlgV + E) $$

Rust介绍 官网对rust的介绍为一门赋予每个人构建可靠且高效软件能力的语言。 Rust是一门系统编程语言。简单来说，系统编程语言是一种资源受限的编程，你需要对每个字节和每个CPU时钟周期精打细算，做到高效的完成任务。 常见的系统编程应用场景: 操作系统 各种设备驱动 文件系统 数据库 嵌入式设备 内存管理程序 高级编程语言 虚拟化及软件程序 游戏 等等… 为什么选择Rust 系统编程语言已经有C/CPP了，为什么我还要选择Rust? C语言诞生于1972年，C++诞生于1979年，这至今41+年的时光中一直没有编程语言去挑战他们的地位。 由于时代原因，C和C++是两门过于相信程序员的编程语言，不会去检查程序员出错的代码。 Rust的第一个正式版本发布于2015年，融合了现代编程语言的优秀设计，解决了传统系统编程语言的痛点问题。产生了高性能，可靠性，生产力三个优秀特点。 最值得一提的是可靠性，Rust的设计使得你可以在编译器解决各种错误，而不是运行时。同时他的这种设计也让多核时代的多线程编写变得更加简单。 又有谁没被segmentation fault折磨过呢？ 享受编程 一旦你学会了rust，你就会享受到面向编译编译器开发带来的好处（虽然我个人现在还在痛苦当中）。感受前期多用脑子，开发不用脑子的特点了。 官方文档丰富 官方（社区）为Rust提供了许多优良的文档，比如the book，他们本身的优秀使得你可以从官网快速开始学习Rust。 Rust的缺陷之处 学习曲线陡峭 Rust与C-like语言较大的差异使得上手Rust变得困难。为了严格防止未定义行为，Rust又引入了所有权，生命周期等概念。这使得学习Rust的难度进一步提高。 编译时间长 为了保证可靠性，Rust需要在编译时进行大量的检查（编译器教你做事），这使得一个大的项目要花费更多的时间在编译上。更为遗憾的是这个缺点可能需要很久（甚至不可能）改善。 不过现在已经有多线程编译的出现以减少编译时间。 就算你不致力于使用Rust，也可以看一看Rust Rust吸收了许多编程语言的优良设计，并解决了许多过去编程的痛点问题。就算你不使用Rust，去学一学Rust的哲学也可以帮助你成为更好的程序员。