Posts

以下内容转载自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)

什么是Ownership Ownership是Rust中的一个核心特点，可以理解成是Rust做到内存安全的重要手段。不同于带GC的语言或是C/C++这样显式管理内存的语言，ownership系统实现了在编译期管理内存(但又不需要程序员过分手动介入)从而避免了GC开销。 硬要说的话个人感觉像是C++中的RAII，但是由于带有编译器级别的检查，比C++更不容易出错。 Ownership的规则 Rust中所有的值(value)都有一个作为所有者(owner)的变量(variable) (一个值)同时只能有一个owner(参考Rust中赋值的Move语义和在内存管理中起到的作用) 当owner离开作用域(scope)时，其对应的值(value)就会被释放(dropped)(无论是堆上还是栈上的) 解释 Variable Scope 和其他语言类似，变量离开作用域后，就失效了。当一个变量离开作用域时，Rust会自动调用drop 函数，释放内存 Heap and Stack 和C/C++一样，Rust的内存管理也分为堆和栈，栈上内存由操作系统自动管理，堆上内存需要程序员手动管理（Rust中通过Ownership规则和编译器自动插入释放内存的语句，避免像C/C++那样的显式管理） Move Rust中的简单赋值=大多类似于其他语言中的浅拷贝，仅拷贝栈上内容。在Rust中，这种变量和数据交互(interact)的方式称为Move。当发生Move(我理解为“实际”所有权的转移)后，原变量在离开作用域后，编译器不会插入drop，从而避免内存的重复释放 这里还引出Rust的另一个设计思想：Rust永远不会“自动”(automatically)去“深拷贝”数据。因此，默认赋值行为的运行时代价都可以认为是比较低的 String结构示例 let s1 = String::from("hello") let s2 = s1 Clone 那么如果我们真的需要深拷贝一块数据需要怎么做呢，在Rust中需要显式调用clone。这实际上也是显式提醒程序员，这里有一段特殊的代码要执行，有可能消耗会比较大 fn main() { let s1 = String::from("hello"); let s2 = s1.clone(); println!("s1 = {}, s2 = {}", s1, s2); } Another wrinkle: Stack-Only Data 一些简单数据类型，像整型，我们不调用clone，也不是Move语义，原因在于，这些简单类型在编译期就能确定大小，并且完全存储于栈上，所以拷贝比较快。 Rust中有一种特殊的注解(annotation) Copytrait, 实现了这个trait类型的变量在赋值后依然可以使用。但如果实现了Droptrait，Copy就无法使用 什么样的类型可以实现Copytrait呢？可以参考官方文档，通常来说，没有需要分配资源的类型可以实现。以下是一些实现了Copy的类型 所有整型，如u32 Boolean类型,bool 浮点型, 如f64 字符类型，char 元组(Tuples)，当然只能包含同样实现Copy的类型，如(i32, i32)实现了，但(i32, String)没有 Functions 函数中传参和返回值也一样有ownership的转移问题，传参即赋值，返回值会将ownship move到调用它的函数 ...