数组排序方法的性能比较（1）：注意事项及试验

2017年02月05日 59 阅读

数组排序方法的性能比较（1）：注意事项及试验2011-09-30 博客园 老赵昨天有朋友写了一篇文章，其中比较了List<T>的Sort方法与LINQ中排序方法的性能，而最终得 到的结果是“LINQ排序方法性能高于 List<T>.Sort方法”。这个结果不禁让我很疑惑。因为 List<T>.Sort方法是改变容器内部元素的顺序，而 LINQ排序后得到的是一个新的序列。假如两个 排序方法的算法完全...

数组排序方法的性能比较（2）：Array.Sort&lt;T&gt;实现分析

2017年02月05日 68 阅读

数组排序方法的性能比较（2）：Array.Sort<T>实现分析2011-09-30 博客园 Jeffrey Zhao昨天我们比较了Array.Sort<T>方法与LINQ排序的性能，知道了LINQ排序的性能以较大幅度落后 于Array.Sort<T>方法。而对于Array.Sort<T>来说，性能最高的是其中使用 Comparer<int>.Default作为比较器的重载方法。在前文的末尾我们做...

数组排序方法的性能比较（3）：LINQ排序实现分析

2017年02月05日 61 阅读

数组排序方法的性能比较（3）：LINQ排序实现分析2011-09-30 博客园 Jeffrey Zhao上次我们分析了Array.Sort<T>方法的实现方式，并了解到类库会为一些特例而使用高性能的排 序方式——int数组便是这样一例，因此从测试结果上来看其性能特别高。不过从数据上看，即便是在普 通的情况下，Array.Sort<T>的性能也比LINQ排序要高。不过也有朋友从测试中得出的结论正好相 反，这又是...

数组排序方法的性能比较（4）：LINQ方式的Array排序

2017年02月05日 56 阅读

数组排序方法的性能比较（4）：LINQ方式的Array排序2011-09-30 博客园 Jeffrey Zhao经过前两篇文章的分析，我们已经了解了Array.Sort<T>与LINQ排序两种实现方式的差别：前者 直接比较两个元素的大小，而后者先选出每个元素的“排序依据”再进行比较。因此，虽然后者需要相对 较多的“周边工作”，但由于每次比较时都可以仅仅使用高效的基础类型（如int），因此从整体来看...

数组排序方法的性能比较（5）：对象大小与排序性能

2017年02月05日 58 阅读

数组排序方法的性能比较（5）：对象大小与排序性能2011-09-30 博客园 Jeffrey Zhao在我公开测试结果之后，有朋友也进行了其他测试。在测试中我使用的是int数组，经过分析之后我们 了解到Array.Sort<T>对于int数组有特殊的优化。于是，某些朋友使用了一些引用类型的数组进行 排序，得到Array.Sort<T>方法的性能落后于LINQ排序——虽然由于测试方式的问题，这个结果和 结论都不...

谈表达式树的缓存（1）：引言

2017年02月05日 59 阅读

谈表达式树的缓存（1）：引言2011-09-30 博客园 Jeffrey Zhao表达式树（Expression Tree）是.NET 3.5中引入的一种表达方式。表达式树的运用十分广泛，可以直 观地表现出各种“数据”，甚至“逻辑”和“行为”。再者，表达式树是强类型的，因此合理地使用这个 新特性可以让代码编写变得优雅，方便。一个最简单而常见的例子便是，某些朋友目前就已经喜欢使用表 达式...

谈表达式树的缓存（2）：由表达式树生成字符串

2017年02月05日 54 阅读

谈表达式树的缓存（2）：由表达式树生成字符串2011-09-30 博客园 Jeffrey Zhao谈到使用表达式树作为key进行缓存，您脑海中最早浮现出来的解决方案是什么？老赵看来，大部分朋 友的第一反应自然就是将作为key的表达式树，使用一定规则生成一个字符串。简而言之，这个生成字符 串的规则F需要能够保证：在同一个缓存空间内，同样的表达式树能够生成相同的字符串。在同一个缓存空间内，不同的表达式树生成不同的字符串。似乎有些罗嗦，朋友们明白便是。其中&ld...

