标签归档:算法

八大排序算法(冒泡,简单选择,直接插入,快速排序,希尔排序,归并排序,堆排序,基数排序)之代码实现(js&php版本) 

前言

从学习数据结构开始就接触各种算法基础,但是自从应付完考试之后就再也没有练习过,当在开发的时候也是什么时候使用什么时候去查一下,现在在学习JavaScript,趁这个时间再把各种基础算法整理一遍,分别以JS和PHP语法的方式编写代码。

冒泡排序

原理:临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位(因为较大的/较小的 总是交换到了右边,当到最后一位时,他肯定是最大的/最小的),然后再从头开始进行两两比较交换,直到倒数第二位时结束
时间复杂度:平均情况:O(n2) 最好情况:O(n) 最坏情况:O(n2)
空间复杂度:O(1)
稳定性:稳定

       //JavaScript语法
       var array = [23,0,32,45,56,75,43,0,34];

       for(var i = 0; i < array.length; i++)
       {
           var isSort = true;
           for(var j = 0; j < array.length - 1 - i; j++)
           {
               if(array[j] > array[j+1])
               {
                   isSort = false;
                   var temp = array[j];
                   array[j] = array[j + 1];
                   array[j + 1] = temp;
               }
           }
           //如果一次交换都没有产生,就说明数据已经是排过序的,可以直接退出。
           if(isSort)
           {
               break;
           }
       }
       console.log(array);    
 <?php
         $array = [23,0,32,45,56,75,43,0,34];
 
         for($i = 0; $i < count($array); $i++)
         {
             $isSort = true;
             for($j = 0; $j < count($array) - 1; $j++)
             {
                 if($array[$j] > $array[$j+1])
                 {
                     $isSort = false;
                     $temp = $array[$j];
                     $array[$j] = $array[$j + 1];
                     $array[$j + 1] = $temp;
                 }
             }
             if($isSort)
             {
                break;
             }
         }
         var_dump($array);
 ?>

简单选择排序

原理:通过n-i次关键字之间的比较,从n-i+1 个记录中选择关键字最小的记录,并和第i(1<=i<=n)个记录交换。简单说就是分成左右两堆,左堆排过序的,右堆未排序的,从未排序的右堆中找出最小的,放到已排序的左边,形成新的两堆,直到最后排序完成。
简单选择排序的性能要略优于冒泡排序
时间复杂度:平均情况:O(n2) 最好情况:O(n) 最坏情况:O(n2)
空间复杂度:O(1)
稳定性:不稳定

//JavaScript
        var array = [23,0,32,45,56,75,43,0,34];

        for(var i = 0; i < array.length - 1; i++)
        {
            var pos = i;
            for(var j = i + 1; j < array.length;j++)
            {
                if(array[j] < array[pos])
                {
                    pos=j;
                }
            }
            var temp=array[i];
            array[i]=array[pos];
            array[pos]=temp;
        }
        console.log(array);
 ```

 ```php
 <?php
         $array = [23,0,32,45,56,75,43,0,34];
         for($i = 0; $i < count($array); $i++)
     {
         $pos = $i;
         for($j = $i + 1;$j < count($array); $j++)
         {
             if($array[$j] < $array[$pos])
             {
                 $pos = $j;
             }
         }
         $temp = $array[$i];
         $array[$i] = $array[$pos];
         $array[$pos] = $temp;
     }
     var_dump($array);
 
 ?>

直接插入排序

原理:将一个记录插入到已排序好的有序表中,从而得到一个新的记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。
这个和平时打牌很像,左边是已排好序的,右边是未排序的。从右边第一个时,一个个拿,拿到后插入到左边已排序的正确位置上,直到排完。
比冒泡法和选择排序的性能要更好一些。
时间复杂度:平均情况:O(n2) 最好情况:O(n) 最坏情况:O(n2)
空间复杂度:O(1)
稳定性:稳定

//JavaScript
var array = [23,0,32,45,56,75,43,0,34];
 for(var j = 0;j < array.length;j++) {
     var key = array[j];
     var i = j - 1;
     while (i > -1 && array[i] > key)
     {
         array[i + 1] = array[i];
         i = i - 1;
     }
     array[i + 1] = key;
 }
 console.log(array);
<?php
    //直接插入排序
        $array = [23,0,32,45,56,75,43,0,34];
        for($i = 0; $i < count($array); $i++)
    {
        $key = $array[$i];
        $j= $i - 1;
        while($j > -1 && $array[$j] > $key)
        {
            $array[$j +1] = $array[$j];
            $j = $j - 1;
        }
        $array[$j + 1] = $key;
    }
    var_dump($array);
?> 

快速排序

原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。实际开发中用得最多的
时间复杂度:平均情况:O(nlog2n) 最好情况:O(nlog2n) 最坏情况:O(n2)
空间复杂度:O(nlog2n)
稳定性:不稳定

 //JavaScript 快速排序

 var array = [23,0,32,45,56,75,43,0,34];
 var quickSort = function(arr) {
    if (arr.length <= 1) { return arr; }//检查数组的元素个数,如果小于等于1,就返回。
    var pivotIndex = Math.floor(arr.length / 2);//
    var pivot = arr.splice(pivotIndex,1)[0];//选择"基准"(pivot),并将其与原数组分离,
    var left = [];//定义两个空数组,用来存放一左一右的两个子集
    var right = [];
    for (var i = 0; i < arr.length; i++)//遍历数组,小于"基准"的元素放入左边的子集,大于基准的元素放入右边的子集。
      {
          if (arr[i] < pivot) {
              left.push(arr[i]);
          } else {
              right.push(arr[i]);
          }
      }
 
      return quickSort(left).concat([pivot], quickSort(right));//使用递归不断重复这个过程,就可以得到排序后的数组。
  };
  var newArray=quickSort(array);
  console.log(newArray);
 <?php
                $array = [23,0,32,45,56,75,43,0,34];
         function quick_sort($arr) {
             //先判断是否需要继续进行
             $length = count($arr);
             if($length <= 1) {
                 return $arr;
             }
         
             $base_num = $arr[0];//选择一个标尺  选择第一个元素
 
             //初始化两个数组
             $left_array = array();//小于标尺的
             $right_array = array();//大于标尺的
             for($i=1; $i<$length; $i++) {            //遍历 除了标尺外的所有元素,按照大小关系放入两个数组内
                 if($base_num > $arr[$i]) {
                     //放入左边数组
                     $left_array[] = $arr[$i];
                 } else {
                     //放入右边
                     $right_array[] = $arr[$i];
                 }
             }
             //再分别对 左边 和 右边的数组进行相同的排序处理方式
             //递归调用这个函数,并记录结果
             $left_array = quick_sort($left_array);
             $right_array = quick_sort($right_array);
             //合并左边 标尺 右边
             return array_merge($left_array, array($base_num), $right_array);
         }
                $newArray=quick_sort($array);
                var_dump($newArray);
 ?>

希尔排序

原理:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。。
时间复杂度:平均情况:O(n√n) 最好情况:O(nlog2n) 最坏情况:O(n2)
空间复杂度:O(1)
稳定性:不稳定

javaScript  希尔排序
 var array = [23,0,32,45,56,75,43,0,34];
 var shellSort = function (arr)
 {
     var length=arr.length;
     var h=1;
     while(h<length/3)
     {
         h=3*h+1;//设置间隔
     }
     while(h>=1)
     {
         for(var i=h; i<length; i++)
         {
             for(var j=i; j>=h && arr[j]<arr[j-h]; j-=h)
             {
                 var temp =arr[j-h];
                 arr[j-h]=arr[j];
                 arr[j]=temp;
             }
         }
         h=(h-1)/3;
     }
     return arr;
 }
 var newArray = shellSort(array);
 console.log(newArray);
 <?php
 //希尔排序
         $array = [23,0,32,45,56,75,43,0,34];
         function shellSort($arr)
         {
             $length=count($arr);
             $h=1;
             while($h<$length/3)
             {
                 $h=3*$h+1;//设置间隔
             }
             while($h>=1)
             {
                 for($i=$h; $i<$length; $i++)
                 {
                     for($j=$i; $j>=$h && $arr[$j]<$arr[$j-$h]; $j-=$h)
                     {
                          $temp =$arr[$j-$h];
                          $arr[$j-$h]=$arr[$j];
                          $arr[$j]=$temp;
                     }
                 }
                 $h=($h-1)/3;
             }
             return $arr;
         }
         $newArray = shellSort($array);
         var_dump($newArray)
 ?>

归并排序

原理:假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,…如此重复,直至得到一个长度为n的有序序列为止
时间复杂度:平均情况:O(nlog2n) 最好情况:O(nlog2n) 最坏情况:O(nlog2n)
空间复杂度:O(1)
稳定性:稳定

 //JavaScript 归并排序
         function isArray1(arr){
             if(Object.prototype.toString.call(arr) =='[object Array]'){
                 return true;
             }else{
                 return false;
             }
         }
         function merge(left,right){
             var result=[];
             if(!isArray1(left)){
                 left = [left];
             }
             if(!isArray1(right)){
                 right = [right];
             }
             while(left.length > 0&& right.length >0){
                 if(left[0]<right[0]){
                     result.push(left.shift());
                 }else{
                     result.push(right.shift());
                 }
             }
             return result.concat(left).concat(right);
         }
 
         function mergeSort(arr){
             var len=arr.length;
             var lim ,work=[];
             var i,j,k;
             if(len ==1){
                 return arr;
             }
             for(i=0;i<len;i++){
                 work.push(arr[i]);
             }
             work.push([]);
             for(lim=len;lim>1;){//lim为分组长度
                 for(j=0,k=0;k<lim;j++,k=k+2){
                     work[j]=merge(work[k],work[k+1]);
                 }
                 work[j]=[];
                 lim=Math.floor((lim+1)/2);
             }
             return work[0];
         }
         var array = [23,0,32,45,56,75,43,0,34];
         
         console.log(mergeSort(array));
<?php  
      //归并排序
       function mergeSort(&$arr) {
            $len = count($arr);//求得数组长度
         
            mSort($arr, 0, $len-1);
        }
        //实际实现归并排序的程序
        function mSort(&$arr, $left, $right) {
         
            if($left < $right) {
                //说明子序列内存在多余1个的元素,那么需要拆分,分别排序,合并
                //计算拆分的位置,长度/2 去整
                $center = floor(($left+$right) / 2);
                //递归调用对左边进行再次排序:
                mSort($arr, $left, $center);
                //递归调用对右边进行再次排序
                mSort($arr, $center+1, $right);
                //合并排序结果
                mergeArray($arr, $left, $center, $right);
            }
        }

        //将两个有序数组合并成一个有序数组
        function mergeArray(&$arr, $left, $center, $right) {
            //设置两个起始位置标记
            $a_i = $left;
            $b_i = $center+1;
            while($a_i<=$center && $b_i<=$right) {
                //当数组A和数组B都没有越界时
                if($arr[$a_i] < $arr[$b_i]) {
                    $temp[] = $arr[$a_i++];
                } else {
                    $temp[] = $arr[$b_i++];
                }
            }
            //判断 数组A内的元素是否都用完了,没有的话将其全部插入到C数组内:
            while($a_i <= $center) {
                $temp[] = $arr[$a_i++];
            }
            //判断 数组B内的元素是否都用完了,没有的话将其全部插入到C数组内:
            while($b_i <= $right) {
                $temp[] = $arr[$b_i++];
            }
         
            //将$arrC内排序好的部分,写入到$arr内:
            for($i=0, $len=count($temp); $i<$len; $i++) {
                $arr[$left+$i] = $temp[$i];
            }
         
        }

        $arr = array(23,0,32,45,56,75,43,0,34);
        mergeSort($arr);
        var_dump($arr);
