标签归档:算法

分布式唯一标识snowflake算法

snowflake算法核心:

这里写图片描述

如图,64位。主要由3块构成:时间戳、工作机器id、序列号。 
– 其中第一位不用,也可以理解作为正负数来使用,默认正数的。 
– 随后41位表示时间戳,在实际使用时,可以当做时间差来使用,比如现在离2017-01-01 00:00:00的时间差。这样的话,时间范围就能达到: (2^41-1)/(1000*60*60*24*365)=69.7年。 
– 中间10位用于工作机器的。可以用于 2^10-1=1023台机器。 
– 最后12位表示序列号,一个机器在一个毫秒时最大能产生 2^12-1=4095个。 
**在实际应用中,可能无需最大化的,比如时间戳只用30位就能达到要求的就无需41位,其他的同理。 
工作机器ID,可以是进程级别。机器级别的话,可以使用机器的mac地址或ip地址经过算法;如果是进程级别的话,可以使用path+进程标识;也可以混编,列如前5位标识机器,后5位标识进程。 
关于序列号有个注意点,如果一个毫秒内,序列号已经达到上限,就等到下一毫秒,同时序列号置零开始。**

具体代码:

/**
 * 
 **
 /
 public class MagicSnowFlake {
    private final static long twepoch = 1483200000000l;    //10bit(位)的工作机器id  中IP标识所占的位数 8bit(位)
    private final static long ipIdBits = 8L;    //IP标识最大值 255  即2的8次方减一。
    private final static long ipIdMax = ~ (-1L << ipIdBits);    //10bit(位)的工作机器id  中数字标识id所占的位数 2bit(位)
    private final static long dataCenterIdBits = 2L;    //数字标识id最大值 3  即2的2次方减一。
    private final static long dataCenterIdMax = ~ (-1L << dataCenterIdBits);    //序列在id中占的位数 12bit
    private final static long seqBits = 12L;    //序列最大值 4095 即2的12次方减一。
    private final static long seqMax = ~(-1L << seqBits);    // 64位的数字:首位0  随后41位表示时间戳 随后10位工作机器id(8位IP标识 + 2位数字标识) 最后12位序列号
    private final static long dataCenterIdLeftShift = seqBits;    private final static long ipIdLeftShift = seqBits + dataCenterIdBits;    private final static long timeLeftShift = seqBits  + dataCenterIdBits + ipIdLeftShift;    //IP标识(0~255)
    private long ipId;    // 数据中心ID(0~3)
    private long dataCenterId;    // 毫秒内序列(0~4095)
    private long seq = 0L;    // 上次生成ID的时间截
    private long lastTime = -1L;    
    
    public MagicSnowFlake(long ipId, long dataCenterId) {        
        if(ipId < 0 || ipId > ipIdMax) {
            System.out.println(" ---------- ipId不在正常范围内(0~"+ipIdMax +") " + ipId);
            System.exit(0);
        }        
        if(dataCenterId < 0 || dataCenterId > dataCenterIdMax) {
            System.out.println(" ---------- dataCenterId不在正常范围内(0~"+dataCenterIdMax +") " + dataCenterId);
            System.exit(0);
        }        
        this.ipId = ipId;       
        this.dataCenterId = dataCenterId;
    }    
    
    public synchronized long nextId() {        
        long nowTime = System.currentTimeMillis();        
        if(nowTime < lastTime) {
            System.out.println(" ---------- 当前时间前于上次操作时间,当前时间有误: " + nowTime);
            System.exit(0);
        }        
        
        if(nowTime == lastTime) {
            seq = (seq + 1) & seqMax;            
            if(seq == 0) {
                nowTime = getNextTimeStamp();
            }
        } else {
            seq = 0L;
        }

        lastTime = nowTime;        
        return ((nowTime - twepoch) << timeLeftShift
                | (ipId << ipIdLeftShift)
                | (dataCenterId << dataCenterIdLeftShift)
                | seq;
    }    
    
    private long getNextTimeStamp() {        
        long nowTime;
        do {
            nowTime = System.currentTimeMillis();
        } while(nowTime <= lastTime);       
        return nowTime;
    }
}

/**---------------------------------------------------------------**/

 public class ThreadSnowFlake extends Thread {

    MagicSnowFlake msf;    
    int cnt = 0;    
    public ThreadSnowFlake(MagicSnowFlake msf) {        
        this.msf = msf;
    }    
    
    public void run() {
        System.out.println();        
        if(msf != null) {            
            while(cnt < 10) {
                System.out.println(Thread.currentThread().getId() + " : " + msf.nextId());
                cnt ++;
            }
        }
    }
}

/**-----------------------------------------------------------------------**/
public class AlgorithmMain {

