ARTS 打卡第 3 周

发布于: 2020 年 07 月 18 日

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. 最后,把你的工作室升级成工厂。

最后,最重要的建议:坚持和动手。

用户头像

Scotty

关注

我爱编程 Always Be Coding 2017.12.05 加入

11年程序员,4年java web全栈,7年服务端C++

评论

发布
暂无评论
ARTS打卡第3周