Hello World
Spiga

归档:2013年01月

真是O(1)吗?想清楚了没?

2013-01-18 11:21 by 老赵, 13013 visits
摘要:话说写程序的时候我们会用到各种数据结构,但十有八九不会由我们自己从头写起,都会直接拿来用。于是很多人就会记住,譬如HashMap或Dictionary的存取是O(1)的操作,二分查找什么的则是O(log(N))。不过,我们在实践中直接把这些类拿来用的时候,最好也留个心眼,知道这些类内部到底做了些什么,为什么它们能够达到O(1)之类的时间复杂度。我们在了解“理论”的同时也需要注意实践上的细节,例如,其实在实践中O(log(N))其实也是个不比O(1)大多少的时间复杂度,此时可能也需要考虑下“常数”会对性能造成多大影响。 阅读全文

一个最基本的HashedLinkedList

2013-01-07 23:52 by 老赵, 3425 visits
摘要:Tmc的初衷是补充一些常用的数据结构,例如对null作为字典键的支持,以及带有一个额外Remove方法的HashDictionary。但是,其实我创建Tmc项目的“初衷”却是HashedLinkedList。.NET BCL中已经有一个LinkedList,这是一个双向链表。说起来,我之前在面试中经常会提出一系列数据结构的基础问题,其中便包含LinkedList,我会问各个操作的时间复杂度,以及如何改进它们。例如,如何将它的Remove操作优化成O(1)的时间复杂度?最容易想到的做法便是使用一个字典来记录元素到特定LinkedListNode的映射关系。这种模式实在过于常见,所以便有了个特别的名称,叫做HashedLinkedList。 阅读全文

阅读.NET源代码那些事

2013-01-06 16:32 by 老赵, 16822 visits
摘要:谁都知道.NET(的大部分组件)是不开源的,但是我不止在一个场合不止一次地强调过,“不开源”不代表你没法看代码,不代表你没法知道里面发生了什么。这里我不是在说.NET Reflector或是ILSpy这类反编译工具,当然它们在平时开发中也起到了很大的作用,不过很多时候更直接的方式便是阅读代码本身,尤其是当你像我一样时不时要“抄”点代码的时候。由于最近我在Tmc中“大张旗鼓”地使用.NET中BCL的代码,因此也再次强调一下这部分经验。 阅读全文
1
使用Live Messenger联系我