分类目录归档:编程基础

埃拉托斯特尼筛法求素数

算法

要得到自然数n以内的全部素数,必须把不大于 的所有素数的倍数剔除,剩下的就是素数。 [1]
给出要筛数值的范围n,找出以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去……。

python实现

def print_prime(N):
    ret = list()
    for i in range(2, N):
        ret.append(i)
    idx = 0
    def remove_multiple(n):
        for v in ret:
            if v%n==0 and v//n > 1:
                ret.remove(v)
    while ret[idx]*ret[idx] <= N-1:
        remove_multiple(ret[idx])
        idx+=1
    print(ret)


if __name__ == '__main__':
    print_prime(10000)

参考

算法说明

C语言程序设计阅读笔记

  1. 第一章 导言
  2. 第二章 类型、运算与表达式
    1. 类型转换
    2. 运算符优先级与求值次序
  3. 第三章 控制流
  4. 第四章 函数与程序结构
    1. C预处理器
      1. 宏替换
  5. 第五章 指针与数组
    1. 指针与地址
    2. 指针与函数参数
    3. 指针与数组
    4. 地址算术运算
    5. 字符指针与函数
    6. 指针数组以及指向指针的指针
    7. 命令行参数
    8. 复杂声明
  6. 第六章 结构
    1. 结构的基本知识
    2. 结构与函数
    3. 结构数组
    4. 指向结构的指针
    5. 自引用结构
    6. 类型定义(typedef)
    7. 联合
    8. 位字段
  7. 第七章 输入输出
    1. 标准输入/输出
    2. 格式化输出 – printf函数
    3. 变长参数表
    4. 格式化输入 – scanf函数
    5. 文件访问
    6. 错误处理 – stderr 和 exit
    7. 行输入和行输出
    8. 其它函数

第一章 导言

浮点数知识:

  1. http://www.jb51.net/article/103412.htm 原码、反码、补码、移码的作用
  2. 浮点数结构 http://blog.csdn.net/whzhaochao/article/details/1288587
  3. https://jingyan.baidu.com/article/425e69e6e93ca9be15fc1626.html 小数转二进制

在程序中使用300、20等"幻数"并不是好习惯,它们几乎不能给以后阅读程序的人提供什么信息,而且使程序的修改更加困难。处理这类幻数的一种方法是赋与它们有意义的名字。
如果程序中的幻数都以符号常量的形式出现,对程序进行大量修改就会相对容易很多。

#define 指令行的未尾没有分号。

标准库提供的输入/输出模型非常简单:无论文本从何处输入,输出到何处,其输入/输出都是按照字符流的方式处理。

语句++nc比nc=nc+1更精炼一些,且通常效率更高一些。

%.0f强制不打印小数点和后面的小数部分,因此小数部分的位数为0。

单独的分号称为空语句。

单引号中的字符表示一个整型值,该值等于此字符在机器字符集中对应的数值,我们称之为字符常量。
但是,它只不过是小的整型数的另一种写法而已。

在兼有值与赋值两种功能的表达式中,赋值结合次序是由右至左。

char类型的字符是小整数,因此char类型的变量和常量在算术表达式中等价于int类型的变量和常量。

之所以getchar的返回值得是int 而不是char, 是因为它需要包含int类型的EOF。

程序中的每个局部变量只在函数被调用时存在,在函数执行完毕退出时消失,这也是其他语言通常把这类变量称为 自动变量 的原因。
如果 自动变量 没有赋值,则其中存放的是无效值。
外部变量 必须定义在所有函数之外,且只能定义一次,定义后编译程序将为它分配存储单元。在每个需要访问外部变量的函数中,必须声明相应的外部变量,此时声明其类型。
声明时可以用 extern 语句显示声明,也可以通过上下文隐式声明。
在源文件中,如果外部变量的定义出现在使用它的函数之前,那么在那个函数中就没有必要使用extern声明。
在通常的做法中,所有外部的变量的定义都是放在源文件中的开始处,这样就可以省略extern声明。
如果程序包含在多个源文件中,而某个变量在file1中定义,在file2和file3文件中使用,那么在文件file2与file3中就需要使用 extern 声明来建立该变量与其定义之间的联系。

"定义"表示创建变量或分配存储单元,而"声明"指的是说明变量的性质,但并不分配存储单元。
有赋值语句叫定义,没有赋值说句叫声明.

int a=5;//定义
int b;//声明

过分依赖外部变量会导致一定的风险,因为它会使程序中的数据关系模糊不清–外部变量的值可能会被意外地或不经意地修改,而程序的修改又变得十分困难。

第二章 类型、运算与表达式

标准函数strlen(s)可以返回字符串参数s的长度,但长度不包括末尾的'\0'。

枚举为建立常量值与名字之间的关联提供了一种便利的方式。相对于#define语句来说,它的优势在于常量值可以自动生成。

字符常量'\0'表示值为0的字符,也就是空字符(null)。我们通常用'\0'的形式代替0,以强调某些表达式的字符属性,但其数字值是0。

所有变量都必须先声明后使用,尽管某些变量可以通过上下文隐式地声明。

如果变量不是自动变量,则只能进行一次初始化操作,从概念上讲,应该是在程序开始执行之前进行,并且初始化表达式必须为常量表达式。
默认情况下,外部变量与静态变量将被初始化为0。未经显式初始化的自动变量的值为未定义的(即无效值)。

对数组而言,const限定符指定数组所有元素的值都不能被修改。
const限定符也可配合数组参数使用,它表明函数不能修改数组元素的值。
如果试图修改const限定的值,其结果取决于具体的实现。

逻辑非运算符!的作用是将非0操作数转换为0,将操作数0转换为1。

需要注意的是, C语言没有指定同一运算符中多个操作数据的计算顺序。(&&、|| 、?:和,运算符除外).
类似的, C语言也没有指定函数各参数的求值顺序。
像下面的语句:

a[i] = i++;//数组下标i是引用的旧值还是新值,编译器会有不同的解释,因为最佳的求值顺序同机器结构有很大的关系。。实际开发中,需要避免这样的代码。

在任何一种编程语言中,如果代码的执行结果与求值顺序相关,则都是不好的程序设计风格。

类型转换

一般来说,自动转换是指把"比较窄"操作数转换为"比较宽的"操作数,并且不丢失信息的转换。

C语言没有指定char类型的变量是无符号变量还是有符号变量。
C语言定义保证了机器的标准打印字符集中的字符不会是负值,因此,在表达式中这些字符总是正值。但是,存储在字符变量中的位模式在某些机器中可能是负的,
而在另一些机器中可能是正的。为了保证程序的可移植性,如果要在char类型的变量中存储非字符数据,最好指定signed或unsigned限定符。

注意,表达式中的float类型的操作数不会自动转换为double类型,这一点与最初的定义有所不同。一般来说,数学函数使用double的变量。
使用float类型主要是为了在使用较大的数组时节省存储空间,有时也是为了节省机器执行时间(双精度算术运算特别费时)。

带符号与无符号值之间的比较运算是与机器相关的,因为它们取决于不同整数类型的大小。譬如-1L<1U, -1L>1UL(-1L被转换成UL,转成了正数)

当把较长的整数转换为较短的整数或char类型时,超出的高位部分将被丢弃。

当被double类型转换为float类型时,是进行四舍五入还是截取取决于具体的实现。

即使调用函数的参数为char或float类型, 我们也把函数参数声明为int或者double类型。(在没有函数原型的情况下,char与short类型者将被转换为
int类型, float类型将被转换为double类型。)

通常情况下,参数是通过函数原型声明的。

在对signed类型的带符号值进行右移时,某些机器将对左边空出的部分用符号位填补(即“算术移位”),而另一些机器则对左边空出来的部分用0填补(即“逻辑位移”)

x = x & ~077

注意,表达式x&~077与机器字长无关,它比形式为x&0177700的表达式要好,因为后者假定x是16位的数值。这种可移植的形式并没有增加额外开销,因为
~077是常量表达式,可以在编译时求值。

赋值语句具有值,且可以用在表达式中,在这类表达式中,赋值表达式的类型是它的左操作数的类型,
其值是赋值操作完成后的值。

运算符优先级与求值次序