?>

堆排序

原理:堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便��得到一个有序序列了
时间复杂度:平均情况:O(nlog2n) 最好情况:O(nlog2n) 最坏情况:O(nlog2n)
空间复杂度:O(1)
稳定性:不稳定

//JavaScript  堆排序    
      var array = [23,0,32,45,56,75,43,0,34];
       function heapSort(array)
       {
           for (var i = Math.floor(array.length / 2); i >= 0; i--)
           {
               heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆
           }
           for (i = array.length - 1; i >= 0; i--)
           {
               /*把根节点交换出去*/
               var temp = array[i];
               array[i] = array[0];
               array[0] = temp;
               /*余下的数组继续构建成大顶堆*/
               heapAdjust(array, 0, i - 1);
           }
           return array;
       }

       function heapAdjust(array, start, max)
       {
           var temp = array[start];//temp是根节点的值
           for (var j = 2 * start; j < max; j *= 2)
           {
               if (j < max && array[j] < array[j + 1])
               {  //取得较大孩子的下标
                   ++j;
               }
               if (temp >= array[j])
                   break;
               array[start] = array[j];
               start = j;
           }
           array[start] = temp;
       }
       var newArray = heapSort(array);
       console.log(newArray);
 
<?php
    //堆排序
    function heapSort(&$arr) {
        #初始化大顶堆
        initHeap($arr, 0, count($arr) - 1);
        
        #开始交换首尾节点,并每次减少一个末尾节点再调整堆,直到剩下一个元素
        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(23,0,32,45,56,75,43,0,34);
    heapSort($arr);
    var_dump($arr);
?>        

基数排序

原理:将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
时间复杂度:平均情况:O(d(r+n)) 最好情况:O(d(n+rd)) 最坏情况:O(d(r+n)) r:关键字的基数 d:长度 n:关键字个数
空间复杂度:O(rd+n)
稳定性:稳定

<?php
      #基数排序,此处仅对正整数进行排序,至于负数和浮点数,需要用到补码,各位有兴趣自行研究
      
      #计数排序
      #@param $arr 待排序数组
      #@param $digit_num 根据第几位数进行排序
      function counting_sort(&$arr, $digit_num = false) {
          if ($digit_num !== false) { #如果参数$digit_num不为空,则根据元素的第$digit_num位数进行排序
              for ($i = 0; $i < count($arr); $i++) {
                  $arr_temp[$i] = get_specific_digit($arr[$i], $digit_num);
              } 
          } else {
              $arr_temp = $arr;
          }
  
          $max = max($arr);
          $time_arr = array(); #储存元素出现次数的数组
  
          #初始化出现次数数组
          for ($i = 0; $i <= $max; $i++) {
              $time_arr[$i] = 0;
          }
  
          #统计每个元素出现次数
          for ($i = 0; $i < count($arr_temp); $i++) {
              $time_arr[$arr_temp[$i]]++;
          }
  
          #统计每个元素比其小或相等的元素出现次数
          for ($i = 0; $i < count($time_arr) - 1; $i++) {
              $time_arr[$i + 1] += $time_arr[$i];
          }
  
          #利用出现次数对数组进行排序
          for($i = count($arr) - 1; $i >= 0; $i--) {
              $sorted_arr[$time_arr[$arr_temp[$i]] - 1] = $arr[$i];
              $time_arr[$arr_temp[$i]]--;
          }
  
          $arr = $sorted_arr;
          ksort($arr);    #忽略这次对key排序的效率损耗
      }
  
      #计算某个数的位数
      function get_digit($number) {
         $i = 1;
         while ($number >= pow(10, $i)) {
            $i++;
         }

         return $i;
      }
  
      #获取某个数字的从个位算起的第i位数
      function get_specific_digit($num, $i) {
         if ($num < pow(10, $i - 1)) {
             return 0;
         }
         return floor($num % pow(10, $i) / pow(10, $i - 1));
      }
  
      #基数排序,以计数排序作为子排序过程
      function radix_sort(&$arr) {
          #先求出数组中最大的位数
          $max = max($arr);
          $max_digit = get_digit($max);
  
          for ($i = 1; $i <= $max_digit; $i++) {
              counting_sort($arr, $i);
          }   
      }
  
  
      $arr = array(23,0,32,45,56,75,43,0,34);
      radix_sort($arr);
  
      var_dump($arr);
?>    

主宰这个世界的10种算法

Reddit有篇帖子介绍了算法对我们现在生活的重要性,以及哪些算法对现代文明所做贡献最大。如果对算法有所了解,读这篇文章时你可能会问“作者知道算法为何物吗?”,或是“Facebook的‘信息流’(News Feed)算是一种算法吗?”,如果“信息流”是算法,那就可以把所有事物都归结为一种算法。才疏学浅,结合那篇帖子,接下来我试着解释一下算法是什么,又是哪10个算法正在主导我们的世界。

JQI6.jpg

什么是算法?

简而言之,任何定义明确的计算步骤都可称为算法,接受一个或一组值为输入,输出一个或一组值。(来源:homas H. Cormen, Chales E. Leiserson 《算法导论第3版》)

可以这样理解,算法是用来解决特定问题的一系列步骤(不仅计算机需要算法,我们在日常生活中也在使用算法)。算法必须具备如下3个重要特性:

[1] 有穷性。执行有限步骤后,算法必须中止。

[2] 确切性。算法的每个步骤都必须确切定义。

[3] 可行性。特定算法须可以在特定的时间内解决特定问题,

其实,算法虽然广泛应用在计算机领域,但却完全源自数学。实际上,最早的数学算法可追溯到公元前1600年-Babylonians有关求因式分解和平方根的算法。

那么又是哪10个计算机算法造就了我们今天的生活呢?请看下面的表单,排名不分先后:

1. 归并排序(MERGE SORT),快速排序(QUICK SORT)和堆积排序(HEAP SORT)

AI7N.jpg

哪个排序算法效率最高?这要看情况。这也就是我把这3种算法放在一起讲的原因,可能你更常用其中一种,不过它们各有千秋。

归并排序算法,是目前为止最重要的算法之一,是分治法的一个典型应用,由数学家John von Neumann于1945年发明。

快速排序算法,结合了集合划分算法和分治算法,不是很稳定,但在处理随机列阵(AM-based arrays)时效率相当高。

堆排序,采用优先伫列机制,减少排序时的搜索时间,同样不是很稳定。

与早期的排序算法相比(如冒泡算法),这些算法将排序算法提上了一个大台阶。也多亏了这些算法,才有今天的数据发掘,人工智能,链接分析,以及大部分网页计算工具。

2. 傅立叶变换和快速傅立叶变换

这两种算法简单,但却相当强大,整个数字世界都离不开它们,其功能是实现时间域函数与频率域函数之间的相互转化。能看到这篇文章,也是托这些算法的福。

因特网,WIFI,智能机,座机,电脑,路由器,卫星等几乎所有与计算机相关的设备都或多或少与它们有关。不会这两种算法,你根本不可能拿到电子,计算机或者通信工程学位。(USA)

3.迪杰斯特拉算法 (Dijkstra’s algorithm)

可以这样说,如果没有这种算法,因特网肯定没有现在的高效率。只要能以“图”模型表示的问题,都能用这个算法找到“图”中两个节点间的最短距离。

虽然如今有很多更好的方法来解决最短路径问题,但迪杰斯特拉算法的稳定性仍无法取代。

4. RSA非对称加密算法

FS6I.jpg

毫不夸张地说,如果没有这个算法对密钥学和网络安全的贡献,如今因特网的地位可能就不会如此之高。现在的网络毫无安全感,但遇到钱相关的问题时我们必需要保证有足够的安全感,如果你觉得网络不安全,肯定不会傻乎乎地在网页上输入自己的银行卡信息。

RSA算法,密钥学领域最牛叉的算法之一,由RSA公司的三位创始人提出,奠定了当今的密钥研究领域。用这个算法解决的问题简单又复杂:保证安全的情况下,如何在独立平台和用户之间分享密钥。

5. 哈希安全算法(Secure Hash Algorithm)

确切地说,这不是一种算法,而是一组加密哈希函数,由美国国家标准技术研究所首先提出。无论是你的应用商店,电子邮件和杀毒软件,还是浏览器等等,都使用这种算法来保证你正常下载,以及是否被“中间人攻击”,或者“网络钓鱼”。

6. 整数质因子分解算法(Integer factorization)

这其实是一个数学算法,不过已经广泛应用与计算机领域。如果没有这个算法,加密信息也不会如此安全。通过一系列步骤将,它可以将一个合成数分解成不可再分的数因子。

很多加密协议都采用了这个算法,就比如刚提到的RSA算法。

7. 链接分析算法(Link Analysis)

CNA8.jpg

在因特网时代,不同入口间关系的分析至关重要。从搜索引擎和社交网站,到市场分析工具,都在不遗余力地寻找因特网的正真构造。

链接分析算法一直是这个领域最让人费解的算法之一,实现方式不一,而且其本身的特性让每个实现方式的算法发生异化,不过基本原理却很相似。

链接分析算法的机制其实很简单:你可以用矩阵表示一幅“图“,形成本征值问题。本征值问题可以帮助你分析这个“图”的结构,以及每个节点的权重。这个算法于1976年由Gabriel Pinski和Francis Narin提出。

谁会用这个算法呢?Google的网页排名,Facebook向你发送信息流时(所以信息流不是算法,而是算法的结果),Google+和Facebook的好友推荐功能,LinkedIn的工作推荐,Youtube的视频推荐,等等。

普遍认为Google是首先使用这类算法的机构,不过其实早在1996年(Google问世2年前)李彦宏就创建的“RankDex”小型搜索引擎就使用了这个思路。而Hyper Search搜索算法建立者马西莫·马奇奥里也曾使用过类似的算法。这两个人都后来都成为了Google历史上的传奇人物。

8. 比例微积分算法(Proportional Integral Derivative Algorithm)

CHZ7.jpg

飞机,汽车,电视,手机,卫星,工厂和机器人等等事物中都有这个算法的身影。

简单来讲,这个算法主要是通过“控制回路反馈机制”,减小预设输出信号与真实输出信号间的误差。只要需要信号处理,或电子系统来控制自动化机械,液压和加热系统,都需要用到这个算个法。

没有它,就没有现代文明。

9. 数据压缩算法

数据压缩算法有很多种,哪种最好?这要取决于应用方向,压缩mp3,JPEG和MPEG-2文件都不一样。

哪里能见到它们?不仅仅是文件夹中的压缩文件。你正在看的这个网页就是使用数据压缩算法将信息下载到你的电脑上。除文字外,游戏,视频,音乐,数据储存,云计算等等都是。它让各种系统更轻松,效率更高。

10. 随机数生成算法

到如今,计算机还没有办法生成“真正的”随机数,但伪随机数生成算法就足够了。这些算法在许多领域都有应用,如网络连接,加密技术,安全哈希算法,网络游戏,人工智能,以及问题分析中的条件初始化。

这个表单并不完整,很多与我们密切相关的算法都没有提到,如机器学习和矩阵乘法。另外,知识有限,如有批漏,还望指正。

 

个性化算法那么牛逼,为什么拯救不了你的产品?

没人带,自学慢,不在BAT怎么学产品?人人都是产品经理联合200+BAT资深产品经理带你学 点此查看详情

现在是一个个性化的时代,这个时代还将继续个性化下去

-Sugar

gexinhuasuanfan

现在几乎所有的产品都在做一件事情:为了提高用户的点击率、日活,通过对用户行为的分析,得出用户画像,然后为用户推送个性化的内容。

在电商行业,利用个性化算法最为成功的是淘宝。

IMG_5054

手机淘宝能够根据你的每一次访问计算你的购物偏好,通过不同渠道或者用不同方式,为你推荐你可能喜欢的商品和店铺、推送相关的内容或活动等。在你的一次点击前后,页面的内容就会发生一次变化。这种精准的计算和推荐模式为手淘带来了更高的用户活跃度和转化率。

于是,我们想以手淘个性化的成功案例作为参考,希望我们的产品更加个性化,可以更精准地击中用户的诉求,于是做了一个新版应用个性化算法的首页。

然而,点击量虽然有提升,但是效果并不明显。

事后反思,我们和手淘有这四方面明显的差别:

1|手淘商品多,我们商品少

手淘的类目比其他产品要丰富得多

手淘的商品有庞大的类目数量,每个类目有更庞大的商家提供海量的商品。而有的产品内容并没有那么丰富,就旅行而言,提供服务的商家并没有那么多,商品无非机票酒店跟团游自由行,线路来来回回也就昆大丽,日韩东南亚这些。所以从商品数量来讲,手淘多,我们少。

2|手淘商品差异性大,我们的商品差异性小

我和女朋友的手淘界面完全不一样

商品的差异性越大,个性化算法的价值也就越大。不同用户会喜欢不同种类的商品,而且具有明显的区别。就像平时买parda的人,打死也不会买zara。再加上商品的差异性与数量是正相关的,数量越多,商品性质也会产生更大的差异。

3|手淘用户量大,我们用户量少

手淘的用户量比我们要大得多

用户数量越多,越需要个性化的算法。一般来讲,用户越多,用户的需求就越多,种类也越丰富。在需求太多人工无法满足的时候,通过机器的优势显而易见。而如果用户的需求本来就没有那么多,个性化的价值就会被削弱。

4|手淘用户差异性大,我们用户差异性小

手淘的用户需求比我们大得多

去逛淘宝买东西的用户,从购买期望来划分就有成百上千的目的性,再细分到价格、品牌等维度又有数不清的选择性。而选择旅行的用户,根据目的地划分大多数情况也不超过100个,就算细分到玩法也比不上淘宝那么夸张。

总结

综上,我们可以对个性化算法的应用场景进行一下总结:

  • 内容数量越多,个性化算法越重要
  • 内容质量差异性越大,个性化算法越重要
  • 用户数量越多,个性化算法越重要
  • 用户差异性越大,个性化算法越重要

这四点导致,如果在目前阶段照搬手淘的个性化方案,可能并没有手淘那么好的效果,反而可能由于个性化,让个性化的商品把优质好商品挤出用户的触及范围。

个性化内容的关系

举个例子:我有10000篇文章,其中有100篇是超级热门的文章,但这100篇超级热门的文章中只有1篇是关于杭州这个目的地的。现在我们知道一个用户对杭州感兴趣,要给用户推送4篇杭州相关他可能感兴趣的内容,于是从10000篇文章里挑了4篇杭州相关的文章,我们认为这是对用户的精准推荐,但用户实际看到的内容中,除了1篇超级热门的他愿意看,其他的3篇全都是腊鸡。

而如果我有更多的文章,就有更多可选择的优质内容推送给用户。

所以大家可以参考这四点总结,首先看自己的产品是否有做个性化的潜力,然后找到不足的点(比如内容不够丰富),然后弥补不足,让个性化的效果最大化。

 

作者:Sugar(微信alibabadesigner)阿里高级设计师

本文由 @Sugar 原创发布于人人都是产品经理。未经许可,禁止转载。

Facebook动态消息算法揭秘:它比你还了解你自己

没人带,自学慢,不在BAT怎么学产品?人人都是产品经理联合200+BAT资深产品经理带你学 点此查看详情

你登陆社交网站,以为新鲜事中都是自己订阅的内容,但它还包括平台想让你看到的,以及猜测你可能喜爱的内容。平台会猜测用户的心思,用户也往往沦为小白鼠。本文编译自SLATE,揭露了Facebook动态消息的背后的技术原理。为了了解你,科技公司可是很努力的。

suanfasheji

每次你打开 Facebook ,这个世界上最具影响力,最有争议也是最被人误解的一套算法机制就开始运行。它会收集关于你的一切状态更新:你朋友每周发过的状态,你关注的每一个人,你加入的每一个群组,以及你赞过的每一条消息。对于 Facebook 用户来说,平均每周有一千五百次状态更新。如果你有数百位好友,那这个数字可能会高达一万以上。通过对这些数据细致入微的观察,工程师们对推荐算法进行不断的优化,Facebook 的动态消息(news feed)才能做到出现你真正感兴趣的内容。因为,大多数人并不会每天都把时间线完整看一遍,只会看最上面几百个。

没有人能够猜透 Facebook 的算法究竟是如何生成的,而内部人员更不可能告诉你这些。这个自动化的算法对于人们的社交有着重大的影响,而且它决定了我们每天会看到什么,要知道世界上有五分之一的人口——近 10 亿的 Facebook 活跃用户每天就在动态消息里面阅读新闻。病毒式扩散的算法机制完全颠覆了传统的媒体,把新兴的创业公司 BuzzFeed 和 Vox 市值推上了高位,而拥有一百年历史的报纸们则被陆续带进了坟墓。社交游戏公司 Zynga 和团购网站  LivingSocial 凭借 Facebook ,在短短一两年的时间内就做到了数十亿美金的估值,投资者们赚得盆满钵满。Facebook 的动态消息甚至能够左右我们的喜怒哀乐,它推送给我们真正优质有趣的消息,并将仅仅是情绪性的表达筛选掉。

然而, 尽管它拥有如此的权力,它的动态消息却一直难以让人满意,推送的内容十分随意,变幻莫测,有时候甚至出奇的不雅。经常会推送一些无关紧要的东西,谣言,琐事,充满戾气的话,或者是无趣的消息。Facebook 的内部人员很清楚这件事。在过去的几个月内,这个社交网络巨头开始将重新设计过的动态消息推送算法在用户内进行小范围的测试,你猜结果如何?

用户们普遍反馈「有时」,新的动态消息会击中他们的兴奋点。Facebook 对此表示欣慰,并强调会进行持续性的改进。

「有时」代表着你离完全的成功还有很长的路要走。

近年来,Facebook 和其他硅谷巨头们越来越习惯于用机器学习软件替我们做出选择。硅谷明星埃隆马斯克和著名科学家霍金都曾经提出警惕人工智能的观点,而「算法」这个词本身,就是为了大幅提高效率而生的。「算法」对于普通人来说,是「不明觉厉」的计算机名词,神秘而充满魔性,而 Facebook 等科技巨头使用的算法更是令人好奇。

最近,我参观了 Facebook 总部,与动态消息的算法团队相处,了解这套机制背后的故事。他们是如何把臭名昭著的动态消息算法扭转口碑的,为什么要这么做,如何做到,及背后的运行机理。此外,我们还能了解到很多关于算法局限性的问题,数据有时候也会撒谎,Facebook 为此专门请了外包团队进行人肉反馈,以达到更准确的效果。

算法

Facebook 的算法,据我所知,有点小瑕疵并非系统的缘故。以现在的科技水平而言,算法想要达到科幻小说一般洞悉人性是不可能的。Facebook 算法的背后还是人。工程师们决定了数据的筛选,加工,及输出。算法出错,背锅的当然是设计算法的工程师。算法的一步步进化,也是无数工程师们看了无数的数据,开了无数会议,反复测试,最终的结果。然而,Facebook 算法的持续进步仍然使人感到好奇,他们是如何做到的?

Facebook动态消息算法揭秘:它比你还了解你自己

当我到达 Facebook 总部时,一名 37 岁的大男孩接待了我,他脸上挂着善意微笑,充沛的精力及旺盛的表达欲望是他最明显的特征。他就是 Tom Alison ,「动态消息」算法的工程主管,他管理着设计算法的工程师们。

Alison 带着我穿过迷宫般的 Facebook 办公区,穿过一个小厨房之后,我们进入了一件小型会议室里。Alison 向我承诺会把 Facebook 算法背后的原理讲清楚,即使对于我这种外行来说。 到了以后,我想去一趟洗手间,我问了他应该怎么走。他很抱歉的对我说,「还是我带你去吧」。起初我以为他是怕我迷路,当我从洗手间出来时,发现他就站在门口等着我。我不禁认为,他被上级要求不能让我在办公室里单独走动。

Facebook动态消息算法揭秘:它比你还了解你自己

Facebook 总部

同样,Facebook 对于他们的商务信息守口如瓶,Alison 不能告诉我有关「动态消息」 算法的实际代码。然而,他能告诉我大概的原理,以及为什么它一直在改变。工程师们通常喜欢站在白板前讲解,他也不例外。

刚开始学习计算机科学的时候,你第一个接触到的算法必然是关于排序的。他在白板上快速的写下这几个数:4、1、3、2、5。

接着,他随手写下了一个简单的任务:设计一套算法,使数组按从小到大排序。「人类可以很容易的做到,这仅仅是举手之劳而已。」他对我说。

然而,对于计算机,你应该给出具体而明确的方法。这就需要算法的帮忙:算法就是用于计算机解决问题的一系列步骤。Alison 告诉我的算法叫「冒泡排序」 ,它的具体做法如下:

  • 1.对于每一个数组,从第一个数起,与后一个数比较大小,如果后者较大,则不变。
  • 2.如果前者较大,则两者置换位置。
  • 3.重复前两步,直到没有任何一对数字需要比较。

冒泡排序的优点是简单易懂。坏处也显而易见,如果你的数据过大,计算量会很大,速度也随之变慢。对于 Facebook 数十亿用户而言,当然不能用这种算法。Facebook 的算法要求你在打开 App 的瞬间就把所有的动态消息准确归位,对速度的要求极其严苛。但这仅仅是算法里的子算法而已。最重要的是把所有的动态消息按照正确的方式排序,最重要的出现在最顶端。这就是 Facebook news feed 排序团队的工作了,就是把所有用户关注的信息按用户的关联度排序。

这是一项非常艰难的任务。因为你在 Facebook 上的朋友们发的消息,还有你关注的明星们发的消息,哪些「和你有关」,是很难量化的事情。为此,Alison 解释,Facebook 使用了一套与众不同的算法,称为预测式算法。(Facebook 的 news feed 算法,和谷歌的搜索引擎算法,Netflix 的推荐算法都是分布式的复杂算法,包涵很多小的算法)

让我们猜猜下一场篮球赛,公牛对湖人,谁会赢? Alison 说。「公牛」,我不假思索的说出了口。Alison 笑了,但他随后点头表示同意  。如果把我的大脑类比为计算机,我刚刚输入了他提的问题,输出了 公牛这个回答,我大脑里的直觉反应就是算法。(人类心灵的算法远比目前计算机使用的复杂的多,但稳定性也差的多)

「当你不会感到压力时,这种仅凭直觉的猜测往往正确率惊人。」Alison 说。「但如果刚刚的猜测有金钱上的挂钩,数百万每次,每天预测数百次。那我们就需要一个成体系的方法。你可能会看看历史数据,每一个球队的胜负纪录,是否有伤员,谁正手感火热。可能你还会考虑环境因素,谁是主场?客队是背靠背比赛还是经过了一段时间的休息?你的算法可能会把这些因素全部考虑在内。如果你的算法足够完美,你可能不仅仅预测到了胜负情况,你连比分都能猜个大概。」

同理,Facebook 的动态消息算法也是这样的情况。(动态消息是 Faceboook 最大的现金牛,平均日入 2000 万美金)我问 Alison 在 Facebook 算法的机器学习语言中,总共考虑了多少种条件,他回答道「数百种。」

Facebook动态消息算法揭秘:它比你还了解你自己

Adam Mosseri (站着)

Facebook动态消息算法揭秘:它比你还了解你自己

整个动态消息算法设计团队

它不仅仅会根据你以往的点赞习惯预测你会不会点赞。它还会预测你点击展开全文,评论,分享的可能性,甚至标记为垃圾的可能性。从而确定一个关联分,这个分数决定了它是否会出现在你的动态消息列表中,以及所在的位置。所以,每次你打开 Facebook 动态消息上的第一条,是从数百条消息中脱颖而出的,最能刺激你点赞,评论,分享,及改变你情绪的消息。

点赞

然而,无论你怎样精心构建一个算法,总是有很多的数据你是不得而知的:教练的比赛计划,德里克罗斯(公牛队球星)的膝盖伤势,甚至是篮球的气压。从微观层面讲,比赛也不是一个单纯比数值的游戏。这是人参与的游戏,「人」的复杂程度远非算法可以预测。

这套预测算法还面临着其他的挑战,这些挑战是来自认识论的。关联度的分预测公牛队将会赢得比赛。显然这个结果是可量化的:输了或赢了,猜中了或猜不中。Facebook 尝试着使用相似的思路解决问题,记录你与这些动态消息的互动频率。而这些互动也正好成为了 Facebook 收入的来源:点赞,点击,分享,评论,使消息病毒式传播,把每一个单独的用户串起来,精准地投放广告。

但是这些交流对于真正的用户来说,是非常粗糙且不准确的。他们点了赞,并不一定代表他们真的喜欢这条消息,故事看到一半就关闭,也不一定是不喜欢。如何优化这样的情况?

Facebook动态消息算法揭秘:它比你还了解你自己

「点赞」

在 2013 年末,Facebook 已经是当时最炙手可热的公司。用户数量超过 10 亿,估值达到 1000 亿美金以上。当时它们已经花了数年的时间不断优化移动端的应用体验,在国际上,受欢迎程度已经超过谷歌搜索和谷歌地图。Facebook 已经不仅仅是一个朋友间社交的工具,事实上,它还是 21 世纪全球化的新闻源:一个针对每一位用户量身定制,瞬时更新的新闻,娱乐资讯,朋友动态聚合网站。

在公司之中,动态消息收入的增长让他们感到震惊。但在用户数量暴涨的同时,Facebook 员工们并不能确定用户的满意度究竟如何。人们在 Facebook 上点赞的数量前所未有的多,但他们讨厌什么?

为了搞清楚这件事,我们必须把镜头拉回到 2006 年。当时的 Facebook 与现在复杂的侧栏及群组相比,还处于原始状态。和竞争对手 Myspace 相似,「动态消息」仅仅是朋友间的状态更新的聚合。

Facebook动态消息算法揭秘:它比你还了解你自己

2006 年的 Facebook 主页

甚至,你朋友的更新你不一定能看得到。为了防止信息过多给用户造成太大压力,Facebook 用了一种简单粗暴的算法过滤掉了一部分它认为用户不感兴趣的信息。而当时并没有东西能够能够衡量用户对于信息究竟是否感兴趣——点赞功能距推出还有三年时间。工程师们靠直觉判断消息的呈现与否。一开始的标准是,这条消息发布了多久,以及你的朋友提及这条消息的次数。之后的一段时间里,工程师们决定停止这种简单粗暴的方式,而把用户在消息上停留的时间总数作为消息重要性的依据。但这样的机制难以分辨哪条消息令用户感到愉悦,那条消息冒犯了用户,那些是无聊的,那些是纯碎的谣言。本质上,工程师们还是在碰运气。

「点赞」功能并非一个新鲜的交流方式。而 Facebook 推出点赞功能最初的用意,是想了解用户对消息的偏好。可能用户没有意识到,这是一个非常精妙的设计。如果用户们明确知道「点赞」是为了方便 Facebook 进行偏好纪录,那么这个过程将显得十分单调乏味。Facebook 的「动态」算法是世界上第一个在用户没有感受的情况下,了解用户习惯及偏好的,并且影响了我们所有人。

没有一点点防备,这套算法就在不知不觉中有了辨认实时热点的能力,然后让它们病毒式传播。以前热点是一个人链式的传播,现在一个人点赞以后,他的好友都能看到这一则消息,传播效率堪比滚雪球。这样的效应不仅仅让 Facebook 的员工们看见了,广告商,出版商,造谣者,甚至普通用户都看到了其中巨大的威力——轻点一赞,即可把消息传播给自己所有的好友,关注者甚至陌生人。很多人开始绞尽脑汁思考如何制造「引爆点」。甚至这催生了一项新职业——专门教人发状态的社交网络顾问,他们精于研究文字,发消息的时间,及照片对于传播度的影响。「求点赞」成为常态,甚至他们已经忘记了他们发状态的初衷。许多人的发的状态变得同质化:庸俗,矫情,自怜,只为获得更多的「赞」。「大拇指」成了社交网络的中心。

人肉反馈

就这样,网站的交互度有了长足的提升,但这应该是动态消息所追求的吗?这个问题一直困扰着 Chris Cox ,他是 Facebook 的元老了,也是动态算法的工程师。「观察用户的点赞,点击,分享,评论等行为,是为了更好的弄清楚用户的心理。」Cox 在邮件中这么对我讲。(他是 Facebook 的首席产品官)「但我们很清楚这不是一个完美的解决方案。例如,当你看到一则悲伤的新闻,你肯定不会点赞,但这并不能代表你没有受到触动。几年过去了,我们需要知道比点赞和点击更细节的用户行为。」

一个算法可以尽可能的算出最优解,但是不是最优解,还得由人来评判。Cox 等人为动态消息机制设立的终极目标就是,把所有人们真正关系的消息按重要程度排序,把无关的全部隐去。他们知道,这意味着牺牲一些短期的广告收入及用户体验。Facebook 目前持有着大把现金,而 CEO 扎克伯格有着长远的目标,这给了他们宝贵的试错机会。但如何把握机会,还是要靠他们自己。

长久以来,媒体机构对于判断受众们对什么内容感兴趣都源于主观判断。这样的判断影响编辑们讲故事的方法,价值观的取向,新闻价值的判断及题材的选取。但这样的主观判断是 Cox 和其他 Facebook 同事们极力避免的。他们与 Facebook 想要的效果是:用户在动态里看到的都是他们感兴趣的内容,而不是 Facebook 强推的内容。「最完美的解决方案是给用户选择权,让他们挑出自己爱看的,但这明显不实际。」Cox 对我说。所以次好的解决方案就是用算法猜测用户喜爱什么,然后花钱雇佣一批人看效果如何。事实上这个外包团队已经达到上千人之多,之前他们统一在 Knoxville 的办公室工作,现在他们在自己家里。

Facebook动态消息算法揭秘:它比你还了解你自己

Adam Mosseri 是现 32 岁的动态消息产品主管,与 Alison 处于同一层级,但前者更关注战略而后者更关注技术细节。他找到问题,Alison 负责解决问题。他负责从哲学层面思考动态消息问题。

动态消息从人性化方面的改善始于 Mosseri 的前任主管,Will Cathcart。Cathcart 的工作从采集更多细节信息开展,不仅仅是用户点击了什么,还有用户在每一个页面上的停留时间,不仅仅是用户点赞的内容及倾向,还有他是在看前点赞,还是看了之后再点赞。对于看前就点赞的消息,Facebook 倾向于认为你并不是那么喜欢。

自 2013 年主政以后,Mosseri 又有了一个大举动,在 2014 年夏季创立了「动态消息质量评测小组」,该小组包含数百名成员,在诺克斯维尔市的办公室,每天负责不断体验自己的 Facebook 动态消息时间线,并把细节及满意程度反馈给 Facebook 的工程师。(他们其实是 Facebook 一个秘密的外包团队。)Mosseri 和工程师们不止于此,他们还会问体验者为什么点赞,为什么不点赞,他们对自己点赞的标准,还有他们的点赞倾向。「事实上,他们几乎每天都要写调查报告」, Greg Marra 是评测小组的主管,他这么对我讲。

「问题是,我们可能错过了什么?」Mosseri 说,「有哪一方面的事实是我们的盲点?」 例如,他补充道,「我们知道有些消息是你感兴趣的,但你并不会参与讨论交流。如果没有关注到这种情况,算法会误以为你对这些消息并不感兴趣,因为你即没有点赞,也没有评论。所以什么东西能把这些消息和普通消息区分开来?」

Mosseri 任命了产品经理 Max Eulenstein 还有用户体验研究员 Lauren Scissors 管理着评测小组的日常运营,对问题的咨询也是他们负责。例如,Eulenstein 让小组成员们看一篇故事,测试他们在喜欢或不喜欢这条消息时,分别在网页上停留的时间。一般认为,你在网页上停留的时间越长,你对它越感兴趣,即使你并没有为它「点赞」。「但没那么简单,不仅仅是『 5 秒表示喜欢,2 秒表示不喜欢』」,Eulenstein 对我解释,「每一位用户的阅读速度也大有差异,这个时间值应该和用户平均阅读时间结合起来看。」关于这个问题的研究成果在六月的算法改进中得以体现,Facebook 会尽量把用户停留时间长的消息排名靠前。

花费了数月的时间,Mosseri 和他的团队终于建起了一个可以信赖的测评小组,这是一个国际化的团队,根据 Facebook 在全球的用户数量分配团队中成员的国籍,并且允许他们在家办公。在 2015年末,Facebook 遣散了之前在诺克斯维尔市的办公室,并扩张了海外测试团队。Mosseri 的直觉是对的:动态消息算法推荐上存在盲点,但这件事工程师们自己发现不了。这需要另一种数据的支持——人肉反馈。

Facebook动态消息算法揭秘:它比你还了解你自己

评测小组对于动态消息算法的成熟起到了至关重要的作用,摆脱了对「大数据」的迷信之后,团队迅速成长。 取而代之的是一个具有完善的反馈及平衡机制的系统,每一次算法的改动都必须经历不同类型,不同国籍的用户的反馈,经过多维度的标准测试正确率。

这一个包含排序工程师,产品经理,数据分析师的小团队最主要的任务就是平衡算法的准确性。Sami Tas 是其中的一位软件工程师,他的工作是把动态消息排序小组写出的目标(即伪代码)翻译成电脑可以理解的语言。这个下午,我盯着他看,他从我旁边经过,被一个看似微不足道的问题困扰了。这真的是一个微不足道的问题啊,然而,Facebook 的员工们却锱铢必较。

5% 的用户

大多数时候,人们看到一则不感兴趣的消息,会直接跳过去。但有些消息使他们感到恼怒,他们会特地点开下拉栏,找到「隐藏」按键。Facebook 算法将「隐藏」视为强烈的不满信号,并尽量减少相似的消息出现。

Facebook动态消息算法揭秘:它比你还了解你自己

「隐藏」功能藏在下拉栏的二级菜单里

显然,每个用户的习惯都是不同的,有趣的是,Facebook 的数据分析师们发现,5% 的用户使用「隐藏」功能占了总数的 85 %。他们更深入的了解,这一小部分人几乎把自己看过的所有消息都隐藏了——即使是他们点过赞的或评论过的消息。对于这些「『隐藏』强迫症患者」,显然,「隐藏」不代表他们不喜欢这条消息,他们想要表达的是「已阅」标记,就像Gmail 里的「归档」。

然而他们的行为将使赖以排序的数据造成偏差。对于这么复杂的情况,算法并不能分辨出这样的行为。它只会傻傻地认为点赞即代表满意,隐藏代表强烈的不满意。所以,对于这样的「『隐藏』强迫症患者」,工程师们决定为他们做专门的优化。Tas 为此专门写了代码辨别出这群人,并减低他们「隐藏」的负面权重。

这看似一个小问题呢。但这套算法对于 Facebook 是如此重要,以至于这样小小的改动都应该经过严密的测试才能真正投入使用。首先是离线测试,在 Facebook 内部小组内小范围测试,然后推出到一小部分用户上,最后才是全面使用。每一步,数据分析师们都要收集对于用户的网站交互度,广告投放收入和加载速度影响。如果有哪一项出现大幅度的波动,则会出现警报并自动通知到工程师们。

即便如此,Facebook 也不能确定对于长期来看是否有负面影响。为了防止意外,还留有一部分「保留小组」,即一小部分的用户会在几个月内保持原样。

动态消息排序算法不仅仅有一套,这是广泛的误解。事实上,这不是一套有几百个小算法组成的算法。由于总共有很多个测试小组,「保留小组」,这个世界上同时运行着很多个版本的排序算法。我猜,有一部分「『隐藏』强迫症患者」已经可以愉快地刷动态消息了,但还有一部分的用户仍受到不准确算法的困扰。

Facebook动态消息算法揭秘:它比你还了解你自己

质量评测小组的出线另动态消息算法团队的数据更立体,这是大数据不能给予的。至此,Tas 和其余的排序团队成员对于机器算法的盲点有了深刻的认识。但是,Facebook 还有一个小组,对于这套算法的成熟也起到了至关重要的作用,那就是包括你我在内的普通用户。

在过去的六个月中,Facebook 一直在普通用户中做着随机的调查,设置左右两列动态消息,让普通用户选择更感兴趣的那一列,这是全民参与的「动态消息评测小组」。但是,不仅如此,Facebook 在最近两年一直给予用户更多定制自己动态消息的权力。

你不仅可以「取关」某人,还可以把你的好朋友列入优先列表中,把某个类型的消息屏蔽掉。当然,这些功能对于粗心的用户来说很难发现,并不会增加轻度用户的上手成本——它藏在右上角的灰色小箭头里。大部分用户甚至永远都不会发现这些功能。当你打开导航及帮助页面时,Facebook 会对这些功能进行详细的说明。

你了解自己吗?

这些转变有部分原因是为了起到防御作用。近年来,Facebook 在社交网络的统治地位屡遭威胁,正如当年 MySpace 的地位遭到 Facebook 的挑战一样。而新兴的创业公司完全避开了数据驱动的模式,以 Instagram 为例,他们直接把你关注的所有人的状态消息以反时间顺序的时间线列出,Facebook 不得不买下 Instagram 以维持老大哥地位。Sanpchat 则以独特的阅后即焚模式侵蚀着 Facebook 的青少年市场。

Facebook 并不是近年来唯一数据驱动优化推荐算法的公司。Neflix 的最佳影片推荐,同样更具海量的用户数据,给用户分成无数小类,分类推荐。为了平衡亚马逊的自动 A/B 测试,首席执行官贝索斯一直设立一个单独的反馈邮箱供用户提出意见。现在将数据的处理完全交给机器学习还为时尚早,但机器学习的时代正在加速到来。Facebook 主管 Mosseri 在开会时并不喜欢使用时髦的“数据驱动”,他说的是「数据辅助」。

Facebook动态消息算法揭秘:它比你还了解你自己

Facebook 动态消息排序小组相信他们的努力终将得到回报。「如果我们继续根据反馈提升动态消息推送,我们呈现的消息就回越来越接近人们心中所想。」负责与动态消息反馈小组对接的用户体验分析师 Scissors 说。

这里有一个潜在的负面影响:给用户控制的权利,可是他们真的知道自己究竟想要什么吗?还是数据驱动的 Facebook 比我们更懂自己?可能做出比用户自己想要的更吸引人的动态消息吗?

Mosseri 告诉我他并不会过度担心这些。他解释道,这些数据目前为止,都暗示应该多做调查,给予用户更多的选择权,这样可以增加用户的参与度及在网站上停留的时间,这两项看似都是短期最主要的目标。

动态消息推送算法的改进是一个非常长期的过程。如果它恰好每次都击中你的痛点,那也仅仅是一个令人愉快的巧合。在长达十年的动态消息运营过程中,数据从来就没有尽善尽美过。而算法的改进就是一个否定之否定的过程,今天辛苦写成的代码也许明天就会被无情删除。日复一日,工程师们在 Facebook 门洛帕克市的总部里的研究体验报告,开会,进行一系列测试,然后一次又一次修正算法。

 

原文地址:slate

译者:刘家欣

本文来源于人人都是产品经理合作媒体@雷锋网

C++ STL算法之accumulate函数

1. 介绍

  用来计算特定范围内(包括连续的部分和初始值)所有元素的和,除此之外,还可以用指定的二进制操作来计算特定范围内的元素结果。其头文件在numeric中。
  accumulate原函数声明定义如下:   

template<class InputIterator, class Type>
   Type accumulate(
      InputIterator _First, 
      InputIterator _Last, 
      Type _Val
   );
template<class InputIterator, class Type, class Fn2>
   Type accumulate(
      InputIterator _First, 
      InputIterator _Last, 
      Type _Val, 
      BinaryOperation _Binary_op
   );

参数说明。

参数 描述
_First 指定范围内第一个迭代的值或者结合操作选项使用。
InputIterator _Last 指定范围内最后一个迭代值或者结合操作项使用。
_Val 要计算的初始值。
_Binary_op 运用于指定范围内所有元素和前面计算得到结果的参数。

但看说明也许不太容易懂,我们通过例子更具体的解释下这个函数。

2. 应用举例

#include 
#include 
#include 
#include 

using namespace std;

int main( ) 
{

   vector <int> v1, v2( 20 );
   vector <int>::iterator Iter1, Iter2;

   int i;
   for ( i = 1 ; i < 21 ; i++ )
   {
      v1.push_back( i );
   }

   cout << "最初向量v1中个元素的值为:n ( " ;
   for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
      cout << *Iter1 << " ";
   cout << ")." << endl;

   // accumulate函数的第一个功能,求和
   int total;
   total = accumulate ( v1.begin ( ) , v1.end ( ) , 0 );

   cout << "整数从1到20的和为: " 
        << total << "." << endl;

   // 构造一个前n项和的向量
   int j = 0, partotal;
   for ( Iter1 = v1.begin( ) + 1; Iter1 != v1.end( ) + 1 ; Iter1++ )
   {
      partotal = accumulate ( v1.begin ( ) , Iter1 , 0 );
      v2 [ j ] = partotal;
      j++;
   }

   cout << "前n项和分别为:n ( " ;
   for ( Iter2 = v2.begin( ) ; Iter2 != v2.end( ) ; Iter2++ )
      cout << *Iter2 << " ";
   cout << ")." << endl << endl;

   // accumulate函数的第二个功能,计算连乘积
   vector <int> v3, v4( 10 );
   vector <int>::iterator Iter3, Iter4;

   int s;
   for ( s = 1 ; s < 11 ; s++ )
   {
      v3.push_back( s );
   }

   cout << "向量v3的初始值分别为:n ( " ;
   for ( Iter3 = v3.begin( ) ; Iter3 != v3.end( ) ; Iter3++ )
      cout << *Iter3 << " ";
   cout << ")." << endl;

   int ptotal;
   ptotal = accumulate ( v3.begin ( ) , v3.end ( ) , 1 , multiplies<int>( ) );

   cout << "整数1到10的连乘积为: " 
        << ptotal << "." << endl;

   // 构造一个前n项积的向量
   int k = 0, ppartotal;
   for ( Iter3 = v3.begin( ) + 1; Iter3 != v3.end( ) + 1 ; Iter3++ ) {
      ppartotal = accumulate ( v3.begin ( ) , Iter3 , 1 , multiplies<int>( ) );
      v4 [ k ] = ppartotal;
      k++;
   }

   cout << "前n项积分别为:n ( " ;
   for ( Iter4 = v4.begin( ) ; Iter4 != v4.end( ) ; Iter4++ )
      cout << *Iter4 << " ";
   cout << ")." << endl;
}

编译运行,看一下输出结果:

C++ STL算法之accumulate函数

用 Python 实现 各种排序算法

归并排序

归并排序也称合并排序,是分治法的典型应用。分治思想是将每个问题分解成个个小问题,将每个小问题解决,然后合并。

具体的归并排序就是,将一组无序数按n/2递归分解成只有一个元素的子项,一个元素就是已经排好序的了。然后将这些有序的子元素进行合并。

合并的过程就是 对 两个已经排好序的子序列,先选取两个子序列中最小的元素进行比较,选取两个元素中最小的那个子序列并将其从子序列中去掉添加到最终的结果集中,直到两个子序列归并完成。

代码如下:

#!/usr/bin/python
import sys

def merge(nums, first, middle, last):
    ”’ merge ”’
    # 切片边界,左闭右开并且是了0为开始
    lnums = nums[first:middle+1]
    rnums = nums[middle+1:last+1]
    lnums.append(sys.maxint)
    rnums.append(sys.maxint)
    l = 0
    r = 0
    for i in range(first, last+1):
        if lnums[l] < rnums[r]:
            nums[i] = lnums[l]
            l+=1
        else:
            nums[i] = rnums[r]
            r+=1
def merge_sort(nums, first, last):
    ”’ merge sort
    merge_sort函数中传递的是下标,不是元素个数
    ”’
    if first < last:
        middle = (first + last)/2
        merge_sort(nums, first, middle)
        merge_sort(nums, middle+1, last)
        merge(nums, first, middle,last)

if __name__ == ‘__main__’:
    nums = [10,8,4,-1,2,6,7,3]
    print ‘nums is:’, nums
    merge_sort(nums, 0, 7)
    print ‘merge sort:’, nums

稳定,时间复杂度 O(nlog n)

插入排序
代码如下:

#!/usr/bin/python
import sys

def insert_sort(a):
    ”’ 插入排序
    有一个已经有序的数据序列,要求在这个已经排好的数据序列中插入一个数,
    但要求插入后此数据序列仍然有序。刚开始 一个元素显然有序,然后插入一
    个元素到适当位置,然后再插入第三个元素,依次类推
    ”’
    a_len = len(a)
    if a_len < 2:
        return a_list
    for i in range(1,a_len):
        key = a[i]
        j = i-1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]
            j-=1
        a[j+1] = key
    return a

