Lib.rs

作业 5 - readme.txt

如何运行 "word-count"：使用 BinarySearchTree ("-b")、AVLTree ("-a") 或 SplayTree ("-s") 运行 "word-count"，以及其中一种排序算法（SelectionSort ("-selectionSort")、QuickSort ("-quickSort")、Heapsort ("-heapSort")）。如果没有指定排序算法，则默认为 Heapsort。以下是通用命令

   ./word-count "tree" "sort" < "inputfile" > "outputfile"

包含在此项目中的文件：AVLNode.cpp BSTNode.cpp SplayTree.cpp Pair.cpp Makefile heap.ps AVLNode.h BSTNode.h SplayTree.h Pair.h word-count quick.ps AVLTree.cpp BinarySearchTree.cpp Heap.cpp Main.cpp readme.txt selection.ps AVLTree.h BinarySearchTree.h Heap.h TemplateInst.cpp

设计决策与项目问题：我们已经实现了我们的 AVLTree 和 SplayTree，如下所示：两者都继承自 BinarySearchTree，并分别实现了 AVLTree 和 SplayTree 的规范形式、Find()、Insert() 和 SingleRotate() 以及 Splay() 方法。这些方法根据 Weiss 书籍中的示例执行重新平衡操作。我们实现了 SingleRotate()，以便 AVL 的 Insert() 方法可以确定何时使用它，以及是否执行单次或双旋转（在这种情况下，SingleRotate() 将被调用两次）。Splay() 在每次插入或搜索节点（或其父节点，如果它不在树中）时被调用，并且完全负责将该节点旋转到根。Heap 使用 Floyd 方法实现，我们必须感谢 Weiss 的示例，我们遵循了这些示例。我们还必须感谢 Weiss 对 Quicksort 的实现，我们部分遵循了它。Pair 是一个包装类，它包含键和值对。所有排序算法和 Heap 都依赖于 Pair。我们必须感谢您，CSE 326 的教职员工，您提供了 SelectionSort 的示例，我们遵循了它以编写自己的示例，并实现了 BinarySearchTree 的 Find() 和 Insert() 方法的基实现。我们将这些方法的主体复制到 AVLTree 和 SplayTree 中，并添加了必要的代码以执行重新平衡操作。

莎士比亚是否真的写了归功于他的作品？是的，他确实写了。下表显示了每位作者的单词总数、平均wpb、每部作品的wpb以及每部作品中最常使用的五个单词及其相应频率。请注意，这些单词几乎完全相同，这是由于常见的英文单词，而不是每位作者的写作风格。我的兴趣在于莎士比亚拥有最大的词汇量，而且莎士比亚使用这些单词的频率比培根低得多。由于培根的平均wpb比莎士比亚高，这意味着他平均使用的单词更多，因为常见的单词在他的作品中占的比例比莎士比亚多。但是，他使用常见单词的频率更高，因此看起来他的词汇量比莎士比亚小。此外，莎士比亚的结果非常规律，而培根的则不然。基于所有这些，没有足够的证据表明培根写了归功于莎士比亚的作品。

威廉·莎士比亚：总单词数：14872，平均wpb：42.3482 《哈姆雷特》：8311个单词，40.2782 wpb “the”(0.1167)，"and"(0.0852)，"of"(0.0801)，"to"(0.0760)，"I"(0.0626) 《皆大欢喜》：6561个单词，44.4181 wpb “the”(0.1082)，"I"(0.1018)，"and"(0.0806)，"to"(0.0759)，"of"(0.0734)

弗朗西斯·培根爵士：总单词数：16848，平均wpb：43.4245 《论文》：12174个单词，38.9955 wpb “the”(0.2243)，"of"(0.1733)，"and"(0.1719)，"to"(0.1232)，"a"(0.0923) 《新大西洋》：4674个单词，47.8534 wpb “of”(0.1863)，"the"(0.1771)，"and"(0.1739)，"to"(0.0849)，"that"(0.0562)

分析结果：由于不同的树，我们预计每种树中的减速情况都不同。总的来说，使用字符串及其所有方法应该会有一些开销。在二叉树中，最大的减速应该在插入和查找时，因为它在这两种情况下都需要遍历树。

在AVL树中，实际上不应该有任何巨大的瓶颈，但在插入和单旋转上会花费相当多的时间，因为任何相当大的输入都可能会调用单旋转，这应该会频繁发生。

在伸展树中，应该类似于AVL树，因为应该没有大的瓶颈减速。伸展树可能会稍微慢一点，因为它一旦运行得很快，就会经常被调用，因为东西被插入。

程序的其他部分将花费相当多的时间，将是HeapSort。它应该在堆类上花费相当多的时间，构建堆将花费一些时间（O(n)），排序也是如此。

查看gprof输出，结果大致符合我们的预期，也有一些有趣的细节。花费时间最多的地方是在Base类BinarySearchTree中的FindNode。在AVL树中，第二个最耗时的函数是Pair类的copy函数，而在伸展树中是Pair类的默认构造函数和拷贝构造函数。这可能是由于我们用字符串实例化了pair，整个程序的最大开销是字符串。

对于伸展树，Insert和splay是调用次数最多的前10个函数（忽略由字符串生成的调用）。

对于AVL树，Insert和Single Rotate的调用次数也接近顶端。

程序最大的瓶颈是FindNode的调用。这是因为必须搜索树（无论类型如何）以查找新键以检查频率。一种使程序稍微流畅一些的方法是编写一个专门的冲突函数，以便在函数的ValueType为整数时，整数会递增。

算法分析结果 我们实现了三种搜索算法：选择排序、堆排序和快速排序。这三种算法的时间复杂度分别是 O(n^2)、O(nlog n) 和摊销 O(n log n)，这些都是我们在课堂上学习的。由于示例的时间限制，由于绘图点的数量较少，从图中真的看不清排序的本质。实际的区别实际上可以从实际的运行时间差异中看出。虽然堆排序和快速排序对于输入分别在大约 5 秒、8 秒、11 秒和 17 秒内运行，但选择排序对于每个输入分别需要 7 秒、12 秒、17 秒和 31 秒。正如你所看到的，快速排序和堆排序的增长并不快，而选择排序随着输入大小的增加而迅速增长。

Included are the following plots:
     quick.ps - QuickSort graph.
     selection.ps - SelectionSort graph.
     heap.ps - HeapSort graph.