PHP的算法可以实现大数据分析吗

1.Bloom filter

环翠ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联公司的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：18980820575（备注：SSL证书合作）期待与您的合作！

适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集

基本原理及要点：

对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。

还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为 0，则m 应该=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。

注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

扩展：

Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个 bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。

2.Hashing

适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存

基本原理及要点：

hash函数选择，针对字符串，整数，排列，具体相应的hash方法。

碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法，opened addressing。 ()

扩展：

d-left hashing中的d是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key时，同时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置，哪一个位置已经存储的（有碰撞的）key比较多，然后将新key存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。

问题实例：

1).海量日志数据，提取出某日访问百度次数最多的那个IP。

IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。

3.bit-map

适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下

基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码

扩展：bloom filter可以看做是对bit-map的扩展

问题实例：

1)已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。

2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。

4.堆

适用范围：海量数据前n大，并且n比较小，堆可以放入内存

基本原理及要点：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很高。

扩展：双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。

问题实例：

1)100w个数中找最大的前100个数。

用一个100个元素大小的最小堆即可。

5.双层桶划分 ----其实本质上就是【分而治之】的思想，重在“分”的技巧上！

适用范围：第k大，中位数，不重复或重复的数字

基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。

扩展：

问题实例：

1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。

2).5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。

6.数据库索引

适用范围：大数据量的增删改查

基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。

扩展：

问题实例：

7.倒排索引(Inverted index)

适用范围：搜索引擎，关键字查询

基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

以英文为例，下面是要被索引的文本：

T0 = "it is what it is"

T1 = "what is it"

T2 = "it is a banana"

我们就能得到下面的反向文件索引：

"a": {2}

"banana": {2}

"is": {0, 1, 2}

"it": {0, 1, 2}

"what": {0, 1}

检索的条件"what", "is" 和 "it" 将对应集合的交集。

正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。

扩展：

问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。

8.外排序

适用范围：大数据的排序，去重

基本原理及要点：外排序的归并方法，置换选择 败者树原理，最优归并树

扩展：

问题实例：

1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。

这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。

9.trie树

适用范围：数据量大，重复多，但是数据种类小可以放入内存

基本原理及要点：实现方式，节点孩子的表示方式

扩展：压缩实现。

问题实例：

1).有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序 。

2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？

3).寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。

10.分布式处理 mapreduce

适用范围：数据量大，但是数据种类小可以放入内存

基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。

扩展：

问题实例：

1).The canonical example application of MapReduce is a process to count the appearances of

each different word in a set of documents:

void map(String name, String document):

// name: document name

// document: document contents

for each word w in document:

EmitIntermediate(w, 1);

void reduce(String word, Iterator partialCounts):

// key: a word

// values: a list of aggregated partial counts

int result = 0;

for each v in partialCounts:

result += ParseInt(v);

Emit(result);

Here, each document is split in words, and each word is counted initially with a "1" value by

the Map function, using the word as the result key. The framework puts together all the pairs

with the same key and feeds them to the same call to Reduce, thus this function just needs to

sum all of its input values to find the total appearances of that word.

2).海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

3).一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？

经典问题分析

上千万or亿数据（有重复），统计其中出现次数最多的前N个数据,分两种情况：可一次读入内存，不可一次读入。

可用思路：trie树+堆，数据库索引，划分子集分别统计，hash，分布式计算，近似统计，外排序

所谓的是否能一次读入内存，实际上应该指去除重复后的数据量。如果去重后数据可以放入内存，我们可以为数据建立字典，比如通过 map，hashmap，trie，然后直接进行统计即可。当然在更新每条数据的出现次数的时候，我们可以利用一个堆来维护出现次数最多的前N个数据，当然这样导致维护次数增加，不如完全统计后在求前N大效率高。

如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情形，可以做的改变就是将字典存放到硬盘上，而不是内存，这可以参考数据库的存储方法。

当然还有更好的方法，就是可以采用分布式计算，基本上就是map-reduce过程，首先可以根据数据值或者把数据hash(md5)后的值，将数据按照范围划分到不同的机子，最好可以让数据划分后可以一次读入内存，这样不同的机子负责处理各种的数值范围，实际上就是map。得到结果后，各个机子只需拿出各自的出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是reduce过程。

实际上可能想直接将数据均分到不同的机子上进行处理，这样是无法得到正确的解的。因为一个数据可能被均分到不同的机子上，而另一个则可能完全聚集到一个机子上，同时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个，我们将1000万的数据分布到10台机器上，找到每台出现次数最多的前 100个，归并之后这样不能保证找到真正的第100个，因为比如出现次数最多的第100个可能有1万个，但是它被分到了10台机子，这样在每台上只有1千个，假设这些机子排名在1000个之前的那些都是单独分布在一台机子上的，比如有1001个，这样本来具有1万个的这个就会被淘汰，即使我们让每台机子选出出现次数最多的1000个再归并，仍然会出错，因为可能存在大量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上，而是要根据hash 后的值将它们映射到不同的机子上处理，让不同的机器处理一个数值范围。

