Posts

在内存不够大时，需要开启Swap，使用一部分硬盘，作为虚拟内存，解决内存容量不足的情况。这篇博客是以 Ubuntu 基础来操作的，其他 Linux 系统基本类似。很简单，跟着下面的步骤，一步一步来操作即可。 ...

Google的VPS创建好后，默认是无法通过外部的工具ssh登录的，要使用外部SSH工具登录，需要修改ssh的配置。 ...

上一篇博客我们实现了一些简单的数学曲面，这一节我们将继续更复杂的数学曲面展示，所有资源完全承接上一篇内容。 2.5 创建一个涟漪效果 先来看一下最终要实现的效果图 我们一步一步来实现这个效果。首先，要创建一个基于到原点距离正弦波。而这个距离，我们使用毕达哥拉斯定理也就是勾股定理 $a^2 + b^2 = c^2$ 。对于这个效果来说，我们是基于XZ坐标来求Y坐标的，所以也就是 $\sqrt{x^2 + z^2}$ 。 ...

这篇博客是上一篇 使用Unity3D展示Sin函数动画 的续篇，在上一篇的基础上，来实现更复杂的效果。在文章最后会有完整的 C# 代码和 Shader 代码，先来看一下最终的效果图 由于篇幅太长，所以将分为上下两部分，现在开始第一部分的内容。 先将上一节 使用Unity3D展示Sin函数动画 的资源准备好，可以按下面的步骤手动建立，也可以直接导入上一节内容的完整 Unity 资源包，点这里下载 使用Unity的Cube做成一个Prefab 新建一个 Shader，命名为 ColoredPoint，Shader 的代码为上一篇博客的 Shader 新建一个材质，命名为 ColoredPoint，并使用第2步中创建的Shader C# 逻辑代码，也使用上一篇博客中的完整代码，在本文中会有很多修改 接下来，我们开始新的内容。 1 在不同的效果函数之间切换 在上一篇博客中我们实现了Sine函数的展示，现在要加入更多函数的展示，为了方便在运行状态可以随时切换到其他函数，我们需要把每一种类型的展示放在独立的函数中。 1.1 将 Sine 函数的表示放在独立函数中 首先在 Graph 脚本中添加一个新的函数 float SineFunction(float x, float t) {}，这个函数将用于展示 $f(x,t) = sin(π(x + t))$。然后我们需要将函数体的内容填写进去，代码如下 float SineFunction(float x, float t) { Mathf.Sin(Mathf.PI * (x + t)); } 然后把 Update 函数里的代码改为调用我们新添加的函数 void Update () { for (int i = 0; i < points....

