本文系转载 关于看别人的代码 自己曾是过来人，经常遇到刚毕业的同学很反感看别人的代码，也很反感使用别人的代码，甚至与他人协作开发还有点小抗拒 据我个人总结，出现这种问题的根本原因，是因为经验不足，无法瞬间秒懂别人写的代码（其他的原因可能根本原因都是这个），以前我觉得自己太菜了感觉分享此类心得会被人笑话，但是现在，我阅码无数，因工作原因腾讯几大最热门游戏源码我都瞄过，且因本人目前工作关系，几乎查阅过字节80%游戏的反编译代码，我有多年的逆向分析经验，如何快速定位感兴趣的代码也有些许心得。然后我来分享几点，如何超高速秒懂别人代码的几个心得。 在讨论心得之前，先讲一个理论原则，这个原则应该是科班《数据结构》里的内容，大意是指一个程序的输出仅与输入（输入不仅包括UI输入，控制台输入，也包括网络输入，甚至随机数也算是输入，任何外部的数据都算输入）有关。好，记住这点，将大大加快你阅码速度。 首先，第一点，最简单，也是最吃经验的一点，就是面对一份庞大的代码，如何快速定位自己感兴趣的代码，这最简单的一点就是全局搜索字符串和猜测函数名，这点应该都是大家的共识，函数名猜测，这是共识，就跟公理一样不需要证明了（当然也吃经验和英语水平）。另外是字符串搜索，一个程序，目光所及固定可见字符串，90%都可以在源代码中找到，关键代码基本上就在附近。 其次，是找关键代码的思维，不好描述，我举个例子： 比如你想找一个游戏代码里面发包相关的函数，通过Send关键字搜索发现没有相关函数的时候，此时可以换种思维，思考一下发包上下游关系，发包可能要对包进行压缩，加密，可以尝试搜索compress，encrypt等关键字，交叉引用看看是否有你感兴趣的代码，也可以通过上游的Login看看有没有关键的函数，Logon啊这些，甚至是相近的 Message，Msg啊这些都可以是关键字进行搜索，如果百般尝试最终无果的话，动用我们linux系统调用的“原子技术”，从send一步步反推吧~。 有一些好的项目，基本上从文件名就可以知道这个文件做了什么功能的。如果以上，可能比较吃经验，那么以下这个，我应该可以把这个过程讲清楚 找到了代码之后如何看懂（这里的看懂，指的是了解这个函数哪些做了什么事情，输出了什么东西）呢？ 看懂一个函数，无非是看懂这个函数对哪些数据做了什么处理，最终对外输出了什么数据，因为函数的本质就是这个，函数无法再做其他事情了，所以，此时，你需要一个能将某个变量高亮的IDE，选中所有参数，看看函数对参数做了什么处理，应该是一目了然，秒懂应该没有问题，接下来以C讲几个特殊case分支（以下讲解仅限值传递类语言，比如C。引用传递类语言例如java，C#等的除外，看完应该也应该知道为什么要除外了） 参数进入了另一个函数，如果此参数前没有&，那么直接忽略 参数进入了另一个函数，如果此参数前面有&，那么跟进此函数，循环本过程看懂该子函数 高亮返回值和指针进来的参数，看如何构造的返回值以及有没有对指针参数指向内容进行修改，因为不高亮的地方，不用黑科技是改不了的 如果中间有赋值的地方，高亮赋值后的变量继续看 注意看一下，此函数有没有对全局变量做处理 如果是引用传递类的语言，比如java，C++（C++属于显式引用传递，看一下子函数形参里有没有&就知道了），C#这类语言就麻烦一点，可能还要跟进每个子函数看下，有没有做处理 如果是面向对象类的语言，可能还要麻烦点，因为有个this指针，本函数可能无形当中还会对本对象进行一些修改，注意那些凭空多出来的没有定义就拿来用的变量就行（所以，你们现在清楚将成员变量命名为m_开头是多么重要了吧？因为能让别人秒懂！） 好了，讲完了，讲完了，之后，也许有人已经知道了 linus大神为何如此不待见C++了吧，因为C++的确是一门自己用起来很爽，但是要让别人看懂你写的代码，的确可以让人口吐芬芳。据我这么多年的经验，在看懂别人写的代码难易程度上，C最简单，C#次之，C++最难懂（仅根据语言特性来分，无关我对这些语言的熟悉程度，特性一样的语言效果等同）。 当你看懂了一个函数的输入输出以后，你基本上已经认定了这个写法是没问题的，不然如果代码有bug，你在查阅的时候应该就已经发现了。所以，此时此刻，你再使用别人的代码，或者修改别人的代码，还有那么抗拒吗？