而外排序的方法会消耗大量的IO，效率不会很高。而上面的分布式方法，也可以用于单机版本，也就是将总的数据根据值的范围，划分成多个不同的子文件，然后逐个处理。处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排序的归并过程。

另外还可以考虑近似计算，也就是我们可以通过结合自然语言属性，只将那些真正实际中出现最多的那些词作为一个字典，使得这个规模可以放入内存。

PHP的性能探讨和测试

缘起

关于PHP 很多人的直观感觉是PHP是一种灵活的脚本语言 库类丰富 使用简单 安全 非常适合WEB开发 但性能低下 PHP的性能是否真 的就如同大家的感觉一样的差呢？本文就是围绕这么一个话题来进行探讨的 从源码 应用场景 基准性能 对比分析等几个方面深入分析PHP之性能问题 并通 过真实的数据来说话

从原理分析PHP性能

从原理分析PHP的性能 主要从以下几个方面 内存管理 变量 函数 运行机制来进行分析

内存管理

类似Nginx的内存管理方式 PHP在内部也是基于内存池 并且引入内存池的生命周期概念 在内存池方面 PHP对PHP脚本和扩展的所有内 存相关操作都进行了托管 对大内存和小内存的管理采用了不同的实现方式和优化 具体可以参考以下文档 在内存分配和回收的生命周期内 PHP采用一次初始化申请+动态扩容+内存标识回收机制 并且在每次请求结束后直 接对内存池进行重新mask

变量

总所周知 PHP是一种弱变量类型的语言 所以在PHP内部 所有的PHP变量都对应成一种类型Zval 其中具体定义如下

图一PHP变量

在变量方面 PHP做了大量的优化工作 比如说Reference counting和copy on writer机制 这样能够保证内存使用上的优化 并且减少内存拷贝次数（请参考） 在数组方面 PHP内部采用高效的hashtable来实现

函数

在PHP内部 所有的PHP函数都回转化成内部的一个函数指针 比如说扩展中函数

ZEND_FUNCTION ( my_function );//类似function my_function(){}

在内部展开后就会是一个函数

void zif_my_function ( INTERNAL_FUNCTION_PARAMETERS );

void zif_my_function(

int ht

zval * return_value

zval * this_ptr

int return_value_used

zend_executor_globals * executor_globals

);

从这个角度来看 PHP函数在内部也是对应一个函数指针

运行机制

在话说PHP性能的时候 很多人都会说“C/C++是编译型 JAVA是半编译型 PHP是解释型” 也就是说PHP是先动态解析再代码运行的 所以从这个角度来看 PHP性能必然很差

的确 从PHP脚本运行来输出 的确是一个动态解析再代码运行的过程 具体来说 PHP脚本的运行机制如下图所示

图二 PHP运行机制

PHP的运行阶段也分成三个阶段

Parse 语法分析阶段

Compile 编译产出opcode中间码

Execute 运行 动态运行进行输出

所以说 在PHP内部 本身也是存在编译的过程 并且据此产生了大量的opcode cache工具 比如说apc eacc xcache等等 这些opcode cache在生产环境基本上在标配 基于opcode cache 能到做到“PHP脚本编译一次 多次运行”的效果 从这点上 PHP就和JAVA的半编译机制非常类似

所以 从运行机制上来看 PHP的运行模式和JAVA是非常类似的 都是先产生中间码 然后运行在不同虚拟机上

动态运行

从上面的几个分析来看 PHP在内存管理 变量 函数 运行机制等几个方面都做了大量的工作 所以从原理来看 PHP 不应该存在性能问题 性能至少也应该和Java 比较接近

这个时候就不得不谈PHP动态语言的特性所带来的性能问题了 由于PHP是动态运行时 所以所有的变量 函数 对象调用 作用域实现等等都是在 执行阶段中才确定的 这个从根本上决定了PHP性能中很难改变的一些东西 在C/C++等能够在静态编译阶段确定的变量 函数 在PHP中需要在动态运行 中确定 也就决定了PHP中间码不能直接运行而需要运行在Zend Engine上

说到PHP变量的具体实现 又不得不说一个东西了 Hashtable Hashtable可以说在PHP灵魂之一 在PHP内部广泛用到 包含变量符号栈 函数符号栈等等都是基于hashtable的

以PHP变量为例来说明下PHP的动态运行特点 比如说代码

?php

$var = “hello  blog xiuwz ”;

?

该代码的执行结果就是在变量符号栈（是一个hashtable）中新增一个项

当要使用到该变量时候 就去变量符合栈中去查找（也就是变量调用对出了一个hash查找的过程）

同样对于函数调用也基本上类似有一个函数符号栈（hashtable）

其实关于动态运行的变量查找特点 在PHP的运行机制中也能看出一些 PHP代码通过解释 编译后的流程下图

图 PHP运行实例

从上图可以看出 PHP代码在pile之后 产出的了类符号表 函数符号表 和OPCODE 在真正执行的时候 zend Engine会根据op code去对应的符号表中进行查找 处理