*同大多数语言一样,C语言没有指定同一运算符中多个操作数的计算顺序。* 如 x=f()+g(), f()是先于g(),还是后于g()调用,是未定义的。
*类似地,C语言也没有指定函数各参数的求值顺序。* printf("%d %d\n", ++n, power(2,n)), 执行结果取决于编译器。
*注意*
a[i] = i++; 此问题,i是引用旧值,还是新值,C语言是未定义的,执行结果由编译器决定,因为最佳的求值顺序同机器结构有很大的关系。
在任何一种编程语言中,如果代码的执行结果与求值顺序相关,则都不是好的程序设计风格。

需要记忆的优先级
() [] . -> 从左至右
! ~ ++ – + – * & (type) sizeof 从右至左

第三章 控制流

标号可以位于对应的goto语句所在函数的任何语句的前面。标号的作用域是整个函数。

在深度潜逃的场景下,跳出循环。用goto语句还是有用的。但不应该滥用。

第四章 函数与程序结构

如果函数定义中省略了返回值类型,则默认为int类型。
程序可以看成是变量定义和函数定义的集合。函数之间的通信可以通过参数、函数返回值、外部变量进行。
return 表达式。
在必要时,表达式将被转换为函数的返回值类型。表达式两边通常加一对圆括号,此处的括号是可选的。

如果某个函数从一个地方返回时有返回值,而从另一个地方返回时没有返回值,该函数并不非法,但可能是一种出问题的征兆。
在任何情况下,如果函数没有成功地返回一个值,则它的"值"肯定是无用的。

如果没有函数原型,则函数将在第一次出现的表达式中被隐式声明。
例如:

 sum += atof(line)

atof被假设为返回值为int值,同时为了兼容旧版本,并不会对参数做假设。 并且,如果函数声明中不包含参数,编译程序不会对参数做任何假设,并会关闭所有的参数检查。

规范的做法是:
*如果函数带有参数,则要声明它们;如果没有参数,则使用void进行声明*

由于C语言不允许在一个函数中定义其他函数,因此函数本身是“外部”的。默认情况下,外部变量与函数具有下列性质:
通过同一个名字对外部变量的所有引用(即使这种引用来自于单独编译的不同函数)实际上都是引用的同一个对象(标准中把这一性质称为外部链接)

名字的作用域指的是程序中可以使用该名字的部分。
外部变量 或函数的作用域从声明它的地方开始,到其所在的(待编译)文件的末尾结束。

如果要在外部变量的定义之前使用该变量,或者外部变量的定义与声明不在同一个源文件中,则必须在相应的变量声明中强制性地使用关键字 **extern**。

变量声明用于说明变量的属性(主要是变量的类型),而变量定义除此以外还将引起存储器的分配。

在一个源程序的所有源文件中,一个外部变量只能在某个文件中定义一次,而其它文件可以通过extern声明来访问它。

static 声明限定外部变量与函数,可以将其后声明的对象的作用域限定为被编译文件的剩余部分。

static类型的内部变量是一种只能在某个特定函数中使用但一直占据存储空间的变量。

register 变量放在机器的寄存器中,这样可以使程序更小、执行速度更快。
register变量只适用于自动变量以及函数的形式参数。
无论寄存器变量实际上是不是存放在寄存器中,它的地址都是不能访问的。

在一个好的程序设计中,应该避免出现变量名隐藏外部作用域中相同名字的情况,否则,很可能引起混乱和错误。

在不进行显示初始化的情况下,外部变量与静态变量都将被初始化为0, 而自动变量及寄存器变量的初值则没有定义(即初值为无用的信息)
对于外部变量与静态变量来说,初始化表达式必须是常量表达式,且只初始化一次(从概念上讲是在程序开始执行前进行初始化)

int days[13] = {1,2}

如果初始化表达的个数比数组元素少,则对外部变量、静态变量和自动变量来说,没有初始化表达式的元素将被初始化为0。

递归的执行速度并不快,但递归代码比较紧凑,并且比相应的非递归的代码更易于编写与理解。

C预处理器

宏替换

###
如果在替换文本中,参数名以 # 作为前缀则结果将是被扩展 为 *由实际参数替换为该参数的带引号的字符串*。

#define dprint(expr) printf(#expr " = %g\n", expr)

使用语句
dprint(x/y);
调用该宏时,该宏将被扩展为:
printf("x/y" " = %g\n", expr) 等价于printf("x/y = %g\n", x/y)

如果替换文本中的参数与 ## 相邻,则该参数将被实际参数替换,##与前后的空白符将被删除,并对替换后的结果 *重新扫描*。

#define paste(front, back) front ## back // paste(name,1) 将建立记号name1, 可用作动态变量?

第五章 指针与数组

C语言中,指针使用很广泛:

  1. 指针常常是表达某个计算的唯一途径。
  2. 使用指针通常可以生成更高效、更紧凑的代码。

ANSI C使用类型void*(指向void的指针)代替char*作为通用指针的类型。

指针与地址

指针是能够存放一个地址的一组存储单元(通常是2个或4个字节)
地址运算符&只能应用于内存中的对象,即变量与数组元素。 它不能作用于表达式、常量或register类型的变量。
一元运算符*是间接寻址或间接引用运算符。当它作用于指针时,将访问指针所指向的对象。

int *ip;
上述声明语句表明*ip指向的对象类型是int。

每个指针都必须指向某个特定类型的数据类型。(void类型指针例外,但它不能间接引用其自身)

指针与函数参数

  1. 由于C语言是以传值的方式将参数值传递给被调用函数。因此,被调用函数不能直接修改主调函数中变量的值。如果修改形参的值,实际修改的是副本。
  2. 指针参数使得被调用函数能够访问和修改主调函数中对象的值。因为形参指向的地址和实参指向的地址一样。

指针与数组

通过数组下标所能完成的任何操作都可以通过指针来实现。一般来说,用指针编写的程序比用数组下标编写的程序执行速度快,但更难理解。

根据定义,数组类型的变量或表达式的值是该数组第0个元素的地址。因此pa = &a[0] 和 pa = a是相同的。

对数组元素a[i]的引用也可以写成*(a+i)这种形式。
在计算数组a[i]时,C语言实际上先将其转换为*(a+i)的形式,然后再进行求值,因此在程序中这两种形式是等价的。

数组名和指针之间有一个不同之处。
指针是一个变量,因此pa=a 和 pa++都合法。
但数组名不是变量,因此类型于a = pa 和a++形式的语句是非法的。

在函数定义中,形式参数

char s[];

char *s;

是等价的。更习惯用后一种。

地址算术运算

通常,对指针有意义的初始化只能是0或者是表示地址的表达式。

指针与整数之间不能相互转换,但0是惟一例外,因为把0定义为指针的一个特殊值,常用符号常量NULL代替常量0,表示指针还未指向合适的地址。

有效的指针运算有以下情况:

  1. 相同类型指针之间的赋值运算;
  2. 指针同整数之间的加法或减法运算;数组位移
  3. 指向相同数组中元素的两个指针间的减法或比较运算;位置关系
  4. 将指针赋值为0或指针与0之间的比较运算。 判断指针的值是否有效

字符指针与函数

C语言没有提供将整个字符串作为一个整体进行处理的运算符。

注意以下声明的区别:

char amessage[] = "now is the time";
char *pmessage = "now is the time";

amessage是一个仅仅足以存放初始化字符串以及空字符'\0'的一维数组。数组中的内容可以修改,但amessage始终指向同一个存储地址。
pmessage是一个指针,其初值指向一个字符串常量,之后它可以指向其它地址,但如果试图修改字符串的内容,结果是没有定义的

指针数组以及指向指针的指针

区分指针数组和数组指针:

int (*p)[n]

()的优先级最高,所以这说明定义的是一个指针。接下来是int [n], *p返回的是一个int[n], 即p指向一个整形的一维数组,它的长度是n。

int *p[n]

[]的优先级更高。所以这说明定义的是一个数组。接下来是int *p,说明这个数组存放的是整型指针。

命令行参数

ANSI标准要求argv[argc]的值必须为一空指针。

复杂声明

复杂的声明让人难以理解,原因在于:
C语言的声明不能从左至右阅读,而且使用了太多的圆括号。

规则如下:
dcl: 前面带有可选的*的direct-dcl
direct-dcl: name
(dcl)
direct-dcl()
direct-dcl[]

理解的方法有:右左方法。
几个关键运算符: *、 []、 ()。

从规则不难推导出右左法则。

  1. 首先找到name, 为direct-dcl