if __name__ == ‘__main__’:
    nums = [10,8,4,-1,2,6,7,3]
    print ‘nums is:’, nums
    insert_sort(nums)
    print ‘insert sort:’, nums

稳定,时间复杂度 O(n^2)

交换两个元素的值python中你可以这么写:a, b = b, a,其实这是因为赋值符号的左右两边都是元组(这里需要强调的是,在python中,元组其实是由逗号“,”来界定的,而不是括号)。

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

import sys
def select_sort(a):
    ”’ 选择排序
    每一趟从待排序的数据元素中选出最小(或最大)的一个元素,
    顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
    选择排序是不稳定的排序方法。
    ”’
    a_len=len(a)
    for i in range(a_len):#在0-n-1上依次选择相应大小的元素
        min_index = i#记录最小元素的下标
        for j in range(i+1, a_len):#查找最小值
            if(a[j]                min_index=j
        if min_index != i:#找到最小元素进行交换
            a[i],a[min_index] = a[min_index],a[i]

if __name__ == ‘__main__’:
    A = [10, -3, 5, 7, 1, 3, 7] 
    print ‘Before sort:’,A 
    select_sort(A) 
    print ‘After sort:’,A

不稳定,时间复杂度 O(n^2)

希尔排序
希尔排序,也称递减增量排序算法,希尔排序是非稳定排序算法。该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行排序;
然后,取第二个增量d2def shell_sort(a):
    ”’ shell排序
    ”’
    a_len=len(a)
    gap=a_len/2#增量
    while gap>0:
        for i in range(a_len):#对同一个组进行选择排序
            m=i
            j=i+1
            while j                if a[j]                    m=j
                j+=gap#j增加gap
            if m!=i:
                a[m],a[i]=a[i],a[m]
        gap/=2

if __name__ == ‘__main__’:
    A = [10, -3, 5, 7, 1, 3, 7] 
    print ‘Before sort:’,A 
    shell_sort(A) 
    print ‘After sort:’,A

不稳定,时间复杂度 平均时间 O(nlogn) 最差时间O(n^s)1节点 i 的右子节点在位置 2 * i + 24) 节点 i 的父节点在位置 floor( (i – 1) / 2 )  : 注 floor 表示“取整”操作
堆的特性:
每个节点的键值一定总是大于(或小于)它的父节点

