一、介绍
 
1、一维离散傅里叶变换DFT。
 
        DFT:(Discrete Fourier Transform)离散傅里叶变换是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其DTFT的频域采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作其周期延拓的变换。
 
        根据欧拉公式，其中，i为虚数单位，即。
 
        公式

我自己搭建了博客，以后可能不太在CSDN上发博文了，https://www.qingdujun.com/ 。
 
 
去年写了一篇《分治算法 求第$k$小元素 $O(n)$ & $O(nlog{2}^n$)》的文章。介绍了一种对快排进行改进的算法，可以在时间复杂度$O(n)$的情况下，找到第$k$小的数字。
 
那时候，我还不知道这个算法叫BFPRT算法——现在知道了，还知道它又被称为中位数的中位数算法，它的最坏时间复杂度为$O(n)$ ，它是由Blum、Floyd、Pratt、Rivest、Tarjan提出，它的思想是修改快速选择算法的主元选取方法，提高算法在最坏情况下的时间复杂度。
 
1 STL std::nth_element
 
而且，我还发现了STL中有一个类似的函数——std::nth_element （位于头文件<algorithm>中）:
 http://www.cplusplus.com/reference/algorithm/nth_element/
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main() {
    std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
    std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
    std::cout << "The median is " << v[v.size()/2] << '\n';
    std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());
    std::cout << "The second largest element is " << v[1] << '\n';
}
 
The median is 5
 The second largest element is 7
 
2 BFPRT算法(中位数的中位数算法)
 
好了，言归正传。BFPRT算法主要由两部分组成（快排、基准选取函数）。基准选取函数也就是中位数的中位数算法（Median of Medians algorithm）的实现，具体来说——就是将快排中基准选取策略进行了优化，改为每次尽可能的选择中位数作为基准。
 
那么是如何尽可能的选出中位数？ 如果要找到一个精确的中位数，所消耗的时间代价将得不偿失，而且对于快排算法来说，只要基准尽可能的接近真正的中位数，就能形成近似的均分。我在上一篇文章中举了个例子，这里我再重复一遍：
 
2.1 举个例子
 
假设，我们要找arr[18]的近似中位数——其实，也就是找到数字8。（注意到，由于使用了分组，这里产生的只是尽可能的中位数）
 
int arr[18] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };
 
BFPRT算法规定了，将5个元素作为一组（选出中位数）。然后，再选出中位数中的中位数…一直到，最终选出一个数字。
 
那么，第一轮就是这样（将选出的中位数放置在最前面）：
 
//执行momedians之前
{ 1,2,3,4,5} {6,7,8,9,10} {11,12,13,14,15} {16,17,18 };
 
分别对每组sort后选取小组中位数，再使用swap将小组中位数放置在“最前面”对应位置（注意下文中*号的标注，它表示这一步选出的小组中位数放置到哪儿去了）。
 
//开始momedians
{ 3*,2,1*,4,5};//sort->swap(3,1)
{ 3,8*,1,4,5} {6,7,2*,9,10};//sort->swap(8,2)
{ 3,8,13*,4,5} {6,7,2,9,10} {11,12,1*,14,15};//sort->swap(13,1)
{ 3,8,13,17*,5} {6,7,2,9,10} {11,12,1,14,15} {16,4*,18 };//sort->swap(17,4)
 
同样，第二轮初始时就成如下样子了，很显然已经少于5个数字了：
 
//执行momedians之前
{ 3,8,13,17};
 
直接选出中位数8。
 
2.2 算法实现(c++)
 
可以将上述过程使用C++代码描述如下（对于5个数字的排序，使用Insert sort可能会效率更高）。再次强调，下面这段代码唯一的作用，就是用来选出每次快排的基准：
 
//Median of Medians algorithm
int momedians(int* const low, int* const high) {
	if (low >= high - 1) {
		return *low;
	}
	//int grp_length = (int)std::sqrt(high - low);
	int grp_length = 5, grp_idx = 0;
	for (int* l = low, *r; l < high; l = r+1) {
		r = (l + grp_length >= high) ? high : l + grp_length - 1;
		std::sort(l, r); //可以使用下文的void isort(int* const low, int* const high)
		std::swap(*(low+grp_idx++), *(l + (r - l) / 2));
	}
	return momedians(low, low + grp_idx);
}
 
写到这里已经将BFPRT算法核心介绍完毕了。
 
