实用的Linux命令-screen

2014年9月12日 没有评论

我们经常要使用ssh进行远程连接Linux服务器,而且希望程序在我们关闭ssh连接后,能够继续程序,我们一般会使用nohup启动程序,那nohup是怎么做到的呢?

一般情况步,当远程连接终端与服务器的网络连接断开后,操作系统会向正在运行的程序发送SIGHUP信号(即挂断信号),而这个情况会使程序退出。但当使用nohup执行其它命令时,nohup会忽略掉SIGHUP信号,这样就使得程序可以在连接断开后继续执行。

nohup既然可以实现我们的需求,那为什么我们还要介绍screen呢?

因为有时,我们需要有这样一种需求:比如第一天我们进入到了相关目录,并启动了相关程序,我们想第二天来的时候继续回到这个目录,并查看程序运行状态。这时使用nohup就达不到我们的需求了。

screen就可以达到我们的要求。 阅读全文…

分类: Linux 标签: , ,

彻底搞定堆排序

2014年8月9日 没有评论

堆是一种特殊的二叉树,分为最小堆和最大堆。所谓的最小堆是指父节点小于或等于左右子节点;最大堆是指父节点大于或等于左右子节点。

  1. 堆插入操作
  2. 堆删除操作
  3. 建立一个堆
  4. 堆排序

在讲堆排序之前,我们先来了解一下堆的插入操作和删除操作。插入操作主要就是用到堆的向上调整(请允许我这么叫吧,哈哈);删除操作主要用到的是堆的向下调整。

我们先来看一下堆的插入操作示意图,以下是以小堆为例:

insert

 

 

 

 

也就是在插入一个元素,先将元素放置在底层(表层),然后从个元素开始,依次和上层的父节点比较,对于小堆来说,如果新插入的元素比父节点还小,就要和父节点进行交换,依次进行更新,整个堆就恢复状态了。

对于小堆来说,其插入操作代码如下: 阅读全文…

分类: 编程算法 标签: , , ,

彻底搞定二路归并

2014年8月6日 没有评论

归并排序,是分治算法的典型应用,它通过将待排序序列不断进行分治,进而得到最小的单元(一个数),然后再利用两个有序序列的o(n)的合并算法,进行合并,一层层返回就使得整个序列有序。

这里只介绍二路归并排序。

先来看一下二路归并的流程。

1)         起始状态,整个序列无序,设置left = 0; right = n -1

2)         如果left < right,求出middle = (left+ right) / 2。然后分别对left,middle进行归并排序,并且对middle+1,right进行归并排序

3)         将left,middle和middle+1,right进行合并

这三个步骤中,对子序列left,middle和middle+1,right进行归并排序,就进行了递归。 阅读全文…

分类: 编程算法 标签: , ,

彻底搞定选择类排序

2014年8月6日 没有评论

选择类排序的思想是选择合适的数将其放到合适的位置,由于选择类排序每次调整位置时跨度都比较大,存在不稳定的情况,所以是一种不稳定的排序。

         选择类排序主要有两个方法:直接选择和快速选择排序。

         我们先来看一下直接选择排序,我们先来用流程来描述一下它:

1)         开始认为所以都为无序区,另i=0

2)         a[i-n-1]中找到最小的值,将其与a[i]交换

3)         i++,直到i不满足i < n –
1

其实选择排序也是将数据分为了有序区和无序区,然后将无序区的最小的放到合适的位置,这样就保证放置位置到0的位置是有序的。

看一下直接选择排序的代码:

/*
 * 直接选择排序,增序
 */

void selectSort(int* a, int n){
	//每次都将最小的和有放到有有序区的后一位,开始是全部无序
	for(int i = 0; i &lt; n - 1; i++){
		int min = i;
		for(int j = i + 1; j &lt; n; j++){
			if (a[j] &lt; a[min])
				min = j;
		}
		//交换两个人值,跨度很大,所以直接选择是不稳定的
		int tmp = a[i];
		a[i] = a[min];
		a[min] = tmp;
	}
}

 

直接选择是相当简单一种排序方法,从代码中可以看到直接选择的时间复杂度是o(n^2)

直接选择每次在无序区做筛选时,做了很多次的重复工作,就有人想可不可以利用分治思想,每次筛选时把比某个数小的移到一边,把比某个数大的移到另一边,这样不就将数分为两个区,依次再进行迭代,最终就实现了有序,这就是快速选择排序的思想。

我们用流程来描述一下快速选择排序。 阅读全文…

分类: 编程算法 标签: , ,