“最大堆”:
“堆”的根节点保存的是键值最大的节点。即“堆”中每个节点的键值都总是大于它的子节点。
上移,下移 :
当某节点的键值大于它的父节点时,这时我们就要进行“上移”操作,即我们把该节点移动到它的父节点的位置,
而让它的父节点到它的位置上,然后我们继续判断该节点,直到该节点不再大于它的父节点为止才停止“上移”。
现在我们再来了解一下“下移”操作。当我们把某节点的键值改小了之后,我们就要对其进行“下移”操作。

方法:
我们首先建立一个最大堆(时间复杂度O(n)),然后每次我们只需要把根节点与最后一个位置的节点交换,然后把最后一个位置排除之外,然后把交换后根节点的堆进行调整(时间复杂度 O(lgn) ),即对根节点进行“下移”操作即可。 堆排序的总的时间复杂度为O(nlgn).
代码如下:

#!/usr/bin env python

# 数组编号从 0开始
def left(i):
    return 2*i +1
def right(i):
    return 2*i+2

#保持最大堆性质 使以i为根的子树成为最大堆
def max_heapify(A, i, heap_size):
    if heap_size <= 0:
        return
    l = left(i)
    r = right(i)
    largest = i # 选出子节点中较大的节点
    if l < heap_size and A[l] > A[largest]:
        largest = l
    if r < heap_size and A[r] > A[largest]:
        largest = r
    if i != largest :#说明当前节点不是最大的,下移
        A[i], A[largest] = A[largest], A[i] #交换
        max_heapify(A, largest, heap_size)#继续追踪下移的点
    #print A