如果想测试使用Insert sort是否会带来效率上提升的小伙伴，可以试试下面这段代码insert_sort，尝试着替换文中的std::sort排序函数。
 
//Insert sort
void insert_sort(int* const low, int* const high) {
	for (int* i = low + 1; i <= high; ++i) {
		if (*i < *(i-1)) {
			int border = *i, *j = i-1;
			for ( ; border < *j; --j) {
				*(j+1) = *j;
			}
			*(j+1) = border;
		}
	}
}
 
让我们思维次再回到momedians函数。从上述代码中可以看到grp_length = 5是一个固定值。那么，在BFPRT算法中，为什么是选5个作为分组？ 这个我也不是很明白，我也尝试使用sqrt(数组长度)作为分组的长度。
 
有兴趣的可以阅读 ACdreamer 的一篇《BFPRT算法原理》，他在文章结尾处，对为什么使用5作为固定分组长度进行了简单说明。同时，还附有BFPRT算法的最坏时间复杂度为 $O(n)$ 的证明。
 
好了，以下为完整的“BFPRT算法：时间复杂度$O(n)$求第k小的数字”代码。如上文所说，算法主体功能是快排，只是在基准选取的时候使用了momedians算法——而不是直接取第一个数作为基准（严蔚敏版教材中的做法）。
 
#include <iostream>
#include <algorithm>
using namespace std;

//Median of Medians algorithm
int momedians(int* const low, int* const high) {
	if (low >= high - 1) {
		return *low;
	}
	int grp_length = 5, grp_idx = 0;
	for (int* l = low, *r; l < high; l = r+1) {
		r = (l + grp_length >= high) ? high : l + grp_length - 1;
		std::sort(l, r);
		std::swap(*(low+grp_idx++), *(l + (r - l) / 2));
	}
	return momedians(low, low + grp_idx);
}

//Quick sort
int qsort(int* const low, int* const high, int* const ptrk) {
	int* l = low, *r = high;
	if (l < r) {
		int pivot = momedians(l, r);
		while (l < r) {
			while (l < r && *r >= pivot) {
				--r;
			}
			*l = *r;
			while (l < r && *l <= pivot) {
				++l;
			}
			*r = *l;
		}
		*r = pivot;
	}
	//per qsort end, check left == right == ptrk?
	return r == ptrk ? *ptrk :
		(r > ptrk ?
			qsort(low, r - 1, ptrk) :
			qsort(r + 1, high, ptrk));
}

//Blum、Floyd、Pratt、Rivest、Tarjan
int bfprt(int* const low, int* const high, const int k = 1) {
	if (low >= high || k < 1 || k > high - low) {
		throw std::invalid_argument("low > high || k < 1");
	}
	return qsort(low, high-1, low + k -1);//[low, high)
}

int main() {
	int arr[18] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };
	//cout << bfprt(&arr[0], &arr[0]+1, 1) << endl;
	cout << bfprt(&arr[0], &arr[0] + 18, 18) << endl;

	return 0;
}
 
以上的代码是针对int数组编写的，下面再测试一下对于其他类型的支持情况（这里直接粗暴的加上了一个模板）。有一点想强调的是，这里的bfprt函数参数是左闭右开区间[low,high)，同时k必须是从1开始的正数。
 
//Blum、Floyd、Pratt、Rivest、Tarjan
template<typename T>
T bfprt(T* const low, T* const high, const int k = 1) {
	if (low >= high || k < 1 || k > high - low) {
		throw std::invalid_argument("low > high || k < 1");
	}
	return qsort(low, high-1, low + k -1);//[low, high)
}
 
在main函数中对int、char、string类型进行了测试。完整代码如下…
 
#include <iostream>
#include <algorithm>
using namespace std;

//Median of Medians algorithm
template<typename T>
T momedians(T* const low, T* const high) {
	if (low >= high - 1) {
		return *low;
	}
	int grp_length = 5, grp_idx = 0;
	for (T* l = low, *r; l < high; l = r+1) {
		r = (l + grp_length >= high) ? high : l + grp_length - 1;
		std::sort(l, r);
		std::swap(*(low+grp_idx++), *(l + (r - l) / 2));
	}
	return momedians(low, low + grp_idx);
}