    public static void main(String[] args) {

        MagicSnowFlake msf = new MagicSnowFlake(196, 2);

        ThreadSnowFlake t1 = new ThreadSnowFlake(msf);
        ThreadSnowFlake t2 = new ThreadSnowFlake(msf);

        t1.start();
        t2.start();
    }
}

排序算法-堆排序-php

<?php
#堆排序
function heapSort(&$arr) {
    #初始化大顶堆
    initHeap($arr);
 
    #开始交换首尾节点,并每次减少一个末尾节点再调整堆,直到剩下一个元素
    for($end = count($arr) - 1; $end >= 0; $end--) {
        $temp = $arr[0];
        $arr[0] = $arr[$end];
        $arr[$end] = $temp;
        ajustNodes($arr, 0, $end - 1);
    }
}
 
#初始化最大堆,从最后一个非叶子节点开始,最后一个非叶子节点编号为 数组长度/2 向下取整
function initHeap(&$arr) {
    $len = count($arr);
    for($start = floor($len / 2) - 1; $start > 0; $start--) {
        ajustNodes($arr, $start, $len - 1);
    }
}
 
#调整节点
#@param $arr    待调整数组
#@param $start    调整的父节点坐标
#@param $end    待调整数组结束节点坐标
function ajustNodes(&$arr, $start, $end) {
    $maxInx = $start;
    $len = $end + 1;    #待调整部分长度
    $leftChildInx = ($start + 1) * 2 - 1;    #左孩子坐标
    $rightChildInx = ($start + 1) * 2;    #右孩子坐标
 
    #如果待调整部分有左孩子
    if($leftChildInx + 1 <= $len) {
        #获取最小节点坐标
        if($arr[$maxInx] < $arr[$leftChildInx]) {
            $maxInx = $leftChildInx;
        }
 
        #如果待调整部分有右子节点
        if($rightChildInx + 1 <= $len) {
            if($arr[$maxInx] < $arr[$rightChildInx]) {
                $maxInx = $rightChildInx;
            }
        }
    }
 
    #交换父节点和最大节点
    if($start != $maxInx) {
        $temp = $arr[$start];
        $arr[$start] = $arr[$maxInx];
        $arr[$maxInx] = $temp;
 
        #如果交换后的子节点还有子节点,继续调整
        if(($maxInx + 1) * 2 <= $len) {
            ajustNodes($arr, $maxInx, $end);
        }
    }
}
 
$arr = array(1, 5, 3, 7, 9 ,10, 2, 8);
heapSort($arr);
print_r($arr);
?>

kmp算法

#include<stdio.h>
#include<string.h>
void makeNext(const char P[],int next[])
{
    int q,k;
    int m = strlen(P);
    next[0] = 0;
    for (q = 1,k = 0; q < m; ++q)
    {
        while(k > 0 && P[q] != P[k])
            k = next[k-1];
        if (P[q] == P[k])
        {
            k++;
        }
        next[q] = k;
    }
}

int kmp(const char T[],const char P[],int next[])
{
    int n,m;
    int i,q;
    n = strlen(T);
    m = strlen(P);
    makeNext(P,next);
    for (i = 0,q = 0; i < n; ++i)
    {
        while(q > 0 && P[q] != T[i])
            q = next[q-1];
        if (P[q] == T[i])
        {
            q++;
        }
        if (q == m)
        {
            printf("Pattern occurs with shift:%d\n",(i-m+1));
        }
    }    
}

int main()
{
    int i;
    int next[20]={0};
    char T[] = "ababxbababcadfdsss";
    char P[] = "abcadfd";
    printf("%s\n",T);
    printf("%s\n",P );
    // makeNext(P,next);
    kmp(T,P,next);
    for (i = 0; i < strlen(P); ++i)
    {
        printf("%d ",next[i]);
    }
    printf("\n");

    return 0;
}

排序算法-归并算法