彻底搞定插入排序

2014年8月5日 没有评论

插入排序的思想是在前面已有序的情况下,将下一个元素插入到有序元素中。由于插入排序中相同的元素的前后位置是不变的,所以插入排序是稳定排序(具体可以查看代码)。

对于一个数组int  a[n],按照插入排序的直接定义,其实现方式如下:

1)         初始时,a[0]为有序区,a[1-n-1]为无序区,另i=1

2)         a[i]插入到a[0-i-1]有序区

3)         i++,直至i == n

对于第2步,实现方式也比较多。

    我们先来看一下直接插入排序的两种实现方式。

第一种实现是先找到a[i]待插入的位置j,最后将a[j-i-1]分别向后移一个,最后将a[i]插入到j的位置。

实现代码如下:

/*
 * 直接插入,先找位置,再后移,增序
 */
 
void insertSort(int* a, int n){
         for(int i = 1; i &lt; n; i++){
                   //找要插入的位置
                   int j = 0;
                   for(; j &lt; i; j++){
                            if (a[j] &gt; a[i])
                                     break;
                   }
                   //依次向后移
                   //先暂存一下a[i]的值
                   int tmp = a[i];
                   for(int k = i; k &gt; j; k--){
                            a[k] = a[k-1];
                   }
                   a[j] = tmp;
         }
}

 

   从上面的代码可以看到直接插入排序的时间复杂度为o(n^2),上面的代码其实是不够简洁的,我们可以把搜索和后移合并为一个,具体看代码:

阅读全文…

分类: 编程算法 标签: , , ,

彻底搞定冒泡排序

2014年8月5日 1 条评论

 在七大排序算法中,冒泡排序可以是比较简单的一个了,虽然简单,变种却很多,比如双向冒泡。

 这里就来简单的回顾一下冒泡排序及双向冒泡排序(鸡尾酒排序)。

 冒泡其实是一种交换排序思路,每次通过相邻结点的比较,把最大的或最小的结点向指定的方向移动,如果把最大的向移,那就是增;如果把最小的向后移,那就是降序。由于每次交换不会导致拥有相同值的元素的前后顺序改变,所以冒泡排序是稳定排序。

  对于有n个元素的数组来说,由于进行n-1次这样的交换后,就有序了,所以最外层会有n-1次循环,内部还要有一层循环,具体上代码

/*
 * 这是一个简单的冒泡算法,增序
 */
void bubbleSort(int* a, int n){
         //外层有n-1次循环
         for(int i = 1; i &lt; n; i++){
                   //内部循环,结止点为n-i,每次都是前边的后边的进行比较
                   for(int j = 0; j &lt; n - i; j++){
                            if (a[j] &gt; a[j+1]){
                                     int tmp = a[j];
                                     a[j] = a[j+1];
                                     a[j+1] = tmp;
                            }
                   }
         }
}

 

 从代码中,可以看到冒泡排序的时间复杂度为o(n^2),在七大排序中是效率是最低的。

 对于冒泡排序,还有一些简单实用的小改进,如监测每次循环是否有交换,如果没有说明已经有序,就没必要再进行下面的循环操作。

  下面我们重点讲一下双向冒泡排序,也被称为鸡尾酒排序,其思想就是在每次进行双向排序,把未有序区间的最小的和最大的数放到合适的位置。

   举个简单的例子来说,对于有6个元素的数组 int
array = {3,4,2,5,6,1}
,将其增序排序,可以按如下步骤对其进行排序。 阅读全文…

分类: 编程算法 标签: , ,

彻底理清C/C++中的static关键字

2014年8月4日 没有评论

我们知道在C中有static关键字,C++中也有static关键字,那C++中的static关键字相对于C中的static关键字有那些不同点呢?

这个问题,可以简单的理解为:C中的static关键字是面向过程用的,而C++中的static关键字除了可以面向过程外,还可以用在面向对象编程中。

1.       C中修饰函数

2.       C中修改变量

3.       类中的修饰函数

4.       类中修饰变量

 

 我们先来看一下C中的static关键字的作用。

 Cstatic可以修饰变量也可以用来修饰函数,修饰变量又分为两种,一种是修饰全局变量,一种是修饰局部变量。

1.       我们先来看一下C中的static修饰函数

         static1.cc

#include &lt;iostream&gt;
 
using namespace std;
 
void say(){
         cout&lt;&lt;"this is file static1"&lt;&lt;endl;
}

 

 

static2.cc

#include &lt;iostream&gt;
 
using namespace std;
 
extern void say();
 
