Wikiracer

PartA

1. 函数未实现异常

在编写代码的过程中，经常会遇到一些已有 API 但尚未实现的函数。如果我们盲目地将这些函数简单地返回 0，那么在下次继续进行编码时，可能会使用这些未实现的函数，并在调试代码时浪费大量时间来查找这个问题。特别是在多人协作开发的情况下，这种做法是非常不好的。因此，作为良好的编程习惯，我们应该让这些函数返回一些有用的信息来告诉调用者这个函数 API 的功能还没有被实现。
例如，在 C++ 中可以使用以下代码：

throw std::invalid_argument("Not implemented yet.\n");

在 Python 中可以使用以下代码：

raise NoImplementedError('No idea how')

这些代码会抛出一个异常，从而使调用者意识到该函数尚未实现，并且提供了有用的信息来解释这个问题。

在 C 语言中可以使用panic 来实现

#define TODO() panic("please implement me")

2. 如何理解平衡二叉搜索树的遍历复杂度是 O (logn)?

通过下面这个图来进行理解:

O (logn) 就是你从二叉树中找到一个 solution 时需要做的 workload。(计算机科学中 log 经常指的是以 2 为底的对数函数)

3. 了解 check-in 框架

Assignment 的 PartA 部分带有一个测试框架，其组成部分主要有:

• test-wikiscraper.cpp
  用来测试 wikiscraper.cpp 中关键函数 valid_wikilink 和 findWikiLinks ， test-wikiscraper.cpp 中主要写了 8 个函数:

 valid_wikilink_test1, # 返回值为valid or invalid两个字符串之一
 valid_wikilink_test2,
 valid_wikilink_test3,
 valid_wikilink_test4,
 valid_wikilink_test5,
 valid_wikilink_test6,
 valid_wikilink_test7,
 findWikiLinks_test1   # 返回值为所有的page name组成的一个字符串

每次都可以通过命令行参数选定要执行上面这些函数中的哪一个 (巧妙的使用了 std 库中的 std::function 来实现)，比如 ./build/test 8 表明执行函数 findWikiLinks_test1 ，将函数的返回值输出到标准输出流中。

• test-wikiscraper.sh
• 首先通过执行 CMake 构建目标 test (由源文件 test-wikiscraper.cpp wikiscraper.cpp error.cpp 组成)
• 然后从一个测试文件 test_case 中读取测试命令，比如读取到 ./build/test 8 就说明要使用 findWikiLinks_test1 进行测试。
• 然后运行 ./build/test 8 ，同时也运行作者写好的绝对正确的可执行目标 ./test-resource/test 8
• 通过比较两者的结果中标准输出流，标准错误流是否一摸一样，就可以判断我们本次测试是否正确。

4. lamda 表达式

lambda 表达式的结构如下图所示:

[ capture clause ] (parameters) -> return-type  
{   
   definition of method   
} 

最重要的是 capture clause 部分可以传入 surrounding scope (即包裹 lambda 表达式的作用域) 的变量，比如:
target_set 就是外部函数 numCommonLinks 的变量.

int numCommonLinks(const unordered_set<string>& curr_set, const unordered_set<string>& target_set) {
    return count_if(curr_set.begin(), curr_set.end(), [&target_set](string s){return target_set.find(s) != target_set.end();});
}

其他部分解释请 RTFM (opens new window)。

5. Assignment1 中主要是学习了一些 std 函数的使用:

std::search    // to find the start of a link
std::find      // to find the end of a link
std::all_of    // to check whether the link contains an invalid character.

这告诉我们，cpp 的一个优点在于，使用 std 容器很方便，而且对容器的操作只要你敢想，那么就大概率会有这么一个函数可以实现你想实现的功能。

6. 什么是优先级队列？

• decltype():STL function to find the type of any parameters whose types you might be missing

7. CMake 和 vcpkg

CS106L 实验是通过 CMake 构建 Makefile， 然后通过 GNU Make 来编译和链接所有的源文件。

其中用到的第三方库使用了包管理工具 vcpkg 进行管理，vcpkg+CMake 的用法我在 packge-management 05-vcpkg 进行了仔细的介绍。

PartB

寻找从 start_page 到 end_page 的 link ladder

Pseudocode:

创建一个优先级队列，每个位置都能存放一个ladder
Create an empty priority queue of ladders (a ladder is a vector<string>).

将start_page作为ladder添加到优先级队列中
Create/add a ladder containing {start_page} to the queue.

只要队列不为空，说明还可以创建新的ladder
While the queue is not empty:

    将优先级最高的ladder从队列中取出
    Dequeue the highest priority partial-ladder from the front of the queue.


    访问取出队列的尾部页面作为当前页面, 并获得当前页面中的所有link name作为neighbour page
    Get the set of links of the current page i.e. the page at the end of the
      just dequeued ladder. 

    如果有neighbor page是target_page中，则查找成功
    If the end_page is in this set:
        We have found a ladder!
        Add end_page to the ladder you just dequeued and return it.

    否则，就遍历每一个neighbor page
    For each neighbour page in the current page’s link set:

        如果neighbor page还没有被访问过
        If this neighbour page hasn’t already been visited:

            创建当前ladder的副本ladder
            Create a copy of the current partial-ladder.

            在副本ladder中加入neighbor page
            Put the neighbor page string at the end of the copied ladder.

            把副本ladder放会到优先级队列中
            Add the copied ladder to the queue.

如果循环结束都没有找到一条合适的ladder，就说明没有这么一条ladder
If while loop exits without returning from the function, no ladder was found so return an empty vector<string>