php数据平均分布算法 php数组平均值

PHP实现常见的排序算法

注:为方便描述,下面的排序全为正序(从小到大排序)

创新互联成立以来不断整合自身及行业资源、不断突破观念以使企业策略得到完善和成熟,建立了一套“以技术为基点,以客户需求中心、市场为导向”的快速反应体系。对公司的主营项目,如中高端企业网站企划 / 设计、行业 / 企业门户设计推广、行业门户平台运营、成都APP应用开发移动网站建设、微信网站制作、软件开发、四川乐山服务器托管等实行标准化操作,让客户可以直观的预知到从创新互联可以获得的服务效果。

假设有一个数组[a,b,c,d]

冒泡排序依次比较相邻的两个元素,如果前面的元素大于后面的元素,则两元素交换位置;否则,位置不变。具体步骤:

1,比较a,b这两个元素,如果ab,则交换位置,数组变为:[b,a,c,d]

2,比较a,c这两个元素,如果ac,则位置不变,数组变为:[b,a,c,d]

3,比较c,d这两个元素,如果cd,则交换位置,数组变为:[b,a,d,c]

完成第一轮比较后,可以发现最大的数c已经排(冒)在最后面了,接着再进行第二轮比较,但第二轮比较不必比较最后一个元素了,因为最后一个元素已经是最大的了。

第二轮比较结束后,第二大的数也会冒到倒数第二的位置。

依次类推,再进行第三轮,,,

就这样最大的数一直往后排(冒),最后完成排序。所以我们称这种排序算法为冒泡排序。

选择排序是一种直观的算法,每一轮会选出列中最小的值,把最小值排到前面。具体步骤如下:

插入排序步骤大致如下:

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

步骤:

从数列中挑出一个元素,称为 “基准”(pivot),

重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

php的:在指定的时间段内总是去除能够均匀分布在这个时间段内的数据???

可以在查询获取50条后对数据进行处理,那就是用公式如何50条取12条的问题,当然也可用随机,但是随机的分布就不是那么均匀了,另外也可用直接查询的时候用随机或者分段取值

php的memcached分布式hash算法,如何解决分布不均?crc32这个算法没办法把key值均匀的分布出去

memcached的总结和分布式一致性hash

当前很多大型的web系统为了减轻数据库服务器负载,会采用memchached作为缓存系统以提高响应速度。

目录: ()

memchached简介

hash

取模

一致性hash

虚拟节点

源码解析

参考资料

1. memchached简介

memcached是一个开源的高性能分布式内存对象缓存系统。

其实思想还是比较简单的,实现包括server端(memcached开源项目一般只单指server端)和client端两部分:

server端本质是一个in-memory key-value store,通过在内存中维护一个大的hashmap用来存储小块的任意数据,对外通过统一的简单接口(memcached protocol)来提供操作。

client端是一个library,负责处理memcached protocol的网络通信细节,与memcached server通信,针对各种语言的不同实现分装了易用的API实现了与不同语言平台的集成。

web系统则通过client库来使用memcached进行对象缓存。

2. hash

memcached的分布式主要体现在client端,对于server端,仅仅是部署多个memcached server组成集群,每个server独自维护自己的数据(互相之间没有任何通信),通过daemon监听端口等待client端的请求。

而在client端,通过一致的hash算法,将要存储的数据分布到某个特定的server上进行存储,后续读取查询使用同样的hash算法即可定位。

client端可以采用各种hash算法来定位server:

取模

最简单的hash算法

targetServer = serverList[hash(key) % serverList.size]

直接用key的hash值(计算key的hash值的方法可以自由选择,比如算法CRC32、MD5,甚至本地hash系统,如java的hashcode)模上server总数来定位目标server。这种算法不仅简单,而且具有不错的随机分布特性。

但是问题也很明显,server总数不能轻易变化。因为如果增加/减少memcached server的数量,对原先存储的所有key的后续查询都将定位到别的server上,导致所有的cache都不能被命中而失效。

一致性hash

为了解决这个问题,需要采用一致性hash算法(consistent hash)

相对于取模的算法,一致性hash算法除了计算key的hash值外,还会计算每个server对应的hash值,然后将这些hash值映射到一个有限的值域上(比如0~2^32)。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到,则直接把具有最小hash值的server作为目标server。

为了方便理解,可以把这个有限值域理解成一个环,值顺时针递增。

如上图所示,集群中一共有5个memcached server,已通过server的hash值分布到环中。

如果现在有一个写入cache的请求,首先计算x=hash(key),映射到环中,然后从x顺时针查找,把找到的第一个server作为目标server来存储cache,如果超过了2^32仍然找不到,则命中第一个server。比如x的值介于A~B之间,那么命中的server节点应该是B节点

可以看到,通过这种算法,对于同一个key,存储和后续的查询都会定位到同一个memcached server上。

那么它是怎么解决增/删server导致的cache不能命中的问题呢?

假设,现在增加一个server F,如下图

此时,cache不能命中的问题仍然存在,但是只存在于B~F之间的位置(由C变成了F),其他位置(包括F~C)的cache的命中不受影响(删除server的情况类似)。尽管仍然有cache不能命中的存在,但是相对于取模的方式已经大幅减少了不能命中的cache数量。

虚拟节点

但是,这种算法相对于取模方式也有一个缺陷:当server数量很少时,很可能他们在环中的分布不是特别均匀,进而导致cache不能均匀分布到所有的server上。

如图,一共有3台server – 1,2,4。命中4的几率远远高于1和2。

为解决这个问题,需要使用虚拟节点的思想:为每个物理节点(server)在环上分配100~200个点,这样环上的节点较多,就能抑制分布不均匀。