2.然后看右边是()还是[], 如果是(),说明声明的函数,如果是[],说明声明的数组。
3.看完右边看左边,如果左边是*,则说明内容是指针。
4.按此解析直到解析完。

第六章 结构

ANSI标准在结构方面的主要变化是字义了结构的赋值操作– **结构可以拷贝、赋值、传递给函数,函数也可以返回结构类型的返回值。
在ANSI标准中,自动结构和数组现在也可以进行初始化。
可以理解是一个复合类型, 高级语言里面的类和对象就是通过结构体实现的。

结构的基本知识

struct point {
    int x;
    int y;
}

关键字struct 引入结构声明。结构声明由包含在花括内的一系列声明组成。
struct 后面的名字是可选的,称为结构标识。结构标记用于为结构命名,在定义之后,结构标记就代表花括号内的声明,可以用它作为该声明的简写形式。
struct 声明定义了一种数据类型。

结构与函数

结构的合法操作只有几种:

  1. 作为一个整体复制和赋值
  2. 通过&运算符取地址。
  3. 访问其成员

如果传递给函数的结构很大,使用指针的方式的效率通常比复制整个结构的效率要高。

注意运算符的优先级和结合顺序:
在所有运算符中,结构运算符"." 和 "->"、用于函数调用的"()"以及用于下标的"[]",因此,它们同操作数之间的结合也最紧密。
注意,他们都是从左至右的结合顺序。

结构数组

条件编译语句#if中不能使用 sizeof, 因为预处理不对类型名进行分析。
但预处理器并不计算#define中的表达式,因此在#define中使用 sizeof是合法的。

指向结构的指针

自引用结构

struct tnode {
    char \*word;
    int count;
    struct tnode \*left;
    struct tnode \*right;
};

一个包括其自身实例的结构是非法的,但是,下列声明是合法的。
struct tnode *left;

类型定义(typedef)

typedef用来建立新的数据类型名。
从任何意义上讲,typedef并没有创建一个新类型,它只是为某个已存在的类型增加了一个新的名称而已。
typdef声明也并没有增加任何新的语义:通过这种方式声明的变量与通过普通声明方式声明的变量具有完全相同的属性。
实际上,typedef 类似于#define 语句,但由于typedef是由编译器解释的,因此它的文本替换功能要超过预处理器的能力。

除了表达方式更简洁之外,使用typedef还有另外两个重要原因。

  1. 它可以使程序参数化,以提高程序的可移值性。如果typdef声明的数据类型同机器有关,那么,当程序移植到其他机器上时,只需改变typedef类型定义就可以了。
  2. 为程序提供更好的说明性。

联合

联合是可以(在不同时刻)保存不同类型和长度的对象的变量,编译器负责跟踪对象的长度和对齐要求。
联合提供了一种方式,以在单块存储区中管理不同类型的数据,而不需要在程序中嵌入任何同机器有关的信息。

联合的目的:一个变量可以合法地保存多种数据类型中任何一种类型的对象。其语法基于结构,如下所示:

union tag {
    int ival;
    float fval;
    char *sval;
}

实际上,联合就是一个结构,它的所有成员相对于基地址的偏移量都为0, 此结构空间要大到足够容纳最"宽"的成员,并且,其对齐方式要适合于联合中所有类型的成员。
联合只能用其第一个成员类型的值进行初始化。

ps:不知道怎么用。能节省能内存,但真正使用的时候,还得知道最后存的值是什么类型,管理也挺麻烦的。
关于对齐,参考文章: http://blog.sina.com.cn/s/blog_715de2f50100pgs3.html

位字段

多个对象保存在一个机器字中,取和设置的时候只操作字的部分位。
这其实可以通过移位运算、屏蔽运算、补码运算进行简单的位操作来实现。

#define EXTERNAL 02
#define STATIC   04

利用|来实现置1操作

flags |= EXTERNAL | STATIC;

利用&来实现置0操作

flags &= ~(EXTERNAL | STATIC);

相对于以上方法,C语言提供了另一种可替代的方法,即直接定义和访问一个字中位字段的能力,而不需要通过按位逻辑运算符。
位字段,或简称字段,是"字"中相邻位的集合。"字"是单个的存储单元,它同具体的实现有关。
示例如下:

struct {
    unsigned int iskeyword : 1;
    unsigned int isextern  : 1;
    unsigned int isstatic  : 1;
}

字段的所有属性几乎都同具体的实现有关。字段是否能覆盖边界由具体的实现定义。
字段可以不命名,无名字段(只有一个冒号和宽度)起填充作用。特殊宽度0可以用来强制在下一个字边界上对齐。

某些机器 上字段的分配是从字的左端至右端进行的,而某些机器则相反。

位字段不是数组,并且没有地址,因此对它们不能使用&运算符。

第七章 输入输出

标准库函数并不是C语言本身的组成部分。
ANSI标准精确定义了这些库函数,所以,只用库函数完成的程序是可移植的。

标准输入/输出

文本流由一系列的行组成,每一行的未尾是一个换行符。
如果系统没有遵循这种模式,则标准库将通过一些措施使得该系统适应这种模式。

格式化输出 – printf函数

printf转换说明:
负号,用于指定被转换的参数按照左对齐的形式输出。

变长参数表

中包含了一组宏定义,它们对如何遍历参数表进行了定义。该文件的实现因不同的机器而不同。
使用流程一致:

  1. va_list ap;//声明
  2. va_start(ap, 最后一个有名参数);//初始化,将ap指向第一个无名参数
  3. value = va_arg(ap,参数类型);//获取参数的值,需要把类型传进行,才可以取得正确的值以及正确地移动到下一个无名参数。
  4. va_end(ap);//释放资源

格式化输入 – scanf函数

两个注意点:

  1. 输入字段定义为一个不包括空白符的字符串,其边界定义为下一个空白符或达到指定的字段宽度。
    这表明scanf函数将越过行边界读取输入,因为换行符也是空白符。(空白符包括空格符、横向制表符、纵向制表符、换行符、回车符、换页符)
  2. 如果转换说明中有赋值禁止字符*,则跳过该输入字段,不进行赋值。

文件访问

关于linux的标准输入、标准输出以及重定向。