<?php
/**
* 并归排序
* 思想:将数据排序,一个小的,一个大的,这样遍历数据得时候,这样第一次遍历得时候可以得到一个(小,大),(小,大)数组
* 然后通过递归合并,(小1,大1),(小2,大2)每次取出2个数组的第一个数,比较,哪个小,放到一个新的数据tmp里面,然后小的数组current指针后移,继续比较,如果大1<小2,将大1放到
* tmp里面,然后将剩余的小2,大2依次放入数组,就是两个数组合并排序完了,即tmp = array(小1,大1,小2,大2)
*
* 如果刚才大1>小2,则先放入小2,然后(小2,大2)的数组current后移,然后比较大1和大2,如果大1>大2,则大2先放入tmp数组,剩下的大1,放入数组,就是(小1,小2,大2,大1)升序的排好数组
*/
//测试类
class MergeTest
{
private $data;
public function __construct($data)
{
$this->init($data);
}

//执行
public function run()
{
$this->merge();
print_r($this->data);
}
//初始化并归数组,相邻两个元素合并为一个数组(小的在前面)
private function init($data)
{
$tmp = [];
$num = count($data);
if ($num % 2 == 0) {
$items = $num / 2;
} else {
$items = ($num 1) / 2;
}

for ($i = 0; $i < $items; $i++) {
if ($data[2 * $i] < $data[2 * $i + 1]) {
array_push($tmp, [$data[2 * $i], $data[2 * $i + 1]]);
} else {
array_push($tmp, [$data[2 * $i + 1], $data[2 * $i]]);
}

}
if ($num % 2 != 0) {
array_push($tmp, [$data[$num 1]]);
}

$this->data = $tmp;
}

//并归递归调用
private function merge()
{
$re = [];
$size = count($this->data);
if ($size != 1) //没有完成并归,继续
{
for ($i = 0; $i < $size 1; $i += 2) {
$re[] = $this->doubleMerge($this->data[$i], $this->data[$i + 1]);
}

if ($size % 2 != 0) {
$re[] = $this->data[$size 1];
}

$this->data = $re;
$this->merge();
}
}

//合并两个有序序列
private function doubleMerge($a, $b)
{
$re = [];
$i = $j = 0;
$s1 = count($a);
$s2 = count($b);

while (true) {
if ($a[$i] <= $b[$j]) {
array_push($re, $a[$i]);
$i++;
} else {
array_push($re, $b[$j]);
$j++;
}

if ($i == $s1) {
return array_merge($re, array_slice($b, $j));
}

if ($j == $s2) {
return array_merge($re, array_slice($a, $i));
}

}

}
}

$a = new MergeTest([3,8,8,19, 1, 9, 2, 7, 6, 11,19, 5, 4, 13]);
$a->run();

最短路径算法-Dijkstra

image.png

<?php

//最短路径算法,核心思路是广度遍历
//一个p(a,b)表示a到b的最短距离路径,m,n是最短路径上的2个点,则p(a,m) p(m,n)一定是a到n的最短路径
//反证法:设q是a到n的最短距离,则有p(a,q) + p(q,n) < p(a,m) + p(m,n)
//p(a,q) + p(q,n) + (n,b) < p(a,m)+ p(m,n) + p(n,b) 即,p(a,q) + p(q,n) + p(n,b) < p(a,b)
//因为p(a,b)是最短距离,q不能比最短距离还短,所以,p(a,m) p(m,n)一定是最短距离
//使用二维数据来表示1个点到其它点之间的距离,为0表示无穷大
//aa = 0 ab = 2 ac = 0 ad = 1 ae = 5 af = 0 ag = 0
define("INT_MAX", 1000000);

$key_alphabet = array(0=>'a', 1=>'b', 2=>'c', 3=>'d', 4=>'e', 5=> 'f', 6=>'g');

$arr = array(
    array(0, 2, 0, 1, 5, 0, 0), //a
    array(2, 0, 4, 0, 0, 0, 0), //b
    array(0, 4, 0, 0, 2, 0, 0), //c
    array(1, 0, 0, 0, 2, 1, 0), //d
    array(5, 0, 2, 2, 0, 0, 4), //e
    array(0, 0, 0, 1, 0, 0, 3), //f
    array(0, 0, 0, 0, 4, 3, 0), //g
);

$ready_array = array(0); //最短路径集合
$future_array = array(1, 2, 3, 4, 5, 6); //未加入最短路径集合
$d = array();
$d_path = $key_alphabet[0] . '->';

//初始化图中节点与源点0的最小距离
for ($i = 1; $i < 7; $i++) {
    if ($arr[0][$i] > 0) {
        $d[$i]['value'] = $arr[0][$i];
        $d[$i]['path'] = $d_path . $key_alphabet[$i];
    } else {
        $d[$i]['value'] = INT_MAX;
        $d[$i]['path'] = '';
    }
}
// n-1次循环完成转移节点任务
for ($j = 1; $j < 7; $j++) {
    // 查找剩余节点中距离源点最近的节点v
    $current_min = INT_MAX;
    $current_min_v = 0;

    

    foreach ($future_array as $k => $v) {
        if ($d[$v]['value'] < $current_min) {
            $current_min = $d[$v]['value'];
            $current_min_v = $v;
        }
    }

    

    //$d_path .= $key_alphabet[$current_min_v] . '->';
    //ab  ac ad ae af ag 报存最短路径
    //$d[$current_min_v]['path'] = $d_path;
    $d[$current_min_v]['value'] = $current_min;

    //array_push($d_path, $d_path.$key_alphabet[$current_min_v] .'->');

    

    //从V中更新顶点到U中
    array_push($ready_array, $current_min_v);
    array_splice($future_array, array_search($current_min_v, $future_array), 1);
//var_dump($future_array);
    //更新
    foreach ($future_array as $k => $u) {
        if ($arr[$current_min_v][$u] != 0 && $d[$u]['value'] > $d[$current_min_v]['value'] + $arr[$current_min_v][$u]) {
            $d[$u]['value'] = $d[$current_min_v]['value'] + $arr[$current_min_v][$u];
            $d[$u]['path'] = $d[$current_min_v]['path'] . '->' . $key_alphabet[$u];
        }
    }
}