以下内容转载自https://stackoverflow.com/questions/30548170/dfa-construction-in-knuth-morris-pratt-algorithm，帮助理解KMP算法中根据模式串构造DFA，以及与LPS的关系 Question I am referring to the outline of the Knuth-Morris-Pratt (KMP) algorithm for substring search in Sedgewick’s book “Algorithms” (4th ed.). The KMP algorithm uses a backup in substring search based on a deterministic finite automaton (DFA). I understand how the DFA enters the algorithm, however I don’t understand how to construct the DFA, which is done by the following code snippet: dfa[pat.charAt(0)][0] = 1; for (int X = 0; j = 1; j< M; j++) { for (int c = 0; c < R; c++) { dfa[c][j] = dfa[c][X]; } dfa[pat.charAt(j)][j] = j+1; X = dfa[pat.charAt(j)][X]; } where M is the the length of the pattern pat and R the size of the alphabet. The charAt() function returns the integer value of the character at the respective position. ...

稳定婚姻问题 Stable Marriage Problem定义 两个集合men、women数量相等，每个人持有对异性的好感度顺序表。现在假定要对这n对进行匹配，如果某种匹配存在同时满足以下三个条件的m-w对(blocking-pair)，则认为此匹配是不稳定的：1)m和w目前没有订婚（意味着它们的订婚对象是别人） 2) 在m的优先级列表中，w的级别比当前订婚对象高 3) 在w的优先级列表中，m的优先级比当前订婚对象优先级高。 反之则称这个匹配是稳定的。在这样一个场景中求解稳定订婚关系的问题，称之为稳定婚姻问题 常见变种 SMI:(SM with Incomplete lists) SMT:(SM with Ties) 按照稳定条件依次减弱 super-stability strong stability weak stability: 总是存在解，并能在多项式时间内解决 SMTI(SM with Ties and Incomplete lists) 三种稳定关系定义，同上 super/strong关系，存在算法可以确定一个问题是否有解，以及求出一个解，super stability时间复杂度O(a), strong stabilityO(na)， a表示所有优先级列表的整体长度（2n^2如果所有优先级列表都是完整的），且所有的解都具有相同的大小 weak stablity，任何情况下都存在一个稳定匹配，并且可以在O(a)时间内找到，但是解的大小可以有多个，求解其中最大的那个是NP-Hard的 经典解法 Gale-Shapley Algorithm algorithm stable_matching is Initialize all m ∈ M and w ∈ W to free while ∃ free man m who still has a woman w to propose to do w := first woman on m's list to whom m has not yet proposed if w is free then (m, w) become engaged else some pair (m', w) already exists if w prefers m to m' then m' becomes free (m, w) become engaged else (m', w) remain engaged end if end if repeat 按轮次进行 ...

Concept A partial reference of a contiguous sequence of elements in a collection. contiguous a data type that does not have ownership Usage String Slices let s = String::from("hello world"); let hello = &s[0..5]; let world = &s[6..11]; Like others languages, we can simpify the syntax if we want to start at the first index(zero) or include the last byte of String #![allow(unused)] fn main() { let s = String::from("hello"); let slice = &s[0..2]; let slice = &s[..2]; } #![allow(unused)] fn main() { let s = String::from("hello"); let len = s.len(); let slice = &s[3..len]; let slice = &s[3..]; } #![allow(unused)] fn main() { let s = String::from("hello"); let len = s.len(); let slice = &s[0..len]; let slice = &s[..]; } Attention String slice range indices must occur at valid UTF-8 character boundaries. String literals are slices Using string slices as parameters usually make our API more general and useful without losing any functionality.

References Something like &String, the concept is similar to a Pointer in C/C++/Golang/… It will not take the ownership, thus we can drop some tuple code to make it simpler. Borrowing having references as function parameters Scope A reference’s scope starts from where it is introduced and continues through the last time that reference is used. let mut s = String::from("hello"); let r1 = &s; // no problem let r2 = &s; // no problem println!("{} and {}", r1, r2); // r1 and r2 are no longer used after this point let r3 = &mut s; // no problem println!("{}", r3); Recapitulation At any given time, you can have either one mutable or any number of immutable references. References must always be valid. (Dangling references will not be allowed in Rust by compiler)