Fork me on GitHub

ARTS 打卡第一周

What’s ARTS?
A:Algorithm 每周至少做一个leetcode的算法题
R:Review 阅读并点评至少一遍英文技术文章
T:Tip 学习至少一个技术技巧
S:Share 分享一篇有观点和思考的技术文章

ARTS打卡第一周

1.Algorithm

 本周做了几个难度为Easy的算法,记录下。

1.1 Palindromic number

 判断一个数是否为回文数,方法很简单,只需要逆置前后判断是否相等就行了,不过还是有几个地方需要注意下

 1. 负数、个位上为0的数都不是回文数
 2. 注意int类型的溢出

 代码如下

1
2
3
4
5
6
7
8
9
10
11
bool determine(int num)
{
if (num < 0 ||(num != 0) && num %10 ==0)
return false;
int x = 0;
while (num > x) {
x = num % 10 + x * 10;
num /= 10;
}
return num == x || (x / 10 == y);
}

1.2 Roman To Intger

 将罗马数字转换为整数,此题感觉主要考查对罗马数字的转换熟悉不,当一个罗马数字前面部分小于后面部分,就是使用后面部分减去前面部分,否则就是加。第一时间想到的是直接使用个switch进行判断就好了,不过这样不够简洁,到最后发现有更简洁的办法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int romantoint(string str)
{
int num[26] = {0};
num['I'-'A'] = 1;
num['V'-'A'] = 5;
num['X'-'A'] = 10;
num['L'-'A'] = 50;
num['C'-'A'] = 100;
num['D'-'A'] = 500;
num['M'-'A'] = 1000;

int sum = 0;
for (size_t i = 0; i < str.size(); ++i) {
if (i+1 = str.size()) {
sum += num[str[i]-'A'];
break;
}
if (num[str[i]-'A'] >= num[str[i+1]-'A'])
sum += num[str[i]-'A'];
else {
++i;
sum += num[str[i]-'A'] - num[str[i-1]-'A'];
}
}
return sum;
}

2.Review

文章链接-需要能打开Google才能打开
 这篇文章讲述了C++虚函数的性能开销,从重载、override 多态一步步到虚函数,写的很详细。也从各方面分析了虚函数的开销,主要体现在虚函数调用需要间接跳转带来的分支预测成本和cache miss,文章中也讲了该如何尽可能的去最小化cache miss,通过虚函数分组的办法使用std::set来进行分组{函数指针,对象指针},通过分组将函数调用保存在缓存中最小化cache miss。

3.Tip

 前面先说一下,感觉学习真的是一个不断完善、不断修剪的过程,本周学到的tips都跟上面讲的文章相关。看到文章中提到的cache miss,才知道cache miss是什么东西,也才学会使用linux下的性能调优工具perf.

  1. perf list 查看perf能监控哪些性能指标 主要有三类指标
    1.1 Hardware Event 是由PMU硬件产生的事件 比如cache命中
    1.2 Software Event 由内核产生,比如进程切换,page-faults等
    1.3 TracePoint Event 是核心中的静态 tracepoint 所触发的事件,这些 tracepoint 用來判断在程序执行时期核心的行为

  2. perf stat -e -L1-dcache-load-misses ./test 查看test程序的L1 cache miss的指标

4. Share

关于技术文章,这周看的比较多的是耗子叔的文章,里面有一篇很有意思,讲的是“魔数 Ox5f3759df” ,主要讲的是求平方根,硬是看了好几遍,才看懂,后面又看到用牛顿迭代法求平方根,都很不错,分享给大家,有兴趣的小伙伴可以留言一起讨论讨论。
如何通俗易懂地讲解牛顿迭代法–戳我打开

您的赞赏是对我最大的支持,谢谢!