# 建堆 
def bulid_max_heap(A):
    heap_size = len(A)
    if heap_size >1:
        node = heap_size/2 -1
        while node >= 0:
          max_heapify(A, node, heap_size)
          node -=1

# 堆排序 下标从0开始
def heap_sort(A):
    bulid_max_heap(A)
    heap_size = len(A)
    i = heap_size – 1
    while i > 0 :
        A[0],A[i] = A[i], A[0] # 堆中的最大值存入数组适当的位置,并且进行交换
        heap_size -=1 # heap 大小 递减 1
        i -= 1 # 存放堆中最大值的下标递减 1
        max_heapify(A, 0, heap_size)

if __name__ == ‘__main__’ :

    A = [10, -3, 5, 7, 1, 3, 7]
    print ‘Before sort:’,A
    heap_sort(A)
    print ‘After sort:’,A

不稳定,时间复杂度 O(nlog n)

快速排序
快速排序算法和合并排序算法一样,也是基于分治模式。对子数组A[p…r]快速排序的分治过程的三个步骤为:

分解:把数组A[p…r]分为A[p…q-1]与A[q+1…r]两部分,其中A[p…q-1]中的每个元素都小于等于A[q]而A[q+1…r]中的每个元素都大于等于A[q];
解决:通过递归调用快速排序,对子数组A[p…q-1]和A[q+1…r]进行排序;
合并:因为两个子数组是就地排序的,所以不需要额外的操作。

