Archive by category "程序算法"
Blog Archives
，涵盖了计算机算法，数据挖掘(机器学习)算法，统计算法，金融算法等的多种跨学科算法组合。在大数据时代的背景下，算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国，就像Google。
算法为王的时代正式到来….
关于作者：
张丹(Conan), 程序员Java,R,PHP,Javascript
weibo：@Conan_Z
转载请注明出处：
人类总是在生活中摸索规律，把规律总结为经验，再把经验传给后人，让后人发现更多的规规律，每一次知识的传递都是一次进化的过程，最终会形成了人类的智慧。自然界规律，让人类适者生存地活了下来，聪明的科学家又把生物进化的规律，总结成遗传算法，扩展到了更广的领域中。
本文将带你走进遗传算法的世界。
遗传算法介绍
遗传算法原理
遗传算法R语言实现
1. 遗传算法介绍
遗传算法是一种解决最优化的搜索算法，是进化算法的一种。进化算法最初借鉴了达尔文的进化论和孟德尔的遗传学说，从生物进化的一些现象发展起来，这些现象包括遗传、基因突变、自然选择和杂交等。遗传算法通过模仿自然界生物进化机制，发展出了随机全局搜索和优化的方法。遗传算法其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程，计算出全局最优解。
遗传算法的操作使用适者生存的原则，在潜在的种群中逐次产生一个近似最优解的方案，在每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程会导致种群中个体的进化，得到的新个体比原来个体更能适应环境，就像自然界中的改造一样。
如果从生物进化的角度，我们可以这样理解。在一个种群中，个体数量已经有一定规模，为了进化发展，通过选择和繁殖产生下一代的个体，其中繁殖过程包括交配和突变。根据适者生存的原则，选择过程会根据新个体的适应度进行保留或淘汰，但也不是完全以适应度高低作为导向，如果单纯选择适应度高的个体可能会产生局部最优的种群，而非全局最优，这个种群将不会再进化，称为早熟。之后，通过繁殖过程，让个体两两交配产生下一代新个体，上一代个体中优秀的基因会保留给下一代，而劣制的基因将被个体另一半的基因所代替。最后，通过小概率事件发生基因突变，通过突变产生新的下一代个体，实现种群的变异进化。
经过这一系列的选择、交配和突变的过程，产生的新一代个体将不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体交配，然后突变，产生第三代。周而复始，直到终止条件满足为止。
遗传算法需要注意的问题：
遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。
初始种群的数量很重要，如果初始种群数量过多，算法会占用大量系统资源；如果初始种群数量过少，算法很可能忽略掉最优解。
对于每个解，一般根据实际情况进行编码，这样有利于编写变异函数和适应度函数。
在编码过的遗传算法中，每次变异的编码长度也影响到遗传算法的效率。如果变异代码长度过长，变异的多样性会受到限制；如果变异代码过短，变异的效率会非常低下，选择适当的变异长度是提高效率的关键。
变异率是一个重要的参数。
对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再产生变化。对于这个问题，研究者提出了一些方法增加基因的多样性，从而防止过早的收敛。其中一种是所谓触發式超级变异，就是当染色体群体的质量下降（彼此的区别减少）时增加变异概率；另一种叫随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。
选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解；而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效于一个非常大的变异率，而这么大的变异很可能影响进化过程。
遗传算法很快就能找到良好的解，即使是在很复杂的解空间中。
遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试其他算法，互相补充，甚至根本不用遗传算法。
遗传算法不能解决那些“大海捞针”的问题，所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题，使得算法的进化失去导向。
对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好的更快的收敛，这些参数包括个体数目、交叉率和变异率。例如太大的变异率会导致丢失最优解，而过小的变异率会导致算法过早的收敛于局部最优点。对于这些参数的选择，现在还没有实用的上下限。
适应度函数对于算法的速度和效果也很重要。
遗传算法的应用领域包括计算机自动设计、生产调度、电路设计、游戏设计、机器人学习、模糊控制、时间表安排，神经网络训练等。然而，我准备把遗传算法到金融领域，比如回测系统的参数寻优方案，我会在以后的文章中，介绍有关金融解决方案。
2. 遗传算法原理
在遗传算法里，优化问题的解是被称为个体，它表示为一个变量序列，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串，也有其他表示法，这一过程称为编码。首先要创建种群，算法随机生成一定数量的个体，有时候也可以人工干预这个过程进行，以提高初始种群的质量。在每一代中，每一个个体都被评价，并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序，适应度高的在前面。
接下来，是产生下一代个体的种群，通过选择过程和繁殖过程完成。
选择过程，是根据新个体的适应度进行的，但同时并不意味着完全的以适应度高低作为导向，因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，我们称之为早熟。作为折中，遗传算法依据原则：适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。
繁殖过程，表示被选择的个体进入交配过程，包括交配(crossover)和突变(mutation)，交配对应算法中的交叉操作。一般的遗传算法都有一个交配概率，范围一般是0.6~1，这个交配概率反映两个被选中的个体进行交配的概率。
例如，交配概率为0.8，则80%的“夫妻”个体会生育后代。每两个个体通过交配产生两个新个体，代替原来的“老”个体，而不交配的个体则保持不变。交配过程，父母的染色体相互交換，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里指的半段並不是真正的一半，这个位置叫做交配点，也是随机产生的，可以是染色体的任意位置。
突变过程，表示通过突变产生新的下一代个体。一般遗传算法都有一个固定的突变常数，又称为变异概率，通常是0.1或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的突变，通常就是改变染色体的一个字节（0变到1，或者1变到0）。
遗传算法实现将不断的重复这个过程：每个个体被评价，计算出适应度，两个个体交配，然后突变，产生下一代，直到终止条件满足为止。一般终止条件有以下几种：
进化次数限制
计算耗费的资源限制，如计算时间、计算占用的CPU，内存等
个体已经满足最优值的条件，即最优值已经找到
当适应度已经达到饱和，继续进化不会产生适应度更好的个体
算法实现原理：
1. 创建初始种群
2. 循环：产生下一代
3. 评价种群中的个体适应度
4. 定义选择的适应度函数
5. 改变该种群（交配和变异）
6. 返回第二步
7. 满足终止条件结束
3. 遗传算法R语言实现
本节的系统环境
Win7 64bit
R: 3.1.1 x86_64-w64-mingw32/x64 (64-bit)
一个典型的遗传算法要求：一个基因表示的求解域, 一个适应度函数来评价解决方案。
遗传算法的参数通常包括以下几个：
种群规模(Population)，即种群中染色体个体的数目。
染色体的基因个数(Size)，即变量的数目。
交配概率(Crossover)，用于控制交叉计算的使用频率。交叉操作可以加快收敛，使解达到最有希望的最优解区域，因此一般取较大的交叉概率，但交叉概率太高也可能导致过早收敛。
变异概率(Mutation)，用于控制变异计算的使用频率，决定了遗传算法的局部搜索能力。
中止条件(Termination)，结束的标志。
在R语言中，有一些现成的第三方包已经实现的遗传算法，我们可以直接进行使用。
mcga包，多变量的遗传算法，用于求解多维函数的最小值。
genalg包，多变量的遗传算法，用于求解多维函数的最小值。
rgenoud包，复杂的遗传算法，将遗传算法和衍生的拟牛顿算法结合起来，可以求解复杂函数的最优化化问题。
gafit包，利用遗传算法求解一维函数的最小值。不支持R 3.1.1的版本。
GALGO包，利用遗传算法求解多维函数的最优化解。不支持R 3.1.1的版本。
本文将介绍mcga包和genalg包的遗传算法的使用。
3.1 mcga包
我们使用mcga包的mcga()函数，可以实现多变量的遗传算法。
mcga包是一个遗传算法快速的工具包，主要解决实值优化的问题。它使用的变量值表示基因序列，而不是字节码，因此不需要编解码的处理。mcga实现了遗传算法的交配和突变的操作，并且可以进行大范围和高精度的搜索空间的计算，算法的主要缺点是使用了256位的一元字母表。
首先，安装mcga包。
> install.packages("mcga")
> library(mcga)
查看一下mcga()函数的定义。
function (popsize, chsize, crossprob = 1, mutateprob = 0.01, elitism = 1, minval, maxval, maxiter = 10, evalFunc)
参数说明：
popsize，个体数量，即染色体数目
chsize，基因数量，限参数的数量
crossprob，交配概率，默认为1.0
mutateprob，突变概率，默认为0.01
elitism，精英数量，直接复制到下一代的染色体数目，默认为1
minval，随机生成初始种群的下边界值
maxval，随机生成初始种群的上边界值
maxiter，繁殖次数，即循环次数，默认为10
evalFunc，适应度函数，用于给个体进行评价
接下来，我们给定一个优化的问题，通过mcga()函数，计算最优化的解。
题目1：设fx=(x1-5)^2 + (x2-55)^2 +(x3-555)^2 +(x4-5555)^2 +(x5-55555)^2，计算fx的最小值，其中x1,x2,x3,x4,x5为5个不同的变量。
从直观上看，如果想得到fx的最小值，其实当x1=5,x2=55,x3=555,x4=55时，fx=0为最小值。如果使用穷举法，通过循环的方法找到这5个变量，估计会很费时的，我就不做测试了。下面我们看一下遗传算法的运行情况。
# 定义适应度函数
print(m$population[1,])
554.55.54.218695
# 执行时间
> m$costs[1]
[1] 3.6104556
我们得到的最优化的结果为x1=5.000317, x2=54.997099, x3=554.999873, x4=, x5=，和我们预期的结果非常接近，而且耗时只有3.6秒。这个结果是非常令人满意地，不是么！如果使用穷举法，时间复杂度为O(n^5)，估计没有5分钟肯定算不出来。
当然，算法执行时间和精度，都是通过参数进行配置的。如果增大个体数目或循环次数，一方面会增加算法的计算时间，另一方面结果也可能变得更精准。所以，在实际的使用过程中，需要根据一定的经验调整这几个参数。
3.2 genalg包
我们使用genalg包的rbga()函数，也可以实现多变量的遗传算法。
genalg包不仅实现了遗传算法，还提供了遗传算法的数据可视化，给用户更直观的角度理解算法。默认图显示的最小和平均评价值，表示遗传算法的计算进度。直方图显出了基因选择的频率，即基因在当前个体中被选择的次数。参数图表示评价函数和变量值，非常方便地看到评价函数和变量值的相关关系。
首先，安装genalg包。
> install.packages("genalg")
> library(genalg)
查看一下rbga()函数的定义。
> rbga(stringMin=c(), stringMax=c(),
suggestions=NULL,
popSize=200, iters=100,
mutationChance=NA,
elitism=NA,
monitorFunc=NULL, evalFunc=NULL,
showSettings=FALSE, verbose=FALSE)
参数说明：
stringMin，设置每个基因的最小值
stringMax，设置每个基因的最大值
suggestions，建议染色体的可选列表
popSize，个体数量，即染色体数目，默认为200
iters，迭代次数，默认为100
mutationChance，突变机会，默认为1/(size+1)，它影响收敛速度和搜索空间的探测，低机率导致更快收敛，高机率增加了搜索空间的跨度。
elitism，精英数量，默认为20%，直接复制到下一代的染色体数目
monitorFunc，监控函数，每产生一代后运行
evalFunc，适应度函数，用于给个体进行评价
showSettings，打印设置，默认为false
verbose，打印算法运行日志，默认为false
接下来，我们给定一个优化的问题，通过rbga()函数，计算最优化的解。
题目2：设fx=abs(x1-sqrt(exp(1)))+abs(x2-log(pi))，计算fx的最小值，其中x1,x2为2个不同的变量。
从直观上看，如果想得到fx的最小值，其实当x1=sqrt(exp(1))=1.648721, x2=log(pi)=1.14473时，fx=0为最小值。同样地，如果使用穷举法，通过循环的方法找到这2个变量，估计会很费时的，我也不做测试了。下面我们看一下rbga()函数的遗传算法的运行情况。
# 定义适应度函数
> f monitor
m2 = rbga(c(1,1),
popSize=100,
iters=1000,
evalFunc=f,
mutationChance=0.01,
verbose=TRUE,
monitorFunc=monitor
Testing the sanity of parameters...
Not showing GA settings...
Starting with random values in the given domains...
Starting iteration 1
Calucating evaluation values... ....................................................... done.
Sending current state to rgba.monitor()...
Creating next generation...
sorting results...
applying elitism...
applying crossover...
applying mutations... 2 mutations applied
Starting iteration 2
Calucating evaluation values... ...................... done.
Sending current state to rgba.monitor()...
Creating next generation...
sorting results...
applying elitism...
applying crossover...
applying mutations... 4 mutations applied
Starting iteration 3
Calucating evaluation values... ....................... done.
# 省略输出...
程序运行截图
需要注意的是，程序在要命令行界面运行，如果在RStudio中运行，会出现下面的错误提示。
Creating next generation...
sorting results...
applying elitism...
applying crossover...
applying mutations... 1 mutations applied
Starting iteration 10
Calucating evaluation values... .......................... done.
Sending current state to rgba.monitor()...
Error in get(name, envir = asNamespace(pkg), inherits = FALSE) :
object 'rversion' not found
Graphics error: Error in get(name, envir = asNamespace(pkg), inherits = FALSE) :
object 'rversion' not found
我们迭代1000次后，查看计算结果。
# 计算结果
> m2$population[1,]
[1] 1..145784
我们得到的最优化的结果为x1=1.650571, x2=1.145784，非常接近最终的结果。另外，我们可以通过genalg包的可视化功能，看到迭代过程的每次的计算结果。下面截图分为对应1次迭代，10次迭代，200次迭代和1000次迭代的计算结果。从图中可以看出，随着迭代次数的增加，优选出的结果集变得越来越少，而且越来越精准。
默认图输出，用于描述遗传过程的进展，X轴为迭代次数，Y轴评价值，评价值越接近于0越好。在1000迭代1000次后，基本找到了精确的结果。
> plot(m2)
直方图输出，用于描述对染色体的基因选择频率，即一个基因在染色体中的当前人口被选择的次数。当x1在1.65区域时，被选择超过80次；当x2在1.146区域时，被选择超过了80次。通过直方图，我们可以理解为更优秀的基因被留给了后代。
> plot(m2,type='hist')
参数图输出，用于描述评价函数和变量的值的相关关系。对于x1，评价值越小，变量值越准确，但相关关系不明显。对于x2，看不出相关关系。
> plot(m2,type='vars')
对比mcga包和genalg包，mcga包适合计算大范围取值空间的最优解，而用genalg包对于大范围取值空间的计算就表现就不太好了。从另一个方面讲，genalg包提供了可视化工具，可以让我们直观的看遗传算法的收敛过程，对于算法的理解和调优是非常有帮助的。
在掌握了遗传算法后，我们就可以快度地处理一些优化的问题了，比如接下来我会介绍的金融回测系统的参数寻优方案。让我们远离穷举法，珍惜CPU的每一秒时间。
转载请注明出处：
，涵盖了计算机算法，数据挖掘(机器学习)算法，统计算法，金融算法等的多种跨学科算法组合。在大数据时代的背景下，算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国，就像Google。
算法为王的时代正式到来….
关于作者：
张丹(Conan), 程序员Java,R,PHP,Javascript
weibo：@Conan_Z
转载请注明出处：
一个好的程序算法，可以提升百倍的程序性能。但并没有一种通用的算法，适用于所有场景。选择合适的算法，用在正确的地方，是一个好算法的开始。
本文将用Nodejs实现桶排序算法。
桶排序介绍
桶排序算法演示
Nodejs程序实现
案例：桶排序统计高考分数
1. 桶排序介绍
桶排序(Bucket sort)是一种基于计数的排序算法，工作的原理是将数据分到有限数量的桶子里，然后每个桶再分别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。当要被排序的数据内的数值是均匀分配的时候，桶排序时间复杂度为Θ(n)。桶排序不同于快速排序，并不是比较排序，不受到时间复杂度 O(nlogn) 下限的影响。关于快速排序，请参考文章：
桶排序按下面4步进行：
1. 设置固定数量的空桶。
2. 把数据放到对应的桶中。
3. 对每个不为空的桶中数据进行排序。
4. 拼接从不为空的桶中数据，得到结果。
桶排序，主要适用于小范围整数数据，且独立均匀分布，可以计算的数据量很大，而且符合线性期望时间。
2. 桶排序算法演示
举例来说，现在有一组数据[7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101]，怎么对其按从小到大顺序排序呢？
操作步骤说明：
1. 设置桶的数量为5个空桶，找到最大值110，最小值7，每个桶的范围20.8=(110-7+1)/5 。
2. 遍历原始数据，以链表结构，放到对应的桶中。数字7，桶索引值为0，计算公式为floor((7 – 7) / 20.8)， 数字36，桶索引值为1，计算公式floor((36 – 7) / 20.8)。
3. 当向同一个索引的桶，第二次插入数据时，判断桶中已存在的数字与新插入数字的大小，按照左到右，从小到大的顺序插入。如：索引为2的桶，在插入63时，桶中已存在4个数字56，59，60，65，则数字63，插入到65的左边。
4. 合并非空的桶，按从左到右的顺序合并0，1，2，3，4桶。
5. 得到桶排序的结构
3. Nodejs程序实现
像桶排序这种成熟的算法，自己实现一下并不难，按照上文的思路，我写了一个简单的程序实现。我感觉其中最麻烦的部分，是用Javascript操作链表。
现实代码如下：
'use strict';
/////////////////////////////////////////////////
/////////////////////////////////////////////////
var _this = this
, L = require('linklist');//链表
* 普通数组桶排序,同步
* @param arr Array 整数数组
* @param num 桶的个数
* @example:
* sort([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1],5)
* sort([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1],5,0,5)
exports.sort = function (arr, count) {
if (arr.length == 0) return [];
count = count || (count > 1 ? count : 10);
// 判断最大值、最小值
var min = arr[0], max = arr[0];
for (var i = 1; i < arr. i++) {
arr[i] ? max : arr[i];
var delta = (max - min + 1) /
// console.log(min+","+max+","+delta);
//初始化桶
var buckets = [];
//存储数据到桶
for (var i = 0; i < arr. i++) {
var idx = Math.floor((arr[i] - min) / delta); // 桶索引
if (buckets[idx]) {//非空桶
var bucket = buckets[idx];
var insert =//插入标石
L.reTraversal(bucket, function (item, done) {
if (arr[i] <= item.v) {//小于，左边插入
L.append(item, _val(arr[i]));
done();//退出遍历
if (!insert) { //大于，右边插入
L.append(bucket, _val(arr[i]));
} else {//空桶
var bucket = L.init();
L.append(bucket, _val(arr[i]));
buckets[idx] = //链表实现
var result = [];
for (var i = 0, j = 0; i < i++) {
L.reTraversal(buckets[i], function (item) {
// console.log(i+":"+item.v);
result[j++] = item.v;
//链表存储对象
function _val(v) {
return {v: v}
运行程序：
var algo = require('./index.js');
var data = [ 7, 36, 65, 56, 33, 60, 110, 42, 42, 94,
59, 22, 83, 84, 63, 77, 67,101 ];
console.log(data);
console.log(algo.bucketsort.sort(data,5));//5个桶
console.log(algo.bucketsort.sort(data,10));//10个桶
[ 7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101 ]
[ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ]
[ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ]
需要说明的是：
1. 桶内排序，可以像程序中所描述的，在插入过程中实现；也可以插入不排序，在合并过程中，再进行排序，可以调用快度排序。
2. 链表，在Node的底层API中，有一个链表的实现_linklist.js，我没有直接使用，而是通过包调用的。
程序源代码已上传到github, 。下载后，可以参考example.js文件中，来调用桶排序程序。
同时也在npm发布了，安装命令：
npm install ape-algorithm
4. 案例：桶排序统计高考分数
桶排序最出名的一个应用场景，就是统计高考的分数。一年的全国高考考生人数为900万人，分数使用标准分，最低200 ，最高900 ，没有小数，如果把这900万数字进行排序，应该如何做呢？
算法分析：
1. 如果使用基于比较的排序，快速排序，平均时间复杂度为O(nlogn) = O(9000000*log.44亿次比较。
2. 如果使用基于计数的排序，桶排序，平均的时候复杂度，可以控制在线性复杂度，当创建700桶时从200分到900分各一个桶，O(N)=O(9000000)，就相当于扫描一次900W条数据。
我们跑一个程序，对比一次快速排序和桶排序。
//产生100W条，[200,900]闭区间的数据
var data = algo.data.randomData(0,900);
var s1 = new Date().getTime();
algo.quicksort.sort(data);//快速排序
var s2 = new Date().getTime();
algo.bucketsort.sort(data,700);//装到700个桶
var s3 = new Date().getTime();
console.log("quicksort time: %sms",s2-s1);
console.log("bucket time: %sms",s3-s2);
quicksort time: 14768ms
bucket time: 1089ms
所以，对于高考计分的案例来说，桶排序是更适合的！我们把合适的算法，用在适合的场景，会给程序带来超越硬件的性能提升。
转载请注明出处：
，涵盖了计算机算法，数据挖掘(机器学习)算法，统计算法，金融算法等的多种跨学科算法组合。在大数据时代的背景下，算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国，就像Google。
算法为王的时代正式到来….
关于作者：
张丹(Conan), 程序员Java,R,PHP,Javascript
weibo：@Conan_Z
转载请注明出处：
排序算法，是程序开发中最基本的一项任务。教科课上讲的排序算法大概有7-8种，快速排序(QuickSort)是使用最广泛的一种基于比较排序的算法。网上已经有了各种语言的实现。本文则是利用快速排序的原理，实现对数组对象中的属性进行排序，利用Nodejs来实现。
快速排序介绍
快速排序算法演示
Nodejs程序实现
1. 快速排序算法介绍
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n^2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
快速排序的思想很简单，排序过程只需要三步：
1. 从数列中挑出一个元素，称为 “基准”（pivot）
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
2. 快速排序算法演示
举例来说，现在有一组数据[9,23,12,11,43,54,43,2,12,66]，怎么对其按从小到大顺序排序呢？
Step1，选择第一个元素9作为分隔值，把小于9的数字放左边，大于等于9的数字放右边。原来的一个数组就被分成了3个部分，左边+分隔值+右边=[2]+9+[23 12 11 43 54 43 12 66]
Step2, 选择Step1数组左边的第一元素2作为分隔值，左边只有一个元素，左边排序完成。选择Step1数组右边的第一个元素23作为分隔值，把小于23的数字放左边，大于等于23的数字放右边，得到[ 12 11 12 ] 23 [ 43 54 43 66 ]。
Step3，选择Step2数组以23分隔的左边第一个元素12作为分隔值，把小于12的数字放左边，大于等于12的数字放右边，得到[ 11 ] 12 [ 12 ]。选择Step2数组以23分隔的左边第一个元素43作为分割值，把小于43的数字放左边，大于等于43的数字右边，得到 [] 43 [ 54 43 66 ]。
Step4，对Step3数组以12分隔的左右两边进行排序，都只有一个元素，排序完成。对Step3数组以43分隔左右两进行排序，左边无元素，右边第一个元素54作为分隔值，得到[ 43 ] 54 [ 66 ]。
Step5，对Step4数组以54分隔的左右两边进行排序，都只有一个元素，排序完成。
最后，后整个数组拼接在一起就得到排序结果：[2 9 11 12 12 23 43 43 54 66 ]
我们看到快速排序，其实就是一种分而治之的办法。网上还有很多快速排序的优化方法，可以尽一步减少时间复杂度和空间复杂度的开销。
3. Nodejs程序实现
像快速排序这种成熟的算法，我以为在Nodejs中早就有人已经封装好了程序包。等我用到的时候竟然找不到，所以自己花了点时间，动手实现了快速排序的Node模块。
当然，除了支持对普通数组的快速排序，还支持按数组对象中的某个属性进行快速排序，已满足自己的功能需求。
3.1 普通数组的快速排序
这部分的实现就和上文中演示的思路是一样的，我另外加了方向的判断。可以从小到大排序，也可以从大到小排序。
现实代码如下：
* 普通数组快速排序
* @param arr Array 数字数组
* @param dir asc升序、desc降序
* @example:
* sort([1,4,2,5])
* sort([1,4,2,5],'asc')
* sort([1,4,2,5],'desc')
exports.sort=function(arr,dir){
dir=dir||'asc';
if (arr.length == 0) return [];
var left = new Array();
var right = new Array();
var pivot = arr[0];
if(dir==='asc'){//升序
for (var i = 1; i < arr. i++) {
arr[i] < pivot ? left.push(arr[i]): right.push(arr[i]);
}else{//降序
for (var i = 1; i
pivot ? left.push(arr[i]): right.push(arr[i]);
return _this.sort(left,dir).concat(pivot, _this.sort(right,dir));
运行程序：
var algo = require('./index.js');
var arr = [23,12,11,43,54,43,2,12,66];
console.log(arr);
console.log(algo.quicksort.sort(arr));
console.log(algo.quicksort.sort(arr,'desc'));
[ 23, 12, 11, 43, 54, 43, 2, 12, 66 ]
[ 2, 11, 12, 12, 23, 43, 43, 54, 66 ]
[ 66, 54, 43, 43, 23, 12, 12, 11, 2 ]
3.2 按数组对象中的属性进行快速排序
按数组对象中的属性快速排序，是指在数组中存储的不是数字类型，而是对象类型，如[{name:’小B’,id:12},{name:’小C’,id:21},{name:’小A’,id:2}]，然后想要按对象中的id属性把对象排序。这样需求，其实在程序开发中更常见。那我们怎么做呢？其实，原理是一样的，只要把分隔值(pivot)和存储值(pivotObj)分成2个变量就行了。
实现代码如下：
* 对象数组快速排序
* @param arr Array 对象数组
* @param key string 用于排序的属性
* @param dir asc升序、desc降序
* @example:
* sort([{name:'b',id:12},{name:'c',id:21},{name:'a',id:2}],'id')
* sort([{name:'b',id:12},{name:'c',id:21},{name:'a',id:2}],'id','asc')
* sort([{name:'b',id:12},{name:'c',id:21},{name:'a',id:2}],'id','desc')
exports.sortObj=function(arr,key,dir){
key=key||'id';
dir=dir||'asc';
if (arr.length == 0) return [];
var left = new Array();
var right = new Array();
var pivot = arr[0][key];//分割值
var pivotObj = arr[0];//存储值
if(dir==='asc'){//升序
for (var i = 1; i < arr. i++) {
arr[i][key] < pivot ? left.push(arr[i]): right.push(arr[i]);
}else{//降序
for (var i = 1; i
pivot ? left.push(arr[i]): right.push(arr[i]);
return _this.sortObj(left,key,dir).concat(pivotObj, _this.sortObj(right,key,dir));
运行程序：
var algo = require('./index.js');
var arrObj = [{name:'b',id:12},{name:'c',id:21},{name:'a',id:2}];
console.log(arrObj);
console.log(algo.quicksort.sortObj(arrObj,'id','asc'));
console.log(algo.quicksort.sortObj(arrObj,'id','desc'));
[ { name: 'b', id: 12 },{ name: 'c', id: 21 },{ name: 'a', id: 2 } ]
[ { name: 'a', id: 2 },{ name: 'b', id: 12 },{ name: 'c', id: 21 } ]
[ { name: 'c', id: 21 },{ name: 'b', id: 12 },{ name: 'a', id: 2 } ]
不用多少代码，就能实现快速排序。程序源代码已上传到github, 。下载后，可以参考example.js文件中，来调用快速排序程序。
同时也在npm发布了，安装命令：
npm install ape-algorithm
有时候写写算法，感觉又回到了学生时代，还是挺有意思的。
转载请注明出处：
，主要介绍Hadoop家族产品，常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Zookeeper, Avro, Ambari, Chukwa，新增加的项目包括，YARN, Hcatalog, Oozie, Cassandra, Hama, Whirr, Flume, Bigtop, Crunch, Hue等。
从2011年开始，中国进入大数据风起云涌的时代，以Hadoop为代表的家族软件，占据了大数据处理的广阔地盘。开源界及厂商，所有数据软件，无一不向Hadoop靠拢。Hadoop也从小众的高富帅领域，变成了大数据开发的标准。在Hadoop原有技术基础之上，出现了Hadoop家族产品，通过“大数据”概念不断创新，推出科技进步。
作为IT界的开发人员，我们也要跟上节奏，抓住机遇，跟着Hadoop一起雄起！
关于作者：
张丹(Conan), 程序员Java,R,PHP,Javascript
weibo：@Conan_Z
转载请注明出处：
如果说Google改变了互联网，那么社交网络就改变人们的生活方式。通过社交网络，我们每个个体，都是成为了网络的中心。我们的生活半径，被无限放大，通过6个朋友关系，就可以认识世界上任何一个人。
未来的互联网将是属于我们每一个人。
PeopleRank和PageRank
需求分析：从社交网络中发现个体价值
算法模型：PeopleRank算法
架构设计：PeopleRank计算引擎系统架构
程序开发：PeopleRank算法实现
1. PeopleRank和PageRank
PageRank让Google成为搜索领域的No.1，也是当今最有影响力的互联网公司之一，用技术创新改变人们的生活。PageRank主要用于网页评分计算，把互联网上的所有网页都进行打分，给网页价值的体现。
自2012以来，中国开始进入社交网络的时代，开心网，人人网，新浪微博，腾讯微博，微信等社交网络应用，开始进入大家的生活。最早是由“抢车位”，“偷菜”等社交游戏带动的社交网络的兴起，如今人们会更多的利用社交网络，获取信息和分享信息。我们的互联网，正在从以网页信息为核心的网络，向着以人为核心的网络转变着。
于是有人就提出了，把PageRank模型应用于社交网络，定义以人为核心的个体价值。这样PageRank模型就有了新的应用领域，同时也有了一个新的名字PeopleRank。
关于PageRank的介绍，请参考文章：
注：PeopleRank网上还有不同的解释，我这里仅仅表示用来解释“PageRank模型”。
下面我们将从一个PeopleRank的案例来解释，如何从社交网络中发现个体价值。
2. 需求分析：从社交网络中发现个体价值
案例介绍：
以新浪微博为例，给微博中每个用户进行评分！
从新浪微博上，把我们的关注和粉丝的关系都找到。
如下图：我在微博上，随便找了几个微博账号。
我们的任务是，需要给这些账号评分！
方法一，简单求和：评分=关注数+粉丝数+微博数
方法二，加权求和：评分=a*关注数+b*粉丝数+c*微博数
新建数据文件：weibo.csv
~ vi weibo.csv
E,318,547,4899
F,166,145,170
G,17,890,169
R语言读入数据文件
weibo<-read.csv(file="weibo.csv",header=FALSE)
names(weibo)<-c("id","follow","fans","tweet")
1). 方法一，简单相加法
> data.frame(weibo[1],rank=rowSums(weibo[2:4]))
这种方法简单粗暴的方式，是否能代码公平的打分呢？！
2). 方法二，加权求和
通过a,b,c的3个参数，分别设置权重求和。与方法一存在同样的问题，a,b,c的权值都是人为指定的，也是不能表示公平的打分的。
除了上面的两个方法，你能否想到不一样的思路呢！
3. 算法模型：PeopleRank算法
基于PageRank的理论，我们以每个微博账户的“关注”为链出链接，“粉丝”为链入链接，我们把这种以人为核心的关系，叫PeopleRank。
关于PageRank的介绍，请参考文章：
PeopleRank假设条件：
数量假设：如果一个用户节点接收到的其他用户“关注”的数量越多，那么这个用户越重要。
质量假设：用户A的“粉丝”质量不同，质量高的“粉丝”会通“关注”接向其他用户传递更多的权重。所以越是质量高的“用户”关注用户A，则用户A越重要。
衡量PeopleRank的3个指标：
粉丝是否有较高PeopleRank值
粉丝关注了多少人
我们以下的数据为例，构造基于微博的数据模型：
(由于微博数据已增加访问权限，我无法拿到当前的实际数据，我用以前应用，收集到的微博数据为例，这里ID已经过处理)
测试数据集：people.csv
66个关系，关注和粉丝的关系
数据集: people.csv
第一列为用户ID，第二列也是用户ID。第一列用户，关注了第二用户。
以R语言可视化输出
library(igraph)
people<-read.csv(file="people.csv",header=FALSE)
drawGraph<-function(data){
names(data)<-c("from","to")
g <- graph.data.frame(data, directed=TRUE)
V(g)$label <- V(g)$name
V(g)$size <- 15
E(g)$color <- grey(0.5)
g2 <- simplify(g)
plot(g2,layout=layout.circle)
drawGraph(people)
用R语言构建PeopleRank的算法原型
构建邻接矩阵
变换概率矩阵
递归计算矩阵特征值
标准化结果
对结果排序输出
R语言算法模型
#构建邻接矩阵
adjacencyMatrix<-function(pages){
n<-max(apply(pages,2,max))
A <- matrix(0,n,n)
for(i in 1:nrow(pages)) A[pages[i,]$dist,pages[i,]$src]<-1
#变换概率矩阵
dProbabilityMatrix<-function(G,d=0.85){
cs <- colSums(G)
cs[cs==0] <- 1
n <- nrow(G)
delta <- (1-d)/n
A <- matrix(delta,n,n)
for (i in 1:n) A[i,] <- A[i,] + d*G[i,]/cs
#递归计算矩阵特征值
eigenMatrix<-function(G,iter=100){
n<-nrow(G)
x <- rep(1,n)
for (i in 1:iter) x <- G %*% x
#直接计算矩阵特征值
calcEigenMatrix<-function(G){
x <- Re(eigen(G)$vectors[,1])
PeopleRank计算，带入数据集people.csv
people<-read.csv(file="people.csv",header=FALSE)
names(people)<-c("src","dist");people
A<-adjacencyMatrix(people);A
G<-dProbabilityMatrix(A);G
q<-calcEigenMatrix(G);
[1] 0.......
[8] 0.......
[15] 0.......
[22] 0....
我们给这25用户进行打分，从高到低进行排序。
对结果排序输出：
result<-data.frame(userid=userid,PR=q[userid])
查看评分最高的用户18的关系数据：
people[c(which(people$src==18), which(people$dist==18)),]
粉丝的PeopleRank排名：
which(result$userid %in% people$src[which(people$dist==18)])
粉丝的关注数:
table(people$src)[people$src[which(people$dist==18)]]
数据解释：用户18
有4个粉丝为别是6,7,10,19。(粉丝数)
4个粉丝的PeopleRank排名，是3,5,8,20。(粉丝是否有较高PeopleRank值)
粉丝的关注数量，是6,3,2,1。（粉丝关注了多少人）
因此，通过对上面3个指标的综合打分，用户18是评分最高的用户。
通过R语言实现的计算模型，已经比较符合我们的评分标准了，下面我们把PeopleRank用MapReduce实现，以满足对海量数据的计算需求。
4. 架构设计：PeopleRank计算引擎系统架构
上图中，左边是数据爬虫系统，右边是Hadoop的HDFS, MapReduce。
数据爬虫系统实时爬取微博数据
设置系统定时器CRON，每xx小时，增量向HDFS导入数据(userid1,userid2)
完成导入后，设置系统定时器，启动MapReduce程序，运行推荐算法。
完成计算后，设置系统定时器，从HDFS导出推荐结果数据到数据库，方便以后的及时查询。
5. 程序开发：PeopleRank算法实现
win7的开发环境 和 Hadoop的运行环境 ，请参考文章：
微博好友的关系数据: people.csv
出始的PR数据:peoplerank.csv
邻接矩阵: AdjacencyMatrix.java
PeopleRank计算: PageRank.java
PR标准化: Normal.java
启动程序: PageRankJob.java
1). 微博好友的关系数据: people.csv，在上文中已列出
2). 出始的PR数据:peoplerank.csv
3). 邻接矩阵
矩阵解释：
阻尼系数为0.85
用户数为25
reduce以行输出矩阵的列，输出列主要用于分步式存储，下一步需要转成行
部分数据输出：
~ hadoop fs -cat /user/hdfs/pagerank/tmp1/part-r-00000|head -n 4
1 0.........................
10 0.........................
11 0.........................
12 0....5,0..................
4). PeopleRank计算: PageRank.java
迭代一次的PeopleRank值
~ hadoop fs -cat /user/hdfs/pagerank/pr/part-r-00000
5). PR标准化: Normal.java
迭代10次，并标准化的结果：
~ hadoop fs -cat /user/hdfs/pagerank/result/part-r-00000
我们对结果进行排序
10 18 0.094460
11 0.077670
6 0.070516
15 0.066614
10 0.065405
3 0.059864
11 19 0.050673
14 0.050574
5 0.043805
13 0.039175
17 24 0.036111
4 0.035314
12 0.034864
2 0.034054
8 0.033715
1 0.032842
13 20 0.030835
14 21 0.029657
17 0.027990
7 0.027444
9 0.021251
16 0.019167
15 22 0.006000
16 23 0.006000
18 25 0.006000
第一名是用户18，第二名是用户11，第三名是用户6，第三名与之前R语言单机计算的结果有些不一样，而且PR值也稍有不同，这是因为我们迭代10次时，特征值还没有完全的收敛，需要更多次的迭代计算，才能得矩阵的特征值。
程序API的实现，请参考文章：
我们通过PageRank的模型，成功地应用到了社交网络，实现了PeopleRank的计算，通过设计数据挖掘算法，来取代不成熟的人脑思想。算法模型将更客观，更精准。
最后，大家可以利用这个案例的设计思路，认真地了解社交网络，做出属于的自己的算法。
由于时间仓促，代码可能存在bug。请有能力同学，自行发现问题，解决问题！！
######################################################
看文字不过瘾，作者视频讲解，请访问网站：
######################################################
转载请注明出处：
，涵盖了计算机算法，数据挖掘(机器学习)算法，统计算法，金融算法等的多种跨学科算法组合。在大数据时代的背景下，算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国，就像Google。
算法为王的时代正式到来….
关于作者：
张丹(Conan), 程序员Java,R,PHP,Javascript
weibo：@Conan_Z
转载请注明出处：
Google搜索，早已成为我每天必用的工具，无数次惊叹它搜索结果的准确性。同时，我也在做Google的SEO，推广自己的博客。经过几个月尝试，我的博客PR到2了，外链也有几万个了。总结下来，还是感叹PageRank的神奇！
改变世界的算法，PageRank！
PageRank算法介绍
PageRank算法原理
PageRank算法的R语言实现
1. PageRank算法介绍
PageRank是Google专有的算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。它由Larry Page 和 Sergey Brin在20世纪90年代后期发明。PageRank实现了将链接价值概念作为排名因素。
PageRank让链接来”投票”
一个页面的“得票数”由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面（“链入页面”）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反如果一个页面没有任何链入页面，那么它没有等级。
简单一句话概括：从许多优质的网页链接过来的网页，必定还是优质网页。
PageRank的计算基于以下两个基本假设：
数量假设：如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要
质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A，则页面A越重要。
要提高PageRank有3个要点：
反向链接数
反向链接是否来自PageRank较高的页面
反向链接源页面的链接数
2. PageRank算法原理
在初始阶段：网页通过链接关系构建起有向图，每个页面设置相同的PageRank值，通过若干轮的计算，会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。
在一轮更新页面PageRank得分的计算中，每个页面将其当前的PageRank值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。
1). 算法原理
PageRank算法建立在随机冲浪者模型上，其基本思想是：网页的重要性排序是由网页间的链接关系所决定的，算法是依靠网页间的链接结构来评价每个页面的等级和重要性，一个网页的PR值不仅考虑指向它的链接网页数，还有指向’指向它的网页的其他网页本身的重要性。
PageRank具有两大特性：
PR值的传递性：网页A指向网页B时，A的PR值也部分传递给B
重要性的传递性：一个重要网页比一个不重要网页传递的权重要多
2). 计算公式：
PR(pi): pi页面的PageRank值
n: 所有页面的数量
pi: 不同的网页p1,p2,p3
M(i): pi链入网页的集合
L(j): pj链出网页的数量
d:阻尼系数, 任意时刻，用户到达某页面后并继续向后浏览的概率。
(1-d=0.15) :表示用户停止点击，随机跳到新URL的概率
取值范围: 0 & d ≤ 1, Google设为0.85
3). 构造实例：以4个页面的数据为例
图片说明：
ID=1的页面链向2,3,4页面，所以一个用户从ID=1的页面跳转到2,3,4的概率各为1/3
ID=2的页面链向3,4页面，所以一个用户从ID=2的页面跳转到3,4的概率各为1/2
ID=3的页面链向4页面，所以一个用户从ID=3的页面跳转到4的概率各为1
ID=4的页面链向2页面，所以一个用户从ID=4的页面跳转到2的概率各为1
构造邻接表：
链接源页面
链接目标页面
构造邻接矩阵(方阵):
列：源页面
行：目标页面
[,1] [,2] [,3] [,4]
转换为概率矩阵(转移矩阵)
[,1] [,2] [,3] [,4]
通过链接关系，我们就构造出了“转移矩阵”。
3. R语言单机算法实现
创建数据文件：page.csv
分别用下面3种方式实现PageRank:
未考虑阻尼系统的情况
包括考虑阻尼系统的情况
直接用R的特征值计算函数
1). 未考虑阻尼系统的情况
#构建邻接矩阵
adjacencyMatrix<-function(pages){
n<-max(apply(pages,2,max))
A <- matrix(0,n,n)
for(i in 1:nrow(pages)) A[pages[i,]$dist,pages[i,]$src]<-1
#变换概率矩阵
probabilityMatrix<-function(G){
cs <- colSums(G)
cs[cs==0] <- 1
n <- nrow(G)
A <- matrix(0,nrow(G),ncol(G))
for (i in 1:n) A[i,] <- A[i,] + G[i,]/cs
#递归计算矩阵特征值
eigenMatrix<-function(G,iter=100){
n<-nrow(G)
x <- rep(1,n)
for (i in 1:iter) x
pages names(pages) A G q<-eigenMatrix(G,100);q
[1,] 0.0000000
[2,] 0.4036458
[3,] 0.1979167
[4,] 0.3984375
结果解读：
ID=1的页面，PR值是0，因为没有指向ID=1的页面
ID=2的页面，PR值是0.4，权重最高，因为1和4都指向2，4权重较高，并且4只有一个链接指向到2，权重传递没有损失
ID=3的页面，PR值是0.19，虽有1和2的指向了3，但是1和2还指向的其他页面，权重被分散了，所以ID=3的页面PR并不高
ID=4的页面，PR值是0.39，权重很高，因为被1,2,3都指向了
从上面的结果，我们发现ID=1的页面，PR值是0，那么ID=1的页，就不能向其他页面输出权重了，计算就会不合理！所以，增加d阻尼系数，修正没有链接指向的页面，保证页面的最小PR值>0，。
2). 包括考虑阻尼系统的情况
增加函数：dProbabilityMatrix
#变换概率矩阵,考虑d的情况
dProbabilityMatrix<-function(G,d=0.85){
cs <- colSums(G)
cs[cs==0] <- 1
n <- nrow(G)
delta <- (1-d)/n
A <- matrix(delta,nrow(G),ncol(G))
for (i in 1:n) A[i,]
pages names(pages) A G q<-eigenMatrix(G,100);q
[1,] 0.0375000
[2,] 0.3738930
[3,] 0.2063759
[4,] 0.3822311
增加阻尼系数后，ID=1的页面，就有值了PR(1)=(1-d)/n=(1-0.85)/4=0.0375，即无外链页面的最小值。
3). 直接用R的特征值计算函数
增加函数：calcEigenMatrix
#直接计算矩阵特征值
calcEigenMatrix<-function(G){
pages names(pages) A G q<-calcEigenMatrix(G);q
[1] 0....3824972
直接计算矩阵特征值，可以有效地减少的循环的操作，提高程序运行效率。
在了解PageRank的原理后，使用R语言构建PageRank模型，是非常容易的。实际应用中，我们也愿意用比较简单的方式建模，验证后，再用其他语言语言去企业应用！
下一篇文章，将介绍如何用MapReduce分步式算法来实现PageRank模型，
Google 的秘密 PageRank 彻底解说中文版
转载请注明出处：
Designed by
