Web Analytics
yangyang

码农兼一个普普通通小青年

Data Structures and Algorithms


.NET常用数据结构及复杂度

在.NET中的基础类库(Basic Class Liberary,BCL)中有一些基本的数据类型比如Stack、List、Dictionary、LinkList等等,这些类型虽然看上去五花八门,但是其内部的实现所使用的数据结构无外乎是那些经典的结构比如数组、链表、哈希表、树等。了解这些类型背后的结构就能很清楚的知道对应数据类型的插入、查找、删除的时间和空间复杂度。在应用开发中可以根据具体的使用场景,选择合适的、高效的数据结构可以提高应用程序的效率。本文试图通过源码来查看这些基本类型的内部实现方式。 …

Priority Queue quaternary min-heap

使用treemap图来显示沪深300指数热点图

前几天看到一篇新闻里做的下面这张股票热点图,单纯的觉得这个图很好看,于是研究了一下如何自己绘制这个图,后来发现这种类型的图还有个专有的名字,叫treemap图。本文先介绍什么是treemap图,然后展示如何使用C#来生成沪深300指数的treemap。 …

treemap HS300 squarified

DataGridView绑定到DataTable和BindingList的分析与比较

本文介绍了使用DataGridView绑定数据的两种方法,一种是直接将其DataSource属性绑定到DataTable的DefaultView,绑定后它默认支持排序,筛选等高级功能,另外当DataTable值发生变化时DataGridView也会自动刷新,它的缺点是DataTable结构过于重,而且对于单元格赋相同的值时,仍然会触发事件导致界面刷新,这在有些场景下会影响效率。另外一种方法是DataGridView绑定BindingList实体,它的有点是能够进行更多的精细控制,并且效率会更高,缺点是内置的BindingList对象并没有实现排序,筛选等功能。针对BindingList的缺点,本文介绍了BindingListView这个第三方的库,它完美解决了BindingList默认不支持排序和筛选,且要实现筛选筛选功能单一的问题。 …

DataTable DataGridView BindingList BindingListView DataBinding

一种实时监控日志文件变更并读取变更内容的方法

本文介绍了一种监控日志文件变化,并读取变动内容的方法。通过使用FileSystemWatcher类,可以监控文件变化,并通过回调事件触发通知。为了避免文件频繁变动导致频繁的文件读写,这里使用了一个定时器来定时读取。当文件距离上一次读取发生变化时就读取。在读取文件的时候,由于涉及到多进程读写同一个文件,所以这里创建了FileStream并通过指定FileShare参数,而不是直接创建StreamReader来解决了读写冲突导致日志文件丢失的问题。在解决这一问题的过程中,还分析了long4net源码中RollingFileAppender写入文件时的FileShare参数以及StreamReader源码中,如果直接指定path时FileStream的参数。 …

RollingFileAppender log4net FileShare FileSystemWatcher

Aho-Corasick多模式匹配算法

aho-corasick-automation简称AC自动机算法,它是一个经典的多模式匹配算法,它借鉴了KMP算法的思想,可以由有限状态机来表示。具体实现中可以通过构建状态转移函数,失配函数,结果输出函数来实现。用于匹配的FSA跟输入的字符串无关,只跟模式串有关。匹配中如果发生失败,则FSA回退到某一状态,而输入的字符串则无须回退,从而能够实现通过一次遍历给定的字符串来查找所有的关键字匹配。 …

aho-corasick pattern-match automation kmp

从Dictionary中key为大小写不敏感的字符串类型说起

本文由一个在Dictionary中使用String作为key,且支持大小写不敏感匹配的例子来说明Dictionary的内部原理。由Key获取hash值是Dictionary实现的关键。在Dictionary声明的时候,可以通过构造函数传递IEqualityComparer参数来指定比较器,通过该对象来获取哈希值。如果不提供这个参数,则会在内部判断Key是否实现了IEquatable泛型接口,如果提供了,则使用该泛型接口中定义的GetHashCode来获取哈希值,否则会根据Key的类型生成一个通用的EqualityComparer,这个通过的EqualityComparer的参数是object类型,所以如果Key的类型为结构体,则必须为其实现IEquatable泛型接口,否则就会产生装箱从而严重影响性能。 …

Dictionary Hash StringComparer IEquatable IEqualityComparer

.NET中几种名字包含Dictionary的数据结构

在.NET Core的源代码中,除了常用的Dictionary、ConcurrentDictionary之外,还有几种名称包含Dictionary的数据结构,它们是ListDictionary、OrderedDictionary、SortedDictionary、HybirdDictionary和StringDictionary。这些个杂牌Dictionary用得很少,不看源代码可能还不知道😂。表面上看,好像都是Dictionary,但研究发现其内部实现却大不相同。 …

ListDictionary OrderedDictionary SortedDictionary HybridDictionary

.NET Core中Dictionary的实现

Dictionary是一种存储键值对的数据结构,可以根据Key快速查找对应的Value,它的内部实现原理其实很简单,在浅谈算法和数据结构: 十一 哈希表这篇文章中有详细介绍,但实际的原理和工程实现可能有所不同,在.NET中有.NET Framework和.NET Core的两个版本,大体相同,但细节上有所区别。这里以.NET Core中的Dictionary源码为例,来说明Dictionary的实现细节。 …

Hashtable Dictionary

从C++中的迭代器说到左闭合区间

和C#中的IEnumerable接口类似,在C++中,遍历标准容器库比如vector、deque、list等,都需要用到迭代器对象(iterator),根据容器的类型不同以及访问时是否需要读写,迭代器也分为可读写迭代器iterator,只读迭代器const_iterator以及反向迭代器reverse_itertaor。 调用容器类型成员的begin和end方法(或者cbegin,cend,rbegin,rend)方法,这两个方法分别返回指向容器首元素,以及尾元素之后的位置(one past the last element),简称尾后的迭代器。 这里面有一个容易误解的地方在于,end方法返回的迭代器,从来都不会指向容器的最后一个元素,而是指向最后一个元素之后的元素。如果容器v的第一个和最后一个元素分别记为first和last,那么调用v.begin()和v.end()返回的迭代器范围( …

iterator left-inclusive Dijkstra

布隆过滤器原理及应用

布隆过滤器(Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数,主要用于判断一个元素是否在一个集合中。与直接存储数据不同,布隆过滤器是通过一系列随机映射函数,将待存储的数据通过映射函数提取特征,然后将这些特征存储到二进制向量对应的二进制位上(类似于前文的Bitmap存储),当查找某个值时,通过随机映射函数,提取特征,然后检查这些特征所在的二进制位上是否都为1,如果都为1,表示该可能存在在集合中,但只要有一个为0,则一定不在集合中。 …

Bloom Filter Hash table collision