对于划分partition 每一轮迭代的开始,x=A[r], 对于任何数组下标k,有:

1) 如果p≤k≤i,则A[k]≤x。
2) 如果i+1≤k≤j-1,则A[k]>x。
3) 如果k=r,则A[k]=x。

代码���下:

#!/usr/bin/env python
# 快速排序
”’
划分 使满足 以A[r]为基准对数组进行一个划分,比A[r]小的放在左边,
  比A[r]大的放在右边
快速排序的分治partition过程有两种方法,
一种是上面所述的两个指针索引一前一后逐步向后扫描的方法,
另一种方法是两个指针从首位向中间扫描的方法。
”’
#p,r 是数组A的下标
def partition1(A, p ,r):
    ”’
      方法一,两个指针索引一前一后逐步向后扫描的方法
    ”’
    x = A[r]
    i = p-1
    j = p
    while j < r:
        if A[j] < x:
            i +=1
            A[i], A[j] = A[j], A[i]
        j += 1
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def partition2(A, p, r):
    ”’
    两个指针从首尾向中间扫描的方法
    ”’
    i = p
    j = r
    x = A[p]
    while i < j :
        while A[j] >= x and i < j:
            j -=1
        A[i] = A[j]
        while A[i]<=x and i < j:
            i +=1
        A[j] = A[i]
    A[i] = x
    return i

# quick sort
def quick_sort(A, p, r):
    ”’
        快速排序的最差时间复杂度为O(n2),平时时间复杂度为O(nlgn)
    ”’
    if p < r:
        q = partition2(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)

if __name__ == ‘__main__’:

    A = [5,-4,6,3,7,11,1,2]
    print ‘Before sort:’,A
    quick_sort(A, 0, 7)
    print ‘After sort:’,A

不稳定,时间复杂度 最理想 O(nlogn)最差时间O(n^2)

说下python中的序列:
列表、元组和字符串都是序列,但是序列是什么,它们为什么如此特别呢?序列的两个主要特点是索引操作符和切片操作符。索引操作符让我们可以从序列中抓取一个特定项目。切片操作符让我们能够获取序列的一个切片,即一部分序列,如:a = [‘aa’,’bb’,’cc’], print a[0] 为索引操作,print a[0:2]为切片操作。

总结如下:

无需操作系统直接运行 Python 代码  http://www.linuxidc.com/Linux/2015-05/117357.htm

CentOS上源码安装Python3.4  http://www.linuxidc.com/Linux/2015-01/111870.htm

《Python核心编程 第二版》.(Wesley J. Chun ).[高清PDF中文版] http://www.linuxidc.com/Linux/2013-06/85425.htm

《Python开发技术详解》.( 周伟,宗杰).[高清PDF扫描版+随书视频+代码] http://www.linuxidc.com/Linux/2013-11/92693.htm

Python脚本获取Linux系统信息 http://www.linuxidc.com/Linux/2013-08/88531.htm

Ubuntu下用Python搭建桌面算法交易研究环境 http://www.linuxidc.com/Linux/2013-11/92534.htm

Python 语言的发展简史 http://www.linuxidc.com/Linux/2014-09/107206.htm

Python 的详细介绍请点这里
Python 的下载地址请点这里

排序算法:查找最小的k个元素

