ARTS 打卡第 4 周

用户头像
Scotty
关注
发布于: 2020 年 07 月 26 日

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



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

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

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



用户头像

Scotty

关注

我爱编程 Always Be Coding 2017.12.05 加入

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

评论

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