May 25, 2022
原理 # 跳表作为一个没有被正规教材收录的数据结构，在工业场景下的用途非常广泛，常常用来媲美红黑树等一系列平衡二叉查找树。其核心的原理是通过多级索引层层二分构建一个支持二分查找的有序链表。
有序链表无法进行二分查找的原因在于无法随机访问，一个完美的跳表应该类似一个平衡二叉树的模样。
我们通过间隔一个选一个点复制出来，构成一个一级索引，针对一级索引链表，再通过间隔一个的方式构建二级索引，以此类推，最多$$log_2 n$$层就可以只剩两个点，这就是一个极其类似平衡二叉查找树的结构。查询的复杂度必然也是$$$log_2 n$$$。
但是上述的结构在insert和delete的时候动态调整的代价非常大，甚至无法通过log级别的复杂度完成。因此在实现的时候，并没有按照这个完美的结构来实现。而是采用了一个随机化抽点的方式来构建索引。事实验证的效率是令人满意的。
顺带提一下空间复杂度，虽然复制了一些点，但是依然是$O(n)$的复杂度，计算方式非常简单。并且索引部分并不需要记录完整的数据，只需要记录用于比较大小的score即可，因此索引与数据节点之间的空间比起来微不足道了。
实现原理 # 我们定义最底层的链表是原始的有序链表，向上一层为一级索引，再上一层为二级索引，以此类推。
我们基于完美形态的跳表可以发现，一级索引的点数为$n$， 二级索引点数为$n/2$, 三级索引的点数为$n/4$, 换个角度来看，一个点出现在一级索引中的概率是1， 出现在二级索引中的概率是1/2， 出现在三级索引中的概率是1/4。因此在插入数据的时候，我们只要按照概率分布，随机出这个点需要出现在哪几级索引中，然后按照索引层去查找和插入即可。
如何随机出一个点需要被插入的索引层？直接看代码：
// 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ： // 1/2 的概率返回 1 // 1/4 的概率返回 2 // 1/8 的概率返回 3 以此类推 private int randomLevel() { int level = 1; // 当 level < MAX_LEVEL，且随机数小于设定的晋升概率时，level + 1 while (Math.random() < 0.5 && level < MAX_LEVEL) level += 1; return level; } 代码的逻辑非常简单：
...
May 19, 2017
从开发这个Online Judge开始到现在，我自己收获颇多。有的时候是为了这个项目去学了很多东西，有的时候是学了其他的东西刚好就用在了这个项目上。一个良性的过程就是这样，有的是目的去做，有的是无心为之，但总会带来新的峰回路转，柳暗花明。从最开始的稚嫩，连MVC的概念都不清晰，就开始写，一点点实现，写的很丑，然后就写不下去了；后来学习了Java 的MVC， 然后又偶然看到了Php的MVC，然后就开始写自己的框架，有了Husky，然后就把OJ用框架进行重构。写了一段时间后，写到了后台的判题核心，一部分是自己闭门造车，一部分借鉴了网上的思路，但是实现起来总是那么别扭，说不上的不放心。刚好在这样的情况下，又看到了一些实现的细节，有了新的思路。意识到自己的技术实力贸然开发是很不成熟的，但是，没有关系，本来就是这样，它成功了是我的成功，他不成功也不会失败，是我增长经验最重要的一次经历，我借此机会学习到了很多知识和经验。但是我一定是对此有很大的信心和决心，要做好，并且要做的更优秀，虽然可能会花费比较长的时间。
写这篇博客的时候，此时我坐在理工楼三楼的悬空阳台上吹着风，听着手机的歌，塞着耳机，桌子是暗红色，很沉稳；一字排开手机、电脑、鼠标。很少会动鼠标，更少动手机，很简洁也很舒服，优美又惬意的工作环境。
下午的时候，突然大脑进入了很奇怪的状态，突然想不起来刚刚要做什么，跑出去打了一个多小时的球，然后回来去洗澡，车忘了骑回来，裤子也被打出一条口子，整个人的状态就不对。可能最近一直都是满载运行，所以需要休息一下，然后就过来写博客了。
写这篇博客干什么呢？ 为了更好的出发。
意识到自己在C++的操作系统部分的薄弱，所以下一步就是要开始学习，以OJ的判题核心为基础，一个一个的学习下来。学习的过程与开发过程是完全不一样的，因为学习是很卡顿的过程，总是不懂，然后查，然后想，记下来。所以带着开发的节奏来学习就不行，开发的时候要一气呵成，行云流水的代码一行一行的开始码，思路很清晰，然后单元测试，几个修改，结束。就像是一切都准备好后开始做菜，一步一步几分钟就出锅了。学习的过程就不一样了，要看，要记下来，更主要的是，要实践，甚至是各种情况都要试验一下，才能熟练的掌握用法，处变不惊。
所以这篇博客就是自己跟自己谈谈心，调整一下装态和心态。同时也规划一下学习的路线。
路线： # C++中的系统进程、内存、CPU时间相关的函数用法。 C++编译器的参数使用。 C++头文件使用。 C++机器相关的常量与不同机器之间的区别。 以上是第一部分，另外就是关于如何在服务器上开设一个独立服务，监听端口。还有消息队列怎么在PHP和OJCore之间传递。 一点一点来，应该会需要1周左右的时间。
明天是5.20，此时的我毫无想法。其实大家都差不多，看谁能得偿所愿吧。或许再过一段时间，都明白了是怎么一回事，就再也不会这么傻了，那个时候就挺可笑的了。
有些事情，只有一次机会，错过了，就变成了另一种，虽然表面一样，但是实质已经不同。
Glade to see you.