查找最小的 k 个元素
题目:输入 n 个整数,输出其中最小的 k 个。
例如输入 1,2,3,4,5,6,7 和 8 这 8 个数字,则最小的 4 个数字为 1,2,3 和 4。
代码思路:方法有很多种,只是时间复杂度问题。
代码一:快速排序c语言实现
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#define N 6
int partition(int a[], int low, int high)
{
int key = a[low];
a[0] = a[low];
while (low < high)
{
while (low < high&&a[high] >= key)
{
high–;
}
a[low] = a[high];
while (low < high&&a[low] <= key)
{
low++;
}
a[high] = a[low];
}
a[low] = a[0];
return low;
}
void qsort(int a[], int low, int high)
{
int p;
if (low < high)
{
p = partition(a, low, high);
qsort(a, low, p – 1);
qsort(a, p + 1,high);
}
}
void output(int a[], int num)
{
for (int i = 1; i <= num; i++)
{
printf(“%d “, a[i]);
}
}
void main()
{
int a[N];
int num;
printf(“请输入数字个数n”);
scanf(“%d”, &num);
for (int i = 0; i < num; i++)
{
scanf(“%d”, &a[i]);
}
qsort(a, 1, 5);
printf(“n”);
printf(“请输入最小的n个元素n”);
int n;
scanf(“%d”, &n);
output(a, n);
system(“pause”);
}