var_dump($d);
//打印最短路径

function print_short_path($d, $begin)
{
echo  $begin . "为起点的图的最短路径为:";
for ($i = 0; $i< 7; $i++) {
if($d[$i]!=INT_MAX)
echo  $d[$i] ."=" . $d[$i];
else {
echo $d[$i] . "是无最短路径的";
}
}
}

//print_short_path($d, 6);
//var_dump('最短路径是: ' . $d_path );
//var_dump("最短路径是: " . $d[6]);
// foreach ($ready_array as $k => $u) {
//  var_dump($k . '=>' . $key_alphabet[$u]);
// }

获得a点到各个点的最短路径和距离

array(6) {

  [1]=>

  array(2) {

    ["value"]=>

    int(2)

    ["path"]=>

    string(4) "a->b"

  }

  [2]=>

  array(2) {

    ["value"]=>

    int(5)

    ["path"]=>

    string(10) "a->d->e->c"

  }

  [3]=>

  array(2) {

    ["value"]=>

    int(1)

    ["path"]=>

    string(4) "a->d"

  }

  [4]=>

  array(2) {

    ["value"]=>

    int(3)

    ["path"]=>

    string(7) "a->d->e"

  }

  [5]=>

  array(2) {

    ["value"]=>

    int(2)

    ["path"]=>

    string(7) "a->d->f"

  }

  [6]=>

  array(2) {

    ["value"]=>

    int(5)

    ["path"]=>

    string(10) "a->d->f->g"

  }

}

排序算法-直接插入排序

<?php

function insert_sort($arr) {
//区分 哪部分是已经排序好的
//哪部分是没有排序的
//找到其中一个需要排序的元素
//这个元素 就是从第二个元素开始,到最后一个元素都是这个需要排序的元素
//利用循环就可以标志出来
//i循环控制 每次需要插入的元素,一旦需要插入的元素控制好了,
//间接已经将数组分成了2部分,下标小于当前的(左边的),是排序好的序列
$len=count($arr);
for($i=1; $i<$len; $i++)
{
//获得当前需要比较的元素值。
$tmp = $arr[$i];
//内层循环控制 比较 并 插入
for($j=$i-1;$j>=0;$j--) {
//$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素
if($tmp < $arr[$j]) {
//发现插入的元素要小,交换位置
//将后边的元素与前面的元素互换
$arr[$j+1] = $arr[$j];
//将前面的数设置为 当前需要交换的数
$arr[$j] = $tmp;
} else {
//如果碰到不需要移动的元素
//由于是已经排序好是数组,则前面的就不需要再次比较了。
break;
}
}
}
//将这个元素 插入到已经排序好的序列内。
//返回
return $arr;
}

$arr = array(8,4,6,3,9,1,7,2);

$sort_arr = insert_sort($arr);


print_R($sort_arr);

排序算法-冒泡排序

<?php

$arr=array(1,43,54,62,21,66,32,78,36,76,39);

function maopao($arr)
{
$len=count($arr);
//设置一个空数组 用来接收冒出来的泡
//该层循环控制 需要冒泡的轮数
for($i=1;$i<$len;$i++)
{ //该层循环用来控制每轮 冒出一个数 需要比较的次数
for($k=0;$k<$len-$i;$k++)
{
if($arr[$k]>$arr[$k+1])
{
$tmp=$arr[$k+1];
$arr[$k+1]=$arr[$k];
$arr[$k]=$tmp;
}
}
}
return $arr;
}

$newarr = maopao($arr);

print_r($newarr);

排序算法-快速排序

<?php

//快速排序
//待排序数组
$arr=array(6,3,8,6,4,2,9,5,1);
//函数实现快速排序
function quick_sort($arr)
{
//判断参数是否是一个数组
if(!is_array($arr)) return false;
//递归出口:数组长度为1,直接返回数组
$length=count($arr);
if($length<=1) return $arr;
//数组元素有多个,则定义两个空数组
$left=$right=array();
//使用for循环进行遍历,把第一个元素当做比较的对象
for($i=1;$i<$length;$i++)
{
//判断当前元素的大小
if($arr[$i]<$arr[0]){
$left[]=$arr[$i];
}else{
$right[]=$arr[$i];
}
}
//递归调用
$left=quick_sort($left);
$right=quick_sort($right);
//将所有的结果合并
return array_merge($left,array($arr[0]),$right);


}
//调用
echo "<pre>";
print_r(quick_sort($arr));