ARTS-7

Algorithm 一道算法题

https://leetcode.cn/problems/n-queens/

https://leetcode.cn/problems/n-queens/solutions/2443999/di-jiu-shi-jiu-tian-bu-po-bu-li-chang-sh-67fo/

class Solution {    public List<List<String>> solveNQueens(int n) {        List<List<String>> solutions = new ArrayList<List<String>>();        int[] queens = new int[n];        //填充-1;        Arrays.fill(queens,-1);        //横        Set<Integer> columns = new HashSet<Integer>();        //撇        Set<Integer> diagonals1 = new HashSet<Integer>();        //捺        Set<Integer> diagonals2 = new HashSet<Integer>();        backtrack(solutions,queens,n,0,columns,diagonals1,diagonals2);        return solutions;    }
    //回溯    private void backtrack(List<List<String>> solutions, int[] queens, int n, int row,    Set<Integer> columns,Set<Integer> diagonals1,Set<Integer> diagonals2){        //当填的数等于N时，生成结果        if(row == n){            List<String> board = generateBoard(queens,n);            solutions.add(board);        } else {            for(int i = 0; i < n; i++){                //检查横                if(columns.contains(i)){                    continue;                }                int diagonal1 = row - i;                //检查撇                if(diagonals1.contains(diagonal1)){                    continue;                }                int diagonal2 = row + i;                //检查捺                                if(diagonals2.contains(diagonal2)){                    continue;                }                //成功把下标记录好                queens[row] = i;                columns.add(i);                diagonals1.add(diagonal1);                diagonals2.add(diagonal2);                //检查下一行                backtrack(solutions,queens,n,row + 1, columns,diagonals1,diagonals2);                //不满足将这行填加的去掉重新检查 start                queens[row] = -1;                columns.remove(i);                diagonals1.remove(diagonal1);                diagonals2.remove(diagonal2);                //不满足将这行填加的去掉重新检查 end            }        }    }
    //生成结果    private List<String> generateBoard(int[] queens, int n){        List<String> board = new ArrayList();        for(int i = 0; i < n; i++){            char[] row = new char[n];            Arrays.fill(row,'.');            //将下标填充Q            row[queens[i]] = 'Q';            board.add(new String(row));        }        return board;    }}

Review 读一篇英文文章

https://www.quora.com/What-are-some-of-the-most-basic-things-every-programmer-should-know

每个程序员都应该知道哪些最基本的事情？

What are some of the most basic things every programmer should know?

如果没有经过测试，它就不起作用。

If it's not tested, it doesn't work.

源代码控制是你的朋友——一定要使用它

Source control is your friend - make sure you use it.

仅仅因为你编写了它并不意味着你拥有它——如果你团队中的其他人必须更改你的代码，请不要生气。

Just because you wrote it doesn't mean you own it — don't be offended if someone else on your team has to change your code.

不要重新发明轮子，代码库可以提供帮助。

Don't reinvent the wheel, library code is there to help.

最快的代码是从未执行过的代码——寻找早期退出的代码。

The fastest code is code that's never executed — look for early outs.

仅仅因为你没有写它并不意味着它是垃圾。

Just because you didn't write it doesn't mean it's crap.

源代码只是向编译器提示您想要做什么，它不一定会这样做（例如，您可以将函数声明为内联，但编译器不必遵守）。

Source code is just a hint to the compiler about what you want to do, it won't necessarily do it (e.g. You might declare a function as inline but the compiler doesn't have to obey).

难以理解的代码也很难维护。

Code that's hard to understand is hard to maintain.

难以维护的代码几乎毫无用处。

Code that's hard to maintain is next to useless.

“当我编辑这个文件时，我只会……”是引入功能蔓延和错误的好方法。

“Whilst I'm editing this file I’ll just…” is a great way to introduce feature creep and bugs.

代码布局越整洁，就越容易阅读。越容易阅读，就越容易理解和维护。

The neater your code layout, the easier it is to read. The easier it is to read, the easier it is to understand and maintain.

代码不是自记录的。通过添加评论来指导其他人，从而帮助他们。现在你可能明白了，但是 5 年后呢？

Code is not self documenting. Help others by adding comments to guide them. You may understand it now but what about in 5 years time?

糟糕的代码可能并且将会再次困扰您。

Bad Code can and will come back to haunt you.

世界上不存在 5 分钟的工作。总是至少需要半天时间。

There is no such thing as a 5 minute job. It'll always take at least half a day.

魔法数字很糟糕。

Magic numbers are bad.

常量不占用存储空间，它们是编译时文本替换。

Constants don't take up storage, they're compile time text substitutions.

项目管理总是希望您事半功倍。

Project management will always want you to do twice as much in half the time.

如果存在错误，用户会发现它。

If there is a bug, the user will find it.

代码审查不是批评。

A code review is not a criticism.

重要的不是代码的数量，而是质量。任何白痴都可以跑出 40kloc，但这并不意味着它符合目的。

It's not the quantity of code that matters, it's the quality. Any idiot can bang out 40kloc but that doesn't make it fit for purpose.

写得不好的代码的真正成本在于维护。

The true cost of poorly written code is in the maintenance.

吃你自己的狗粮——修复你自己代码中的错误可以帮助你更好地编码并提高你的理解。

Eat your own dog food — fixing bugs in your own code helps you code better and improves your understanding.

代码会随着时间的推移而腐烂。

Code rots over time.

如果用户没有要求某个功能，则不要添加它。

If the user didn't ask for a feature, don't add it.

如果没有经过测试，它就不起作用（是的，我知道我已经包含了两次，但这非常重要）。

If it's not tested, it doesn't work (yes, I know I've included that twice but it's really important).

Technique/Tips 分享一个小技术

什么是零拷贝？

​ 取消用户空间与内核空间之间的数据拷贝操作，应用进程每一次的读写操作，都可以通过一种方式，让应用进程向用户空间写入或者读取数据，就如同直接向内核空间写入或者读取数据一样，再通过 DMA 将内核中的数据拷贝到网卡，或将网卡中的数据 copy 到内核。

正常的 IO 流程

​ 磁盘 - 内核缓冲 - 用户缓冲 - 套接字缓冲 - 协议引擎

​ hard drive - kernel buffer - user buffer - socket buffer - protocol engine

​ 协议引擎 - 套接字缓冲 - 用户缓冲 - 内核缓冲 - 磁盘

​ protocol engine - socket buffer - user buffer - kernel buffer - hard drive

其中内核缓冲到用户缓冲和用户缓冲到套接字缓冲是占用 CPU 来完成的。

零拷贝两种实现方式：

​ 1、mmap + write

​ 通过内存映射，内核缓冲和用户缓冲达成共享，可以去掉用户缓冲拷贝流程，即：

磁盘 - （内核缓冲 用户缓冲） - 套接字缓冲 - 协议引擎

hard drive - （kernel buffer user buffer） - socket buffer - protocol engine

少了一次 CPU 拷贝的操作，四次上下文切换，三次数据拷贝

​ 2、sendfile

sendfile 方式与 mmap + wirte 方式类似，流程：

磁盘 - 内核缓冲 - 套接字缓冲 - 协议引擎

hard drive - kernel buffer - socket buffer - protocol engine

网上说 linux2.1 还是和 mmap 类似 kernel buffer 到 socket buffer 还有一次 CPU 拷贝，linux2.4 时通过 copy desc，类似变成如下流程，没有 cpu 拷贝，只剩下两次 DMA 拷贝，两次上下文切换。

磁盘 - （内核缓冲 套接字缓冲） - 协议引擎

hard drive - (kernel buffer socket buffer) - protocol engine

Share 分享一个观点

我昔所造诸恶业，皆由无始贪嗔痴。

For all the evil deeds I have done in the pastBased on beginningless greed, anger, and delusion.