今天我们来聊一下哈希(Hashing)，有时候也被称为散列。简单来说，哈希是一个唯一标识，用于标识一个东西。例如，一个人的身份证号就可以称为一个哈希，通过一个身份证号，可以定位到某一个人的信息。一个人的名字，也可以用作哈希，不过这个可能会产生重复，因为有很多人重名，这样导致的问题就是，通过名字，可能定位到多个人的信息，这种情况叫做哈希碰撞。 哈希表(Hash Table) 哈希表是一种存储结构，也称为散列表，是一种 Key-Value 的存储结构。通过 Key 可以直接访问在内存存储位置的数据(Value)。例如 C# 中的 Dictionary 数据结构就是一种哈希表，还有一些编程语言中的 Tuple，也可以用哈希表实现。 哈希函数/散列函数 哈希函数也可以称为散列函数，是在哈希表内部，用于将我们之前提到的 Key，转为哈希表用于直接访问数据的索引。 哈希表的实现 在哈希表的内部，可以用数组来存储数据，当我们添加一个 Key-Vale 时，首先会使用哈希函数将 Key 转换成索引，然后将 Value 存储在数组中，而位置就是刚才计算出来的索引。哈希表通常有一个默认容量大小，而哈希函数计算出来的索引，通常会和当前的哈希表容量进行取模计算，然后得到最终的索引，这样能保证不管计算出来的索引有多大，永远不会超界。而当哈希表快要满时，则会进行自动扩容，通常扩为当前容量的2倍，而扩容后，当前哈希表中的所有数据，会重新计算位置。 举一个例子，假设当前哈希表的容量为 10，我们要将 jack 作为 Key 存放在哈希表中，那索引是什么呢。我们这里使用一个简单哈希函数将Jack转为数据，使用每一个字母的Ascii值之和，也就是 106 + 97 + 99 + 107，最后的结果是 409，然后用 409 % 10，也就是对当前的容量取模，最后得到的索引就是 9，所以数据最终放在数据中索引为9的位置。 而从哈希表中取数据，也是通过Key来取的，内部也是先把Key计算成索引，然后取数据。 有时，哈希表部分结构也会使用树的形式来存储数据，也有可能在不同容量时，线性存储和树形存储会互相转换 哈希碰撞 哈希函数在计算索引时，有时候同一个 Key 得到的索引是一样的，这种情况称为哈希碰撞，通常的解决方案是，哈希表内部的数组不直接存储数据，而是存储一个数据的指针，当有碰撞时，会以链表的形式将数据挂到索引所对应的数据指针上，这种处理碰撞的方法，也叫做拉链法。看一下下面的图，就会很容易明白。 总结 哈希表的实现要考虑很多情况，例如哈希函数是否均匀、处理冲突的方法、哈希表的载荷因子等等，这些细节直接决定了哈希表增删改查数据的效率。通常情况下我们直接使用编程语言已经实现好的哈希表结构即可，没有必要自己实现。 更多资料 维基百科 哈希表 Hashing data structure

今天我们要实现的东西，就是下面这个动图的效果。使用代码控制方块的坐标，来展示 Sin 函数。方块的颜色变化，是随着坐标变化而动态改变的，我们会写一个超简单的 Shader 来实现。 ...

这是 Unity 基础系列教程的第一篇博客。我们将由浅入深，一步一步学习Unity及游戏开发相关的东西。整个系列教程所使用的Unity版本为 2018.4 及以上就可以，如果要使用特殊版本，则会在文中指出。 今天要做的是一个能够实时显示当前时间的时钟，就是下面这个东东。 1 首先建立一个新工程 首先打开Unity，创建一个新工程，名字自己定，例如 Clock 就可以。默认打开后，Unity 默认布局是下面图的样子。 你也可以更新布局，例如换成同时显示View和Game视图的布局，只需要点击编辑器最右上角的那个按钮，然后选择 2 by 3 即可成为下面图的样子。 下面是分辨率的设置，一般游戏开发中，会使用一个基准分辨率，很多游戏采用的是 16:9 的模式。这个在 Game 视图中设置，看下面的图，选择 16:9 即可 1.1 创建一个 GameObject 默认的场景中，会包含两个 GameObject，一个是主相机 MainCamera， 一个是灯光 Directional Light。这两个东西保持默认就好，现在我们创建一个新的物体，在 Hierarchy 面板右键，然后 Create Empty，或者通过菜单栏 GameObject/Create Empty都可以，这样就会在Hierarchy 面板上看到我们新建的物体，然后对这个物体重命名为 Clock，并且把它的位置置为 (0,0,0)。看下面的图 1.2 创建时钟的表盘 创建表盘，我们使用 Unity 默认的物体 Cylinder，然后改变它的大小，使其成为我们的表盘。首先，通过右键 Hierarchy 空白处，或者通过菜单栏 GameObject 中的 3D Object/Cylinder 选项，来创建一个 Cylinder，就是一个圆柱体。 Cylinder 默认已经有了很多组件，Mesh Filter、Capsule Collider、MeshRenderer。默认我们不需要物理模拟方面的东西，所以我们先把 Capsule Collider 这个碰撞器给删掉，通过右键这个组件，Remove Component 即可。 然后我们改变园柱体的大小，因为表盘是一个圆盘形状的东西，所以我们把圆柱体压平，也就是改变y轴的大小始可。把圆柱体 Scale 设置为 (10, 0.1, 10)，如下图。...

