分类 技术 下的文章

堆排序\链表实现局部排序

以前面试时被问一个问题:有10万个乱序的数,要前5个最大(或最小)的数?
作为一个没好好学算法的人,还没有算法时间、空间复杂度的概念,只提出了冒泡、快速排序等,然后取前5。这显然不是合理的做法。

读了几本书,有一点点心得,下面介绍两个做法:
假设:输入为[31,5,12,24,41,63,7,61,42,21,9,123,24...] ,总数为N=100000,要求前M=5个最大的数

  1. 对10万个建立二叉堆,然后应用堆排序5次,即取出前5个最大(或最小)的数。
    只是一个可行的方法,在此不敖述,具体可参见《数据结构与算法分析:C语言描述》、《数据结构(C语言版)》严蔚敏等书中的堆排序。

  2. 考虑:能否维护一个数据结构用来存储排好序的5个数,要求如果输入数大于5个中最小的数,就将其插入至正确位置,并删除最小的数。这样对输入进行一次遍历,即可找出最大的5个数。
    此处想到的是用单链表,首先对输入中前5个数字升序排序,插入空的链表中。

//简单冒泡排序,输入少,对整体性能影响可忽略不计
for(int j=1; j<M; j++){
    for(int k=0; k<M-j; k++){
        if(input[k]>input[k+1]){
            tmp = input[k];
            input[k] = input[k+1];
            input[k+1]=tmp;
        }
    }
}
for(int i=0; i<M; i++){
    Insert(input[i],L,P);//依次插入链表
    P = P->Next;
}

图片 1.png

Position Tmp,TmpCell;
for( ; i<N; i++){ //对其余输入进行一次遍历
    P = Header(L); //表头
    do{
        Tmp = P;//暂存前驱元,保存位置
        P = P->Next;//第一个元素
        if( input[i] <= P->Value ){ //小于第一个元素或者后面的某一个元素
            if(P != L->Next){ //input[i]大小介于第一个元素与此位置的元素
                Insert(in[i],L1,Tmp); //插入
                TmpCell = L1->Next;
                L1->Next = TmpCell->Next;
                free( TmpCell ); //挤出第一个元素,也就是5+1=6个中最小的元素
            }
            break;
        }else if(input[i] > P->Value && IsLast( P, L )){ //如果大于最后一个(也就是最大的)元素
            Insert(in[i],L,P); //插入到最后
            TmpCell = L->Next; L->Next = TmpCell->Next; free(TmpCell); //删除第一个元素(6个中最小的)
            break;
        }
    } while( !IsLast(P, L) );
}

插入可能是这样的:
图片 2.png

删除首元可能是这样的:
图片 3.png

小结:当输入大数据量,而只需前m个最大(最小)值时,应用链表不失为一个好办法,它只对输入进行一次遍历,时间复杂度O(N),空间也只不过额外是一个含6个元素的链表大小而已。
欢迎指教。

PHP的GD库freetype编译安装问题及解决办法

首先说明:

  1. 我的环境是Mac OS X,大家知道mac是基于unix,所以从源代码编译安装三步曲:./configure 、 make 、 make install 是都知晓的。
  2. 编译安装三步曲,是可以无限重复进行的。当然有时你要make clean一下。

在一些带验证码、做水印、一些图片处理的PHP项目中,要用到GD库(从PHP 4.3.0开始,绑定到PHP源代码的ext里),在./configure时,使用 --with-gd安装。通常GD库主要有libpng\libjpeg\freetype2\t1lib这四个依赖,而libpng需要zlib(unix/linux系统都会有这个库,不用自己下载安装)。
libpng\libjpeg\ freetype2 \t1lib 这四个库,就要自己先安装好
三种方式:

  1. 从他们的官网中下载稳定版,从源码安装,安装到/usr/local(./configure --prefix=/usr/local)
  2. yum apt-get等方式安装(我的mac没装这几个命令,所以我没有采用这种方式)
  3. 这个方式仅限Mac:Homebrew ———— The missing package manager for OS X,可去其github看文档,安装后几个简单命令,就把这些依赖的库安装好了,非常方便。

现在,我们已经解决了GD的所有依赖,只要在./configure时加上以下几个配置项:

--with-gd --with-zlib --with-png-dir=/usr/local --with-jpeg-dir=/usr/local --with-freetype-dir=/usr/local --with-t1lib=/usr/local 

再 sudo make 、 sudo make install 就完事了!
gd.png

遇到的一些问题:

  1. Mac是自带PHP的,版本稍旧一点且源码也没有了,不如把自带的干掉,重新编译安装一个(比如PHP 5.5)!系统默认的PHP安装在/usr,我们自己通常安装在/usr/local里。
    彻底删除自带的PHP:
cd /private/etc/
sudo rm -rf php-fpm.conf.default php.ini php.ini.default
cd /usr/bin/
sudo rm -rf php php-config phpdoc phpize
cd /usr/include
sudo rm -rf php
cd /usr/lib
sudo rm -rf php
cd /usr/sbin
sudo rm -rf php-fpm
cd /usr/share
sudo rm -rf php
cd /usr/share/man/man1
sudo rm -rf php-config.1 php.1 phpize.1
cd /usr/share/man/man8
sudo rm -rf php-fpm.8
  1. 因为不断试用关于GD的这几个配置项,我编译安装三步曲起码进行了十多次。你会发现第一次编译安装时间很长,之后重复编译安装很快就完成了,是因为有一些步骤就跳过了。所以改了一些配置项,phpinfo()中的预期的GD的信息却没有。所以重复三步曲前,make clean 进行一下就ok了。

我的配置项:./configure --prefix=/usr/local/php --enable-mbstring --with-apxs2=/usr/sbin/apxs --with-mysql --with-pdo-mysql --enable-zip --with-mysqli --with-curl=/usr/local/opt/curl
说明:
--with-apxs2=/usr/sbin/apxs 这个配置项是针对Apache2.x版本,=[DIR]为apxs命令的位置
--with-curl=/usr/local/opt/curl 详见curl安装

经典排序算法

  1. 冒泡
$arr = array(3,44,38,5,47,15,36,26,27,2,46,4,19,50,48);
$arr = array(2,3,4,5,15,19,26,27,36,38,44,46,47,48,50);
$times = 0;//记录比较的次数
$len=count($arr);
//控制需要冒泡的轮数
for($i=1;$i<$len;$i++){
  $swapped = false;//[优化]跳出循环之用
  //控制每轮 冒出一个数 需要比较的次数
  for($k=0;$k<$len-$i;$k++){
    $times += 1;
    if($arr[$k]>$arr[$k+1]){
      $tmp=$arr[$k+1];
      $arr[$k+1]=$arr[$k];
      $arr[$k]=$tmp;
      $swapped = true;
    }
  }
  $times += 1;
  if(!$swapped)
    break;
}
echo $times;print_r($arr);

冒泡排序无论代码怎么实现,交换的次数是同样。不同的是,设计良好的算法对于排序良好的输入,进行比较的次数会骤减。

  1. 插入排序
function insert_sort(&$arr){
    $sum = count($arr);
    for($i=1;$i<$sum;$i++){
        $tmp=$arr[$i];
        $key=$i-1;
        while($key>=0 && $tmp<$arr[$key]){
            $arr[$key+1]=$arr[$key];
            $key--;
        }
        $key != $i-1 && $arr[$key+1] = $tmp;//如果有移动,就插入
    }
}
  1. 希尔排序
function shell_sort(&$arr)
{
    if(!is_array($arr)) return;
    $n = count($arr);
    for($gap=floor($n/2);$gap>0;$gap=floor($gap/=2))
    {
        for($i=$gap;$i<$n;++$i)
        {
            for($j=$i-$gap;$j>=0 && $arr[$j+$gap]<$arr[$j];$j-=$gap)
            {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+$gap];
                $arr[$j+$gap] = $temp;
            }
        }
    }
}
  1. 选择排序
function selection_sort(&$array){
    $count=count($array);
    for($i=0;$i<$count-1;$i++){
        /*findtheminest*/
        $min=$i;
        echo'$min-->'.$array[$min].'-->';
        for($j=$i+1;$j<$count;$j++){
            //由小到大排列
            if($array[$min]>$array[$j]){
                //表明当前最小的还比当前的元素大
                $min=$j;
                //赋值新的最小的
            }
        }
        echo$array[$min].'coco<br/>';
        /*swap$array[$i]and$array[$min]即将当前内循环的最小元素放在$i位置上*/
        if($min!=$i){
            $temp=$array[$min];
            $array[$min]=$array[$i];
            $array[$i]=$temp;
        }
    }
}
  1. 快速排序
