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.Tips

前面先说一下，感觉学习真的是一个不断完善、不断修剪的过程，本周学到的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” ，主要讲的是求平方根，硬是看了好几遍，才看懂，后面又看到用牛顿迭代法求平方根，都很不错，分享给大家，有兴趣的小伙伴可以留言一起讨论讨论。
如何通俗易懂地讲解牛顿迭代法–戳我打开

相关文章

留下评论