ARTS 打卡第 3 周

Algorithm 一道算法题；

Review 阅读并点评一篇英文文章；

Technique/Tips 是分享一个技术技巧；

Share 是分享一篇有观点和思考的技术文章。



Algorithm



leetcode-136 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1


示例 2:

输入: [4,1,2,1,2]
输出: 4

链接：https://leetcode-cn.com/problems/single-number/

结题思路：

这道题如果不考虑说明里的额外要求，实现的思路有很多，我能想到的就有两种：

1.利用map，存储每个元素出现的次数；

2.先排序，然后遍历。

但是这次都不能满足线性的时间复杂度，且不利用额外的空间来时间。在看官方解答之前，我也一直没有找到思路。

看了官方解答，我晕，原来还有这么骚的套路：利用异或。

异或运算有以下三个性质：

1. 任何数和 000 做异或运算，结果仍然是原来的数，即 a⊕0=a。

2. 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。

3. 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。

惊艳吧，我也是没想到，下面是实现代码：

    int singleNumber(vector<int>& nums) {
        int size = nums.size();
        int rv = 0;
        for(int i = 0; i < size; i++)
        {
            rv = rv ^ nums[i];
        }
        return rv;
    }

简单可靠。



Review

本周的英文阅读文章：Efficient data transfer through zero copy（使用零拷贝进行有效的数据传输）

这篇文章介绍了Zore Copy技术，它被用来提升运行在Linux和UNIX上的Java程序的IO性能。

很多web服务器会读取大量的静态文件，这些文件从磁盘读取，并通过网络发送出去；在这个过程中数据实际上经历了4次拷贝：

1. 从硬盘上，读到操作系统内核的缓冲区里。这个传输是通过 DMA 进行的。

2. 从内核缓冲区里面的数据，复制到我们应用分配的内存里面。这个传输是通过 CPU 进行的。

3. 从我们应用的内存里面，再写到操作系统的 Socket 的缓冲区里面去。这个传输，还是由 CPU 进行的。

4. 再从 Socket 的缓冲区里面，写到网卡的缓冲区里面去。这个传输又是通过 DMA 。



可以看到，在这个过程中，第2次和第3次拷贝都是不必要的。

使用Zore Copy，可以让数据不进入用户态，直接在内核态下拷贝数据，该过程分以下2步：

1. 通过 DMA，从硬盘直接读到操作系统内核的读缓冲区里面。

2. 根据 Socket 的描述符信息，直接从读缓冲区里面，写入到网卡的缓冲区里面。

在JAVA中，实现这个功能需要使用的函数是java.nio.channels.FileChannel.transferTo()

public void transferTo(long position, long count, WritableByteChannel target);

在Unix和Linux系统中，这个函数调用的是系统调用 ：sendfile()

#include <sys/socket.h>
ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);

最后，文章里对这两种方法进行了性能对比：



可以看到，使用零拷贝的方式，程序性能得到了很大的提升，大约有65%。

在以后设计类似的系统时，可以考虑使用这种方式。



Technique/Tips

这次分享一个在工作中提升的性能的技巧：在操作设备的遥控和遥信信号时，针对每一路遥控或遥信，会分别调用一次ioctrl来获取状态，或者控制状态。为了实时的获取遥信状态，程序需要在很短的时间内，不停的轮询，从而产生了大量的ioctrl调用。

有什么办法能优化这种情况呢？我想到的第一办法就是改轮询为通知的方式，但是这样的话，驱动层的动静比较大，有没有什么更好的办法呢？我想到了把多路遥控/遥信状态，合并到一个整型变量里，这样就可以只调用一次ioctrl，大大减少进入内核态的开销。

写了一个测试程序来测试

int main(int argc, char **argv)
{
    int Loop = 10000;
    if(argc == 2)
    {
        std::string loop_str = argv[1];
        Loop = (unsigned int) atoi(loop_str.c_str());
    }
    int fd = open("/dev/io", O_RDWR);
    if (fd < 0)
    {
        printf("test_conbine Open /dev/io error!\n");
        return -1;
    }
    timeval beginTime, endTime;
    gettimeofday(&beginTime, NULL);
    for(int i = 0; i < Loop; i++)
    {
        int conbine;
        ioctl(fd, 0x100, &conbine);
    }
    gettimeofday(&endTime, NULL);
    int diff = (endTime.tv_sec - beginTime.tv_sec) * 1000 + (endTime.tv_usec - beginTime.tv_usec) / 1000;
    printf("test_conbine:conbine %d loop diff: %d ms\n", Loop, diff);
    gettimeofday(&beginTime, NULL);
    for(int i = 0; i < Loop; i++)
    {
        int tmp;
        ioctl(fd, 0x101, &tmp);
        ioctl(fd, 0x102, &tmp);
        ioctl(fd, 0x102, &tmp);
        ioctl(fd, 0x102, &tmp);
    }
    gettimeofday(&endTime, NULL);
    diff = (endTime.tv_sec - beginTime.tv_sec) * 1000 + (endTime.tv_usec - beginTime.tv_usec) / 1000;
    printf("test_conbine:single %d loop diff: %d ms\n", Loop, diff);
    return 0;
}

实测性能提升了一倍。



Share

这周分享耗子叔的文章 程序员练级攻略的正确打开方式

这篇文章对程序员练级攻略系列做了总结，并给出了一个分3步的成长型建议：

1. 首先，你需要建一个自己的实验室。

2. 其次，把你的实验室升级成一个工作室。

3. 最后，把你的工作室升级成工厂。

最后，最重要的建议：坚持和动手。