0 表示标准输入(默认键盘
1 表示标准输出 (默认屏幕)
2表示标准错误。(默认屏幕)
通过重定向,可以控制以上3个的默认值。

cat file > fil2 等同于 cat file 1>fil2, 输出重定 。1>中的1可以省略不写,默认就是标准输出。

&[n] 代表已经存在的文件描述符。&1代表输出,&2代表错误。&-表示关闭与它绑定的描述符。
所以有下面两种方式放弃标准输出和标准错误。
cat file > /dev/null 2>&1
cat file 1>&- 2>&-
/dev/null是黑洞文件,所有到它的输出都会丢弃。

错误处理 – stderr 和 exit

在main程序中return xx; 相当于exit(xx);

尽管输出错误很少出现,但还是存在(例如磁盘满时);

行输入和行输出

库函数gets在读取输入时,会把换行符'\n'删除。
puts则会在行尾添加换行符。

其它函数

int ungetc(char c, FILE \*fp), 每个文件只能有一个写回字符。

system(char \*s)执行命令。

oop设计原则SOLID详解

oop设计原则SOLID详解

简介

面向对象编程设计原则有个总结,叫SOLID原则。
再具体下去就是具体的设计模式了。

S=single Responsibility Principle 单一职责原则

动机

在这里,责任被认为是改变的一个原因。这个原则表明,如果我们有两个原因要修改一个类,我们必须将功能分为两个类。每个类将只处理一个责任,如果将来我们需要做一个更改,我们将在相应的类中处理。 当我们需要在具有更多职责的类中进行更改时,更改可能会影响与类的其他职责相关的其他功能。

单一职责原则是一个简单和直观的原则,但在实践中有时很难正确运用。

意图

一个类,应该仅有一个引起它变化的原因。

举例

让我们假设我们需要一个对象来保存电子邮件。我们将使用从下面的示例中的IEmail接口。看起来没啥问题。但仔细看看,我们可以看到,我们的IEmail接口和Email类有2个责任(改变的原因)。
一个是在一些电子邮件协议如pop3或imap中使用该类。如果必须支持其他协议,则应以另一种方式对对象进行序列化,并且应添加代码以支持新协议。
另一个是Content字段,即使内容是字符串,也许我们将来可能支持HTML或其他格式。

如果我们只保留一个类,每一个职责的改变可能会影响到另一个:

  • 添加新协议将创建需要为每个类型的字段添加用于解析和序列化内容的代码。
  • 添加新的内容类型(如html)使我们为每个协议添加代码。

//单一责任原则 - 错误示例

interface IEmail { 
    public void setSender(String sender); 
    public void setReceiver(String receiver); 
    public void setContent(String content); 
} 

class Email implements IEmail { 
    public void setSender(String sender){// set sender; } 
    public void setReceiver(String receiver){//设置接收器; } 
    public void setContent(String content){//设置内容; } 
}

我们可以创建一个新的接口和类,称为IContent和Content来分担责任。每个类只有一个责任给我们更灵活的设计:

  • 添加新协议只会导致电子邮件类中的更改。
  • 添加新类型的内容支持导致仅在Content类中的更改。
//单一责任原则 - 好的示例
interface IEmail { 
    public void setSender(String sender); 
    public void setReceiver(String receiver); 
    public void setContent(IContent content); 
} 

interface Content { 
    public String getAsString(); //用于序列化
} 

class Email implements IEmail { 
    public void setSender(String sender){// set sender; } 
    public void setReceiver(String receiver){//设置接收器; } 
    public void setContent(IContent content){//设置内容; } 
}

结论

单一责任原则代表在应用程序的设计阶段识别类的一种好方法,它提醒您想一个类可以发展的所有方式。只有当应用程序应该如何工作的全部情况都很好理解时,才能实现良好的责任分离。

O=open close 开闭原则

开放-封闭原则,是说软件实例(类、模块、函数等等)应该可以扩展,但是不可修改。

这个原则其实是有两个特征,一个是说‘对于扩展是开放的(open for extension)’,另一个是说‘对于更改是封闭的(Closed for modification)’

动机

聪明的应用程序设计和代码实现应该考虑到在应用程序的开发和维护阶段会有频繁的更改。通常,当向应用程序添加新功能时,会涉及到许多更改。应该将现有代码中的这些更改最小化,因为假设现有代码已经进行单元测试,并且已编写代码中的更改可能以不必要的方式影响现有功能。

开闭原则指出该代码的设计和实现,应该能让新功能的加入以现有的代码最小的变化来完成。设计应该允许添加新功能作为新类,尽可能保持现有代码不变。

意图

像类,模块和函数的软件实体应该是开放的扩展,但关闭修改

例子

下面是违反开放关闭原则的示例。它实现了一个图形编辑器处理不同形状的绘图。很明显,它不遵循开放关闭原则,因为GraphicEditor类必须为每个必须添加的新形状类进行修改。有几个缺点:

  • 对于每个新形状添加的GraphicEditor的单元测试应该重做。
  • 当添加新类型的形状时,添加它的时间将会很长,因为添加它的开发人员应该理解GraphicEditor的逻辑。
  • 添加新形状可能以不期望的方式影响现有功能,即使新形状完美地工作。

// Open-Close Principle  -  Bad example 
class GraphicEditor { 
 
    public void drawShape(Shape s){ 
        if(s.m_type == 1)
            drawRectangle(s); 
        else if(s.m_type == 2)
            drawCircle(s); 
    } 
    public void drawCircle(Circle r){...} 
    public void drawRectangle(Rectangle r){....} 
} 
 
class Shape { 
    int m_type; 
} 
 
class Rectangle extends Shape { 
    Rectangle(){ 
        super.m_type = 1; 
    } 
} 
 
class Circle extends Shape { 
    Circle(){ 
        super.m_type = 2; 
    } 
}

下面是支持开放关闭原则的示例。在新设计中,我们在GraphicEditor中使用抽象draw()方法绘制对象,同时在具体形状对象中来实现。使用开放关闭原则避免了先前设计的问题,因为在添加新的形状类时不会更改GraphicEditor:

  • 无需单元测试。
  • 无需了解GraphicEditor的源代码。
  • 因为绘图代码被移动到具体的形状类,当添加新的功能时,降低了影响旧功能的风险。

// Open-Close Principle  -  Good example 
class GraphicEditor { 
    public void drawShape(Shape s){ 
        s.draw(); 
    } 
} 
 
class Shape { 
    abstract void draw(); 
} 
 
class Rectangle extends Shape { 
    public void draw(){ 
        //绘制矩形
    } 
}

结论

OCP只是一个原则。做出灵活的设计需要花费额外的时间和精力,并且它引入了新的抽象层次,增加了代码的复杂性。因此,这个原则应该应用于最有可能改变的领域。

有许多设计模式可以帮助我们扩展代码而不改变它。例如装饰者模式帮助我们遵循开放原则。此外,工厂方法或观察者模式可用于设计一个易于随现有代码中的最小变化而改变的应用程序。

L=LSP(Liskov’s Substitution Principle) 里氏代换原则

子类型必须能够替换它们的父类型
一个软件实体如果使用的是一个父类的话,那么一定适用于其子类,而且它察觉不出父类对象和子类对象的区别。也就是说,在软件里面,把父类都替换成它的子类,程序的行为没有变化。

动机

一直以来,我们在设计一个程序模块,我们创建一些类层次结构。然后我们通过扩展一些类来创建一些派生类。

我们必须确保新的派生类只是扩展而不替换旧类的功能。否则,新类在现有程序模块中使用时会产生不良影响。

Likov的替换原则声明,如果程序模块使用Base类,那么对Base类的引用可以替换为Derived类,而不会影响程序模块的功能。

意图

派生类型必须能够完全替代其基本类型。

例子

下面是违反Likov替代原则的典型例子。在示例中使用2个类:Rectangle和Square。让我们假设Rectangle对象在应用程序中的某个地方使用。我们扩展应用程序并添加Square类。正方形类由工厂模式返回,基于一些条件,我们不知道将返回什么类型的对象。但我们知道这是一个矩形。我们得到矩形对象,宽度设置为5,高度设置为10,得到面积。对于宽度为5和高度为10的矩形,面积应为50,而结果却是100。



//违反Likov的替代原则
class Rectangle
{
    protected int m_width;
    protected int m_height;

    public void setWidth(int width){
        m_width = width;
    }}

    public void setHeight(int height){
        m_height = height;
    }}


    public int getWidth(){
        return m_width;
    }}

    public int getHeight(){
        return m_height;
    }}

    public int getArea(){
        return m_width * m_height;
    }}  
}}

class Square extends Rectangle 
{
    public void setWidth(int width){
        m_width = width;
        m_height = width;
    }}

    public void setHeight(int height){
        m_width = height;
        m_height = height;
    }}

}}

class LspTest
{
    private static Rectangle getNewRectangle()
    {
        //它可以是一些工厂返回的对象... 
        return new Square();
    }}

    public static void main(String args [])
    {
        Rectangle r = LspTest.getNewRectangle();
        
        r.setWidth(5);
        r.setHeight(10);
        //用户知道r是一个矩形。 
        //假设他能够为基类设置宽度和高度

        System.out.println(r.getArea());
        //现在他惊讶地发现该面积是100而不是50。
    }}
}}

结论

这个原则只是开放关闭原则的一个扩展,这意味着我们必须确保新的派生类是扩展基类而不改变它们的行为。

I=Interface Segregation Principle 接口隔离原则

动机

当我们设计一个应用程序时,我们应该注意如何使一个包含多个子模块的模块抽象化。考虑由类实现的模块,我们可以在接口中完成系统的抽象。但是如果我们想扩展我们的应用程序添加另一个模块,它只包含原始系统的一些子模块,我们被迫实现完整的接口和写一些虚拟方法。这样的接口被命名为fat接口或污染的接口。具有接口污染不是一个好的解决方案,并且可能在系统中引起不适当的行为。

该接口分离原则规定,客户不应该被强迫来实现它们不使用的接口。基于一组方法,每个方法服务一个子模块,而不是一个胖接口许多小接口是优选的。

意图

不应该强制客户端依赖于他们不使用的接口。

例子

下面是一个违反接口隔离原则的例子。我们有一个经理类,代表管理工人的人。我们有两种类型的工人一些平均和一些非常有效的工人。这两种类型的工人工作,他们需要每天吃午饭。但现在有些机器人来到他们工作的公司,但他们不吃,所以他们不需要吃午饭。一个新的机器人类需要实现IWorker接口,因为机器人工作。在另一方面,不必实施它,因为他们不吃。