当为cache定位目标server时,如果定位到虚拟节点上,就表示cache真正的存储位置是在该虚拟节点代表的实际物理server上。

另外,如果每个实际server的负载能力不同,可以赋予不同的权重,根据权重分配不同数量的虚拟节点。

// 采用有序map来模拟环

this.consistentBuckets = new TreeMap();

MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值

// 计算总权重

if ( this.totalWeight for ( int i = 0; i this.weights.length; i++ )

this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];

} else if ( this.weights == null ) {

this.totalWeight = this.servers.length;

}

// 为每个server分配虚拟节点

for ( int i = 0; i servers.length; i++ ) {

// 计算当前server的权重

int thisWeight = 1;

if ( this.weights != null this.weights[i] != null )

thisWeight = this.weights[i];

// factor用来控制每个server分配的虚拟节点数量

// 权重都相同时,factor=40

// 权重不同时,factor=40*server总数*该server权重所占的百分比

// 总的来说,权重越大,factor越大,可以分配越多的虚拟节点

double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );

for ( long j = 0; j factor; j++ ) {

// 每个server有factor个hash值

// 使用server的域名或IP加上编号来计算hash值

// 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值:

// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor

byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );

// 每个hash值生成4个虚拟节点

for ( int h = 0 ; h 4; h++ ) {

Long k =

((long)(d[3+h*4]0xFF) 24)

| ((long)(d[2+h*4]0xFF) 16)

| ((long)(d[1+h*4]0xFF) 8 )

| ((long)(d[0+h*4]0xFF));

// 在环上保存节点

consistentBuckets.put( k, servers[i] );

}

}

// 每个server一共分配4*factor个虚拟节点

}

// 采用有序map来模拟环

this.consistentBuckets = new TreeMap();

MessageDigest md5 = MD5.get();//用MD5来计算key和server的hash值

// 计算总权重

if ( this.totalWeight for ( int i = 0; i this.weights.length; i++ )

this.totalWeight += ( this.weights[i] == null ) ? 1 : this.weights[i];

} else if ( this.weights == null ) {

this.totalWeight = this.servers.length;

}

// 为每个server分配虚拟节点

for ( int i = 0; i servers.length; i++ ) {

// 计算当前server的权重

int thisWeight = 1;

if ( this.weights != null this.weights[i] != null )

thisWeight = this.weights[i];

// factor用来控制每个server分配的虚拟节点数量

// 权重都相同时,factor=40

// 权重不同时,factor=40*server总数*该server权重所占的百分比

// 总的来说,权重越大,factor越大,可以分配越多的虚拟节点

double factor = Math.floor( ((double)(40 * this.servers.length * thisWeight)) / (double)this.totalWeight );

for ( long j = 0; j factor; j++ ) {

// 每个server有factor个hash值

// 使用server的域名或IP加上编号来计算hash值

// 比如server - "172.45.155.25:11111"就有factor个数据用来生成hash值:

// 172.45.155.25:11111-1, 172.45.155.25:11111-2, ..., 172.45.155.25:11111-factor

byte[] d = md5.digest( ( servers[i] + "-" + j ).getBytes() );

// 每个hash值生成4个虚拟节点

for ( int h = 0 ; h 4; h++ ) {

Long k =

((long)(d[3+h*4]0xFF) 24)

| ((long)(d[2+h*4]0xFF) 16)

| ((long)(d[1+h*4]0xFF) 8 )

| ((long)(d[0+h*4]0xFF));

// 在环上保存节点

consistentBuckets.put( k, servers[i] );

}

}

// 每个server一共分配4*factor个虚拟节点

}

// 用MD5来计算key的hash值

MessageDigest md5 = MD5.get();

md5.reset();

md5.update( key.getBytes() );

byte[] bKey = md5.digest();

// 取MD5值的低32位作为key的hash值

long hv = ((long)(bKey[3]0xFF) 24) | ((long)(bKey[2]0xFF) 16) | ((long)(bKey[1]0xFF) 8 ) | (long)(bKey[0]0xFF);

// hv的tailMap的第一个虚拟节点对应的即是目标server

SortedMap tmap = this.consistentBuckets.tailMap( hv );

return ( tmap.isEmpty() ) ? this.consistentBuckets.firstKey() : tmap.firstKey();

更多问题到问题求助专区()

php如何把一个数分成N份

大致思路

1)取份数的平均值

2)根据允许的各份数间最大差值,动态调整随机数范围,形成各份的数量

3)最后一份的数量由前面已经分出的决定,以保证各份的总和为指定值

代码如下:

?php

$total = 100; //待划分的数字

$div = 5; //分成的份数

$area = 10; //各份数间允许的最大差值

$average = round($total / $div);

$sum = 0;

$result = array_fill( 1, $div, 0 );

for( $i = 1; $i  $div; $i++ ){

//根据已产生的随机数情况,调整新随机数范围,以保证各份间差值在指定范围内

if( $sum  0 ){

$max = 0;

$min = 0 - round( $area / 2 );

}elseif( $sum  0 ){

$min = 0;

$max = round( $area / 2 );

}else{

$max = round( $area / 2 );

$min = 0 - round( $area / 2 );

}

//产生各份的份额

$random = rand( $min, $max );

$sum += $random;

$result[$i] = $average + $random;

}

//最后一份的份额由前面的结果决定,以保证各份的总和为指定值

$result[$div] = $average - $sum;

//结果呈现

echo '划分情况:br';

foreach( $result as $temp ){

echo $temp, 'br';

}

echo '总和:', array_sum( $result );

exit;

?


新闻名称:php数据平均分布算法 php数组平均值
当前路径:http://myzitong.com/article/ddesdpj.html