代码2:最小堆排序算法
#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#define N 6
void heapjust(int a[], int i, int length)
{
int child = 0, tmp;
for (tmp = a[i]; 2 * i + 1
{
child = 2 * i + 1;
if (child < length - 1 && a[child+1] < a[child])
{
child++;
}
if (tmp>a[child])
{
a[i] = a[child];
}
else
{
break;
}
a[child] = tmp;
}
}
int getmin(int a[], int i, int length)
{
int min = a[0];
a[0] = a[length-1];
a[length-1] = min;
int tmp, child = 0;
int k = 0, j = i – 1;
for (tmp = a[0];2 * k + 1 < length-1; k = child)
{
child = 2 * k + 1;
if (child < length - 2 && a[child + 1] < a[child])
{
child++;
}
if (tmp>a[child])
{
a[k] = a[child];
}
else
{
break;
}
a[child] = tmp;
}
return min;
}
void kmin(int a[], int length, int k)
{
for (int i = length – 1; i >= 0; i–)
{
heapjust(a, i, length);
}
int j = length;
for (int i = k; i > 0; i–, j–)
{
int min = getmin(a, i, j);
printf(“%d  n”, min);
}
}
void main()
{
int a[N];
int num;
printf(“请输入数字个数n”);
scanf(“%d”, &num);
for (int i = 0; i < num; i++)
{
scanf(“%d”, &a[i]);
}
kmin(a, num, 3);
system(“pause”);
}

Java常用数据加密算法

Java的数据加密算法,HmacSHA1,MD5等。java自带了加密的方法类SecretKey。

Java 8 中 HashMap 的性能提升 http://www.linuxidc.com/Linux/2014-04/100868.htm

Java 8 的 Nashorn 引擎 http://www.linuxidc.com/Linux/2014-03/98880.htm

Java 8简明教程 http://www.linuxidc.com/Linux/2014-03/98754.htm

private static final String MAC_NAME=”HmacSHA1″; 
    private static final String ENCODING=”UTF-8″;
/**
    *使用HMAC-SHA1签名方法对对encryptText进行签名
    *@paramencryptText被签名的字符串
    *@paramencryptKey密钥
    *@return返回被加密后的字符串
    *@throwsException
    */
    public static String HmacSHA1Encrypt(String encryptText, String encryptKey)throws Exception{
        byte[] data = encryptKey.getBytes( ENCODING );
        // 根据给定的字节数组构造一个密钥,第二参数指定一个密钥算法的名称
        SecretKey secretKey = new SecretKeySpec( data, MAC_NAME );
        // 生成一个指定 Mac 算法 的 Mac 对象
        Mac mac = Mac.getInstance( MAC_NAME );
        // 用给定密钥初始化 Mac 对象
        mac.init( secretKey );
        byte[] text = encryptText.getBytes( ENCODING );
        // 完成 Mac 操作
        byte[] digest = mac.doFinal( text );
        StringBuilder sBuilder = bytesToHexString( digest );
        return sBuilder.toString();
    }
/**
    * 使用 HMAC-SHA1 签名方法对对e
    * @param encryptData 被签名的字
    * @param encryptKey 密钥
    * @return 返回被加密后的字符串
    */
    public static String hmacSHA1Encrypt( byte[] encryptData, String encryptKey ) throws Exception{
        byte[] data = encryptKey.getBytes( ENCODING );
        // 根据给定的字节数组构造一个密钥,第二参数指定一个密钥算法的名称
        SecretKey secretKey = new SecretKeySpec( data, MAC_NAME );
        // 生成一个指定 Mac 算法 的 Mac 对象
        Mac mac = Mac.getInstance( MAC_NAME );
        // 用给定密钥初始化 Mac 对象
        mac.init( secretKey );
        // 完成 Mac 操作
        byte[] digest = mac.doFinal( encryptData );
        StringBuilder sBuilder = bytesToHexString( digest );
        return sBuilder.toString();
    }
    /**
    * 转换成Hex
    * @param bytesArray
    */
    public static StringBuilder bytesToHexString( byte[] bytesArray ){
        if ( bytesArray == null ){
            return null;
        }
        StringBuilder sBuilder = new StringBuilder();
        for ( byte b : bytesArray ){
            String hv = String.format(“%02x”, b);
            sBuilder.append( hv );
        }
        return sBuilder;
    }
public static String md5(String str) {
        StringBuilder sb = new StringBuilder();
        try {
            MessageDigest m = MessageDigest.getInstance(“MD5”);
            m.update(str.getBytes(“UTF8”));
            byte bytes[] = m.digest();

            for (int i = 0; i < bytes.length; i++) {
                if ((bytes[i] & 0xff) < 0x10) {
                    sb.append(“0”);
                }
                sb.append(Long.toString(bytes[i] & 0xff, 16));
            }
        } catch (Exception e) {
        }
        return sb.toString();
    }
   
    public static String createSign(Map params,String appkey) throws Exception {
        String queryString = getString(params);
        return HmacSHA1Encrypt(queryString,appkey);
    }
    //
    private static String getString(Map params) {
        List sList = new ArrayList();
        for(Entry entry:params.entrySet()){
            sList.add(entry.getKey()+”=”+entry.getValue());
        }
        String queryString = Joiner.on(“&”).join(sList);
        return queryString;
    }
/**
    * HmacMD5算法
    * @param msg 加密信息
    * @param keyString 秘钥
    * @return digest 结果
    */
    public static String hmacMD5(String msg, String keyString) {
        String digest = null;
        try {
            SecretKeySpec key = new SecretKeySpec((keyString).getBytes(“UTF-8”), “HmacMD5”);
            Mac mac = Mac.getInstance(“HmacMD5”);
            mac.init(key);

            byte[] bytes = mac.doFinal(msg.getBytes(“UTF-8”));

            StringBuffer hash = new StringBuffer();
            for (int i = 0; i < bytes.length; i++) {
                String hex = Integer.toHexString(0xFF & bytes[i]);
                if (hex.length() == 1) {
                    hash.append(‘0’);
                }
                hash.append(hex);
            }
            digest = hash.toString();
        } catch (UnsupportedEncodingException | NoSuchAlgorithmException | InvalidKeyException e) {
        }
        return digest;

最大子序列和问题之算法优化

算法一:穷举式地尝试所有的可能

int maxSubsequenceSum(const int a[], int n)
{
    int i, j, k;
    int thisSum, maxSum = 0;
    for (i = 0; i < n; i++)
        for (j = i; j < n; j++)
        {
            thisSum = 0;
            for (k = i; k < j; k++)
                thisSum += a[k];
            if (thisSum > maxSum)
                maxSum = thisSum;
        }
    return maxSum;
}

算法复杂度为O(n^3)(三重for循环)


算法二:算法一的改进

int maxSubsequenceSum(const int a[], int n)
{
    int i, j;
    int thisSum, maxSum = 0;
    for (i = 0; i < n; i++)
    {
        thisSum = 0;
        for (j = i; j < n; j++)
        {
            thisSum += a[j];
            if (thisSum > maxSum)
                maxSum = thisSum;
        }
    }
    return maxSum;
} 

该算法去除了算法一中不必要的计算,时间复杂度为O(n^2)(两重for循环)。


算法三:分治(divide-and-conquer)策略

分治策略:

:把问题分成若干个(通常是两个)规模相当的子问题,然后递归地对它们求解。

:将若干个问题的解4合并到一起并可能再做少量的附加工作,最后得到整个问题的解。

在这个问题中,最大子序列和可能在三处出现:即左半部序列、右半部序列、穿过中部从而占据左右两半部分的序列。前两种情况可以通过递归求解。而递归的基准情况(base cases)是序列只有一个元素(left == right),若该元素大于0,则返回该元素,否则返回0。第三种情况的最大和可以通过分别求出左边部分(包含左半部分最后一个)的最大和以及右边部分(包含右边部分的第一个)的最大和,再将它们相加得到。

int maxSubsequenceSum(const int a[], int left, int right)
{
    int i, mid, maxLeftSum, maxRightSum;
    int maxLeftBorderSum, leftBorderSum;
    int maxRightBorderSum, rightBorderSum;

    if (left == right) {            /*基准情况*/
        if (a[left] >= 0)
            return a[left];
        else
            return 0;
    }
    mid = left + (right - left) / 2;
    maxLeftSum = maxSubsequenceSum(a, left, mid);       /*左半部分的最大和*/
    maxRightSum = maxSubsequenceSum(a, mid+1, right);   /*右半部分的最大和*/
    /*下面求穿过中点的最大和*/
    maxLeftBorderSum = 0, leftBorderSum = 0;
    for (i = mid; i >= left; i--)       /*中点及其以左的最大和*/
    {
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }
    maxRightBorderSum = 0, rightBorderSum = 0;
    for (i = mid+1; i <= right; i++)   /*中点以右的最大和*/
    {
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }
    /*返回三部分中的最大值*/
    return max3(maxLeftSum, maxRightSum, maxLeftBorderSum+maxRightBorderSum);
}

int max3(int a, int b, int c)
{
    int maxNum  = a;

    if (b > maxNum)
        maxNum = b;
    if (c > maxNum)
        maxNum = c;
    return maxNum;
}

以序列2,4,-1,-5,4,-1为例,其左半部分最大和为2 + 4 = 6;右半部分最大和为4,穿过中心的最大和为(-1 + 4 + 2)+ (-5 + 4)= 0。故该序列的最大子序列和为max(6,4,0)= 6。

时间复杂度分析: 假设T(n)为求解大小为n的最大子序列和问题所花费的时间。当n = 1是,T(1) = O(1);当n > 1时,两次递归花费的总时间为2T(n/2),两个并列的for循环花费的时间是O(len(left)+len(right)) = O(n),一共为2T(n/2)+O(n)。综上可列如下方程组:

T(1) = 1
T(n) = 2T(n/2) + O(n)

事实上,上述方程组常常通用于分治算法,由方程组可算出T(n) = O(nlogn)。

 


算法四:

算法三利用递归较好的解决了最大子序列和问题,但仔细分析,在递归过程中,同一个元素很可能多次被操作,有没有更高效的算法?先上代码!

int maxSubsequenceSum(const int a[], int n)
{
    int i;
    int maxSum, thisSum;
    maxSum = thisSum = 0;
    for (i = 0; i < n; i++)
    {
        thisSum += a[i];
        if (thisSum > maxSum)
            maxSum = thisSum;
        else if (thisSum < 0)
            thisSum = 0;
    }
    return maxSum;
}

可以简单的分析出上述代码的时间复杂度是O(n),比前三种都高效。它为什么是正确的?从直观上理解:首先for循环的if语句保证了每次更新后最大和保存在maxSum中,而我们从i = 0开始扫描,假设扫描到i = t(t < n),且此时的最大和已经保存在maxSum中,而当前的和(thisSum)如果大于0,不管当i > t的元素大小如何,加上thisSum总会使之后的和变大,而如果thisSum小于0,肯定会使之后的和变小
,既然还会变小,那干脆就重新来过(thisSum = 0),有些另起炉灶的意味。

该算法一个附带的优点是,它只对数据进行一次的扫描,一旦a[i]被读入并被处理,它就不再需要记忆。因此,如果数组在磁盘或磁带上,它就可以被顺序读入,在主存中不必储存数组的任何部分。不仅如此,在任意时刻,该算法都能对它已经读入的数据给出子序列问题的正确答案(其他算法即前三种不具有这个特性)。具有这种特性的算法叫做联机算法(online algorithm。仅需要常量空间并以线性时间运行的online algorithm几乎是完美的算法。

————《数据结构与算法分析》(中文版第二版)

数据结构与算法分析:C语言描述(原书第2版) PDF+源代码+习题答案 下载见 http://www.linuxidc.com/Linux/2014-04/99735.htm

Java AES算法和OpenSSL配对

<

div id=”content” contentScore=”10002″>近日工作上的原因,需要实现Java  AES算法和C语言下基于OpenSSL的AES 算法通信。这是个老问题了,网上搜到不少资料,但都不是很详细,没能解决问题。只能自己来了。

先说说AES算法。AES算法的实现有四种,如CBC/ECB/CFB/OFB,这四种Java和C都有实现。AES算法还有末尾的填充(padding),java支持的padding方式有三种NoPadding/PKCS5Padding/,而C却不能显式的设置padding方式,默认的padding就是在末尾加 ‘\0’。这是一个大坑,多少人都坑在这了。另外,网上很多JAVA AES算法,很多都用SecureRandom,如果你的代码中出现了SecureRandom这个东西,那么你再也不能用C解出来了。

先说Java端的。从良心上说,java的封装比C要强多了。先上代码:

    public static String encrypt(String content, String passwd) {
        try {
            Cipher aesECB = Cipher.getInstance(“AES/ECB/PKCS5Padding”);
            SecretKeySpec key = new SecretKeySpec(passwd.getBytes(), “AES”);
            aesECB.init(Cipher.ENCRYPT_MODE, key);
            byte[] result = aesECB.doFinal(content.getBytes());
            return new BASE64Encoder().encode(result);
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        } catch (NoSuchPaddingException e) {
            e.printStackTrace();
        } catch (InvalidKeyException e) {
            e.printStackTrace();
        } catch (IllegalBlockSizeException e) {
            e.printStackTrace();
        } catch (BadPaddingException e) {
            e.printStackTrace();
        }
        return null;
    }
 
    public String decrypt(String content, String passwd) {
        try {
            Cipher cipher = Cipher.getInstance(“AES/ECB/PKCS5Padding”);// 创建密码器
            SecretKeySpec key = new SecretKeySpec(passwd.getBytes(), “AES”);
            cipher.init(Cipher.DECRYPT_MODE, key);// 初始化
            byte[] result = new BASE64Decoder().decodeBuffer(content);
            return new String(cipher.doFinal(result)); // 解密
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        } catch (NoSuchPaddingException e) {
            e.printStackTrace();
        } catch (InvalidKeyException e) {
            e.printStackTrace();
        } catch (IllegalBlockSizeException e) {
            e.printStackTrace();
        } catch (BadPaddingException e) {
            e.printStackTrace();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        return null;
    }

以上就是两个加密解密函数,默认使用AES算法的ECB,填充方式选择了PKCS5Padding。中间用到了Base64算法将加密后的字串进行再加密,主要是为了可视化读和传递。使用Base64算法要引用sun.misc.BASE64Decoder和sun.misc.BASE64Encoder;

Java就是这么简单,当然它一开始并没有这么简单,我也是从SecureRandom里面跳出来的。

关于openssl库,先看EVP。EVP是OpenSSL自定义的一组高层算法封装函数,它是对具体算法的封装。使得可以在同一类加密算法框架下,通过相同的接口去调用不同的加密算法或者便利地改变具体的加密算法,这样大提高 了代码的可重用性。当你使用EVP的时候你就会发现,它的使用方法和Java是那么的相似,以至于会产生他们的结果肯定会相同的遐想。在使用它之前,我们先来学习学些它的用法。我们这里取出了几个重要的函数列在下面:

【EVP_CIPHER_CTX_init】

该函数初始化一个EVP_CIPHER_CTX结构体,只有初始化后该结构体才能在下面介绍的函数中使用。操作成功返回1,否则返回0。

【EVP_EncryptInit_ex】

该函数采用ENGINE参数impl的算法来设置并初始化加密结构体。其中,参数ctx必须在调用本函数之前已经进行了初始化。参数type通常通过函数类型来提供参数,如EVP_des_cbc函数的形式,即我们上一章中介绍的对称加密算法的类型。如果参数impl为NULL,那么就会使用缺省的实现算法。参数key是用来加密的对称密钥,iv参数是初始化向量(如果需要的话)。在算法中真正使用的密钥长度和初始化密钥长度是根据算法来决定的。在调用该函数进行初始化的时候,除了参数type之外,所有其它参数可以设置为NULL,留到以后调用其它函数的时候再提供,这时候参数type就设置为NULL就可以了。在缺省的加密参数不合适的时候,可以这样处理。操作成功返回1,否则返回0。

【EVP_EncryptUpdate】

该函数执行对数据的加密。该函数加密从参数in输入的长度为inl的数据,并将加密好的数据写入到参数out里面去。可以通过反复调用该函数来处理一个连续的数据块。写入到out的数据数量是由已经加密的数据的对齐关系决定的,理论上来说,从0到(inl+cipher_block_size-1)的任何一个数字都有可能(单位是字节),所以输出的参数out要有足够的空间存储数据。写入到out中的实际数据长度保存在outl参数中。操作成功返回1,否则返回0。

【EVP_EncryptFinal_ex】

该函数处理最后(Final)的一段数据。在函数在padding功能打开的时候(缺省)才有效,这时候,它将剩余的最后的所有数据进行加密处理。该算法使用标志的块padding方式(AKA PKCS padding)。加密后的数据写入到参数out里面,参数out的长度至少应该能够一个加密块。写入的数据长度信息输入到outl参数里面。该函数调用后,表示所有数据都加密完了,不应该再调用EVP_EncryptUpdate函数。如果没有设置padding功能,那么本函数不会加密任何数据,如果还有剩余的数据,那么就会返回错误信息,也就是说,这时候数据总长度不是块长度的整数倍。操作成功返回1,否则返回0。

PKCS padding标准是这样定义的,在被加密的数据后面加上n个值为n的字节,使得加密后的数据长度为加密块长度的整数倍。无论在什么情况下,都是要加上padding的,也就是说,如果被加密的数据已经是块长度的整数倍,那么这时候n就应该等于块长度。比如,如果块长度是9,要加密的数据长度是11,那么5个值为5的字节就应该增加在数据的后面。

【EVP_DecryptInit_ex, EVP_DecryptUpdate和EVP_DecryptFinal_ex】

这三个函数是上面三个函数相应的解密函数。这些函数的参数要求基本上都跟上面相应的加密函数相同。如果padding功能打开了,EVP_DecryptFinal会检测最后一段数据的格式,如果格式不正确,该函数会返回错误代码。此外,如果打开了padding功能,EVP_DecryptUpdate函数的参数out的长度应该至少为(inl+cipher_block_size)字节;但是,如果加密块的长度为1,则其长度为inl字节就足够了。三个函数都是操作成功返回1,否则返回0。

需要注意的是,虽然在padding功能开启的情况下,解密操作提供了错误检测功能,但是该功能并不能检测输入的数据或密钥是否正确,所以即便一个随机的数据块也可能无错的完成该函数的调用。如果padding功能关闭了,那么当解密数据长度是块长度的整数倍时,操作总是返回成功的结果。

前面我们说过,openssl的填充padding方式不能自定义,之后采用默认的在尾端加字符’\0’,但是EVP会默认打开Padding,且使用的Padding方式为PKCS padding,所以只要java使用对应的填充方式,理论上加解密的结果是一样的。知道了这些函数,如何使用呢?上个代码(整理后的):

void encrypt(unsigned char* in, int inl, unsigned char out, int len, unsigned char * key){
    unsigned char iv[8];
    EVP_CIPHER_CTX ctx;
    //此init做的仅是将ctx内存 memset为0 
    EVP_CIPHER_CTX_init(&ctx);
 
    //cipher  = EVP_aes_128_ecb(); 
    //原型为int EVP_EncryptInit_ex(EVP_CIPHER_CTX ctx,const EVP_CIPHER *cipher, ENGINE *impl, const unsigned char *key, const unsigned char *iv) 
    //另外对于ecb电子密码本模式来说,各分组独立加解密,前后没有关系,也用不着iv 
    EVP_EncryptInit_ex(&ctx, EVP_aes_128_ecb(), NULL, key, iv); 
 
    *len = 0;
    int outl = 0;
    //这个EVP_EncryptUpdate的实现实际就是将in按照inl的长度去加密,实现会取得该cipher的块大小(对aes_128来说是16字节)并将block-size的整数倍去加密。
    //如果输入为50字节,则此处仅加密48字节,outl也为48字节。输入in中的最后两字节拷贝到ctx->buf缓存起来。 
    //对于inl为block_size整数倍的情形,且ctx->buf并没有以前遗留的数据时则直接加解密操作,省去很多后续工作。 
    EVP_EncryptUpdate(&ctx, out+
len, &outl, in+len, inl);
    *len+=outl;
    //余下最后n字节。此处进行处理。
    //如果不支持pading,且还有数据的话就出错,否则,将block_size-待处理字节数个数个字节设置为此个数的值,如block_size=16,数据长度为4,则将后面的12字节设置为16-4=12,补齐为一个分组后加密
    //对于前面为整分组时,如输入数据为16字节,最后再调用此Final时,不过是对16个0进行加密,此密文不用即可,也根本用不着调一下这Final。
    int test = inl>>4;
    if(inl != test<<4){
        EVP_EncryptFinal_ex(&ctx,out+
len,&outl); 
        *len+=outl;
    }
    EVP_CIPHER_CTX_cleanup(&ctx);
}

更夼/div>