ARTS 打卡第 4 周

Algorithm 一道算法题；

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

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

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



Algorithm



leetcode-387 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

 

示例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2


 

提示：你可以假定该字符串只包含小写字母。

链接 https://leetcode-cn.com/problems/first-unique-character-in-a-string/

解题思路：

这道题难度不大，一开始就有一个大概的思路，就是要利用map，统计每个字符出现的次数；但是我一开始陷入了误区，因为这题不但要在map里存字符出现次数，还要存每个字符的索引，那么就不能利用基本类型了，还需要定义结构体，而且最后还要遍历map，找到索引值最小的那个字符。

总感觉这么做不够完美，查看解答后恍然大悟：不需要存索引，最后也不需要遍历map，只要按照字符串顺序，遍历一遍字符串即可。

    int firstUniqChar(string s) {
        if(s.length() == 0)
        {
            return -1;
        }
        
        unordered_map<char, int> m;
        unordered_map<char, int>::iterator iter;
        char * pStr = (char*)s.c_str();
        for(int i = 0; i < s.length(); i++)
        {
            iter = m.find(pStr[i]);
            if(iter != m.end())
            {
                iter->second++;
            }
            else
            {
                m.insert(make_pair(pStr[i], 1));
            }
        }
        
        for(int i = 0; i < s.length(); i++)
        {
            if(m[pStr[i]] == 1)
            {
                return i;
            }
        }
        return -1;
    }



Review

本周的英文阅读文章：https://www.agner.org/optimize/optimizing_cpp.pdf

本周开始研读这本C++程序员必读的软件调优手册，这次读了第一章：Introduction。

这一章里，作者阐述了写这本书的目的和面向的读者对象，并由此引出了一系列的性能调优书籍。作者给出的建议是，如果是只满足于写高级程序语言的人，只读这一本就够了；剩下的一系列书籍，是给那些希望能深挖指令时序、汇编编程、编译器技术和处理器架构细节的人。言外之意，如果你有追求的人，应该把这一系列书都研读一遍。

作者总结了当前大学里的编程课程，普遍都是以面向对象、模块化、可重用化和系统化的技术为主，而这些学习目标往往与软件的性能是冲突的。因为计算机的性能更强大，软件开发变的复杂，所以大家普遍更加关注软件开发的成本，而不是性能。这对软件的使用者是不利的，他们花费了高价，买了高性能的计算机，得到了很大的软件包，但是即使是运行一个很简单的任务，系统也会花费很长的时间。

为了能够获得更快的执行速度，和更小的软件，有时我们需要对软件开发的高级原则作出妥协。这本书讨论了如能能够达到这种合理的平衡。

嗯，期待着后面的章节。



Technique/Tips

这次的tip分享一下 深入浅出计算机组成原理-高速缓存里学到的cpu缓存更新策略。

第一种写入策略叫写直达（Write-Through）：

这是最简单的一种写入策略，在这个策略里，每一次数据都要写入到主内存里面。在写直达的策略里面，写入前，会先去判断数据是否已经在 Cache 里面了。如果数据已经在 Cache 里面了，我们先把数据写入更新到 Cache 里面，再写入到主内存里面；如果数据不在 Cache 里，就只更新主内存。写直达的这个策略很直观，但是问题也很明显，那就是这个策略很慢。无论数据是不是在 Cache 里面，我们都需要把数据写到主内存里面。

第二种写入策略叫写回（Write-Back）

在这个策略里，不再是每次都把数据写入到主内存，而是只写到 CPU Cache 里。只有当 CPU Cache 里面的数据要被“替换”的时候，才把数据写入到主内存里面去。

过程是这样的：

• 如果发现要写入的数据，就在 CPU Cache 里面，那么就只是更新 CPU Cache 里面的数据。同时，会标记 CPU Cache 里的这个 Block 是脏（Dirty）的。所谓脏的，就是指这个时候，我们的 CPU Cache 里面的这个 Block 的数据，和主内存是不一致的。

• 如果要写入的数据所对应的 Cache Block 里，放的是别的内存地址的数据，那么就要看一看，那个 Cache Block 里面的数据有没有被标记成脏的。如果是脏的话，要先把这个 Cache Block 里面的数据，写入到主内存里面。然后，再把当前要写入的数据，写入到 Cache 里，同时把 Cache Block 标记成脏的。

• 如果 Block 里面的数据没有被标记成脏的，那么直接把数据写入到 Cache 里面，然后再把 Cache Block 标记成脏的就好了。

在用了写回这个策略之后，在加载内存数据到 Cache 里面的时候，也要多出一步同步脏 Cache 的动作。如果加载内存里面的数据到 Cache 的时候，发现 Cache Block 里面有脏标记，也要先把 Cache Block 里的数据写回到主内存，才能加载数据覆盖掉 Cache。

可以看到，在写回这个策略里，如果有大量的操作，都能够命中缓存。那么大部分时间里，都不需要读写主内存，性能会比写直达的效果好很多。



Share



这周继续分享耗子叔的文章 别让自己“墙”了自己

这篇文章高速我们：让自己有更多的可能性，能到更高的层次，做更有价值的事，成为更强更好的人。

很受启发，自己现在在小城市工作，受限于家庭，总是不想走出去；耗子叔的这篇文章就是劝我们要更加的开放，所有的问题都是有解的。