位运算符作用于整型对象，并把运算对象看作是二进制位的集合。位运算提供了检查和设置二进制位的功能。通常在编写代码中，相比加减乘除，位运算并不常用，但在有些情况下，位运算有用处。本文首先介绍为位运算的基本概念，然后介绍位运算的应用场景，包括使用Bitmap来存储整型数据，并介绍了在此基础上如何对大量不重复的整型数据进行快速排序，对大量整型数进行去重和快速查找，最后介绍了编程语言对Bitmap思想的实现，包括C++里面的bitset，C#里面的BitArray，并介绍了枚举值中使用位运算的一些例子。 …
当多个线程同时访问共享数据对象时，就需要线程同步，以保证数据状态不会被破坏。线程同步的通常做法是加“锁”，以保证某一时刻只有拥有这个锁的对象才能够去操作数据。加“锁”能够保证共享数据不会被破坏，但是它增加了代码的复杂性，并且有时候不容易测试和重现。另外“锁”增加了系统开销，会损害系统性能。本文介绍了C#中的基元用户模式构造和基元内核模式构造两类基本类型构造，并详细介绍了在C#中的实现。 …
股票的行情这种时序数据类型，数据冗余度和相似度较高，天然适合进行压缩。本文分析了几种无损压缩算法，分别是C#内置的和SharpZipLib的GZip、Zstd、LZ4以及Snappy。在对比这几种算法的压缩率，压缩时间后发现，Zstd具有比较好的压缩率和压缩速度，基本能满足行情数据处理以及传输效率的要求。 …
集合竞价是电子撮合交易中的重要撮合方式，通常用来在开盘或者收盘时产生开盘价或者收盘价，或者对于某些流动性差的产品，通过一段时间集中进行撮合，找出能产生最大成交量的价格的方式，（即市场大多数人认可的价格）防止价格被不小心操纵。 中国大陆市场中，由于人口众多，流动性几乎从不缺乏，所以从一开始就是采用把集合竞价生成开盘价和连续竞价高效撮合组合在一体的方式。具体上，沪深交易所都是以集合竞价来场开盘价和收盘价，在收盘价上，如果集合竞价不能产生收盘价，则采用最后一分钟加权平均价（上交所最开始的收盘价是使用的1分钟均价，后来改成了也采用集合竞价的方式产生）。本文对沪深交易所的开盘集合竞价算法作了简单论述和实现。 …
在前面的系列文章中，依次介绍了基于无序列表的顺序查找，基于有序数组的二分查找，平衡查找树，以及红黑树，下图是他们在平均以及最差情况下的时间复杂度： 可以看到在时间复杂度上，红黑树在平均情况下插入，查找以及删除上都达到了lgN的时间复杂度。 那么有没有查找效率更高的数据结构呢，答案就是本文接下来要介绍了散列表，也叫哈希表(Hash Table) 什么是哈希表 哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。 哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。 使用哈希查找有两个步骤: 使用哈希函数将被查找的键转换为数组的索引。在理想的情况 …
从这篇文章开始介绍图相关的算法，这也是Algorithms在线课程第二部分的第一次课程笔记。 图的应用很广泛，也有很多非常有用的算法，当然也有很多待解决的问题，根据性质，图可以分为无向图和有向图。本文先介绍无向图，后文再介绍有向图。 之所以要研究图，是因为图在生活中应用比较广泛： 无向图 图是若干个顶点(Vertices)和边(Edges)相互连接组成的。边仅由两个顶点连接，并且没有方向的图称为无向图。 在研究图之前，有一些定义需要明确，下图中表示了图的一些基本属性的含义，这里就不多说明。 图的API 表示 在研究图之前，我们需要选用适当的数据结构来表示图，有时候，我们常被我们的直觉欺骗,如下图，这两个其实是一样的，这其实也是一个研究问题，就是如何判断图的形态。 要用计算机处理图，我们可以抽象出以下的表示图的API： Graph的API的实现可以由多 …
前面讲解了平衡查找树中的2-3树以及其实现红黑树。2-3树种，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。 维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。” 定义 B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。 根节点至少有两个子节点 每个节点有M-1个key，并且以升序排列 位于M-1和M key的子节点的值位于M-1 和M key对 …
前面一篇文章介绍了2-3查找树，可以看到，2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgN，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，本文介绍一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。 正如在博客推荐里所说，本文以及这一系列文章大部分参考或者引用《Algorithms》第四版，国内已经有中文版《算法》第四版，推荐购买原版学习。这里只是我个人的读书笔记。 定义 红黑树的主要是想对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节 …
前面介绍了二叉查找树(Binary Search Tree)，他对于大多数情况下的查找和插入在效率上来说是没有问题的，但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率，要实现这一目标我们需要保证树在插入完成之后始终保持平衡状态，这就是平衡查找树(Balanced Search Tree)。在一棵具有N 个节点的树中，我们希望该树的高度能够维持在lgN左右，这样我们就能保证只需要lgN次比较操作就可以查找到想要的值。不幸的是，每次插入元素之后维持树的平衡状态太昂贵。所以这里会介绍一些新的数据结构来保证在最坏的情况下插入和查找效率都能保证在对数的时间复杂度内完成。本文首先介绍2-3查找树(2-3 Search Tree)，后面会在此基础上介绍红黑树和B树。 定义 和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。 …
前文介绍了符号表的两种实现，无序链表和有序数组，无序链表在插入的时候具有较高的灵活性，而有序数组在查找时具有较高的效率，本文介绍的二叉查找树(Binary Search Tree，BST)这一数据结构综合了以上两种数据结构的优点。 二叉查找树具有很高的灵活性，对其优化可以生成平衡二叉树，红黑树等高效的查找和插入数据结构，后文会一一介绍。 一 定义 二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3. 任意节点的左、右子树也分别为二叉查找树。 4. 没有键值相等的节点（no …