#1039 : 字符消除
from http://hihocoder.com/problemset/problem/1039
描述 小Hi最近在玩一个字符消除游戏。给定一个只包含大写字母”ABC”的字符串s，消除过程是如下进行的：
Read more...质数分解
将n分解质因数的高效代码
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0&&(n/=i))
{
cout<< i--; //i可以被整除，i--抵消for中的i++继续除i
}
}
cout<< n; // n最后也为一个质因数
一般方法:
i从2开始到sqrt(n)的每一个i由n试除，如果能整除就再判断i是不是素数,如果是则i是n的一个质因子,然后n=n/i ，再将i归位回2 再寻找n的质因子
优化:
大致思路不变，进行了一些剪枝，首先还是i从2开始到sqrt(n)的每一个i由n试除 ,如果i能整除n，那么不用判断i，i必为n的质因子，将n=n/i ， 因为n可能有多个相同的质因子，为了避免遗漏，只需将i– ，当跳到下一步循环的时候与i++抵消，i的值不变，由于由2~i的每一个数都已经判断过是否能整除n，所以不必要再将i回退到2，只需另i在跳到下步循环的时候值不变即可，最后n也会被约成质数，也是一个质因子,这个优化来自 Here。
上面for循环中，求开方每次都有计算可以优化一下：
for(int i=2,sqr=sqrt(n);i<=sqr;i++)
{
if(n%i==0&&(n/=i))
{
sqr=sqrt(n);
cout<< i--;
}
}
cout<< n;
再改进，因为质数中除2外都是奇数，所以i可以一次前进两步：
while(n%2==0)
{
cout<<2;
n/=2;
}
for(int i=3,sqr=sqrt(n);i<=sqr;i+=2)
{
if(n%i==0&&(n/=i))
{
sqr=sqrt(n);
cout<< i;
i-=2;
}
}
cout<< n;
最长公共子序列和最长公共子串
问题定义：
最长公共子序列，序列的意思是顺序对就可以，并不需要是连续的。例如：
ABCDE
OALBLCLDLE
其中ABCDE就是这两个字符串的最长公共子序列。
容易知道一个长度为n的字符串的子序列有\(2^n\)个，假设两个字符串的长度都为n，直接去求解两个字符串的最长公共子序列需要用这\(2^n\)个序列串去匹配另外一个字符串，匹配一次的时间复杂度为\(O(n)\)，则总的时间复杂度为\(O(n·2^n)\) ，显然效率非常之低。
最长公共子串，和上面最长公共子序列不同的地方在于需要匹配连续的字符串。直接求解的话，需要找到所有的公共子串，保留最长的即可。一个长度为n的字符串的子串个数可以有：
\[1+2+3+...+n=(n+1)n/2\]上式每项分别对应于子串长度为\(n,n-1,n-2,n-3,...,1\)的子串个数。每个子串和另一个字符串进行匹配时间复杂度为\(O(mn)\)，m为子串长度，总时间复杂度约为\(O(n^4)\).这样按子串长度排序，从最长开始匹配，如果匹配上了就退出。
简单的优化就是可以简单的通过记录子串的开始位置，然后依次进行比较找到最长，这样并不需要取出所有子串，如果不考虑字符串比较的时间，时间复杂度为\(O(n^2)\), 但是进行串比较时，时间并不是\(O(1)\)所以总的时间应该在\(O(n^2)\)和\(O(n^3)\) ,最坏情况出现在两个字符串完全相同的情况，这种情况下还是要比较完所有子串，每次子串比较耗时也最长。 上面这种考虑的代码：
//from Ider's blog
int longestCommonSubstring_n3(const string& str1, const string& str2)
{
size_t size1 = str1.size();
size_t size2 = str2.size();
if (size1 == 0 || size2 == 0) return 0;
// the start position of substring in original string
int start1 = -1;
int start2 = -1;
// the longest length of common substring
int longest = 0;
// record how many comparisons the solution did;
// it can be used to know which algorithm is better
int comparisons = 0;
for (int i = 0; i < size1; ++i)
{
for (int j = 0; j < size2; ++j)
{
// find longest length of prefix
int length = 0;
int m = i;
int n = j;
while(m < size1 && n < size2)
{
++comparisons;
if (str1[m] != str2[n]) break;
++length;
++m;
++n;
}
if (longest < length)
{
longest = length;
start1 = i;
start2 = j;
}
}
}
#ifdef IDER_DEBUG
cout<< "(first, second, comparisions) = ("
<< start1 << ", " << start2 << ", " << comparisons
<< ")" << endl;
#endif
return longest;
}
malloc的实现原理
CS:APP 《深入理解操作系统》提供了一个实现malloc的小project. 为了弄清楚malloc的实现原理，这两天调研了一下，记录如下。
##1.进程空间
Linux的虚拟内存空间使得每个进程都有一个独立的进程空间，使用地址转换机制把虚存地址转换为物理地址.在进程看来它拥有全部的4G寻址空间(32位系统),然而实际上进程是受操作系统管理的，它只是在理论上拥有全部的寻址空间，实际运行中操作系统只分配了部分物理空间给特定的进程，因为“局部性”原理，虚拟内存空间得以高效的实现。
Linux中进程的控制块(PCB)用一个task_struct 数据结构表示，这个数据结构记录了所有进程信息，包括进程状态、进程调度信息、标示符、进程通信相关信息、进程连接信息、时间和定时器、文件系统信息、虚拟内存信息等，具体参见task_struct结构描述. 这里和malloc密切相关的就是虚拟内存信息，定义为Struct mm_struct *mm
具体描述进程的地址空间.mm_struct结构是对整个用户空间（进程空间）的描述。
mm_strcut 用来描述一个进程的虚拟地址空间，在/include/linux/sched.h 中描述如下：
struct mm_struct {
struct vm_area_struct * mmap; /* 指向虚拟区间（VMA）链表 */
rb_root_t mm_rb; ／*指向red_black树*/
struct vm_area_struct * mmap_cache; /* 指向最近找到的虚拟区间*/
pgd_t * pgd; ／*指向进程的页目录*/
atomic_t mm_users; /* 用户空间中的有多少用户*/
atomic_t mm_count; /* 对"struct mm_struct"有多少引用*/
int map_count; /* 虚拟区间的个数*/
struct rw_semaphore mmap_sem;
spinlock_t page_table_lock; /* 保护任务页表和 mm->rss */
struct list_head mmlist; /*所有活动（active）mm的链表 */
unsigned long start_code, end_code, start_data, end_data;
unsigned long start_brk, brk, start_stack; /*堆栈相关*/
unsigned long arg_start, arg_end, env_start, env_end;
unsigned long rss, total_vm, locked_vm;
unsigned long def_flags;
unsigned long cpu_vm_mask;
unsigned long swap_address;
unsigned dumpable:1;
/* Architecture-specific MM context */
mm_context_t context;
};
其中start_brk 和brk分别是堆的起始和终止地址，我们使用malloc动态分配的内存就在这之间。start_stack是进程栈的起始地址，栈的大小是在编译时期确定的，在运行时不能改变。而堆的大小由start_brk 和brk决定，但是可以使用系统调用sbrk() 或brk()增加brk的值，达到增大堆空间的效果，但是系统调用代价太大，涉及到用户态和核心态的相互转换。所以，实际中系统分配较大的堆空间，进程通过malloc()库函数在堆上进行空间动态分配，堆如果不够用malloc可以进行系统调用，增大brk的值。
Linux中对虚拟内存空间采用分区域进行管理，struct vm_area_struct 数据结构描述了一个虚拟区域，对这个虚拟区域使用双链表或者红黑树进行管理，这样在进行寻址的时候先找虚拟区域。详见虚拟空间的数据结构
这一部分就是malloc底层依赖的相关信息了，但是这对用户进程来说是透明的，总结一下：malloc只知道start_brk 和brk之间连续可用的内存空间它可用任意分配，如果不够用了就向系统申请增大brk。后面一部分主要就malloc如何分配内存进行说明。
##2.内存分配
malloc进行内存分配的时候有很多种策略可以使用，不同的策略运用了不同的数据表示方式，也有不同的性能。这里可以发现数据结构和算法在计算机世界中真的是无处不在，上面对虚拟区间进行管理的时候也说了可用使用双链表或者AVL树、红黑树，在不同情形下有不同的效率。
通过上面的储备，可以知道malloc进行内存分配的时候，可以认为它面对的是一个连续的大数组，要把这个大数组的空间分配给动态内存请求，同时还要处理内存释放。这就需要用一个有效的策略处理内存分配和释放任务，下面涉及到的方法来自《深入理解操作系统》，这里仅简要介绍作为记录，需要详细了解请参考该书动态内存分配部分章节。
动态内存分配不仅要高效的响应动态内存请求，而且也要堆内存释放做出合理的操作，既要保证高效也要保证不浪费空间。处理内存分配碎片，空闲块合并等等。在《深入理解操作系统》中有详细的介绍，这里就不累述。
###A.隐含链表方式
隐含链表方式即在每一块空闲或被分配的内存块中使用一个字的空间来保存此块大小信息和标记是否被占用。根据内存块大小信息可以索引到下一个内存块，这样就形成了一个隐含链表，通过查表进行内存分配。
###B.显示空闲链表
显示空闲链表的方法，和隐含链表方式相似，唯一不同就是在空闲内存块中增加两个指针，指向前后的空闲内存块。
###C.多链表
根据空闲的内存块的不同大小建立多个链表，在分配内存时根据请求大小之间到接近链表中去查找空闲块。
###D.高级方式
前面的几种方法非常简单，但是效率也不高，实际中只在特定情况会使用，通常情况下并不使用这些策略。实际中通常使用红黑树、Splay树等平衡二叉查找树管理空闲块，块大小作为关键字这样可用快速找到合适的内存进行分配。更多可用参考wiki。
##3.总结
本文主要对malloc背后的原理进行了探究，简要了解了Linux操作系统中实现进程控制的数据结构task_struct，重点介绍了其中关于虚拟空间管理的mm_struct，进程中堆空间通过start_brk 和brk进行控制，而malloc的功能就是对start_brk 和brk之间的连续空间进行动态的分配和释放，这里可以使用不同的策略得到不同的效率是空间利用，全文对malloc的功能从原理上进行了总体探究。
Git 使用笔记
方法:
git reset --hard <commit_id>
git push origin HEAD --force