function quickSort($arr){
    if(count($arr)>1){
        $k=$arr[0];
        $x=array();
        $y=array();
        $size=count($arr);
        for($i=1;$i<$size;$i++){
            if($arr[$i]<=$k){
                $x[]=$arr[$i];
            }elseif($arr[$i]>$k){
                $y[]=$arr[$i];
            }
        }
        $x = quickSort($x);
        $y = quickSort($y);
        return array_merge($x,array($k),$y);
    }else{
        return $arr;
    }
}
  1. 选择排序
function selectSort(&$arr){
    $n = count($arr);
    for($i=0; $i<$n-1; $i++){
        $min_k = $i;
        $min_v = $arr[$i];
        for($j = $i+1; $j<$n; $j++){
            if($arr[$j] < $min_v){
                $min_v = $arr[$j];
                $min_k = $j;
            }
        }
        $arr[$min_k] = $arr[$i];
        $arr[$i] = $min_v;
    }
}

Linux下Nginx安装(pcre和openssl)

Nginx ("engine x") 是一个高性能的 HTTP 和 反向代理 服务器,也是一个 IMAP/POP3/SMTP 代理服务器。

想要Linux下安装Nginx作为WEB服务器,要先准备些必要的库和工具,通常必须安装的是:PERC库和Openssl。

分四步走,让你的Nginx迅速跑起来!

1. 安装PCRE库(Nginx的rewrite模块和HTTP核心模块会用到PCRE正则表达式语法)

不用考虑是否已安装,直接上命令:

使用yum来安装:

[root@example.com ~]# yum install pcre pcre-devel

或者用apt-get:

[root@example.com ~]# apt-get install libpcre3 libpcre3-dev

如果这些安装包已经安装在系统上,你会收到Nothing to do 的信息,就是已安装过了的意思。

 

2.安装OpenSSL(若服务器提供安全网页(https://)时,会用到OpenSSL库)

使用yum:

[root@localhost example]# yum install openssl openssl-devel

或者用apt-get:

[root@localhost example]# apt-get install openssl openssl-dev

3.下载、解压Nginx

去http://nginx.org/下载你要使用的版本,放到home目录,然后解压

[root@localhost example]# tar zxf nginx-0.7.66.tar.gz

4.安装Nginx

创建一个应用程序通常分为三步:从源代码到配置、编译和安装编译。每一步都有很多配置项,但对于初学者,我们只是让它能跑起来,可以先忽略这些配置项。最容易的办法依次执行下面三个命令:

[root@localhost nginx-0.7.66]# ./configure             //有一个重要的配置项是 --prefix=...指定安装Nginx的基础目录,比如你想把它安装在 /home/jiang/www/下,这个完整的命令应该是:[root@localhost nginx-0.7.66]# ./configure --prefix=/home/jiang/www

configure过程中可能出现的几个报错,及原因:

  • 1) ./configure: error: C compiler gcc is not found 原因:你没有安装gcc ,这样可能你也没安装下面几个包,请一并安装
    yum install gcc gcc-c++ autoconf make
  • 2) Makefile: 权限不够 原因:当前用户没有权限读写nginx源码目录,请切换到root下运行如下命令,作用是将当前目录的所有文件所有者都设为我们正在使用的普通用户。
    [jiang@localhost nginx-0.7.66]# chown -R jiang:jiang  ./
    [jiang@localhost nginx-0.7.66]# exit
    然后exit退出到普通用户状态下。 chown 后的 feng:feng 分别是所使用的普通账号的用户名,及其用户组名。
[root@localhost nginx-0.7.66]# make

[root@localhost nginx-0.7.66]# make install

至此安装成功,去安装Nginx的基础目录下的sbin/,注意,我这里的目录是/home/jiang/www/sbin,执行命令:

[root@localhost sbin]# ./nginx           //效果见下图

 

屏幕上不会出现任何文本信息,这是个好迹象,意味着正在正确运行。

打开浏览器,输入localhost,done done done done ~~~