在有序数据中，BSTMap 与 LinkedListMap 统计词频运行时间问题

来源：1-1 平衡树和AVL

Wab77

2023-05-27 11:35:57

问题描述

把单词 word 添加到 Map 前，使用 Collections.sort(words) 对单词进行排序，发现 LinkedListMap 的运行时间缩短了很多。
我对此不理解，我认为它的运行时间应该与退化后的 BST 差不多，烦请老师解答。

AVL：0.16 s
BST：5.99 s
LinkedList：0.19 s

我的思考

LinkedListMap 的 add、contains、get、 set 依赖 getnode 函数，即便是有序的数据，时间复杂度也是 O(n)，不应该与退化后的 BST 有很大的差距。

private Node getNode(K key) {
    Node cur = dummyHead.next;
    while (cur != null) {
        if (cur.key.equals(key)) {
            return cur;
        }
        cur = cur.next;
    }
    return null;
}

运行时间测试

写回答

2回答

liuyubobobo

2023-05-31

已采纳

抱歉，因为美国正好是 Memorial Day 的假期，家里有一些事情，所以回复晚了。

非常有意思的问题。我也实验了一阵子才理解是怎么回事儿：）

==========

实际上，问题的关键是：

BST 退化成链表以后，我们每次添加的新的节点，在这个链表的尾端。（也就是每次添加的是 BST 的一个叶子节点）

而我们的链表实现，每次添加新的节点，在链表头：

dummyHead.next =  new Node(key, value, dummyHead.next);

当把所有 words 排序以后，你可以想象，每一组相同的 words 都挨着。

对于 BST 和链表来，在每一组相同的 words 中，第一个 word 都需要是使用 O(n) 的时间做插入；

但是，对于 BST 来说，后续所有相同的 word，都需要使用 O(n) 的时间做 set；

可是，对于链表来说，因为这个 word 一定在链表头，所以只需要使用 O(1) 的时间做 set（遇到的第一个节点就比较成功了。）

因此，在排序情况下，链表并不是每一个 contain 和 set 和 add 操作都是 O(n) 级别的。实际上，只有 |total different words| 这么多的操作是 O(n) 级别的。

而在排序情况下，BST 的每一个操作都是 O(n) 级别的。

所以，这个时间差距不是 O(n^2) 和 O(n) 的差距（不是退化不退化的差距）。BST 确实退化成了链表。链表也确实是一个正确的链表。但是这个链表和 BST 退化的链表不等价，因为插入节点的位置不同。

这个时间差距的本质，是我们的样本中不同的单词数，和总单词之间的差距。

在傲慢与偏见这本书中，这个差距大概是 20 倍。我简单实验了一下，如果把链表的添加操作改成添加到链表尾，大概就会放慢 20 倍的速度。你可以在你的环境下试验一下，把链表的 add 操作改成下面的样子：

    @Override
    public void add(K key, V value){
        Node node = getNode(key);
        if(node == null){
//            dummyHead.next = new Node(key, value, dummyHead.next);

            // 把新节点插入到链表尾
            Node cur = dummyHead;
            while(cur.next != null) cur = cur.next;
            cur.next = new Node(key, value, null);
            
            size ++;
        }
        else
            node.value = value;
    }

==========

P.S.

当对于链表，把新节点插入到链表尾，对于 sort 后，我这里的测试结果，链表还是会快于 BST，但是在同一数量级了（没有数量级的差距。）

这也 make sense，其中的原因可能包括：

1）BST 是递归结构；二链表的实现是非递归的；

2）BST 在每个节点要做 left 和 right 的 if 判断，导致了更多的分支结构。（这很有可能是主要原因）

3）链表的代码更简单（代码行少），代码逻辑更简洁，这使得编译器更容易对链表的代码做优化（类似于这类优化：https://www.harness.io/blog/5-jit-optimization-techniques ）

等等

但注意，AVL 树也有上述 BST 实现上的问题，甚至由于要维护平衡，有更多的复杂操作。但是在我们的实验范围里，不过对数据做不做 sort，AVL 树的性能都比 BST 和链表好。这足以见得保持树的平衡是多么重要，能够带来的性能提升有多大。

继续加油！：）