这就是为什么在这种情况下,IWorker被认为是一个污染的接口。

如果我们保持当前的设计,新的Robot类被迫实现eat方法。我们可以写一个不做任何事情的虚拟类(假设每天吃1秒),并且在应用程序中可能会产生不良效果(例如,管理者看到的报告会报告更多的午餐,而不是人数)。

根据接口分离原则,灵活的设计不会有接口污染。在我们的情况下,IWorker接口应该分为两个不同的接口。


// interface segregation principle - bad example
interface IWorker {
    public void work();
    public void eat();
}

class Worker implements IWorker{
    public void work() {
        // ....working
    }
    public void eat() {
        // ...... eating in launch break
    }
}

class SuperWorker implements IWorker{
    public void work() {
        //.... working much more
    }

    public void eat() {
        //.... eating in launch break
    }
}

class Manager {
    IWorker worker;

    public void setWorker(IWorker w) {
        worker=w;
    }

    public void manage() {
        worker.work();
    }
}

下面是支持接口隔离原则的代码。通过在2个不同的接口中拆分IWorker接口,新的Robot类不再强制实现eat方法。此外,如果我们需要另一个功能的机器人像充电,我们创建另一个有充电方法的接口IRechargeble。


// interface segregation principle - good example
interface IWorker extends Feedable, Workable {
}

interface IWorkable {
    public void work();
}

interface IFeedable{
    public void eat();
}

class Worker implements IWorkable, IFeedable{
    public void work() {
        // ....working
    }

    public void eat() {
        //.... eating in launch break
    }
}

class Robot implements IWorkable{
    public void work() {
        // ....working
    }
}

class SuperWorker implements IWorkable, IFeedable{
    public void work() {
        //.... working much more
    }

    public void eat() {
        //.... eating in launch break
    }
}

class Manager {
    Workable worker;

    public void setWorker(Workable w) {
        worker=w;
    }

    public void manage() {
        worker.work();
    }
}

结论

如果设计已经完成,胖接口可以使用适配器模式进行隔离。
像每个原则一样接口分离原则是一个原则,需要花费额外的时间和精力在设计期间应用它,并增加代码的复杂性。
但它产生灵活的设计。
如果我们要过分地使用应用它,它将导致包含许多只有单个方法接口的代码,因此应该基于经验和常识来识别代码将来可能在哪些该地需要扩展。

D= Dependency依赖反转原则

抽象不应该依赖细节,细节应该依赖于抽象。
说白了,就是要针对接口编程,不要对实现编程

动机

当我们设计软件应用程序时,我们可以考虑低级类实现基本和主要操作(磁盘访问,网络协议,…)的类和高级类封装复杂逻辑(业务流,…)的类。最后一个依赖于低级类。实现这种结构的一种自然方式是编写低级类,一旦我们让它们编写复杂的高级类。由于高级类是根据其他定义的,这似乎是合理的做法。但这不是一个灵活的设计。如果我们需要替换一个低级类会发生什么?
让我们来看一个复制模块的典型例子,它从键盘读取字符并将它们写入打印机设备。包含逻辑的高级类是复制类。低级类是KeyboardReader和PrinterWriter。

在一个糟糕的设计中,高级类直接使用并且在很大程度上依赖于低级类。在这种情况下,如果我们要更改设计以将输出定向到一个新的FileWriter类,我们必须在Copy类中进行更改。(让我们假设它是一个非常复杂的类,有很多逻辑,真的很难测试)。

为了避免这样的问题,我们可以在高级类和低级类之间引入抽象层。由于高级模块包含复杂的逻辑,它们不应该依赖于低级模块,因此不应该基于低级模块来创建新的抽象层。低级模块将基于抽象层创建。

根据这个原则,设计类结构的方法是从高级模块开始到低级模块:
高级类 – >抽象层 – >低级类

意图

  1. 高级模块不应该依赖于低级模块。两者都应该依赖于抽象。
  2. 抽象不应取决于细节。细节应该取决于抽象。

例子

下面是违反依赖反转原则的示例。我们有经理类,它是一个高级类,而低级类称为Worker。我们需要在我们的应用程序中添加一个新模块,以模拟由新的专业工作者雇用决定的公司结构的变化。我们为此创建了一个新类SuperWorker。

让我们假设Manager类相当复杂,包含非常复杂的逻辑。现在我们必须改变它,以引入新的SuperWorker。让我们看看缺点:

  • 我们必须更改Manager类(记住它是一个复杂的,这将涉及时间和精力进行更改)。
  • 某些来自管理器类的当前功能可能会受到影响。
  • 单元测试应重做。

所有这些问题可能需要很多时间来解决,它们可能在旧的功能中引入新的错误。如果应用程序是按照依赖性反转原则设计的,情况会有所不同。这意味着我们设计manager类,一个IWorker接口和实现IWorker接口的Worker类。当我们需要添加SuperWorker类时,我们所要做的就是为其实现IWorker接口。现有类中没有其他更改。

//依赖反转原理 - 错误的示例

class Worker { 

    public void work(){ 

        // .... working 

    } 

} 



class Manager { 

    Worker worker; 



    public void setWorker(Worker w){ 
        worker = w; 
    } 

    public void manage(){ 
        worker.work(); 
    } 
} 

class SuperWorker { 
    public void work(){ 
        // .... working more more 
    } 
}

下面是支持依赖反转原理的代码。在这个新设计中,通过IWorker接口添加了一个新的抽象层。现在来自上面的代码的问题被解决了(考虑到高级逻辑没有变化):

  • 在添加SuperWorkers时,Manager类不需要更改。
  • 最小化风险以影响Manager类中的旧功能,因为我们不更改它。
  • 无需为Manager类重做单元测试。
//依赖反转原则 - 好例子
interface IWorker { 
    public void work(); 
} 

class Manager implements IWorker { 
    public void work(){ 
        // .... working 
    } 
} 

class SuperWorker implements IWorker { 
    public void work(){ 
        // .... working more more 
    } 
} 

class Manager { 
    IWorker worker; 

    public void setWorker(IWorker w){ 
        worker = w; 
    } 

    public void manage(){ 
        worker.work(); 
    } 
}

结论

当应用这个原则时,它意味着高级类不直接与低级类工作,他们使用接口作为抽象层。在这种情况下,不能使用运算符new来在高级类(如果必要)内实例化新的低级对象。相反,可以使用一些Creational设计模式,例如Factory Method,Abstract Factory,Prototype。

模板设计模式是应用DIP原理的示例。

当然,使用这个原则意味着更多的努力,将导致更多的类和接口维护,在一些词语中更复杂的代码,但更灵活。这个原则不应盲目地应用于每个类或每个模块。如果我们有一个更有可能在未来保持不变的类功能,则不需要应用这个原则。

算法分析

算法分析

算法简介

简单来说,所谓算法就是定义良好的计算过程,它取一个或一组值作为输入,并产生出一个或一组值作为输出。亦即,算法就是一系列的计算步骤,用来将输入数据转换成输出结果。

算法分析

算法分析是关于计算机程序性能与资源利用的研究。
计算时间是一种有限的资源,存储空间也是一种有限的资源。
算法尤其关注性能, 这是门关于性能的学问。

循环不变化

循环不变化主要用来帮助我们理解算法的正确性。对于循环不变式,必须证明他的三个性质:

  • 初始化: 它在循环的第一轮迭代开始之前,应该是正确的。
  • 保持: 如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。
  • 终止:当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。

最坏情况和平均情况分析

一般考察算法的最坏情况运行时间。

渐近分析

淅近分析的基本思路是忽略掉那些依赖于机器的常量, 以及,不去检查实际的运行时间,而是关注运行时间的增长。

当n->∞,有 ( \Theta(n^3) < \Theta(n^2) < \Theta(n) < \Theta(lgn) < \Theta(1))
此处<表示消耗时间少,效率更高。

简化分析方法

从极限角度看,我们只关心算法运行时间如何随着输入规模的无限增长而增长。

渐近确界
( \Theta(g(n)) = {f(n): 存在正常数c_1,c_2和n_0, 使对所有的n \geq n_0, 有0 \leq c_1g(n) \leq f(n) \leq c_2g(n) } )
(\Theta(g(n))是一个集合,可以写成f(n) in \Theta(g(n)), 表示f(n)是\Theta(g(n))的元素,不过,通常写成f(n) = \Theta(g(n)) ) 我们说g(n)是f(n)的一个渐近边界。