int main(){
         say();
         return 1;
}

 

使用g++ static1.cc static2.cc –o static,编译并运行是没有错误的。

但如果我们把static1.cc中的void say()定义改为static void say(),再编译就会出错。

也就是说在C(面向过程编程)中,static修饰函数的作用是让这个函数只在本文件内可见。

 

2.       Cstatic修饰变量又有何作用呢 阅读全文…

其实python可以这样学7-python对linux说hello

2014年7月5日 没有评论

         本节主要讲的是pythonlinux的交互问题,通过python可以直接向linux下达命令,这样就可以通过python来编写一些批量处理或者例行化的程序。

         本文共分为以下几个章节来进行。

1.       PythonShell简单对比

2.       文件夹类操作

3.       路径类操作

4.       Linux(shell)命令操作

5.       写在最后

6.       参考文献

 

有时候在使用python的时候,我们经常有这种需求,需要python能够和linux相关的命令打交道,这样我们就可以有一个总控脚本,然后通过调用linux命令将不同部分组合在一起。

还有就是批量处理的功能:比如有一个文件夹存放着一些文件,我如何对这些文件进行批量操作,而不是一个文件一个文件的去手动进行操作,这些都可以通过pythonlinux的交互命令完成。

 

1.      PythonShell

Shell具有与linux天然的结合性,所以python在与linux交互方面确实不如shell方便,但事情总是双面的,shell的语法和格式要求特别严格(如=两边不能有空格),更适合作为一种命令的堆积,而python更准确的说,是一种编程语言(类似java),从软件工程的角度来看,python的代码可维护性更高,复用性更强,开发更高效,最主要的是,python也可以实现shell所有的功能,那就是在python中也可以调用linux(shell)命令。

 

2.      文件夹操作

要进行文件夹或文件的相关操作,首先要引入os模块:import os

os.path.basename(path)

根据给定的路径,返回文件名或目录名,如:./data/src将返回src(在此src可以是目录也可以是文件)

os.path.isdir(path)

判断传入的路径是不是一个目录,如果是返回True,否则返回False

os.path.isfile(path)

判断传入的路径是不是一个文件,如果是返回True,否则返回False

os.path.islink(path)

判断传入的路径是不是一个链接,如果是返回True,否则返回False

os.path.getsize(path)

返回传入路径的大小,如果传入是一个文件,则返回文件大小,如果是一个目录,博主在linux下测试会统一返回4096(4kb)

os.listdir(path)

列出给定目录下的所有文件和目录,如果传入的是一个文件将会发生错误

 

在进行文件夹操作时,有时候很可以会进行拼接,如dirpath+’1.txt’这样,但是首先要保证dirpath最后是一个’/’,否则dirpath+’1.txt’就成了一个文件,而不是一个路径加文件,一般都要对路径进行如下操作:

         if
dirpath[-1] == ‘/’:

                  Pass

         else:

                  dirpath
+= ‘/’

 

3.      路径类操作

这一部分主要讲解与路径相关的操作,如得到当前路径,改变路径等。

os.path. abspath(path)

返回此路径的绝对路径

os.path.isabs(path)

判断传入的路径是否为绝对路径,如果是返回True,否则返回False

os.path.exists(path)

判断传入的路径是不是存在,若存在返回True,否则返回False

os.getcwd()

得到当前工作路径

os.getenv(arg)

得到环境变量arg的值

os.putenv(key,value)

向环境变量中添加变量key,值为value,不过这个能否成功要看你的系统是否支持这个操作。

os.chdir(path)

改变路径,进入到path 阅读全文…

分类: Python 标签: , ,

其实python可以这么学6-模块及异常处理

2014年6月27日 没有评论

         其实我们前边已经使用了很多模块,如第一节的urllib,那本节将为你介绍import urllib背后的秘密。

         对于异常处理,我们已经在其它语言如C++java中有所体会,那python中又是如何进行异常处理的呢?

         稍后,你就会知道答案。本节共分为以下几个部分。

1.      认识模块

2.      模块的引入

3.      定义模块

4.      常用模块介绍

5.      异常处理

6.      写在最后

7.      参考文献

 

下面我们先来了解下模块。

1.      认识模块

模块其实就是一些函数和类的集合文件,它能实现一些相应的功能,当我们需要使用这些功能的时候,直接把相应的模块导入到我们的程序中,我们就可以使用了。这类似于C语言中的include头文件。在 Python中的模块是一个以.py结尾的 Python代码文件。

 

2.      模块的引入