//Quick sort
template<typename T>
T qsort(T* const low, T* const high, T* const ptrk) {
	T* l = low, *r = high;
	if (l < r) {
		T pivot = momedians(l, r);
		while (l < r) {
			while (l < r && *r >= pivot) {
				--r;
			}
			*l = *r;
			while (l < r && *l <= pivot) {
				++l;
			}
			*r = *l;
		}
		*r = pivot;
	}
	//per qsort end, check left == right == ptrk?
	return r == ptrk ? *ptrk :
		(r > ptrk ?
			qsort(low, r - 1, ptrk) :
			qsort(r + 1, high, ptrk));
}

//Blum、Floyd、Pratt、Rivest、Tarjan
template<typename T>
T bfprt(T* const low, T* const high, const int k = 1) {
	if (low >= high || k < 1 || k > high - low) {
		throw std::invalid_argument("low > high || k < 1");
	}
	return qsort(low, high-1, low + k -1);//[low, high)
}

int main() {
	int arr[18] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18 };
	cout << bfprt(&arr[0], &arr[0] + 18, 18) << endl;

	char str[7] = {'a','b','c','d','e','f','g'};
	cout << bfprt(&str[0], &str[0] + 7, 4) << endl;

	string s = "abcdefghijklmnopqrstuvwxyz";
	cout << bfprt(&s[0], &s[0] + 26, 10) << endl;
	
	return 0;
}
 


 

  ©qingdujun
 
2018-12-25 北京 海淀 
 



 
References:
 [1] 为径，分治算法 求第k小元素 $O(n)$ & $O(nlog{2}^n)$ ，2018-12-25
 [2] ACdreamer，BFPRT算法原理 ，2018-12-25
 [3] STL nth_element() , 2018-12-25

拿到代码的时候

 
1、最好先看目录结构并找到配置文件

 
2、以自己的开发经验去判断大概的程序架构，理清楚是否为单点入口，

 
3、让把程序运行起来

 

 
没有数据库的情况下运行起来可能会错误很多，不过这些错误可以引导你对程序理解，对着错误提示，跟踪代码脉络，很容易就把整个系统拿上手了。
 

 
 
我通常是局部功能研究着手，研究一个功能的走向流程，那么基本可以熟悉他的基本工作模式来，然后在逐步的推敲框架结构
 
 

 
 
先看下是否有框架，如果有框架，去看下框架文档就知道了
 如果没有框架，看是否能出框架的出口和入口入手了
 
 

 
 
先看下 目录结构
 使用xdebug生成profile文件，可以用KCachegrind来查看，但是这个工具只在linux下面可用，没有windows下的版本。这里推荐一个win下的免费工具——wincachegrind，也可以查看xdebug的profile文件，用来分析php代码运行情况足够用了（偶尔不太稳定）。
 
 有代码的流程，大部分的项目就可以知道整个代码流程了，
 具体逻辑的东西，就只能你自己慢慢体会。
 奇吧太多了
 
 

 
 
开源的吗? 如果有文档的话 当然是先看文档了 如果没有的话就用调试工具吧 比如Zend Studio什么的
 
 

 
 
