Posts

什么是内存模型 Go的内存模型特指在并发的场景下，一个goroutine所写的变量在另一个goroutine能在哪些情况下被观察到 在计算中，内存模型描述了多线程如何通过内存的交互来共享数据 官方建议 程序可能会并发地访问/修改一些变量，多个goroutine的并发访问一定要保证“可串行化”，尤其是绝对不允许出现数据竞争的场景下 为了保证数据访问的串行化访问，没有数据竞争，在Go语言中，尽量通过channel或者各种同步原语对数据的并发访问进行保护，例如sync 、sync/atomic等 强烈推荐阅读官方文档 If you must read the rest of this document to understand the behavior of your program, you are being too clever. Don’t be clever. C语言中的内存可见性 内存可见性是一个通用性质的问题，类似于 c/c++，golang，java 都存在相应的策略。作为比较，我们先思考下 c 语言，在 c 里面却几乎没有 happens-before 的理论规则，究其原因还是由于 c 太底层了，常见 c 的内存可见性一般用两个比较原始的手段来保证： volatile 关键字（很多语言都有这个关键字，但是含义大相径庭，这里只讨论 c ） memory barrier volatile volatile 声明的变量不会被编译器优化掉，在访问的时候能确保从内存获取，否则很有可能变量的读写都暂时只在寄存器。但是，c 里面的 volatile 关键字并不能确保严格的 happens-before 关系，也不能阻止 cpu 指令的乱序执行，且 volatile 也不能保证原子操作。 以一个常见的c代码为例： // done 为全局变量 int done = 0; while ( ! done ) { /* 循环内容 */ } // done 的值，会在另一个线程里会修改成 1； 这段代码，编译器根据自己的优化理解，可能在编译期间直接展开翻译成（或者每次都直接取寄存器里的值，寄存器里永远存的是 0 ）： ...

本文系转载 关于看别人的代码 自己曾是过来人，经常遇到刚毕业的同学很反感看别人的代码，也很反感使用别人的代码，甚至与他人协作开发还有点小抗拒 据我个人总结，出现这种问题的根本原因，是因为经验不足，无法瞬间秒懂别人写的代码（其他的原因可能根本原因都是这个），以前我觉得自己太菜了感觉分享此类心得会被人笑话，但是现在，我阅码无数，因工作原因腾讯几大最热门游戏源码我都瞄过，且因本人目前工作关系，几乎查阅过字节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.