渐近上界
( O(g(n)) = {f(n): 存在正常数c和n_0, 使对所有的n \geq n_0, 有0 \leq f(n) \leq cg(n) } )

渐近下界
( \Omega(g(n)) = {f(n): 存在正常数c和n_0, 使对所有的n \geq n_0, 有0 \leq cg(n) \leq f(n) } )

o记号
( o(g(n)) = {f(n): 对任意正常数c, 存在n_0 > 0, 使对所有的n \geq n_0, 有0 \leq f(n) \leq cg(n) } )
从直觉上看,在o表示中当n趋于无穷时,函数f(n)相对于g(n)来说不重要了,即
[\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = 0]

(\omega记号)
( \omega(g(n)) = {f(n): 对任意正常数c, 存在n_0 > 0, 使对所有的n \geq n_0, 有0 \leq cg(n) \leq f(n) } )
从直觉上看,在o表示中当n趋于无穷时,函数f(n)相对于g(n)来说变得任意大了,即
[\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = \infty]

定理

对任意两个函数f(n)和g(n), \(f(n) = \Theta(g(n))当且仅当f(n)=O(g(n)) 和 f(n) = \Omega(g(n))。\)

实际应用中,一般是用渐近上界和渐近下界证明了渐近确界。

等式和不等式中的渐近记号

  • 只出现在等式(不等式)的右边: 表示集合的成员关系。如\(n=O(n^2)\)
  • 一般来说,当出现在某个公式中时, 我们将其解释为一个不在乎其名称的匿名函数。如\(2n^2 + 3n + 1 = 2n^2 + \Theta(n) 即表示2n^2 + 3n + 1 = 2n^2 + f(n), 其中f(n)是某个属于\Theta(n)的函数。\)
  • 有时,出现在等式的左边,例如\(2n^2 + \Theta(n) = \Theta(n^2)\) 这时,我们使用以下规则来解释这种等式:无论等号左边的匿名函数如何选择, 总有办法选取选号右边的匿名函数使等式成立。

递归式的解法

代换法

步骤:

  1. 猜测解的形式。
  2. 用数学归纳法找出使解真正有效的常数。

适用情形:
只能用于解的形式很容易猜的情形。

递归树方法

用代换法不好猜,我们可以用递归树方法获得一个猜想,然后用代换法加以验证。

当用递归式表示分治算法的运行时间时,递归树的方法尤其有用。

主方法

主方法给出求解如下形式的递归式的”食谱”方法:

[ T(n) = aT(n/b) + fn(n)]
其中(a \geq 1 和 b > 1 是常数, f(n)是一个渐近正的函数)。

有三种情况:

  1. \(若对于某常数\varepsilon > 0, 有f(n) = O(n^{log_b{a-\varepsilon}}), 则T(n)=\Theta(n^{log_ba});\)
  2. \(若f(n)=\Theta(n^{log_ba}), 则T(n) = \Theta(n^{log_ba}lgn)\);
  3. \(若对某常数\varepsilon>0, 有f(n)=\Omega(n^{log_b{a+\varepsilon}}), 且对常数c<1与所有足够大的n,\) \(有af(n/b) \leq cf(n), 则T(n)=\Theta(f(n)) \);

需要注意三种情况并没有覆盖所有可能的f(n)。

算法设计

增量方法

插入排序有的就是增量方法。

分治法

分治模式在每一层递归上都有三个步骤:

  • 分解:将原问题分解成一系统子问题。
  • 解决:递归地解决各子问题。若子问题足够小,则直接求解。
  • 合并:将子问题的结果合并成原问题的解。

算法经典问题之第k大/小问题(寻找中位数)

算法经典问题之第k大/小问题(寻找中位数)

问题描述

从n个未排序的数中找出第k小的数。
有直接解法是先排序再拿第k个数即可,但是最好的算法也要(O(n\lg{n}))。
下面的解法更优。

解法

这个其实是利用的分治法思考,和二分查找很像。
和快速排序同样的过程,先随机选一个数,然后把比它小的放到左边,比它大的放到右边。设排完后这个数的索引是m,
对比m和k,
如果m==k,说明这个数就是我们要找的。
如果m<k, 说明前m个数都比要找的数小。从而问题变为从右边的数中找到第k-m小的数。
如果m>k,说明要找的数在前m个数中,从而问题变为从右边的数中找到第k小的数。

按此算法,它的时间效率是O(n)。

python实现

#!/usr/bin/env python
import random


def min_k(data, k):

    def swap(i, j):
        temp = data[i]
        data[i] = data[j]
        data[j] = temp

    n = len(data)
    s = random.randint(0, n-1)
    swap(s, 0)
    j = 1
    key = data[0]
    for i in range(1, n):
        if data[i] < key:
            swap(j, i)
            j += 1
    swap(j-1, 0)
    if j == k:
        return data[j-1]
    elif j > k:
        return min_k(data[0:j-1], k)
    else:
        return min_k(data[j:], k-j)

数据结构之哈稀表

数据结构之哈稀表

前言

哈稀表在工作中常用,语言都内置有,对应于字典或者对象。
首先得定义一些操作。我有一组数据,每个数据x有key=>value这样的结构。
操作1, 插入一对新的x到这个集合中。
操作2,删除这个集合中的x.
操作3,搜索这个集合中key为k的x。

最简单的实现

直接映射表。
要求这些x的key是在有限集合中,并且是不重复的,如U = {0,1,…m-1}
你只需要建立一个数组,key为索引,值为value就可以了。

但他的问题是可能m很大,但要操作的数据很小,这样这个数组就会很稀。

哈稀的引入

所谓的哈稀法,就是用一个哈希函数H来随机映射那些键。

其实就是针对上面直接映射表的。即然key的集合很大,那我就通过一个函数把这个key的集合映射到一个比较小的集合上。
但这会引入另一个问题,从大集合到小集合,一定存在着多个key映射到同一个值的情况。这被称为碰撞。

链表法解决碰撞

解决办法就是在新的小集合上,new-key存放的并不是x,而是一个存放有x的链表。当要查找时,就遍历这个链表,对比key和x.key即可。

但这种实现在最坏情况下访问效率很低。
最坏情况是所有key映射到同样的一个new-key,这时候就只剩下一个链表了,查找效率是(\theta(n))

从这可看出哈希的关键是选取恰当哈希函数H, 使得key能均匀地哈希到new-key。
装载因子>1, 即平均每个槽放的元素>1.

开放寻址法解决碰撞

这种方案不是使用链表,而是在第一次哈希后,如果遇到碰撞则再哈希一次看看,如此形成一个哈希序列,也叫探查序列。
好处是不需要增加额外的数据结构,不需要修改元素。缺点是删除不好处理,如果直接删除,则原来因为碰撞而需要再次探查的数据会误以为元素不在哈希表中。

装载因子(\alpha)<1, 即平均每个槽放的元素<1.预期探查次数是( \frac{1}{1-\alpha} )
探查序列有两种方案。

线性方法

[h(k, i) = (h(k, 0) + i)\ mod\ m]
h(k, i)表示对k的第i次探查。

这种方法简单,但是容易遇到集群现象,即当碰撞时,会在局部集中有值。

二次哈希

这种在实践中比较实用。
[h(k ,i) = (h_1(k) + i * h_2(k))\ mod\ m]
其中(m= 2^r), h_2(k) 为奇数。

哈希函数的选择

除法

h(k) – k mod m (m是新集合的大小)
这里m不能太小,最好是质数。

乘法

m是(2^r), 机器字长为w。
[h(k) = (A*k\ mod\ 2^w)\ rsh\ (w-r)]
A为介于(2^{w-1})到(2^w)之间的某个奇数。 rsh表示右移操作。
因为CPU有指令直接可以得到两个w相乘后的低w位,mod和rsh都是位移操作。所以这个算法相对上面的除法效率要高。

高级主题

哈希的问题

因为哈希是从一个大的集合哈希到一个小的集合,那么对于任意一个哈希函数来说,
都存在一个不好的key集合,都会哈希到同一个槽。

全域哈希

