前面讲解了平衡查找树中的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个或者两个的值。 …
上文讲解了.NET中的采用Task可以实现任务的并行。除了任务的并行之外，还有数据的并行。和任务的并行不同，数据的并行是指并行的源头不是算法的代码，而是算法操作的数据的本身，TPL (Task Parallel Library)中提供了几个数据并行的API. 一 数据的并行 1.1 Parallel.For和Parallel.ForEach for 和foreach语句也适合进行并行化。实际上，随着并行计算的流行，对这种循环遍历进行并行化也有过很多种尝试。这些方法包括对在编程语言进行扩充等，比如C++里面的OpenMP标准。C#并行类库(Task Parallel Library, TPL)通过提供一些API实现了数据并行化功能，这就是Parallel.For和Parallel.ForEach方法，分别对应平常用到的for和foreach。 回到上文中的遍历数 …
一、引言 前天在GitHub上看到一幅图，问如何向五岁的小孩讲解并发和并行。然后有人以这幅图做答： 这幅图有点儿意思，用咖啡机的比喻来形容并发和并行，从中最直接的体会是，并发是有状态的，某一线程同时执行一个任务，完了才能进行到下一个，而并行是无状态的。 近些年，计算机的处理能力成指数能力增长。处理能力也越来越快，以前的一些工作站现在都可以移植到笔记本电脑或者手持设备上。但是近几年，由于处理器的处理速度已经达到了极限，所以处理器开始向多核方向发展，而提高程序性能的一个最简单的方式之一就是充分利用多核处理器的计算资源。但要编写利用多核处理器处理的程序并不那么简单。所以一些函数是编程语言，如F#，Scala，Erlang等又开始流行起来，因为他们带来的不可变性，递归思想等在一定程度上简化了并行和并发编程。 本文和下文从任务并行和数据并行两个方面，简要讨论 …
我们知道在.NET平台上有很多种数据存储，检索解决方案-ADO.NET Entity Framework，ASP.NET Dynamic Data，XML, NHibernate，LINQ to SQL 等等，但是由于一些原因，如平台限制，比如说必须基于.NET Framework2.0及以下平台；遗留的或者第三方数据接口采用的就是DataTable等等，仍然需要使用DataTable作为数据存储结构。另一方面DataTable比较容易使用，一些数据访问的接口可能直接采用了DataTable结构。在使用DataTable进行数据检索的时候，有一些需要注意的地方，这些地方会严重的影响对数据的检索效率。 本人最近工作中需要对大量的DataTable进行拼接。接口的数据是以DataSet然后里面放DataTable的方式提供的，暂不提是否合理，同时进行多个请求的时，服务端会返回 …
一 问题重现 前面在减少.NET内存占用的一则实践中，和大家分享了在.NET中使用P/Invoke技术来调用C++编写的非托管代码的例子。虽然性能和内存占用还不错，但是在随后而来的几周里，在某些同事的机器上总是偶尔会出现异常导致应用程序突然崩溃，尤其是在一些配置比较好的机器上。于是完善了一下日志记录，捕捉到最多的异常是: “Attempted to read or write protected memory. This is often an indication that other memory is corrupt.” 然后调试的时候无法跟进去，直接抛出如下的异常： 根据这个异常实在查找不出任何有意义的信息，不过结合这两者很明显的知道，问题出在调用的非托管的代码里面。 二 解决方法 根据之前提示的问题， …
最近一周比较忙，主要的工作内容是在做一个叫“键盘精灵”的东西，简单来讲就是将很多数据放到内存中，对这些数据进行快速检索，然后找出根据输入条件最匹配的10条记录并予以展示。具体和下面两款炒股软件的相关功能类似： 数据以文本形式存在文件中，且数据量较大，有近20万条，每一条记录有几个字段，以分隔符分割。当时使用的是6万条记录的测试数据，文本文件将近10M，这个模块加载到内存并建立缓存之后，大概会占用将近70-80M的内存。自我接手以后，主要的任务就是降低内存消耗和提高匹配效率。 一、避免创建不必要的对象 拿到代码后，第一步就是看设计文档，然后断点一步一步的看代码，大概明白了逻辑之后，发现思路有一些问题。之前的代码处理流程思路大概是下面这样的： 将文件读取到内存，实例化 根据条件对文件进行检索，并存储到结果集1中 对结果集 …
上一篇文章中简单讲了.NET中值类型和引用类型的区别，并分析了引用类型的内存布局和实现方式，并在开始的例子中简单分析了值类型相较于引用类型的若干优点。在平常的开发中，很多人一上来就用class，而很少去想到底该用class还是struct。本文详细介绍.NET中的值类型以及在使用中应该注意的问题。在某些情况下，使用值类型较引用类型可以显著减少内存占用和GC压力，提高程序的执行效率。本文参考《Pro .NET Performance》 《CLR Via C#》和 《Advanced .NET Debugging》，希望对您有帮助。 值类型内部实现 和引用类型相比，值类型具有相对简单的内存布局，但是这种简单的布局也引入了一些限制，尤其是在要将值类型“当做”引用类型使用的时候需要进行装箱操作。 上篇文章提到，使用值类型最主要的原因是：值类型具 …
前面我写过7篇文章粗略的介绍了一下Rx及其方方面面。Rx是一个好东西不然我也不会费这么大的力气来写这些东西。本文打算初略的讲一下传统异步编程方法的缺点，以及为啥Rx能够给异步编程带来新的体验。最后我听译了一篇关于Reactive Extension的非常好的一篇演讲，并制作了中英文字幕。希望大家看完这篇文章之后能够对Reactive Extension能够有比较深的印象，并在实际编程中遇到比较纠结的异步编程问题了能够想到Rx。 1. 传统异步编程存在的问题 异步编程比较困难，这一点老赵讲过很多次，在这里就我的理解有以下几点。 1.1 异步编程的方式太多，缺乏统一性 在.NET下面做异步编程其实有很多种选择的，如果基于事件的异步编程，经典的Begin/End异步方法对，以及针对以上两种存在的问题改进的CCR和AsyncEnumerator，还有F#中的异步工作流，以及C#5. …