好像没有快速的方法。我的做法是看着代码在脑中跑一遍，了解大概流程，然后再细看。
 
 

 
 
 
 
 

  如果没注释的话很困难，如果有phpDocumenter的标准注释可以用它来生成文档
 
 
 

  
 
 
 
 

  
 
 
 
 

  一个源码首先第一步不看代码，看结构，大致知道采用的是那种设计模式，例如函数式的还是mvc方式的，接下来从一个功能入手，先用firebug或者chrome的工具查看请求的url,以及请求url后web前端表现出来的，接下来，上面的模式用到了，去看url对于的方法吧，方法中必定会调用其他的方法，层层递进，分析下来，这个小功能的实现懂了吧，然后多多分析各个功能的实现，大致这个源码的结构熟悉了，那么带着前端的一些操作去摸索各个功能点的实现方法吧
  
 
 
 
 

  
 
 
 
 

  
 
 
 
 

  1、拿到代码查看项目当中是否有readme这样的文件，如果没有查看是否有文档之类的
 
 
 

  2、代码当中没有文档，那么就想你的同事或者其他人要这个框架的介绍或者资料
 
 
 

  3、先请教别人这个框架的大体思路
 
 
 

  4、自己独立去按照文档或者其他人说的思路去看代码
 
 
 

  5、不懂的地方全部记录下面，一次行去问，有的时候很多问题在你看到后面的东西的时候就自然明白了
 
 
 

  6、看懂了代码之后自己尝试着写一个，看自己的理解是否正确就这么多了。
 
 
 
 

  
 
 
 
 

  
 
 
 
 

  先了解整体流程,在个个击破~!
 
 
 
 

  
 
 
 
 

  第一章: 导论
 
 ++++++++++++
 
 
 1.要养成一个习惯, 经常花时间阅读别人编写的高品质代码.
 
 2.要有选择地阅读代码, 同时, 还要有自己的目标. 您是想学习新的模式|编码风格|还是满足某些需求的方法.
 
 3.要注意并重视代码中特殊的非功能性需求, 这些需求也许会导致特殊的实现风格.
 
 4.在现有的代码上工作时, 请与作者和维护人员进行必要的协调, 以避免重复劳动或产生厌恶情绪.
 
 5.请将从开放源码软件中得到的益处看作是一项贷款, 尽可能地寻找各种方式来回报开放源码社团.
 
 6.多数情况下, 如果您想要了解"别人会如何完成这个功能呢?", 除了阅读代码以外, 没有更好的方法.
 
 7.在寻找bug时, 请从问题的表现形式到问题的根源来分析代码. 不要沿着不相关的路径(误入歧途).
 
 8.我们要充分利用调试器|编译器给出的警告或输出的符号代码|系统调用跟踪器|数据库结构化查询语言的日志机制|包转储工具和Windows的消息侦查程序, 定出的bug的位置.
 
 9.对于那些大型且组织良好的系统, 您只需要最低限度地了解它的全部功能, 就能够对它做出修改.
 
 10.当向系统中增加新功能时, 首先的任务就是找到实现类似特性的代码, 将它作为待实现功能的模板.
 
 11.从特性的功能描述到代码的实现, 可以按照字符串消息, 或使用关键词来搜索代码.
 
 12.在移植代码或修改接口时, 您可以通过编译器直接定位出问题涉及的范围, 从而减少代码阅读的工作量.
 
 13.进行重构时, 您从一个能够正常工作的系统开始做起, 希望确保结束时系统能够正常工作. 一套恰当的测试用例(test case)可以帮助您满足此项约束.
 
 14.阅读代码寻找重构机会时, 先从系统的构架开始, 然后逐步细化, 能够获得最大的效益.
 
 15.代码的可重用性是一个很诱人, 但难以理解与分离, 可以试着寻找粒度更大一些的包, 甚至其他代码.
 
 16.在复查软件系统时, 要注意, 系统是由很多部分组成的, 不仅仅只是执行语句. 还要注意分析以下内容: 文件和目录结构|生成和配置过程|
 
 用户界面和系统的文档.
 
 18.可以将软件复查作为一个学习|讲授|援之以手和接受帮助的机会.
 
 ++++++++++++++++++++
 
 第二章: 基本编程元素
 
 ++++++++++++++++++++
 
 
 
 19.第一次分析一个程序时, main是一个好的起始点.
 
 20.层叠if-else if-...-else序列可以看作是由互斥选择项组成的选择结构.
 
 21.有时, 要想了解程序在某一方面的功能, 运行它可能比阅读源代码更为恰当.
 
 22.在分析重要的程序时, 最好首先识别出重要的组成部分.
 
 23.了解局部的命名约定, 利用它们来猜测变量和函数的功能用途.
 
 24.当基于猜测修改代码时, 您应该设计能够验证最初假设的过程. 这个过程可能包括用编译器进行检查|引入断言|或者执行适当的测试用例.
 
 25.理解了代码的某一部分, 可能帮助你理解余下的代码.
 
 26.解决困难的代码要从容易的部分入手.
 
 27.要养成遇到库元素就去阅读相关文档的习惯; 这将会增强您阅读和编写代码的能力.
 
 28.代码阅读有许多可选择的策略: 自底向上和自顶向下的分析|应用试探法和检查注释和外部文档, 应该依据问题的需要尝试所有这些方法.
 
 29.for (i=0; i<n; i++)形式的循环执行n次; 其他任何形式都要小心.
 
 30.涉及两项不等测试(其中一项包括相等条件)的比较表达式可以看作是区间成员测试.
 
 31.我们经常可以将表达式应用在样本数据上, 借以了解它的含义.
 
 32.使用De Morgan法则简化复杂的逻辑表达式.
 
 33.在阅读逻辑乘表达式时, 问题可以认为正在分析的表达式以左的表达式均为true; 在阅读逻辑和表达式时, 类似地, 可以认为正在分析的表达式以左的表达式均为false.
 
 34.重新组织您控制的代码, 使之更为易读.
 
 35.将使用条件运行符? :的表达式理解为if代码.
 
 36.不需要为了效率, 牺牲代码的易读性.
 
 37.高效的算法和特殊的优化确实有可能使得代码更为复杂, 从而更难理解, 但这并不意味着使代码更为紧凑和不易读会提高它的效率.
 
 38.创造性的代码布局可以用来提高代码的易读性.
 
 39.我们可以使用空格|临时变量和括号提高表达式的易读性.
 
 40.在阅读您所控制的代码时, 要养成添加注释的习惯.
 
 41.我们可以用好的缩进以及对变量名称的明智选择, 提高编写欠佳的程序的易读性.
 
 42.用diff程序分析程序的修订历史时, 如果这段历史跨越了整体重新缩排, 常常可以通过指定-w选项, 让diff忽略空白差异, 避免由于更改了缩进层次而引入的噪音.
 
 43.do循环的循环体至少执行一次.
 
 44.执行算术运算时, 当b=2n-1时, 可以将a&b理解为a%(b+1).
 
 45.将a<<n理解为a*k, k=2n.
 
 46.将a>>n理解为a/k, k=2n.
 
 47.每次只分析一个控制结构, 将它的内容看作是一个黑盒.
 
 48.将每个控制结构的控制表达式看作是它所包含代码的断言.
 
 49.return, goto, break和continue语句, 还有异常, 都会影响结构化的执行流程. 由于这些语句一般都会终止或重新开始正在进行的循环, 
 
 因此要单独推理它们的行为.
 
 50.用复杂循环的变式和不变式, 对循环进行推理.
 
 51.使用保持含义不变的变换重新安排代码, 简化代码的推理工作.
 
 
 
 

  
 
 
 
 

  
 
 
 
 

  
 
 
 
 

  全文均为转载 从各个帖子，博文里
 
 
 

  有来源于知乎帖的 最后这段转自jk110333的文章
 
 
 
 
 
 

 