谈表达式树的缓存（3）：使用前缀树

2017年02月05日 70 阅读

谈表达式树的缓存（3）：使用前缀树2011-09-30 博客园 Jeffrey Zhao在上一篇文章里我们设法将前缀树构造为一个唯一的字符串，然后使用字符串作为key缓存在字典中。 这个想法非常直接，做法也不困难（在遍历时记录详细信息便可）。不过事实上，老赵在思考表达式树的 缓存问题时，这种字符串拼接的方式只存在于脑海当中，而上文的实现是为了这一系列文章的完整性而特 地编写的。这是因为它的缺点较为明显，正如上文所述，字符串拼接操作较为耗时耗资源，且很容易生...

谈表达式树的缓存（4）：使用二叉搜索树（AVL树）

2017年02月05日 64 阅读

谈表达式树的缓存（4）：使用二叉搜索树（AVL树）2011-09-30 博客园 Jeffrey Zhao上一篇文章中谈到的前缀树实现方式，时间复杂度从理论上来讲已经达到了最优，而空间复杂度理论 上也可以做到较优。但是理论和实际是有差别的，而对于上文前缀树的实现来说，这两方面并不是非常理 想：时间：前缀树时间复杂度为O（m）的前提是每次哈希表查找操作的时间复杂度为O（1），不过这个O（1）与 一次数值比较相比，从性能上来说还是有比较明显的差距。空间：前缀树空...

谈表达式树的缓存（5）：引入散列值

2017年02月05日 58 阅读

谈表达式树的缓存（5）：引入散列值2011-09-30 博客园 Jeffrey Zhao到目前为止，我们已经实现了三种缓存方式：首先我们设法构建唯一字符串，但是由于它的代价较高 ，于是我们使用了前缀树进行存储；又由于前缀树在实际操作中所花的时间和空间都有不令人满意之处， 我们又引入了二叉搜索树。那么二叉搜索树又有什么缺点呢？其实前文已经谈到过了，那就是从理论上来 说，它的时间复杂度相对前两个要高，在最坏情况下将会出现O（m * log（n））的时间复杂度&...

谈表达式树的缓存（6）：五种缓存方式的性能比较

2017年02月05日 62 阅读

谈表达式树的缓存（6）：五种缓存方式的性能比较2011-09-30 博客园 Jeffrey Zhao开始还债，因为还有至少两个可写的重要话题依赖在这个系列上，不解决就难以前进。目前我们已经涉及了五种不同的缓存实现，它们分别是：SimpleKeyCache：构造字符串作为Key，使用字典作为存储。PrefixTreeCache：使用前缀树进行存储。SortedListCache：使用排序列表或二叉搜索树进行存储。HashedListCache：先对表达式树取...

谈表达式树的缓存（7）：五种缓存方式的总体分析及改进方案

2017年02月05日 61 阅读

谈表达式树的缓存（7）：五种缓存方式的总体分析及改进方案2011-09-30 博客园 Jeffrey Zhao终于到了这个系列的最后一篇文章了，这个系列的文章本是许多话题的基础，却拖了那么长时间还没 有完结。这篇文章主要讨论五种缓存方式各自的优劣，以及他们的性能关键在什么地方，如果要进行改进 又有什么可选方案。在这个问题上，老赵的思考可能会有遗漏，如果您有任何补充，也请不吝指出。SimpleKeyCacheSimpleKeyCache是最直接的缓存方案：将...

通过编程解决《离散数学》“真值表”类问题

2017年02月05日 78 阅读

通过编程解决《离散数学》“真值表”类问题2011-09-30 博客园 邓勖帆问题引入：真值表是数理逻辑中较为常用的基本工具之一，但这东西若要人手计算还是有点麻烦，而 且必须非常仔细才行。现在我们通过编写程序解决这个问题。一、基本思路假定表达式中字母个数为n，那么一个最自然的想法就是让i:0->2^n（取其k:0~n-1位分别作为字母 k的赋值），将{^,&,|,->,<->}中的操作符从字符形式转换成Token存储在栈中，然...