C语言或C++语言中,我们使用include来引入相应的库,那python如何引入模块呢?

Python引入模块与java中引入库有些类似,都使用import

import 会完成以下三个操作:

l  创建新的名称空间(namespace),该名称空间中拥有输入模块中定义的所有对象;

l  执行模块中的代码;

l  创建该名称空间的变量名

import 语句可同时输入多个模块,如:

import
os,sys,system

也可以写成:

import os

import sys

import system

有些模块的名称很长,我们可在输入时给它起个简单的别名,这样在使用模块中

的对象就方便很多,如

import ftplib as
ftp

有时我们可能只想使用模块中某个对象,又不想把整个模块输入,则可以用

from…import 语句输入特定对象。如:

from ftplib
import FTP

这样,我们就可直接使用 FTP(),而不用带前缀。

 

3.      定义模块

Python 脚本和模块都是一个以.py 结束的文件,那程序是如何判断一个.py 文件是作为脚本还是模块呢?关键是一个名为__name__的变量,如果它的值是__main__,则不能作为模块,只能作为脚本直接运行。所以在很多脚本的最后都有一段类似下面的语句,限制只能以脚本方式运行,不作为模块: 阅读全文…

分类: Python 标签: , ,

文本处理中的正则实例

2014年6月20日 1 条评论

         本文主要是总结下博主在百度实习时经常使用的正则表达式,主要涉及到文本的处理,数据的抠取,当然也都比较简单~

         本文主要分为以下几个部分来进行介绍。

1.       我所使用的正则

2.       [].

3.       []嵌套问题

4.       URL与正则

5.       简单数据抠取操作

6.       贪婪与懒惰匹配

7.       一次抠取多个数据

8.       使用^$注意事项

9.       写在最后

 

前一篇文章《正则表达式入门之基础篇》介绍了正则的一些基本知识,可没有一些详细的使用实例,总感觉有些遗憾。恰逢最近时间充裕,正好借此机会总结一下我在实习时使用到的正则表达式,同时也巩固下前前篇文章介绍的正则基础知识。

 

1.      我所使用的正则

我实习所在的部门是百度互联网数据研发部,是百度的数据产出部门,其它各个产品线都要依赖这个部门产出的数据,所以我们几乎每天都在和数据打交道,除了从网页包中抓数据外,还要对抓出的数据进行清洗,这时就要使用正则表达式了。

如果对于一条数据,使用正则是非常简单的,但难就难在数据量大时,数据清洗的任务将是非常繁琐的。数据迭代五六次都是很正常的。

由于主要处理阿拉伯语、葡萄牙语和泰语的站点,所以处理基本上都需要先转换成unicode,否则可能会出一些问题,在这里也建议大家在处理文本的时候先转换成unicode编码。

 

2.      [].

曾经被问到过这要一个问题:[.]匹配什么?

如果没有这样实践过的话,很可能会说出匹配一个任意字符的答案,但事实上[.]是匹配一个.

为什么这样呢?在正则有这样一个解释,在不引起歧义的情况下,特殊字符不需要进行转义。[]的作用是限定一个字符集,所以[.]其实就是限定了一个字符.,而.[]中没有歧义,正则在解释时也不会按匹配任意字符解释,否则[]就没有起作用,因此没有歧义,同时也不需要对.进行转义。注意:[.*]也是没有歧义的,即限定字符集为.*

[]\是需要转义的,否则会出错。如要限定的一个字符集中含有\,需要这样来限定:[\\]

[]中也可以包括\s\w等元字符。

 

3.      []嵌套问题

来几个问题:

a)       [[h]匹配什么?

b)       [[]]匹配什么?

是不是有点迷惑?

         使用python进行简单的实验一下:

a)      我们可以得出a)可以匹配单字符’[‘,而不能匹配’[h’,说明此表达式限定的字符集是[h,也就是最外面的[和最外层的]结合,限定字符集[h;而不是最左边的[h]结合,限定字符h,然后最右边的’[‘自成一个字符

b)      对于b来说,可以拆分为[[]’]’,所以它能匹配’[]’

总上,我们知道[]匹配是不可能嵌套的,第一个[遇到第一个]就认为是一个[]

 

4.      URL与正则

我们有时需要做一些白名单的操作,如果符合相应的规则就认为是个白名单,如果规则比较明显,这时就可以使用正则来实现。

我们在抓数据的时候,只想抓出某个站点的某些符合规则的url,对于不符合的url不予以抓取,这时就可以使用正则了。

举个例子:

假如本站的url结构为 domain/category/pagename.html 阅读全文…