Posts

介绍 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的哲学也可以帮助你成为更好的程序员。

简介 你可能经常看到.tar与.tar.gz文件，但你可能很少思考过他们的用法。下面将介绍他们的区别 tar tar是打包命令，可以把一大堆的文件和目录打包成一个文件，方便文件的备份和文件在网络中的传输。 弄清打包和压缩的概念，打包并不会减小文件的大小。 当我们想要将多个文件压缩成一个压缩包时，我们需要先对这些文件进行打包，然后再用压缩程序进行压缩。 gz(误) gz并不是一个正确的说法，事实上你可以单独使用gzip等压缩程序对文件进行压缩，常见的.tar.gz是直接用tar打包并通过应用程序进行压缩的一种方式。 永远记得一个事实：linux当中后缀名不是必须的，更多是为了便于区别。 从例子学习使用 tar进行文件打包 1.打包文件 tar -cf file.tar file1 file2 将file1和file2进行打包。-c表示进行打包，-f指定打包文档(file.tar) 2.解包文件 tar -xf file.tar -x表示解包，-f指定解包文档(file.tar) 压缩文件进行文件压缩 这里只介绍利用gzip压缩软件，事实上还有其他的压缩软件可以使用 1.压缩文件 gzip file.tar 2.解压文件 gunzip file.tar.gz 直接利用tar进行打包与解压 1.压缩文件 tar -czvf file.tar.gz file1 file2 -c,-f已经介绍过。-z表示使用的压缩是gzip压缩，-v表示显示所有过程 2.解压文件 tar -xzvf file.tar.gz 现在你应该理解了压缩与解压阶段各种参数的意义。 注意：-f后面必须接文档名，所以作为最后一个参数

简介 限制想要将工作从windows迁移到linux上的一个方面就是游戏。Steam已经通过proton给到了游戏玩家更多的选择。暴雪尚未出现linux版本，但好在还有wine的存在。通过lutris，现在你可以更轻松地在linux上享受游戏。 我会尽量给出官方文档，以便于不同时间的不同用户进行操作时可以减少错误。 操作系统：manjaro 显卡：Nvidia no-free驱动 步骤 1.安装合适的Gpu驱动 https://github.com/lutris/docs/blob/master/InstallingDrivers.md lutris为我们创建了一个良好的文档说明。你可以选择与你电脑相符的介绍并继续操作。对我的系统manjaro而言，我已经在安装时选择了no-free驱动，因此已经有了一套正确的驱动支持。 安装wine https://github.com/lutris/docs/blob/master/WineDependencies.md 同样，选择你的发行版并按步骤进行操作,这里以我的系统manjaro为例。 修改/etc/pacman.conf,添加[multilib]启动multilib仓库，在文件中添加以下内容： /etc/pacman.conf -------------------------------------------------------------------------------------- [multilib] Include = /etc/pacman.d/mirrorlist 更新pacman仓库 sudo pacman -Syu 安装wine，要安装的包有点多，但其实很多你已经安装过了，全部的依赖安装可以避免之后出现奇奇怪怪的问题。 sudo pacman -S --needed wine-staging giflib lib32-giflib libpng lib32-libpng libldap lib32-libldap gnutls lib32-gnutls \ mpg123 lib32-mpg123 openal lib32-openal v4l-utils lib32-v4l-utils libpulse lib32-libpulse libgpg-error \ lib32-libgpg-error alsa-plugins lib32-alsa-plugins alsa-lib lib32-alsa-lib libjpeg-turbo lib32-libjpeg-turbo \ sqlite lib32-sqlite libxcomposite lib32-libxcomposite libxinerama lib32-libgcrypt libgcrypt lib32-libxinerama \ ncurses lib32-ncurses opencl-icd-loader lib32-opencl-icd-loader libxslt lib32-libxslt libva lib32-libva gtk3 \ lib32-gtk3 gst-plugins-base-libs lib32-gst-plugins-base-libs vulkan-icd-loader lib32-vulkan-icd-loader 以上，wine安装完成。 ...

简介 数据流重定向是将某个指令执行后要输出在屏幕上的数据，传输到其他的地方。一是可以简化我们的屏幕输出， 去获取我们有用的数据。同时我们还可以将我们想要的数据存储下来。 你可以通过echo "123"和echo "123" > filename 去简单尝试一下这种方式的特点，第二种可以通过 查看新增的file文件观看内容。 标准输入输出与标准错误输出 基本使用 > 是我们实现这种数据流重导向所用的特殊字符，数据流重导向包括标准输入，标准输出和标准错误输出， 他们的规则如下所示： 名称 代码 符号 标准输入(stdin) 0 <或« 标准输出(stdout) 1 >或» 标准错误输出(stderr) 2 2>或2» > 和 » 的区别是 > 以覆盖的方法输出内容， » 则是以累加的方式输出内容。你可以自 己试一试。 标准输入的用法类似，可以尝试一下cat > file 尝试键盘输出，使用[ctrl]+d退出，然后看一下得到的 文件。 /dev/null 垃圾桶 在linux一切皆文件的哲学中 /dev/null是一个特殊的"装置" 你可以将任何你想忽略的内容导向到它，而这些 内容将彻底被丢弃。 特殊写法 如果我们想要将正确与错误数据写入同一个文件时，可能会发生数据交叉写入该文件内的情况，造成次序的错乱， 这个时候你可以使用 2>&1 和 &> 的语法。 find /home -name .bashrc > list 2> list <=错误 find /home -name .bashrc > list 2&>1 <=正确 find /home -name .bashrc &> list <=正确 2>&1 这种写法可以理解为将标准错误输出重定向到标准输出 &>file 这种写法可以理解为将标准输入和输出都重定向到文件file中 ls 2>1 测试一下，不会报没有2文件的错误，但会输出一个空的文件1； ls xxx 2>1测试，没有xxx这个文件的错误输出到了1中； ls xxx 2>&1测试，不会生成1这个文件了，不过错误跑到标准输出了； ls xxx >out.txt 2>&1, 实际上可换成 ls xxx 1>out.txt 2>&1；重定向符号>默认是1,错误和输出都传到out.txt了。 ...