Hello World
Spiga

一个最基本的HashedLinkedList

2013-01-07 23:52 by 老赵, 3429 visits

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

好吧,其实在C5中已经有了一个HashedLinkedList,但是有重大缺陷,例如没有暴露出LinkedListNode这个类型。我们来看下.NET BCL中LinkedList的一些方法:

public class LinkedListNode<T>
{
    public LinkedList<T> List { get; }
    public LinkedListNode<T> Next { get; }
    public LinkedListNode<T> Previous { get; }
    public T Value { get; set; }
}

public class LinkedList<T>
{
    public LinkedListNode<T> AddFirst(T value);
    public LinkedListNode<T> AddLast(T value);
    public LinkedListNode<T> AddBefore(LinkedListNode<T> node, T value);
    public LinkedListNode<T> AddAfter(LinkedListNode<T> node, T value);
    // ...
}

.NET BCL的LinkedList会暴露出配套的LinkedListNode,这样我们便可以保留LinkedListNode对象,并执行O(1)实现复杂度的快速插入。此外,我们还可以根据LinkedListNodeNextPrevious进行前后遍历,这才是真正的“链表”。之前有人问我,为什么LinkedList不实现IList接口呢?我的看法就是LinkedListList在表现上的区别实在太大,而IList的含义是后者,因此就放过LinkedList了。

其实,完全从外部实现一个HashedLinkedList(的部分功能)也不难,我们只要封装一个LinkedList和一个Dictionary即可。例如:

public class HashedLinkedList<T> {
    private readonly LinkedList<T> _list = new LinkedList<T>();
    private readonly Dictionary<T, LinkedListNode<T>> _nodes = new Dictionary<T, LinkedListNode<T>>();

    public LinkedListNode<T> AddLast(T value) {
        var node = _list.AddLast(value);
        _nodes.Add(value, node);

        return node;
    } 

    public void Remove(T value) {
        var node = _nodes[value];
        _nodes.Remove(value);
        _list.Remove(node);
    }
}

当然,这种“粗制滥造”的HashedLinkedList类完全不能作为通用的数据结构来使用,但假如是普通项目需要,这么做往往也够了。而且事实上一个“通用”的HashLinkedList的确也会遇到很多决策问题,例如:是否支持相同元素?我们知道.NET BCL中的LinkedList是支持相同元素的(事实上LinkedListNodeValue属性可读可写),但显然上面这个粗糙的HashedLinkedList便不支持。

有人可能会说,支持相同元素很容易呀,只要用Dictionary<T, List<LinkedListNode>>或类似的结构,将一个值映射到多个LinkedListNode就行了。这可能会解决一部分问题,但事情远没有那么简单。例如.NET BCL的LinkedList还有Find(T value)FindLast(T value)这两个方法,分别用来找出“第一个”和“最后一个”与value相等的LinkedListNode。没错,LinkedList是有顺序的,假如我们要保留FindFindLast的语义不变,就没法提供O(1)的时间复杂度的实现——不信你试试看?

假如我们还是用遍历的方法来实现FindFindLast,这便失去了HashedLinkedList的意义。但是反过来说,在很多时候,我们可以确定不需要其支持相同元素,或者无所谓Find得到的是其中的哪个节点呐。我估计这也是.NET BCL中不提供HashedLinkedList的缘故吧,既然没法“通用”,那么就由开发人员自己根据需要来组合吧。

目前在Tmc中的HashedLinkedList便不支持保存相同元素,它只是将.NET BCL的LinkedList几乎原封不动地复制过来,然后增加一些简单的功能。.NET BCL的LinkedList的实现为“双向循环链表”,不同于某些数据结构书上使用headtail来保存首尾节点,“双向循环列表”只需要记录头节点,而尾节点只需要简单的访问“头节点”的“前一个节点”即可:

private LinkedListNode<T> _head;

public LinkedListNode<T> Last
{
    get { return _head == null ? null : _head._prev; }
}

使用“双向循环列表”的好处在于实现特别简单,各种修改操作都能统一为三个方法:

private void InsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode);
private void InsertNodeToEmptyList(LinkedListNode<T> newNode);
private void RemoveNode(LinkedListNode<T> node);

因此,在此基础上实现的HashedLinkedList也只需要修改这三个方法即可,几乎是瞬间的事情。当然,假如只是这样的HashedLinkedList,我将其放入Tmc项目的意义也不大。因此,不久的将来我会删除这个类,并提供额外的数据结构来应对不同的需求:

  1. 不支持相同元素。
  2. 支持相同元素,但不保证顺序,效率比前者略低。
  3. 支持相同元素,并保证顺序,效率比前两者低,但肯定要高于.NET BCL中自带的LinkedList

这种数据结构(亦或是三种?),我就称之为IndexedLinkedList吧。假如是你,你会怎么做呢?

Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

26 条回复

  1. Eric
    125.95.19.*
    链接

    Eric 2013-01-08 10:48:49

    不知老赵还有没有关注F#?问个不相关的问题。

    我有个长期运行的程序的并行核心用F#的MailBox实现,但线上运行n天后出现丢消息的情况。通过日志打点,我已确认代码能运行到分发函数里的Agent.Post方法上,但是在agent body里没反应。在本机调试上又重现不出这个bug。我已经快要被这个幽灵bug搞疯了……

  2. 老赵
    admin
    链接

    老赵 2013-01-08 12:43:57

    @Eric

    关注但没怎么用了,需要MailboxProcessor的场景都用TPL Dataflow了。你说的问题没遇到过,多打印些日志出来?

  3. Eric
    125.95.19.*
    链接

    Eric 2013-01-08 13:24:15

    已经是一路打点过去了,100%确认是到了agent的body fn里没了踪迹。估计要用C#重写了,又不能用4.5,蛋疼。

  4. 老赵
    admin
    链接

    老赵 2013-01-08 13:40:55

    @Eric

    假如网上搜不到别人有这个问题的话,我还是倾向于认为是代码本身有问题。有没有源代码可以看看?可以一直跑跑跑跑出问题的那种示例代码。

  5. Eric
    113.71.110.*
    链接

    Eric 2013-01-08 21:35:49

    都是业务代码,很难弄出能跑的程序。浓缩一下,大概这样

    type Msg = 
        | BatchCheck
        | DomainObj of DomainObj
    let private agent = Agent<Msg>.Start(fun inbox ->
        let rec loop () = async {
        let! msg = inbox.Receive()
        log(...) // 当bug出现时, 这里不能跟之前的成对出现
        try
            match msg with
            | BatchCheck ->ac
                // 核对数据, 大约25s
            | DomainObj obj ->
                // 轮盘式发到worker agent里处理,再汇集到几个agent组成的并行管道
        with
        | ex ->
            log(...) // bug出现时没记录
        return! loop ()
        }
        loop () )
    agent.Error.Add(fun exn -> Log(...)) // 这里也没记录
    // 由主程序推送的数据流
    let HandleData(obj:DomainObj) =
        agent.Post(DomainObj obj)
    // 由主程序定时发过来的核对数据通知
    let BatchCheck() =
        log(...) // ok this runs
        agent.Post(BatchCheck) // 不知这里发生了什么
    

    即使完整的程序也很难重现bug。运行半年有多,这个bug只出现过2次,第二次通过打点确认不是外部资源问题,然后老大就不高兴了……

    其实就是管道模式,都没用到reply channel等高级货。用C#实现应该不难,只是写异步代码好麻烦啊。你介绍的TPL Dataflow貌似不错,有空看看。

  6. 链接

    子龙 2013-01-08 22:08:57

    @Eric

    有个歪招,你把程序集用ILSpy等工具反编译成c#代码,然后可以去分析一下问题

  7. 老赵
    admin
    链接

    老赵 2013-01-08 22:17:19

    @子龙

    没觉得这会有什么帮助,现在又不是看不懂F#代码……

  8. 链接

    子龙 2013-01-08 22:19:34

    说到F#,match语句很强大,但是一般有多个类型,通过类似switch..case 的这样结构去判断,不是说难以维护吗?这种风格不是被各种设计模式的书批得体无完肤吗?没在实际中用过F#,所以不是很懂,请老赵赐教

  9. 老赵
    admin
    链接

    老赵 2013-01-08 22:25:32

    @子龙

    模式匹配又不是switch...case,模式匹配类似于一种快速的结构选择,而不仅仅是逻辑分支。

  10. 链接

    子龙 2013-01-08 22:32:38

    如果以后增加了新的需要match的类型,应该也有类似的维护问题吧

  11. 老赵
    admin
    链接

    老赵 2013-01-08 22:48:18

    @子龙

    多写点代码体会下吧,不要把match和switch等同起来,match的东西不是一个一个枚举或者选项。

  12. boringame
    110.88.39.*
    链接

    boringame 2013-01-12 23:24:34

    HashedLinkedList的适用场合是那些呢? 组合LinkedList和Dictionary在空间上不占便宜, 时间效率也不如直接使用Dictionary。

    需要同时使用这2种集合特性的场合还真想不到。

  13. boringame
    110.88.39.*
    链接

    boringame 2013-01-12 23:28:37

    顺便提一下,最近你的博客在baidu搜索经常找不到。

  14. 老赵
    admin
    链接

    老赵 2013-01-13 01:07:54

    @boringame

    HashedLinkedList是个LinkedList,跟Dictionary有什么可以比效率的?完全不是一种东西。HashedLinkedList就是一个支持快速定位的LinkedList,比如各种既要快速插入删除又要保持顺序的场景。

    百度搜不到就搜不到吧,随它去。

  15. boringame
    122.90.72.*
    链接

    boringame 2013-01-15 03:01:51

    我的意思是,linked和hashed这2个特性很少需要结合使用吧。我想不到案例呢。

    对单纯LinkedList能否有更高的效率,我做了下面的实验。

    1.普通按照顺序查找。

    2.排序前提下,顺序查找,伪代码:

    if(list.Last.Value>value) return null;
    for (var node=list.first;node!=null;node=node.next){
        if(node.Last.Value==value)return node;
        if(node.Last.Value>value)return null;
    }
    

    3.排序前提下,模拟二分查找:

    记录最后一次比较的node,下一次 node.Next.Next.Next... 或者 node.Pre.Pre.Pre 的方式跳转到二分的索引位置。这样node的移动距离还是可以接受的。

    而后我对比了这些方法应对多种情况下的性能:

    1. 要找的值在集合中:普通查找和排序查找效率差不多,二分查找效率低。
    2. 值在最大和最小范围内,但是找不到:普通查找全表扫描了,顺序查找效率很理想,二分还过得去。
    3. 值不在范围内:普通查找和排序查找都全表扫描了,二分查找就表现的比较理想了。
    4. 还有对很多情况比较,包括值和引用类型、数据量大小等等,都基本都匹配上面的结果。

    虽然排序违背了linkedlist的通常用法,但是作为你面试题的回答应该不失为一种方式。

    同时还需要实现一个linkedList.sortInsert(value){ next = 排序查找(value); return linkedList.AddBefore(next,value) }

  16. 老赵
    admin
    链接

    老赵 2013-01-15 17:02:13

    @boringame

    拍脑袋想连LinkedList都很少用到,HashedLinkedList已经算是很常见了,所以连学名都有。

    排序前提下顺序查找还是O(N)的,数量多不合适。还有没看懂你说的LinkedList二分查找法,上代码吧。

  17. 链接

    Haart 2013-01-15 19:28:48

    @boringame

    链表 进行 二分查找 是毫无意义的。

  18. boringame
    120.32.109.*
    链接

    boringame 2013-01-16 03:30:19

    排序前提不能简单算成O(N),最多找到第一个大于的位置就停止了,有一个命中率的问题。 假设有学生编号{1,2,3,...,100},其中10个是特困生LinkedList{6,33,56,59,60...}。 现在需要一个查询程序,判断某个学生是否特困:

    非排序下执行情况:

    • 1号:10次比较(全表扫描)
    • 2号:10次
    • ...
    • 6号:1次(匹配到第一项)
    • 7号:10次
    • ...

    也就是对找不到的情况都要全表扫描。

    排序的:

    • 1号:1次(第一个数就大于了,得到结果=false)
    • 2号:1次
    • ...
    • 6号:1次(匹配成功的情况,和非排序一样)
    • 7号:2次(到33位置,能够确认不是)
    • ...

    排序前提下,对判定不存在表现的更好。(虽然有一些极端情况如特困生列表:{1,2,3,4,5,6,7,8,99},这种情况下,排序一点帮助都没有,但是通常概率很低)

    例如这个例子,我认为结合具体引用,排序前提有一定的意义。

    对LinkedList模拟二分查找,我也觉得太坑爹了,没什么意义。代码如下,是抄了Array.BinarySearch()改的:

    int BinarySearch(LinkedList items,int begin,int length){
        var begin = index;
        var end = begin + length - 1;
        var nodeIndex = begin;
        var node = NodeMove(items.First,nodeIndex);//相当于item=items[begin]
        while (begin <= end)
        {
            var cindex = begin + ((end - begin) >> 1);
            node = NodeMove(node,cindex-nodeIndex);//相当于item=items[cindex]
            nodeIndex = cindex;
            var citem = nodeIndex.Node.Value;
            var crs = comparer.Compare(citem, item);
            if (crs == 0)
                return cindex;
            if (crs < 0)
                begin = cindex + 1;
            else
                end = cindex - 1;
        }
        return ~begin;
    }
    
    Node NodeMove(Node current,int step){//step为正,next.next.next,为负pre.pre.pre
        var times = Math.Abs(step);
        for (var i = 0; i < times; i++)
        {
            if (step > 0)
                node = node.Next;
            else
                node = node.Previous;
        }
        return node;
    }
    
  19. 老赵
    admin
    链接

    老赵 2013-01-16 10:18:25

    @boringame

    你得再去看下算法分析了,就算排了序还是O(N),即使可能有更早的返回条件,比如前段时间我看得《算法(第四版)》讲搜索的一开始就谈到排序链表……

    你这个完全不是二分排序查找,二分排序查找是O(log(N))的前提,是根据index可以用O(1)的时间获得元素。

    PS,这是Markdown编辑器,还有下方不是有实时预览么,难道你心存侥幸心理最终发出去的看到的不一样嘛……

  20. 链接

    Haart 2013-01-16 10:33:53

    @boringame

    首先O(N)是用来描述复杂度量级的,所以命中率没有意义。比如冒泡排序对于已排序的数组来说非常快,一次交换都没有,但是它的复杂度就是O(N^2),不会变成别的。 同样,你举的这个例子中:排序前提下,查找会变得更快,但是复杂度还是O(N),不会变成别的。

    @老赵

    他这个不是二分排序,是二分查找,你看看那个NodeMove就知道了。

  21. boringame
    120.32.109.*
    链接

    boringame 2013-01-16 12:00:45

    怎么引起吐槽了(-_-b) 我没有说排序了就不是O(N),我想表达的是不应该只关心时间复杂度。 还有二分查找,我说的是“模拟二分查找”。就算我没有“模拟”,这个实现方式也对得起这个名字,即使和O(log(N))没有一点关系。 我觉得讨论这个东西是什么,那个不是什么,应该叫什么名字,不关键。

    最后陈述我方观点: LinkedList本来就不常用,别太认真。 HashedLinkedList要花费成倍的存储空间,我不喜欢这样的方式。但是时间效率不用怀疑,基本等同hashtable。 于是我提出以上几种不需要附加存储的方式,并且做了简单性能测试,把结果拿出来给大家分享。 “你得再去看一下XXXX再来讨论”类似的话,打击我们读者的参与积极性。可以提醒“在XXX有记载相关资料,可以看一下”。

    Ps,编辑器我又研究了一下,代码高亮按钮点击以后需要再输入一个字符才会得到预览。于是导致我之前看不懂,以后会用了。

  22. 链接

    Haart 2013-01-16 13:53:55

    @boringame

    那段对LinkedList的二分查找代码是没问题的,确实是二分查找,这个没问题啊。

    仔细分析下,这个 BinarySearch 算法,最差情况需要比较logN次,移动N次;最好情况需要比较1次,移动N/2次。也就是即使排好序,时间复杂度是O(N)。而顺序比较法,最差需要比较N次,移动N次;最好情况需要比较1次,移动1次。时间复杂度也是O(N)。所以从时间复杂度上说,这个 BinarySearch 没有任何优势,还额外加了一个需要排序的要求。

  23. 链接

    Haart 2013-01-16 14:19:32

    @boringame

    时间复杂度不是描述需要多少时间的,而是描述这个算法的时间价值的。

    “在某些条件下,某个O(N)算法比O(1)算法还要快” 这句话完全正确,但是没有意义。比如对链表用二分查找,你做的实验说明:“对于某些特定的数据,二分查找比较理想”。对,这个结论确实成立,但是二分查找的时间复杂度依旧是O(N)。

    为什么时间复杂度比特定的实验结果更说明问题呢? 因为 时间复杂度表示的是对平均运气下的期望,表示的是量级,而量级决定了这个算法的可用程度和通用程度 。对于一个算法来说,这才是最重要的(暂不讨论空间复杂度)。讨论算法的时间复杂度必然是针对 各种数据的平均表现

    尽管“在某些具体条件下,BinarySearch 算法比 顺序查找 算法更快”, 但是两者依旧是同一个量级的,它们的时间价值相同。而前者更加复杂,还额外要求链表被排好序。结论是: 对 链表 进行 二分查找 没有意义。

  24. 老赵
    admin
    链接

    老赵 2013-01-16 17:39:36

    @Haart

    口误,想着“二分查找”,说成“二分排序了”,活活。

    @boringame

    楼上帮我该说的都说了,我补充点非技术的:

    我只不过说了句“你得再去看看算法分析了”都会被你脑补为“你得再去看一下XXXX再来讨论”,太脆弱的人不建议来这里,我已经很客气了,下次遇到我不客气的时候你会郁闷死的。还有你连“LinkedList本来就不常用,别太认真”这种话都说,既然你一开始就没想要认真,那我还是劝楼上楼下的都别讨论这个话题了,浪费时间。

  25. boringame
    120.32.109.*
    链接

    boringame 2013-01-16 23:19:43

    @Haart

    非常感谢你的分析。是的,这个二分我之前就否定掉了,很烂的说。 这些个东西确实都是特定情况下,所以我一开始就没敢说找到了时间复杂度更优的方法。 对算法本身,我确实是跑题了。

    @老赵

    我们沟通好辛苦(——b)。只不过提示你,可以在不改变语义换一个格式输出,这个格式不友好。 别太认真说的是情绪上别太激动,不是说对技术,是我没有说清楚。 你这样的反映让我很吃惊,脆弱的恐怕不是我们这些来的人吧。

  26. 老赵
    admin
    链接

    老赵 2013-01-16 23:43:55

    @boringame

    觉得辛苦那是因为你扯别的去了,老老实实谈技术一点事情没有。

    其实有什么好吃惊的,我之前那么心平气和地在说话,就让你觉得情绪激动或是不友好了?看来你还真没见过我不客气的时候是什么样子的。认真不认真什么的我是理解不了,有什么不该认真的?要讨论就别随便,不管是对技术还是对讨论本身,这里不是客厅,非得搞的春暖花开宾至如归一般的。还有,别说什么“我们这些来的人”啊,我说“脆弱”的时候单指你一个人,你不要主动代表所有读者,说“我”就行了。

    总之你觉得吃惊那你就吃惊去吧,你觉得我是在打击你积极性那就打击吧。爱来不来,我真无所谓。

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我