ARTS打卡第一周

Algorithm

LeetCode 51. N-Queens

典型的DFS

简单粗暴的实现
对于每一行，遍历所有的列

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> results;
        vector<int> state(n);
        dfs(results, state, 0, n);
        return results;
    }
private:
    void dfs(vector<vector<string>> &results, vector<int> &state, int k, int n) {
        if (k == n) {   // done
            results.emplace_back(n, string(n, '.'));
            vector<string> &result = results.back();
            for (int j = 0; j != n; ++j) {
                result[j][state[j]] = 'Q';
            }
        }
        else {
            for (int j = 0; j != n; ++j) {
                state[k] = j;
                if (check(state, k)) {
                    dfs(results, state, k + 1, n);
                }
            }
        }
    }

    bool check(const vector<int> &state, int k) {
        for (int i = 0; i != k; ++i) {
            if (state[i] == state[k]) return false;
            if (abs(state[i] - state[k]) == k - i) return false;
        }
        return true;
    }
};

n取15时耗时30.412s
Top Hotspots
Function CPU Time
Solution::check 21.540s
Solution::dfs 7.256s

既然hotspot是check，改成在每行的遍历之前先算好可以选择的列，从而消除check的调用

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> results;
        vector<int> state(n);
        vector<vector<char>> choices(n);
        dfs(results, state, choices, 0, n);
        return results;
    }
private:
    void dfs(vector<vector<string>> &results, vector<int> &state, vector<vector<char>> &choices, int k, int n) {
        if (k == n) {   // done
            results.emplace_back(n, string(n, '.'));
            vector<string> &result = results.back();
            for (int j = 0; j != n; ++j) {
                result[j][state[j]] = 'Q';
            }
        }
        else {
            auto &choice = choices[k];
            choice.assign(n, true);
            for (int i = 0; i != k; i++)
            {
                choice[state[i]] = false;
                if (state[i] + k - i < n) choice[state[i] + k - i] = false;
                if (state[i] + i - k >= 0) choice[state[i] + i - k] = false;
            }
            for (int j = 0; j != n; ++j) {
                if (choice[j]) {
                    state[k] = j;
                    dfs(results, state, choices, k + 1, n);
                }
            }
        }
    }
};

耗时 15.779s 缩短了大约一半。
这里有个细节，用了vector<char>来表示bool数组，如果用vector<bool>的话耗时是25.116s。
Top Hotspots
Function CPU Time
Solution::dfs 11.660s
std::vector<char, std::allocator<char> >::_Insert_n 2.339s

既然在处理每一行的时候，要根据之前各行的信息来计算可选的列，那是否可以在之前各行处理的时候就先算好之后各行可选的列呢

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> results;
        vector<int> state(n);
        vector<vector<int>> attacks(n, vector<int>(n, 0));
        dfs(results, state, attacks, 0, n);
        return results;
    }
private:
    void dfs(vector<vector<string>> &results, vector<int> &state, vector<vector<int>> &attacks, int k, int n) {
        if (k == n) {   // done
            results.emplace_back(n, string(n, '.'));
            vector<string> &result = results.back();
            for (int j = 0; j != n; ++j) {
                result[j][state[j]] = 'Q';
            }
        }
        else {
            for (int j = 0; j != n; ++j) {
                if (attacks[k][j] == 0) {
                    state[k] = j;
                    for (int i = k + 1; i != n; i++)
                    {
                        ++attacks[i][j];
                        if (j + i - k < n) ++attacks[i][j + i - k];
                        if (j + k - i >= 0) ++attacks[i][j + k - i];
                    }
                    dfs(results, state, attacks, k + 1, n);
                    for (int i = k + 1; i != n; i++)
                    {
                        --attacks[i][j];
                        if (j + i - k < n) --attacks[i][j + i - k];
                        if (j + k - i >= 0) --attacks[i][j + k - i];
                    }
                }
            }
        }
    }
};

耗时 10.974s 进一步缩短。

Review

Refactoring Large Functions

大函数分解的好处

虽然会产生一些只有一个调用者的函数，但代码复用并不是重要的因素
可以赋一个有意义的函数名
减小变量的作用域
减少缩进
可测试性

策略

闭包可以直接变成具名函数
循环可以提取出来，尤其是C++的break不支持多层跳出
函数中用空格分成多块，每块做一件事的，通常可以提取
一连串对同一个对象的操作可以提取
复杂的if条件

Tip

https://docs.python.org/3/reference/datamodel.html#object.__new__

__new__用于构造新对象，返回值为一个对象实例。
- 也可以返回已有对象，用于实现singleton、flyweight等模式
__init__用户初始化对象，设置对象的字段
- __new__返回的不是本类实例时，__init__不会被调用

The Most Important Software Innovations
文章列举了最重要的软件创新。
（居然没写λ演算。。。）

最后编辑于：2019.03.30 11:29:34

ARTS打卡第一周

Algorithm

LeetCode 51. N-Queens

Review

Tip

Share