我们发现，在int型下使用pow函数求5的三次方，结果为124。
 
如图：
 
 
 
 
原因：
 
pow函数的返回值为double型，因浮点数长度问题，存在截断误差。
 
 
 
 
 
 
解决方法：
 
将变量定义为double型
 
 
 
 
 
 
有没有更快求幂的方法？
 
 假设我们要求a^b，按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)，即是O(n)级别。但快速幂能做到O(logn)的复杂度。
 
 
 
快速幂：
 
 
 
 
 
 
对于二进制的位运算，我们需要用到"&"与">>"运算符，详见位运算符的应用。
 
先上实现快速幂运算的具体代码：
 
int qsm(long long m, long long k, long long p)     //(m^k)%p
{
    long long res = 1, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}
 
LL quickPow(LL a,LL b,LL mod)          //  //(a^b)%mod
{
    LL res=1;
    while(b>0){
        if(b&1)
            res=(res%mod*a%mod)%mod;
        b>>=1;
        a=(a%mod*a%mod)%mod;
    }
    return res;
}
 
其中“b & 1”指取b的二进制数的最末位，如11的二进制数为1011，第一次循环，取的是最右边的“1” ，以此类推。
 
而“b >>= 1”等效于b = b >> 1，即右移1位，删去最低位。
 
 
 
以a^11为例：
 
b的二进制数为1011，二进制从右向左算，但乘出来的顺序是 a^(2^0)*a^(2^1)*a^(2^3)，是从左向右的。我们不断的让base *= base目的是累乘，以便随时对ans做出贡献。
 
要理解base *= base这一步：因为base * base == base ^ 2，下一步再乘，就是(base ^ 2) * (base ^ 2) == base ^ 4，然后同理(base ^ 4) * (base ^ 4) == base ^ 8，由此可以做到base → base ^ 2 → base ^ 4 → base ^ 8 → base ^ 16 → base ^ 32.......指数正好是 2 ^ i 。再看上面的例子，a¹¹= (a ^ 1) * (a ^ 2) * (a ^ 8)，这三项就可以完美解决了，快速幂就是这样。