从某种程度上 在这种问题的上 很难找到解决方案 因为这是由于PHP语言的动态特性所决定的 但是在国内外也有不少的人在寻找解决方案 因为 通过这样 能够从根本上完全的优化PHP 典型的列子有facebook的hiphop

结论

从上面分析来看 在基础的内存管理 变量 函数 运行机制方面 PHP本身并不会存在明显的性能差异 但由于PHP的动态运行特性 决定了 PHP和其他的编译型语言相比 所有的变量查找 函数运行等等都会多一些hash查找的CPU开销和额外的内存开销 至于这种开销具体有多大 可以通过后 续的基准性能和对比分析得出

因此 也可以大体看出PHP不太适合的一些场景 大量计算性任务 大数据量的运算 内存要求很严格的应用场景 如果要实现这些功能 也建议通过扩展的方式实现 然后再提供钩子函数给PHP调用 这样可以减低内部计算的变量 函数等系列开销

基准性能

对于PHP基准性能 目前缺少标准的数据 大多数同学都存在感性的认识 有人认为 QPS就是PHP的极限了 此外 对于框架的性能和框架对性能的影响很没有响应的权威数字

本章节的目的是给出一个基准的参考性能指标 通过数据给大家一个直观的了解

具体的基准性能有以下几个方面

裸PHP性能 完成基本的功能

裸框架的性能 只做最简单的路由分发 只走通核心功能

标准模块的基准性能 所谓标准模块的基准性能 是指一个具有完整服务模块功能的基准性能

环境说明

测试环境

Uname aPnux db forum test db baidu _ # SMP Wed Aug 　 : : CST x _ x _ x _ GNU/Pnux

Red Hat Enterprise Pnux AS release (Nahant Update )

Intel(R) Xeon(R) CPU           E   @ GHz

软件相关

Nginx nginx version: nginx/   built by gcc (Red Hat )

Php （采用php fpm）

PHP (cP) (built: Mar  : : )

Copyright (c) The PHP Group

Zend Engine v Copyright (c) Zend Technologies

with eAccelerator v Copyright (c) eAccelerator by eAccelerator

bingo

PHP框架

其他说明

目标机器的部署方式 nginx php fpm php脚本

测试压力机器和目标机器独立部署

裸PHP性能

最简单的PHP脚本

?php

require_once ‘ /actions/indexAction php’;

$objAction = new indexAction();

$objAction init();

$objAction execute();

?

Acitons/indexAction php里面的代码如下

?php

class indexAction

{

pubPc function execute()

{

echo ‘hello  world!’;

}

}

?

通过压力工具测试结果如下

裸PHP框架性能

为了和 的对比 基于bingo 框架实现了类似的功能 代码如下

?php

require_once ‘Bingo/Controller/Front php’;

$objFrontController = Bingo_Controller_Front::getInstance(array(

‘actionDir’ = ‘ /actions’

));

$objFrontController dispatch();

压力测试结果如下

从该测试结果可以看出 框架虽然有一定的消耗 但对整体的性能来说影响是非常小的

标准PHP模块的基准性能

所谓标准PHP模块 是指一个PHP模块所必须要具体的基本功能

路由分发

自动加载

LOG初始化Notice日志打印 所以的UI请求都一条标准的日志

错误处理

时间校正

自动计算每个阶段耗时开销

编码识别编码转化

标准配置文件的解析和调用

采用bingo 的代码自动生成工具产生标准的测试PHP模块 test

测试结果如下

结论

从测试数据的结论来看 PHP本身的性能还是可以的 基准性能完全能够达到几千甚至上W的QPS 至于为什么在大多数的PHP模块中表现不佳 其实这个时候更应该去找出系统的瓶颈点 而是简单的说OK PHP不行 那我们换C来搞吧 （下一个章节 会通过一些例子来对比 采用C来处理不见得有特 别的优势）

通过基准数据 可以得出以下几个具体的结论

PHP本身性能也很不错 简单功能下能够达到 QPS 极限也能过W

PHP框架本身对性能影响非常有限 尤其是在有一定业务逻辑和数据交互的情况下 几乎可以忽略

一个标准的PHP模块 基准性能能够达到 QPS（ cpu idle）

对比分析

lishixinzhi/Article/program/PHP/201311/21287

物联网，云计算，大数据能用php开发吗

物联网，云计算，大数据能用php开发

PHP（外文名:PHP: Hypertext Preprocessor，中文名：“超文本预处理器”）是一种通用开源脚本语言。语法吸收了C语言、Java和Perl的特点，利于学习，使用广泛，主要适用于Web开发领域。PHP 独特的语法混合了C、Java、Perl以及PHP自创的语法。它可以比CGI或者Perl更快速地执行动态网页。用PHP做出的动态页面与其他的编程语言相比，PHP是将程序嵌入到HTML（标准通用标记语言下的一个应用）文档中去执行，执行效率比完全生成HTML标记的CGI要高许多；PHP还可以执行编译后代码，编译可以达到加密和优化代码运行，使代码运行更快。

新闻标题：php适合做大数据吗 php能做大数据吗
当前地址：http://hbruida.cn/article/ddiscso.html