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; } 代码的逻辑非常简单：
...
September 23, 2017
从北京回来，决定花三天时间把这本书看掉。有两个原因，第一个是我希望主要精通的语言还是选择C++，因为其功能强大，且速度快；优秀的程序员就应该精通C++才可以。其次是在即将要学习的机器学习和深度学习的领域中，C++是后期算法工程化的重要一环。
如果是看完这本书，我觉得三天就够了。如果是精研每个细节就要花个一周了，我决定先快速的get到重点的内容，在接下来写代码的过程中再实践出来。
本书架构 # 这本书被冠以盛名，源自于其内容的独特性、优质性。 书中不是详细介绍C++的各种特性，而是从大量的工程经验中思考c++编写代码的优秀习惯。
本书全局来看，由55条准则构成。这55条准则被由浅入深的分成了8个模块，还有一个杂项模块作为第9个模块。 下面我就这些准则和书中的内容做个整理。
1. 让自己习惯C++ # View C++ as a federation of languages # C++ 今天已经是一个多重范型编程语言，同时支持过程形式、面向对象形式、函数形式、泛型形式、元编程形式的语言。 因此这是一个语言的联邦，几乎各种语言的编程模式都可以在C++中得到体现。 最主要的是，做到这些并且保持着速度。
Prefer const, enum, inline to #define # 主要就是讲了#define的种种缺点。 从我自身的使用上来说，简短的单文件程序中，使用define还是可以的，但是看别人的代码中就非常的困难了。因此我自己也是不倾向于使用define来定义一些东西。
常量： 对于常量我们可以使用const来定义，而不是使用define。这样不仅安全，而且编译后的代码更少。 define的一个比较严重的问题就是作用域的问题，其并不重视作用域，在编译的时候，对此后的内容均有效，除非遇到undefine。但是一个常量是可以有作用域的限制的。 除了使用const还可以用enum来定义一个常量，
class Game{ private: enum{ NumTurns=5 }; } 这样就定义了一个5的代名词，但是并不会被取到地址，也不会被改变。如果使用者企图调用这个的地址会在编译时就被报错，而不是像const那样在运行时报错出来。
函数 很多人会define一个小函数，来达到函数的作用又减小了函数调用的开销。但是这样写，一个是不直观，容易错；还有就是括号要很多，也容易出错。用inline是一样的效果。
Use const whenever possible # 关于const的语法的细节，可以参考之前的相关的内容。 使用const可以避免很多错误，与上面一样，这些错误很可能会发生在运行时。但是如果你适当的用了const，就会在编译的时候被避免。
CLASS a, b ,c; if( a*b = c) 内置类型会编译报错没有问题，但是对于自定义的类型，就会出现意想不到的错误。
确保使用的变量都被初始化了 # 这里有一个很有趣的东西，叫做冒号表达式，没错，就是那个冒号表达式。与一般的赋值初始化不同的是，冒号表达式更快速。
class A{ Som a, b; A(Som _a, Som _b){ a = _a; b = _b; } A(Som _a, Som _b):a(_a), b(_b){} } 对于第一种写法，需要先调用每个类的默认构造函数，随后进行复值。但是默认构造函数就浪费了。 对于第二种，直接调用其copy构造函数，所以更快。
...
August 17, 2017
既然学习了java的lamda表达式，当然要来顺便学习一下C++的实现。
lamda # C++11 有了对lamda表达式的支持。基本的形式有下面几种：
|—–| | [capture] ( params ) mutable exception attribute -> ret { body } | | [capture] ( params ) -> ret { body } | | [capture] ( params ) { body } | | [capture] { body } |
[capture]: 需要用到的外部变量 [a,&b] a变量以值的方式呗捕获，b以引用的方式被捕获。 [this] 以值的方式捕获 this 指针。 [&] 以引用的方式捕获所有的外部自动变量。 [=] 以值的方式捕获所有的外部自动变量。 [] 不捕获外部的任何变量。 [&, x] x显式地按值捕获. 其它变量按引用捕获 [=, &z] z按引用捕获. 其它变量按值捕获 (params): 函数的参数, 无参数括号可以省略。 mutable: 修饰符说明 lambda 表达式体内的代码可以修改被捕获的变量，并且可以访问被捕获对象的 non-const 方法。 exception: 说明 lambda 表达式是否抛出异常(noexcept)，以及抛出何种异常，类似于void f() throw(X, Y) attribute: 用来声明属性 几个例子：
...
July 29, 2017
快速傅立叶变换是离散傅立叶变换的加速版。 傅立叶的一个用途是用来计算多项式乘法。先讲一下多项式乘法。
多项式乘法 # 多项式有两种表示方法：
系数表示法 # $$A = a0 + a1x^1 + a2x^2 + … + anx^n$$
点值表示法 # A ={ (x1, y1), (x2, y2),...,(x3, y3) } 点值表示法相当与用点值来求得各项的系数，所以要准确表示一个多项式就必须至少与多项式未知数的数量一致才可以。
传统的系数表示法求多项式乘法的方式复杂度是O(n^2)。 如果使用点值来计算多项式乘法，就会有一些可优化的地方。首先两个n次多项式相乘得到的结果多项式有2n项，这个是确定的，也就是说要用点值表示法就要有2n个点。如何用点值表示法求多项式相乘呢？我们取点的时候就取x相同的点值，这样对应的y值相乘的结果就是结果多项式的y。所以我们在取两个多项是的点的时候就要取2n个点，然后得到2n个结果点。然后剩余的任务就是将这个点值表示法转换成系数表示法得到了我们要的多项式。这个由点值转换为系数的方式称之为插值。
但是这样的算法，在第一步的时候就崩溃了，因为求一个点的值就要至少O(n)， 我们要求2n×2个点复杂度就O(n^2)了。然后就需要一些数学手段。
秦九韶算法 # 这个算法的中心思想是通过选取特殊的点来简化计算，什么点是特殊的呢，用复数点。
介绍这个之前需要先复习一下复数。 高中数学的基础还是比大学的更有用。 复数的基本表示方法：z = x + yi。在复平面上的从原点到点(x,y)的向量是其对应的几何解释。 利用直角坐标与极坐标之间关系，复数还有一种三角表示：z = r(cosθ + isinθ)，θ代表极角，r是复数向量的模|z|=sqrt(x^2+y^2)。 另一种表示法是指数表示法，见下图. 然后有一个棣莫弗公式能够将两个复数相乘简化：
设两个复数（用三角形式表示）: z1 = r1(cosθ1 + isinθ1) z2 = r2(cosθ2 + isinθ2) 那么相乘的结果就是： z1*z2 = r1*r2[cos(θ1+θ2) + isin(θ1+θ2)] 这个过程很好证明，三角函数就可以了。 这个公式可以进行推广，数学归纳法，得到： z1*z2*...*zn = r1*r2*.
...
July 23, 2017
迭代器是一种对数据结构数据进行遍历的模式，也成为游标(Cursor)模式。这种模式为了适应各种被封装了的复杂数据结构的完全顺序遍历而设计。其设计思想依旧是封装的思想，屏蔽各种数据结构底层的存储差异，使用统一的方法来遍历所有的数据。
C++ # 先以C++中的迭代器的使用来说一下。举两个常用的容器的例子。
vector # 遍历、删除元素 # vector<int>::iterator it; for( it = A.begin(); it!=A.end(); it++){ cout << *it << endl; if(*it == 3){ A.erase(it); } } /* 上面这种写法是有问题的，当你删掉3这元素的时候，it再++，直接就到了5了，4就跳过去了。 因为erase后，后面的元素都会前移。 从这里我们可以看到，vector中的迭代器应该就是指针。 正确的写法如下： */ vector<int>::iterator it; for( it = A.begin(); it!=A.end(); it++){ cout << *it << endl; if(*it == 3){ vector<int>::iterator it_tmp = it; it--; A.erase(it_tmp); } } set # set<int>::iterator it; for(it = S.begin(); it!=S.end(); it++){ cout << *it << endl; if(*it == 3){ set<int>::iterator it_tmp=it; it--; S.
...
May 30, 2017
继续梳理C++中的问题， 今天梳理的是最基础的几个概念，也是比较麻烦的概念。
引用 # 引用是一个变量的别名，声明时必须初始化，而且之能在初始化的时候绑定一个变量对象。
引用不能绑定在引用上，因为引用本身不是对象。 普通引用不能绑定到立即数上，因为立即数不是对象，但是常量引用是可以的。 普通引用不能引用类型不同的对象。 以上的普通引用是相对于常量引用来说的，下面会介绍到。
指针 # 这个概念最简单，他不是是一种数据类型，他的数值是个地址，可以用解地址符*来直接操作指向的地址内的变量。
指针有下面四种状态:
指向一个对象; 指向紧邻对象的下一个位置； 空指针(nullptr, 避免使用NULL，nullptr可以被转为任意类型的指针); 其他指针装态(无意义的状态)； const 常量 # const 修饰的常量，默认是文件内有效，如果想在多文件内可用，就加extern修饰。
这个和其他的东西一结合就比较烦。
首先const是声明常量的作用，用其修饰的变量值必须初始化且不可更改。这就是普通常量了，很好理解。
const 引用 # 如果你声明了一个引用，并且这个引用是const修饰的，那么，你要知道两个事情：第一，引用不能绑定到其他变量了；第二，用这个引用不能改变做引用的对象的值了，但是不影响那个变量通过其他途径改变，改变后的值一样会在引用中表现出来。
如果你引用的对象是个常量，那么这个引用也必须是常量。反过来没有这个限制。
const 指针 # 指针这块又有两种，因为指针是可以改变其指向的对象的，并且其指向的对象也是可以更改的。就出现了指针常量(pointer to const) 和 常量指针(const pointer)。汉字理解起来没有英文来的准确，所以下面不用常量指针和指针常量来表述。
pointer to const 很明显是指向的对象是个常量，而指针不能够修改这个对象的值。
const pointer 很明显就是这个指针是个常量，只能指向这个固定的内存，但是可以通过其修改对象的值。
在定义上如下：
int a; // pointer to const const int *p1 = &a; // 等同于 int const *p = &a; // const pointer int *const p2 = &a; 所以可以看出来，const修饰的就是紧跟其后的内容，在pointer to const的定义中可以认为*p 指代指向的对象；而const pointer中const修饰的是p；
...
May 30, 2017
类的作用域 # 名称查找优先，对于编译器来说，优先寻找名称一致的函数，再关心类型的问题。
编译器在进行名称查找的顺序: 直接类定义 -> 父类定义 -> 祖宗类定义。但是，搜索顺序是按照静态类型开始的，结合上面的动态绑定，如果你的指针类型是父类，那么即使实体是个子类也不会在子类域中搜索，直接从父类开始搜索，因为编译阶段无法做动态绑定。
隐藏&重载&覆盖 # 这个概念刚开始学C++的人可能会比较迷。
隐藏 # 隐藏是在继承中出现的概念。基类与派生类有一个同名函数，则无论是否参数类型一致，基类的函数都会被隐藏掉。这个隐藏的意思，与Java中的override是否一致，我觉得不一致，但是效果一致。因为编译器在搜索名字的时候首先搜索派生类的函数，然后看参数，如果参数类型对的上就调用，对不上就报错。所以根本调用不到基类的函数，实现了隐藏。但是，C++中基类的函数还是存在的，Java中是直接将父类的函数段重写，父类的函数完全从代码段消失了。 既然还存在，就意味着可以访问。使用using关键字调用函数可以直接调用基类被隐藏的函数，可以说using改变了编译器名字查找的顺序。
对于虚函数，我们要求参数类型必须一致，就是这个原因。要实现动态绑定就必须使得当查找到函数名时，此函数可以被调用，而不是报个错说参数不一致。
这个规则是可以类推出来的，从命名上我们就可以窥探出这个东西有什么特质。
比如作为成员函数，就是可以被隐藏，无论是虚函数还是普通函数都是可以的。虚函数可以被普通函数隐藏，普通函数也可以被虚函数隐藏，其他一些概念一样可以用命名来推导出来。
重载 # 重载是对于函数来说的，与类间继承没有关系。对于一个普通函数，即不存在任何的类中的独立函数，重载的概念很清晰，就是相同的函数名，不同的参数列表；
对于成员函数来说，在同一个类中，可以重载，重载的概念也是一样的。
覆盖 # 覆盖与上面的东西又不一样，但是这个不是C++中的重点概念。覆盖是对于基类的虚函数来说的，派生类写一个名称、参数类型完全相同的函数，可以实现覆盖，其实就是虚函数的那一套东西。
只要分清楚，隐藏和覆盖是在父子间作用的，重载是同级内作用的就可以了。
那么有一个问题，很恶心，哈。 就是基类的虚函数被重载了，有很多个版本，子类在覆盖的时候，可以选择覆盖哪个版本。一样是使用using修饰符来将基类的函数作用域同步到当前作用域上来，这样只有对需要覆盖的版本进行覆盖就行了，其他的就使用基类的实现。
May 29, 2017
面向对象其实就是那样，都差不多，不一样就是关键字还有一些奇怪的机制问题，总的来说实现的东西都是一样的。
虚函数 # 对应Java的抽象函数。但是略有区别。 虚函数在定义的时候使用关键字virtual来修饰声明，但是不一定是没有实现的，可以指定一个已经是实现的函数为虚函数。虚函数最主要的定义是使得每个继承他的子类都实现自己的版本。并且虚函数是实现C++动态绑定的关键。 虚函数只能声明在类的内部。
动态绑定 # 所谓动态绑定就是，有些函数并不是在编译的时候就知道要去调用那个函数的，而是在真正运行的时候才能根据变量的类型去调用对应的函数。这个实现就是对于基类的虚函数，子类也实现一个版本（子类在实现的时候不需要指定函数为虚函数，因为继承过来的函数就是虚函数，是可以传递的），这样对于同一个函数就有两个版本，当我在调用的时候使用指针调用或引用调用（注意必须是这两种调用之一的方式才会有动态绑定的效果，其他都是在编译阶段就能够确定下来。）就可以实现动态绑定。
由于虚函数是在执行的时候才调用，所以在编译阶段就有些错误报不出来，比如如果我们没有实现某个子类的虚函数，在调用的时候就没有函数去执行，所以所有的虚函数都必须被定义，而不仅仅是声明，普通的函数只要我们永不到就可以不进行定义。
引用和指针调用 # 所谓引用和指针调用，是指函数中关于虚函数的调用对象是作为引用参数或者是指针参数传进去的，这样就需要根据参数的类型来调用不同版本的虚函数。这里就要说一下基类与派生类之间的类型转化问题，正是因为其二者可以进行类型转化，所以在参数列表中的类型并不能唯一限定参数的类型，才有了虚函数调用时的动态绑定。
类间类型转换 # 子类中有一部分是来自与基类的，这一部分可以被单独利用。也就是说，一个子类，我们也可以把他当作他的某个基类来使用，使用的时候只用到基类的部分。也就是说，我有一个基类的指针，我就可以指向这个子类，此时，指针就操作子类的基类部分。这就是从派生类到基类的类型转换。
反过来就是不行的，可想而知，多的东西可以不要，少了东西就会有问题，所以不存在从基类到派生类的转化。同时我们也就明白了，如果你要对于一个虚函数动态绑定，在调用函数的对象的类型声明的时候就要声明为基类的类型，这样当你传入一个子类的引用的时候，该引用就会转换为子类，进而去调用子类的虚函数实现；如果你写声明的时候声明为了子类的类型，就没有办法动态绑定了，因为反向没有办法转换。
虚函数覆盖 # 子类要实现自己的虚函数版本就要对基类的虚函数进行覆盖，override，又是这个熟悉的东西。覆盖当然就要参数类型完全一样，参数不一样的那是重载，是不同的函数。书上说，一般我们都是要进行覆盖而不是重载，但是有的时候我们会搞错参数列表的顺序等细节，所以，你可以在函数声明的参数列表后加override说明符来告诉编译器，你是要覆盖虚函数的，如果有细节错误就告诉我！
如果你在后面加上了final修饰符，就意味着，这个虚函数不希望再被覆盖了。
关于虚函数的默认参数，不同版本可能会有不同的默认参数值，但是在默认参数的选取上，是依据静态类型决定的，也就是说不能做到动态绑定，调用函数的对象定义成什么类型就用什么默认值。如你调用函数的对象是基类的引用，那么即使你最后执行的是子类的函数，默认值也是基类的默认值，所以这个就会出现隐蔽的问题。所以安全起见，默认参数一致最好。
猜想 # 同时从这里我们也可以窥探出编译器的原理。对于一个函数覆盖来说，函数的默认值必须是在编译阶段就写进机器码中的，尽管你有两个版本的函数，编译器会对两个函数分别编译，但是默认值存储的实现是与函数编译分开的。这里只是猜测，对于函数的默认值，其实编译器可以将其存储在对应的栈位置上，也可以将其转成一个赋值命令存储在函数代码段中，这两种理论上都可以实现默认参数的功能，但是从编译器的定义角度，参数是单独存放在数据段的，而不在代码段，那么在编译的时候就会根据你参数的字面类型进行设定，而无法进行动态绑定。这个应该是C++的一个设计缺陷，最初设计函数编译的时候没有动态一说，就直接写进数据段了，等到出现动态绑定的时候沿用之前的函数处理的方式，就无法实现绑定。（不知道这个思路对不对，以后有时间考证下）。
回避动态绑定 # 除了动态绑定，也可以用作用域操作符来强制执行某一类的虚函数版本。
double ans = C->Base::Update(); 为什么要回避动态绑定，这与类间设计有关。如果基类与派生类关于虚函数功能设定是：基类虚函数处理通用处理，派生类处理剩余子类相关内容，那么对于真的要完整实现功能的时候就要在派生类的虚函数中先调用一下基类的虚函数，再实现派生类的函数剩余部分，所以这时候就要回避动态绑定。
纯虚函数 # 你的直觉会告诉你这个纯虚函数应该是个只有声明没有定义的函数。没错，这就是纯虚函数，在格式上有一个特点，就是函数声明最后有一个=0标志。这个声明必须在类的内部，并且类内不能对这个函数进行定义，在类外部定义是可以的。
纯虚函数是在一些设计上必要的。比如我们有一个操作，有4个版本，每个版本根据不同的参数值有不同的动作，那么我们会设计一个基类，并在基类中声明这个函数，但是这个函数明显什么都不能做，而是要等到不同的子类根据自己的方案实现这个函数。所以这时候就声明一个纯虚函数就好了。
子类只要正常的覆盖这个函数就可以，如果不覆盖就继续往下传递。
抽象类 # 很熟悉，Java中含有抽象函数的类是抽象类，在这里有纯虚函数的类就是抽象类。并没有什么修饰符，就是个类。
继承中的友元 # 友元不可继承、不可传递。 派生类的友元不可访问基类中的非公有成员。