为了解决上面的问题,我们从哈希函数的集合中采取随机的哈希函数,这就叫做全域哈希。这里要求选取随机哈希函数的有限集有一个规律:当从中随机选择两个哈希函数时,他们哈希到同一个槽的概率是1/m。

做法

这里有个前提,选择槽数m为质数。
把key按m进制表示为(<k_0, k_1, …k_r>).
再随机选择一个数a, 也按m进制表示为(<a_0, a_1, a_2…a_r>)
定义(h_a(k) = (\sum_{i=0}^{r}a_iK_i)\ mod \ m)

完全哈希

完全哈希是用来处理静态哈希表。
有两个要求:
1. m = O(n)
2. 在最坏情况下查找的时间效率是O(1)

做法

用二级结构。并且每级结构都用全域哈希。
假设在第一级第i个槽有(n_i)个元素发生碰撞,则二级结构的大小是(n_i^2)

Linux磁盘分区及链接文件的特点-演道网

Linux系统分区

传统的分区fdisk 最大支持2T的硬盘分区

对存储,多分区使用的parted

  • 主分区:最多只能有4个
  • 扩展分区
    • 最多只能有1个
    • 主分区加扩展分区最多有4个
    • 不能写入数据,只能包含逻辑分区
  • 逻辑分区

在Linux中,任何东西都是文件

挂载

  • 必须分区
    • / (根分区)
    • swap分区(交换分区,4G以下,内存两倍,4G以上,内存一样)
  • 推荐分区
    • /boot 启动分区,200MB

fdisk  /dev/sda  ###sdx 都是ISCSI

参数:

  a  toggle a bootable flag
  b  edit bsd disklabel
  c  toggle the dos compatibility flag
  d  delete a partition                              ###删除分区
  l  list known partition types                    ###列分区id信息,82/83
  m  print this menu
  n  add a new partition           ###添加分区
  o  create a new empty DOS partition table
   p  print the partition table                      ###打印分区表
  q  quit without saving changes
  s  create a new empty Sun disklabel
   t  change a partition’s system id     ###修改分区id 82 swap  83默认linux
  u  change display/entry units
  v  verify the partition table
  w  write table to disk and exit      ###保存退出磁盘
  x  extra functionality (experts only)

02、格式化

mkfs.ext4 | xfs |ext3  /dev/sdx 

03、挂载分区

mount  /dev/sdx  /data 

/etc/fstab  ###开机自动挂载

/dev/sdx  /data  ext4  defaults  1 1

mount  -l              ###查看本地挂载信息

mount | column -t ###查看所有挂载信息【多用于排查远程挂载,服务端关闭引起的问题】


ln -s [原文件] [目标文件]
-s
创建软链接

-f 强制建立链接

ln -sf source target

ln    source target    ###硬链接

硬链接特征:
1.
拥有相同的iNode和存储block,可以看做是同一个文件
2.
可通过iNode识别 相同inode
3.
不能跨分区
4.
不能针对目录使用,只能针对文件

软链接特征:
1.
类似windows快捷方式
2.
软链接拥有自己的iNodeblock块,但是数据块中只保存原文件的文件名和iNode,并没有实际的文件数据
3.
lrwxrwxrwx l软链接,文件权限都为全rwx
4.
修改任意文件,另一个都改变
5.
删除原文件,软链接不能使用

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

GitHub 协作冲突原因及解决方法-演道网

GitHub协作冲突出现的原因,是两个人同时修改代码,一个人先提交,后提交的人就会被拒绝rejected

 

 输入 git pull origin master

出现merging

进入文件看到出现冲突信息

 

进行修改,保存

重新提交add commit push 

另一个用户进行pull,冲突解决

 

GitHub 教程系列文章: 

通过GitHub创建个人技术博客图文详解  http://www.linuxidc.com/Linux/2015-02/114121.htm

GitHub 使用教程图文详解  http://www.linuxidc.com/Linux/2014-09/106230.htm 

使用 GitHub / GitLab 的 Webhooks 进行网站自动化部署  http://www.linuxidc.com/Linux/2016-06/131993.htm

多个GitHub帐号的SSH key切换 http://www.linuxidc.com/Linux/2016-05/131080.htm

如何在同一台电脑上使用两个GitHub账户 http://www.linuxidc.com/Linux/2016-05/131079.htm

利用GitHub搭建个人Maven仓库  http://www.linuxidc.com/Linux/2016-04/130197.htm

一分钟认识GitHub http://www.linuxidc.com/Linux/2015-11/125089.htm

分享实用的GitHub 使用教程 http://www.linuxidc.com/Linux/2014-04/100556.htm 

GitHub使用操作指南  http://www.linuxidc.com/Linux/2016-10/135782.htm

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

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

在Ubuntu环境下安装OctoMap-演道网

由于工程实践中需要对机器人地图进行概率化估计并表示,故引入OctoMap库。本文将介绍如何在Ubuntu环境下安装OctoMap。

    1 OctoMap的下载:

    使用git从github下载OctoMap库。

git clone https://github.com/OctoMap/octomap

     如果系统没有安装git则输入以下指令安装git:

sudo apt-get install git

    如果使用git下载OctoMap连接不上,而使用ubuntu自带的浏览器速度又很慢,推荐使用chormium去官网直接下载。 

    输入如下指令安装chormium:

sudo add-apt-repository ppa:a-v-shkop/chromium
sudo apt-get update
sudo apt-get install chromium

    2 编译环境的安装

    由于初期调试的不顺利,尝试了多个版本的ubuntu。推荐使用ubuntu16.04 32bit版本 ,当然选用老版的也都可以,我选择的版本是ubuntu 16.04 32bit 和ubuntu 14.04 32bit。

    OctoMap的编译依赖于以下几个库,输入如下指令对其进行安装。

sudo apt-get install build-essential cmake doxygen libqt4-dev 
libqt4
-opengl-dev libqglviewer-qt4-dev

    若选择Ubuntu 16.04版本则将“libqglviewer-qt4-dev”换成“libqglviewer-dev-qt4”,若为Ubuntu 14.04版本则将“libqglviewer-qt4-dev”换成”libqglviewer-dev” 。

    请对所有编译环境进行安装,尽管在部分库缺失的情况下编译也能够成功,但实际运行时程序将会报错,故老老实实的把所有库都给安装上去吧。

    安装完依赖库之后进入OctoMap的文件夹中,输入如下指令对其进行编译。

cd octomap
mkdir build
cd build
cmake ..
make

3 OctoMap中Octovis的使用 

    编译完成接下来尝试一下OctoMap的图形显示功能,输入:

bin/octovis octomap/share/data/geb079.bt

   可以看到一张基本的地图。如下是使用octovis用不同分辨率显示实验室环境的激光雷达数据。

 

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn

19个Linux备份压缩命令-演道网

<

div id=”content” contentScore=”8103″>

Linux ar命令

Linux ar命令用于建立或修改备存文件,或是从备存文件中抽取文件。

ar可让您集合许多文件,成为单一的备存文件。在备存文件中,所有成员文件皆保有原来的属性与权限。
语法
ar[-dmpqrtx][cfosSuvV][a<成员文件>][b<成员文件>][i<成员文件>][备存文件][成员文件]

Linux bunzip2命令

Linux bunzip2命令是.bz2文件的解压缩程序。

bunzip2可解压缩.bz2格式的压缩文件。bunzip2实际上是bzip2的符号连接,执行bunzip2与bzip2 -d的效果相同。

语法:bunzip2 [-fkLsvV][.bz2压缩文件]

参数

  • -f或–force  解压缩时,若输出的文件与现有文件同名时,预设不会覆盖现有的文件。若要覆盖,请使用此参数。
  • -k或–keep  在解压缩后,预设会删除原来的压缩文件。若要保留压缩文件,请使用此参数。
  • -s或–small  降低程序执行时,内存的使用量。
  • -v或–verbose  解压缩文件时,显示详细的信息。
  • -l,–license,-V或–version  显示版本信息。

实例
解压.bz2文件

bunzip2 -v temp.bz2 //解压文件显示详细处理信息

Linux bzip2命令

Linux bzip2命令是.bz2文件的压缩程序。

bzip2采用新的压缩演算法,压缩效果比传统的LZ77/LZ78压缩演算法来得好。若没有加上任何参数,bzip2压缩完文件后会产生.bz2的压缩文件,并删除原始的文件。
语法
bzip2 [-cdfhkLstvVz][–repetitivebest][–repetitivefast][- 压缩等级][要压缩的文件]