今天我们来说一下二叉堆(BinaryHeap)。堆是很有用的数据结构，例如后面会学到的优先队列，堆排序等，都和堆有关。操作系统中很多调度，也和堆有关。 还记得我们之前学过的完全二叉树吗？如果不记得了，就需要先回去复习一下，因为二叉堆，首先是一棵完全二叉树，或者近似完全二叉树。 再来说一下二叉堆的特性。二叉堆分为最小堆和最大堆。如果是最小堆，那么父节点的值，总是小于或等于任何一个子节点的值，通俗点就是把一棵树从上往下看，值在变大，下面的大于等于上面的。如果是最大堆，则是反过来，父节点的值，总是大于或等于任何一个子节点的值。 如果要简单点记忆，那就是这棵树上的值按层来看，如果是从小到大，那就是最小堆，如果是从大到小，那就是最大堆。 接下来我们就开始说二叉堆的细节，插入节点，删除节点。 插入节点 插入节点，其实也就是构建二叉堆的过程，语言描述流程如下。 找到要插入的位置，这个位置就是当前这棵完全二叉树，最后一个位置 (不太好理解)。如果用代码流程来描述的话，就是按层遍历当前的树，如果遇到一个节点，左子树为空，或者又子树为空，或者左右子树都为空，那么，这个点就是要插入节点的父节点，而要插入的节点，将作为这个节点的左子树或右子树。看下面的图 假设我们要在上面的堆中插入一个节点，按照上面代码流程中描述的，可以找到要插入节点的父节点，是11。 找到了要插入节点的父节点，还要判断这个父节点是左子树为空，还是右子树为空，还是都为空，如果左子树为空，则新点作为左子树，如果左子树不为空，则新点作为右子树。插入后的图如下(假设要插入的数值为3) 节点插入后，当前的树并不满足二叉堆的规则，所以还需要将新插入的点向上浮动。如果当前节点值小于父节点的值，则交换当前节点和父节点的值。然后再次判断，直到当前值不再小于父节点值，或者父节点值为空了，则位置调整完毕，整个插入流程也就结束了。看下面的流程图 上图中，首先用 3 和 11 比较，因为 3 小于 11，所以交换两个节点的值 上图中，再次用 3 和父节点 5 比较，因为 3 小于 5，所以再次交换两个节点的值 上图中，再次用 3 和父节点 1 比较，咦，3 不小于 1，所以不交换，节点调整结束。此时的树满足二叉堆的规则。 以上就是整个插入节点的流程，下面我们用代码去实现一下。代码中的 TreeAlgo 类是我们为了方便写的一个帮助类，实现了层序打印和查找的一些方法。 // 定义节点的结构 public class Node { public int data; public Node parent = null; public Node left = null; public Node right = null; public Node(int data){ this.data = data; } } // 定义二叉堆操作类 using System; public class BinaryHeap { public Node root; public void Insert(int data){ Node lastParentNode = TreeAlgo....