通过分析JDK源代码研究TreeMap红黑树算法实现

2017年02月05日 67 阅读

通过分析JDK源代码研究TreeMap红黑树算法实现2011-09-30 IBM 李刚简介：TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员，其中 TreeMap 是 Map 接口的常用实现类，而 TreeSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范 不同，但 TreeSet 底层是通过 TreeMap 来实现的，因此二者的实现方式完全一样。而 Tr...

图像相似度算法的一点粗糙应用——GUI测试

2017年02月05日 53 阅读

图像相似度算法的一点粗糙应用——GUI测试2011-09-30 博客园 Aaron Wu因为一些私人的事情，本来早已经应该完成的一篇文章一直到今天才可以草草了结。在前面的两篇文 章《图像相似度算法的C#实现及测评》《对“画条线”（Draw a line）的单元测试几点想法和实践 》中 ，先后介绍了一个简单的会读直方图算法和一些关于GUI画图的测试想法。有必要说明的是，在《对“画 条线”（Draw a line...

微软的22道数据结构算法面试题

2017年02月05日 61 阅读

微软的22道数据结构算法面试题2011-09-30 博客园 1、反转一个链表。循环算法。1 List reverse（List l） {2 if（！l） return l;3 list cur = l.next;4 list pre = l;5 list tmp;6 pre.next = null;7 while （cur） {8 tmp=cur;9 c...

有监督下垂直搜索引擎排序算法的设计思路

2017年02月05日 60 阅读

有监督下垂直搜索引擎排序算法的设计思路2011-09-30 博客园 xiaotie本文是很久之前写的，刚才翻硬盘翻到了，现在放出来。这只是一个形式化思路，暂时没时间去实现 ，我简单验证过这个形式化过程，暂时还没发现问题，但不保证这个过程没有问题。如果您发现了问题， 还请指正，谢谢！垂直搜索领域目前没有通用的判断排序结果优劣的标准，为此引入监督者这一角色，希望设计算法， 使该算法对搜索引擎的排序结果尽量接近监督者的排序结果。引入1位专家作为监督者S。S选择关...

有限自动机与建模

2017年02月05日 57 阅读

有限自动机与建模2011-09-30 博客园 abruzzi前言在学校学程序设计语言的时候，能接触到的所有例子没有一个跟现实世界是有关系的。大 多是关注于语言的细节层次，根本没有模型的概念，而我认为，要真正的让别人理解模型是如何建立的， 最好的方法是从一个实实在在的东西开始，逐步的建立一个与物理世界可以有对应关系的模型出来。那样 ，在以后的实践中，可以很轻易的对未知的对象进行数学建模。OO最大的特点并非继承，多态等概念，而 是与物理世界建立对应的关系！选择...

预排序遍历树算法的图文解释

2017年02月05日 58 阅读

预排序遍历树算法的图文解释2011-09-30 博客园 老紫竹预排序遍历树算法：modified preorder tree traversal algorithm这个算法有如下几个数据结构1 lft 代表左 left2 rgt 代表右 right3 lvl 代表所在的层次 level下面这个图是一个典型的结构 我们先看一些使用方法1 查看整个树（A）有多少节点（包含自己）直接看根节点就行了 （right-left+1）/2 = （20-1+1）/2 = ...

子集和问题：一种组合生成算法

2017年02月05日 57 阅读

子集和问题：一种组合生成算法2011-09-30 博客园 JohnWaken今天在网上看见这么一道题目：给你m个数，从里面找出和为sum的n个数，问一共能找到多少组这样的 数。根据我的理解，这是一道组合生成的题目。令m个数组成的集合为M，就是要找到所有元素个数为n且和 为sum的子集。最笨的方法是生成所有的子集，然后进行验证，这样复杂度为阶乘。显然有一种改进的算法，在笨方 法中，我们连元素个数不为n的子集都生成了，而这显然是不必要的。这种改进想到很容易，但...