Linux bzip2recover命令

Linux bzip2recover命令用来修复损坏的.bz2文件。

bzip2是以区块的方式来压缩文件,每个区块视为独立的单位。因此,当某一区块损坏时,便可利用bzip2recover,试着将文件中的区块隔开来,以便解压缩正常的区块。通常只适用在压缩文件很大的情况。
语法
bzip2recover [.bz2 压缩文件]

Linux gunzip命令

Linux gunzip命令用于解压文件。

gunzip是个使用广泛的解压缩程序,它用于解开被gzip压缩过的文件,这些压缩文件预设最后的扩展名为”.gz”。事实上gunzip就是gzip的硬连接,因此不论是压缩或解压缩,都可通过gzip指令单独完成。
语法
参数

gunzip [-acfhlLnNqrtvV][-s <压缩字尾字符串>][文件…] gunzip [-acfhlLnNqrtvV][-s <压缩字尾字符串>][目录]

Linux unarj命令

Linux unarj命令用于解压缩.arj文件。

unarj为.arj压缩文件的压缩程序。
语法
unarj [eltx][.arj压缩文件]

Linux compress命令

Linux compress命令是一个相当古老的 unix 档案压缩指令,压缩后的档案会加上一个 .Z 延伸档名以区别未压缩的档案,压缩后的档案可以以 uncompress 解压。若要将数个档案压成一个压缩档,必须先将档案 tar 起来再压缩。由于 gzip 可以产生更理想的压缩比例,一般人多已改用 gzip 为档案压缩工具。
语法
compress [-dfvcV] [-b maxbits] [file …]

Linux cpio命令

Linux cpio命令用于备份文件。

cpio是用来建立,还原备份档的工具程序,它可以加入,解开cpio或tra备份档内的文件。
语法
cpio [-0aABckLovV][-C <输入/输出大小>][-F <备份档>][-H <备份格式>][-O <备份档>][–blocksize=<区块大小>][–forcelocal][–help][–quiet][–version] cpio [-bBcdfikmnrsStuvV][-C <输入/输出大小>][-E<范本文件>][-F <备份档>][-H <备份格式>][-I <备份档>][-M <回传信息>][-R <拥有者><:/.><所属群组>][–blocksize=<区块大小>][–forcelocal][–help][–noabsolutefilenames][–nopreserveowner][–onlyverifycrc][–quiet][–sparse][–version][范本样式…] cpio [-0adkiLmpuvV][-R <拥有者><:/.><所属群组>][–help][–nopreserveowner][–quiet][–sparse][–version][目的目]

Linux dump命令

Linux dump命令用于备份文件系统。

dump为备份工具程序,可将目录或整个文件系统备份至指定的设备,或备份成一个大文件。
语法
dump [-cnu][-0123456789][-b <区块大小>][-B <区块数目>][-d <密度>][-f <设备名称>][-h <层级>][-s <磁带长度>][-T <日期>][目录或文件系统] dump [-wW]

Linux uuencode命令

Linux uuencode命令用于将uuencode编码后的档案还原。

早期在许多 unix 系统的传送协定只能传送七位元字元,并不支援二进位档案,像中文文字档就有用到八位元,所以无法完整地送到另一架机器上。 uuencode 指令,可以将二进位档转换成七位元的档案,传送到另一架机器上再以 uudecode 还原。最常见的是用在以电子邮件传送二进位档。uuencode 编码后的资料都以 begin 开始,以 end 作为结束。
语法
compress[必要参数][选择参数][目录或者文件]

Linux gzexe命令

Linux gzexe命令用于压缩执行文件。

gzexe是用来压缩执行文件的程序。当您去执行被压缩过的执行文件时,该文件会自动解压然后继续执行,和使用一般的执行文件相同。
语法
gzexe [-d][执行文件…]

Linux gzip命令

Linux gzip命令用于压缩文件。

gzip是个使用广泛的压缩程序,文件经它压缩过后,其名称后面会多出”.gz”的扩展名。
语法
gzip [-acdfhlLnNqrtvV][-S &lt;压缩字尾字符串&gt;][-&lt;压缩效率&gt;][–best/fast][文件…] gzip [-acdfhlLnNqrtvV][-S &lt;压缩字尾字符串&gt;][-&lt;压缩效率&gt;][–best/fast][目录]

Linux lha命令

Linux lha命令用于压缩或解压缩文件。

lha是从lharc演变而来的压缩程序,文件经它压缩后,会另外产生具有”.lzh”扩展名的压缩文件。
语法
lha [-acdfglmnpqtuvx][-a <0/1/2>/u0/1/2>][-<a/c/u>d][-<e/x>i][-<a/u>o][-<e/x>w=<目的目录>][-<a/u>z][压缩文件][文件…] lha [-acdfglmnpqtuvx][-a <0/1/2>/u0/1/2>][-<a/c/u>d][-<e/x>i][-<a/u>o][-<e/x>w=<目的目录>][-<a/u>z][压缩文件][目录…]

Linux restore命令

Linux restore命令用来还原由dump操作所备份下来的文件或整个文件系统(一个分区)。

restore 指令所进行的操作和dump指令相反,dump操作可用来备份文件,而restore操作则是写回这些已备份的文件。
语法
restore [-cCvy][-b <区块大小>][-D <文件系统>][-f <备份文件>][-s <文件编号>] restore [-chimvy][-b<区块大小>][-f <备份文件>][-s <文件编号>] restore [-crvy][-b <区块大小>][-f <备份文件>][-s <文件编号>] restore [-cRvy][-b <区块大小>][-D <文件系统>][-f <备份文件>][-s <文件编号>] restore[chtvy][-b <区块大小>][-D <文件系统>][-f <备份文件>][-s <文件编号>][文件…] restore [-chmvxy][-b<区块大小>][-D <文件系统>][-f <备份文件>][-s <文件编号>][文件…]

Linux tar命令

Linux tar命令用于备份文件。

tar是用来建立,还原备份文件的工具程序,它可以加入,解开备份文件内的文件。
语法
tar [-ABcdgGhiklmMoOpPrRsStuUvwWxzZ][-b <区块数目>][-C <目的目录>][-f <备份文件>][-F <Script文件>][-K <文件>][-L <媒体容量>][-N <日期时间>][-T <范本文件>][-V <卷册名称>][-X <范本文件>][-<设备编号><存储密度>][–afterdate=<日期时间>][–atimepreserve][–backuup=<备份方式>][–checkpoint][–concatenate][–confirmation][–delete][–exclude=<范本样式>][–forcelocal][–group=<群组名称>][–help][–ignorefailedread][–newvolumescript=<Script文件>][–newermtime][–norecursion][–null][–numericowner][–owner=<用户名称>][–posix][–erve][–preserveorder][–preservepermissions][–recordsize=<区块数目>][–recursiveunlink][–removefiles][–rshcommand=<执行指令>][–sameowner][–suffix=<备份字尾字符串>][–totals][–usecompressprogram=<执行指令>][–version][–volnofile=<编号文件>][文件或目录…]

Linux uudecode命令

Linuxuudecode 将 uuencode 编码后的档案还原, uudecode 只会将 begin 与 end 标记之间的编码资料还原,程序会跳过标记以外的资料。
语法
uuencode [-hv] [file1 …]p>

Linux unzip命令

Linux unzip命令用于解压缩zip文件

unzip为.zip压缩文件的解压缩程序。
语法
unzip [-cflptuvz][-agCjLMnoqsVX][-P <密码>][.zip文件][文件][-d <目录>][-x <文件>] unzip [-Z]

Linux zip命令

Linux zip命令用于压缩文件。

zip是个使用广泛的压缩程序,文件经它压缩后会另外产生具有”.zip”扩展名的压缩文件。
语法
zip [-AcdDfFghjJKlLmoqrSTuvVwXyz$][-b <工作目录>][-ll][-n <字尾字符串>][-t <日期时间>][-<压缩效率>][压缩文件][文件…][-i <范本样式>][-x <范本样式>]

Linux zipinfo命令

Linux zipinfo命令用于列出压缩文件信息。

执行zipinfo指令可得知zip压缩文件的详细信息。
语法
zipinfo [-12hlmMstTvz][压缩文件][文件…][-x <范本样式>]

<stro

转载自演道,想查看更及时的互联网产品技术热点文章请点击http://go2live.cn