洗牌(随机)算法有很多应用，例如我们平时用的音乐播放器随机播放，棋牌游戏中的洗牌，扫雷游戏中雷的位置随机等等，都会用到洗牌算法。 今天来介绍一个简单，公平，时间复杂度为O(n)的洗牌算法。什么是洗牌算法呢？其实就是将一些数据以公平随机的方式打乱顺序。这个算法，是由Knuth(高纳德)，也就是计算机程序设计艺术的作者发明的。下面我们直接进入正题。 假设有这样一个数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，我们使用Knuth-Shuffle算法将数据打乱。基本流程是这样的，从最后一个数开始，往前遍历，每一次，从当前数和第1个数之间，随机选择一个数，与当前数字进行交换（这里的随机选择就直接使用程序语言中的Random随机一个索引即可）。 例如上面的数组，第一次循环，当前数字为10，我们从1~10之间，随机选择一个数，与10交换，这样第9个索引位就算洗完了，接下来就是第8个索引位，也就是数字为9，我们从第1个索引位与第8个索引位之间，选择一个数，第9交换，这样第8个索引位也就洗完了…。这个算法之所以公平，是因为保证了每一个元素出现在每一个位置上的概率，都是一样的。 代码实现 using System; using System.Collections.Generic; class Program { static void Main(string[] args) { List<int> songList = new List<int>(); songList.Add(1); songList.Add(2); songList.Add(3); songList.Add(4); songList.Add(5); songList.Add(6); songList.Add(7); songList.Add(8); songList.Add(9); songList.Add(10); Random rand = new Random(); // 开始洗牌算法 int last = songList.Count - 1; for (int i = last; i >= 0; --i) { // 从当0~当前索引位之间，选择一个数 int selection = rand....

二叉查找树（Binary Search Tree），简写BST，是满足某些条件的特殊二叉树。任何一个节点的左子树上的点，都必须小于当前节点。任何一个节点的右子树上的点，都必须大于当前节点。任何一棵子树，也都满足上面两个条件。另外二叉查找树中，是不存在重复节点的。 上图中的二叉查找树，我们从Root节点3开始看，它的左子树（1，2） 和右子树（6，4，9，7）分别满足条件，左子树上的点，都小于当前节点，右子树上的点，都大于当前节点。 继续，我们以6作为起点，来看一下这棵子树，6的左子树（4），右子树（9，7）也满足上面两条规则。 整棵树中，任何一个点下面的子树，都满足上面提到的两条规则。你现在是不是对Binary Search Tree已经有一个大概的形象概念了。 为什么叫做 Binary Search Tree呢？ 因为在BST中搜索一个值是非常简单和高效的。 看上面的树，假设要搜索7这个节点。首先从Root节点出发，我们知道7大于3，所以会走到右子树6，然后因为7也大于6，所以会继续往右子树走，到了9，因为7小于9，所以会向左子树走，走到7，发现7等于7，所以找到要搜索的节点。 二叉树的一些性质 将任何一个点看作Root节点，则这个点的左子树也是 Binary Search Tree 将任何一个点看作Root节点，则这个点的右子树也是 Binary Search Tree Binary Search Tree中的最小节点，一定是整棵树中最左下的叶子节点(从Root开始一直顺着左子树往下走，直到某一个点没有左子节点，则这个点就是最小的) Binary Search Tree中的最大节点，一定是整棵树中最右下的叶子节点(从Root开始一直顺着右子树往下走，直到某一个点没有右子节点，则这个点就是最大的) 怎样构建和插入节点 向BST中插入一个节点，也是一个构建的过程，和上面的搜索思路基本一样。首先从Root开始，如果Root点为空，则直接构建Root点。如果Root点不为空，则要判断要插入的值，比Root点的值大还是小，如果小，则往左子树走，如果大，则往右子树走。直到走到某一个点，我们称为点X，发现要插入的值，小于那个点X的值，并且点X没有左子树，则要插入的点作为X的左子节点。或者，要插入的点大于X，并且X没有右子树，则要插入的点作为X的右子节点。 下面是代码实现（为了方便后面的删除逻辑，我们每一个点，包含了指向左子树，右子树，以及父节点的引用） // 这里先定义出节点的结构 class Node { public int data; public Node parent; public Node left; public Node right; public Node(int _data) { this.data = _data; } } // 定义二叉搜索树结构 class BST { private Node root; // 这个函数是 private 的，递归调用，插入节点 private Node RecursionInsert(Node node, int data) { if (node == null) { return new Node(data); } if (data < node....