书旅

书旅 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑

个人微信公众号:IT猿圈

个人动态

书旅 发布了文章 · 9月29日

不一样的面向对象(三)

设计模式六大原则

里式替换原则(LSP)

定义:所有引用基类的地方都必须能透明地使用其子类进行替换(简单说就是:子类可以扩展基类的功能,但是不能改变基类原有的功能)

里式替换原则是继承复用的基石,只有当子类可以替换掉基类,且其它功能不受到影响,基类才算真正的能够被复用,子类可以在基类的基础上增加新的方法

里式替换原则核心就是继承,通过继承,引用基类的地方就可以使用子类的对象了

继承的优点

(1)代码共享,每个子类都拥有父类的方法和属性

(2)提高了代码的重用性

(3)子类可以在父类的基础上扩展自己特有的功能

继承的缺点

(1)继承是侵入性的。只要继承,就必须拥有父类的所有属性和方法

(2)降低代码的灵活性。子类必须拥有父类的属性和方法

(3)增强了耦合性。当父类的常量、变量和方法被修改时,必需要考虑子类的修改

使用里式替换原则注意的点

(1)子类必须实现父类的抽象方法,但不得重写(覆盖)父类的非抽象(已实现)方法

(2)子类中可以增加自己特有的方法

(3)当子类覆盖或实现父类的方法时,方法的前置条件(即方法的形参)要比父类方法的输入参数更宽松

(4)当子类的方法实现父类的抽象方法时,方法的后置条件(即方法的返回值)要比父类更严格

1、子类必须实现父类的抽象方法,但不得重写(覆盖)父类的非抽象(已实现)方法

<?php


abstract class BaseClass
{
    public abstract function abstractAction();
    public function notAbstractAction() {
        echo "我是基类中的非抽象方法".PHP_EOL;
    }
}

class SonClass extends BaseClass {
    public function abstractAction()
    {

        echo "我是子类,我实现了父类的抽象方法";
    }

    public function notAbstractAction()
    {
        echo "我是子类,我重写了基类的非抽象方法";
    }
}

class SonClass2 extends BaseClass {
    public function abstractAction()
    {

        echo "我是子类2,我实现了父类的抽象方法";
    }
    
    public function mySelfAction() {
        echo "我是子类2,这是我特有的方法";
    }
}

//如果将参数由基类替换成子类,该方法输出的结果就会改变
function testFunction(BaseClass $obj) {
    $obj->notAbstractAction();
}

testFunction(new SonClass2());
testFunction(new SonClass());

输出:
我是基类中的非抽象方法
我是子类,我重写了基类的非抽象方

在上边的例子里边,子类SonClass重写了基类中的非抽象发方法notAbstractAction(),如果将参数中的基类替换成SonClass,就会导致打印的结果发生改变。这样就会导致在父类出现的地方,不能由子类完全替换,违背了“里氏替换原则”

2、子类中可以增加自己特有的方法

还是借用上边的那个例子,SonClass2类中实现了自己特有的方法mySelfAction,子类可以拥有自己特有的方法,去实现其他的业务逻辑

依赖倒置原则(DIP)

定义:高层模块不应该依赖低层模块,两者都应该依赖其抽象;抽象不应该依赖细节,细节应该依赖抽象,其核心思想是:要面向接口编程,不要面向实现编程

通俗来说就是:抽象不应该依赖于细节,细节应当依赖于抽象。 换言之,要针对接口编程,而不是针对实现编程

因为细节很容易发生改变,不稳定。而抽象通常是一个规范,不经常改变

依赖倒置原则的实现方法
  • 每个类尽量提供接口或抽象类
  • 变量的声明类型应该尽量是接口或者是抽象类
  • 任何类都不应该从具体类派生
  • 使用继承的时候,要尽量遵循上边提到的里式替换原则

代码示例

<?php

//射手类
class Shooter
{
    //每一个射手都能够进行射击
    public function shot(Baili $obj) {
        $obj->shot();
    }
}

class Baili
{
    public function shot() {
        echo "百里开始射击了".PHP_EOL;
    }
}

class Mengya
{
    public function shot() {
        echo "蒙犽开始射击了".PHP_EOL;
    }
}

$shooter = new Shooter();
$shooter->shot(new Baili());

上边的类,正常的功能实现了,但是,因为射手类的射击(shot)这个功能是基于具体的类百里类(Baili)实现的,这就给以后的扩展带来了麻烦。这个时候有一个新的射手蒙犽,但是根据射手类的射击方法,蒙犽没法进行射击,除非对射手类的射击方法进行修改。按理说,只要是射手属性的英雄,就应该能够进行射击

改进,射手类中的射击方法,不应该依赖具体的某一个射手英雄,而应该是射手的泛指

<?php

//射手类
class Shooter implements BaseShooter
{
    //每一个射手都能够进行射击
    public function shot(BaseShooter $obj) {
        $obj->attack();
    }

    public function accack()
    {

    }
}

interface BaseShooter {
    public function shot(BaseShooter $shooter);
    public function accack();
}

class Baili extends Shooter
{
    public function attack() {
        echo "百里开始射击了".PHP_EOL;
    }
}

class Mengya extends Shooter
{
    public function attack() {
        echo "蒙犽开始射击了".PHP_EOL;
    }
}


$shooter = new Shooter();
$shooter->shot(new Baili());

这样再进行扩展的话,就会相对的容易一些,耦合度没有上边那种方式大

image.png

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 9月25日

不一样的面向对象(二)

设计模式六大原则

单一职责原则(SRP)

定义:一个类应该只有一个引起它变化的原因

假设有一个类N,它负责两个职责,Z1和Z2。假设职责Z1发生了改变,就需要修改N类,而修改了N类就可能会导致本来可以正常运行的Z2不能正常运行了

在系统中,一个类承担的职责越多,那么它被复用的可能性肯定是越小的。承担的职责越多,很容易将这些职责耦合在一起,这时,一旦某个职责发生了变化,就可能会影响到其它职责的正常运行。所以,可以将不同的职责进行分离,封装到不同的类中

单一职责原则可以说是实现高内聚、低耦合的一个指导方针。show me code


<?php

class BaiLi

{

public function flash() //闪现

{

echo "闪现!".PHP_EOL;

}

public function pushVision() //插眼

{

echo "我插了个眼".PHP_EOL;

}

public function sniper() //狙击

{

echo "我狙了一枪".PHP_EOL;

}

public function backToCity() //回城

{

echo "状态不好,回城".PHP_EOL;

}

}

写了一个百里的类,类的设计看上去好像是没什么问题,类中都是这个英雄的各种技能和操作。单一职责原则要求一个类只有一个原因引起它的变化,也就是它应该只负责一件事。而这里,它其实负责了两件事,或者说三件事,闪现、回城这算是公共技能,插眼、狙击算是该英雄特有的技能。如果该英雄要进行改版,需要更改百里的特有技能,那这里的功能技能可能就会受到影响。公共技能实际上不应该因为任何英雄的改版而受影响的,所以应该将这两个职责拆开,拆成两个类,分别进行封装

例子可能不是特别恰当,大概是这么个意思。假设有一个登录的类(Login),它里边有处理表单数据功能(dealForm)、表单数据校验功能(checkForm)、登录功能(login)、获取用户信息功能(getUserInfo)等

这个类其实就没有遵循单一职责原则,用单一职责原则进行重构,应该将处理表单数据(dealForm)、表单数据校验(checkForm)封装到一个表单处理类中(Form),将获取用户信息(getUserInfo)放到一个User类中

开放封闭原则(OCP)

定义:软件中的对象(类、模块、函数等)应该对扩展是开放的,但是,对修改是封闭的

对扩展开放的意思是,我们可以随便增加新功能,而对原有功能不会产生任何修改。也就是说,软件中的对象尽量应该在不修改原有代码的情况下进行扩展

工作中我们其实大部分时间都是在维护代码,或因需求的变更,或因升级。如果我们在原有的代码基础上进行修改,那么就可能对老的代码造成影响。时间一久,我们就不得不对系统进行重构,而且还需要把原有的代码再重新测一遍。那么如果有需求变更或系统升级,我们是通过扩展来实现新的需求,那么就不会对历史的逻辑和代码造成影响

所以我们在设计代码的时候就应该考虑,如何做到对扩展开放、对修改封闭?

通常的方式就是抽象一个接口或者抽象类,定义公共的方法,从而实现方便的扩展。或者我们去继承一个接口或抽象类来达到扩展的目的。总之,核心就是抽象

为了满足开闭原则,需要对系统进行抽象化设计,抽象化是开闭原则的关键。在像Java、C++这种面相对象的编程语言中,通常是给系统定义一个相对稳定的抽象层,将不同的实现行为移到具体的实现层中完成。当需要改动系统行为的时候,不需要对抽象层进行修改,只需要增加新的具体类来实现新的业务功能即可。从而实现在不修改已有代码的基础上扩展系统的功能,达到开闭原则的要求

假设我按照如下的逻辑来实现王者荣耀的射手属性的英雄


<?php

class Shooter

{

public function firstSkill($hero)

{

if ($hero == 'baiLi') {

$obj = new Baili();

$obj->firstSkill();

} elseif ($hero == 'mengYa') {

$obj = new Mengya();

$obj->firstSkill();

}

}

public function SecondSkill($hero)

{

if ($hero == 'baiLi') {

$obj = new Baili();

$obj->SecondSkill();

} elseif ($hero == 'mengYa') {

$obj = new Mengya();

$obj->SecondSkill();

}

}

public function ThirdSkill($hero)

{

...

}

}

class Baili

{

public function firstSkill()

{

echo "百里的一技能";

}

public function SecondSkill($hero)

{

echo "百里的二技能";

}

public function ThirdSkill($hero)

{

echo "百里的三技能";

}

}

class Mengya

{

public function firstSkill()

{

echo "蒙犽的一技能";

}

public function SecondSkill($hero)

{

echo "蒙犽的二技能";

}

public function ThirdSkill($hero)

{

echo "蒙犽的三技能";

}

}

上边这种方式,如果我现在要增加一个英雄,就需要修改Shooter(射手类)类的三个方法,增加新的判断逻辑,这就违反了开放封闭原则

现在将射手类抽象出来


<?php

abstract class Shooter

{

abstract function firstSkill();

abstract function SecondSkill();

abstract function ThirdSkill();

}

class OperateShooter

{

private $shooter;

public function setShooter(Shooter $shooter)

{

$this->shooter = $shooter;

}

public function firstSkill()

{

$this->shooter->firstSkill();

}

}

class Baili extends Shooter

{

public function firstSkill()

{

echo "百里的一技能";

}

public function SecondSkill()

{

echo "百里的二技能";

}

public function ThirdSkill()

{

echo "百里的三技能";

}

}

class Mengya extends Shooter

{

public function firstSkill()

{

echo "蒙犽的一技能";

}

public function SecondSkill()

{

echo "蒙犽的二技能";

}

public function ThirdSkill()

{

echo "蒙犽的三技能";

}

}

$obj = new OperateShooter();

$obj->setShooter(new Baili());

$obj->firstSkill();

输出:

百里的一技能

重构之后,封装了一个抽象类(Shooter),并且OperateShooter针对射手这个抽象类进行了操作,通过setShooter()方法,可以让使用者来设置实例化具体的射手英雄对象,通过OperateShooter的firstSkill()方法来调用传过来的对象的firstSkill()方法。假设此时增加了一个新的射手英雄,只需要将新的射手英雄继承射手抽象类(Shooter),在使用这个新英雄的一技能时,直接向OperateShooter类中注入一个新英雄的对象即可,这样就不用次改现有类的代码

image.png

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 9月24日

不一样的面向对象(一)

面向对象三大特性

封装

把客观的事物封装成抽象的类,类可以通过访问控制将自己的属性给暴露出去或隐藏起来。让自己信任的类或对象使用自己的暴露出去的属性,对自己不信任的类或对象隐藏自己的属性

这样就做的目的其实就是为了使对象本身和对象的使用者分开,使用者只需要知道这个对象能够做什么就行了,不用知道它怎么实现的,这样可以保证类的安全性

举个不是很恰当的例子,假设我这有一个百里守约的类,属性有:血量、枪、攻击范围、等级,方法有:插眼、狙击、向后跳并狙击


<?php

class BaiLi

{

public $blood; //血量

public $gun;//枪

public $attackRange;//攻击范围

public $level;//等级

//设置等级

private function setLevel($level)

{

$this->level = $level;

}

//插眼

public function pushVision()

{

echo "Push a Vision";

}

//狙击

public function sniper()

{

echo "Shot a Shot";

}

//向后跳跃并狙击

public function jumpAndSniper()

{

echo "Jump And Shot";

}

}

当玩家选择了百里守约,就可以看做创建了一个百里守约类的对象。该对象就具备了该类封装的这些成员属性和方法,玩家只能看到和使用它对外提供的一些属性和方法,比如血量、插眼等,但是像设置等级,对玩家是不可见的。同时,玩家只需要知道百里守约有哪些属性和技能,不用关注它是怎么实现的

继承

继承机制可以创建多个层次的类,子类继承父类的属性和方法,使得子类对象也同时具备了父类对象的属性和方法。通常用来对公共属性或方法进行抽离

拿王者荣耀里边的英雄来举例,看图

当我们去封装王者荣耀里边每一个英雄的时候,会发现一些英雄都有公共的属性,比如百里、蒙犽这类英雄都能进行远程攻击,所以将这类英雄公共属性和方法提取出来,封装成一个底层的类,叫射手类。同样像廉颇、盾山这类血量比较厚的英雄,可以封装一个底层的类叫坦克类等

封装射手类、法师类、坦克类的时候,发现它们还会有一些公共的属性,比如都能进行移动、攻击等,同样可以抽出来封装成一个更加底层的类,也就是英雄类

假设王者荣耀新加了英雄叫属驴,是一个射手,首先它会有一些自己特有的属性和技能,然后这个英雄会继承它的父类射手类,此时这个英雄就拥有了远程攻击这些技能,然后射手类又会继承英雄类,那么这个新英雄就具备了移动、攻击这类属性。此时,一个完整的新英雄就被创建出来了(几个亿到手)

多态

多态其实可以简单的理解成“一个对外接口,多种内部实现”。它的专业定义是:同一个操作作用于不同的类的实例,将产生不同的执行结果。即不同类的对象收到相同的消息时,将得到不同的结果。上边的描述还是很抽象,看例子

在实际开发中,我们通常要写出通用的代码,做出通用的编程,以适应需求的不断变化

还是以王者荣耀来举例,假设下边有各种射手的类,它们都有射击的方法


<?php

class BailiShooter //百里守约

{

public function bailiShot()

{

echo "百里射击".PHP_EOL;

}

}

class mengYaShooter //蒙犽

{

public function mengYaShot()

{

echo "蒙犽射击".PHP_EOL;

}

}

function operateShot($obj = null)//处理射击的方法

{

if ($obj instanceof BailiShooter) {

$obj->bailiShot();

} elseif ($obj instanceof mengYaShooter) {

$obj->mengYaShot();

} else {

echo "操作错误";

}

}

operateShot(new BailiShooter());

operateShot(new mengYaShooter());

输出:

百里射击

蒙犽射击

上边定义了两个射手类:蒙犽和百里。然后下边有一个处理射击的方法,判断传入的是哪个射手要射击,然后调用相应的射击方法

可以看出,如果有新的射手进行射击操作的时候,需要首先定义具体射手的类,然后实现一个射击的方法,再在处理射击的方法中增加一个判断。这种扩展性是很差的,如果使用多态就能很好的解决这个问题

首先可以创建一个射手的父类,在父类中定义一个射击的方法,所有是射手属性的英雄都继承这个父类(同时会继承该父类的所有属性和方法),每个子类都可以对父类的射击方法进行各自的实现


<?php

class Shooter //射手

{

public function shot(){

echo "射击方法要在所有子类中进行重载";

}

}

class BailiShooter extends Shooter //百里守约

{

public function shot()

{

echo "百里射击".PHP_EOL;

}

}

class mengYaShooter extends Shooter //蒙犽

{

public function shot()

{

echo "蒙犽射击".PHP_EOL;

}

}

function operateShot($obj = null)//处理射击的方法

{

if ($obj instanceof Shooter) {

$obj->shot();

} else {

echo "操作错误";

}

}

operateShot(new BailiShooter());

operateShot(new mengYaShooter());

输出:

百里射击

蒙犽射击

此时就可以进行轻松的扩展了,只需要继承射手类,并对射击方法进行重载就可以实现自己的射击方法

image.png

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 9月21日

The Way To Go --- 切片

初识切片

基本使用

在go语言中一般不使用数组,大多都是使用切片(slice),看一个切片的示例


arr := [...]int{0,1,2,3,4,5,6,7,8}

s := arr[2:6]

这里定的s就是切片,上边的arr是一个数组,这里s的结果是[2,3,4,5](取arr中3到5这个区间的数据,是左闭右开的)

切片还有很多的用法,如下:


arr := [...]int{0,1,2,3,4,5,6,7,8}

fmt.Println("arr[2:6] = ", arr[2:6])

fmt.Println("arr[:6] = ", arr[:6])

fmt.Println("arr[2:] = ", arr[2:6])

fmt.Println("arr[:] = ", arr[:])

输出结果:


arr[2:6] = [2 3 4 5]

arr[:6] = [0 1 2 3 4 5]

arr[2:] = [2 3 4 5]

arr[:] = [0 1 2 3 4 5 6 7 8]

像这种方括号中([])加个冒号(:)的数据结构,都可以看做是切片(slice)。当然还有很多其它的声明方法

切片是对数组的view

我们知道在go中,数组是一个值类型,而切片是一个引用类型,切片是对数组的视图(view),可能不太好理解,看下边的代码


func updateSlice(s []int) {

s[0] = 520

}

func main() {

arr := [...]int{0,1,2,3,4,5,6,7,8}

s1 := arr[2:]

fmt.Println("s1更新之前")

fmt.Println("s1 = ", s1)

fmt.Println("arr = ", arr)

fmt.Println("更新切片s1")

updateSlice(s1)

fmt.Println("更新之后,s1和arr的值")

fmt.Println(s1)

fmt.Println(arr)

}

输出结果:


s1更新之前

s1 = [2 3 4 5 6 7 8]

arr = [0 1 2 3 4 5 6 7 8]

更新切片s1

更新之后,s1和arr的值

[520 3 4 5 6 7 8]

[0 1 520 3 4 5 6 7 8]

因为s1(切片)是对arr(数组)的视图(view),所以当s1中的值被改变之后,数组中的值也发生了改变(改变的是s1中下标为0的元素,对应的是数组arr中下标为2的元素)

对切片进行切片操作


func learnSlice1() {

arr := [...]int{0,1,2,3,4,5,6,7,8}

s1 := arr[2:6]

s2 := s1[1:]

fmt.Println("s1 = ", s1)

fmt.Println("s2 = ", s2)

}

输出结果:


s1 = [2 3 4 5]

s2 = [3 4 5]

s2是对切片s1又进行了一次切片

深度理解切片

直接看一个示例


func learnSlice2() {

arr := [...]int{0,1,2,3,4,5,6,7,8}

s1 := arr[2:6]

s2 := s1[3:5]

fmt.Println("s1 = ", s1)

fmt.Println("s2 = ", s2)

}

s1的打印结果,我们肯定知道,但是这里的s2打印结果是什么?

我们知道s1 = [2,3,4,5],s2是对s1取下标是3到5这个区间的数据,也就是s1[3]、s1[4]。但是可以看到s1的下标最大是s[3],那这里s1[3:5]会报错吗?

答案是不会报错,可以看一下打印的结果,然后再解释为什么


s1 = [2 3 4 5]

s2 = [5 6] //s1[3]、s1[4]

可以看到s2中的那个6就不在s1里边,如果我们尝试直接打印s1[4]会报错。但是打印s2这个切片,就会正常打印出结果,那到底这个6是如何取出来的?

上边有说切片(slice)是对数组(array)的视图(view),那这个底层是什么样的,如何view的?

上边给出的基础数组arr是[0,1,2,3,4,5,6,7,8],然后s1 := arr[2:6],取到的就是[2,3,4,5],这四个数字映射到s1的下标就是0、1、2、3,s1里边因为是对底层数组arr的view,它的下标不是到3就结束了,它还有4、5的,但是直接通过s1[4]或s1[5]是取不到的,但是s1还是知道它里边有4和5这两个下标的,因为s1是知道底层的数组的

然后,s2 := s1[3:5],取到的就是s1中3,4这两个下标的值。s2的下标就是0、1、2(2其实是看不见的)。从底层数组的角度s1[3]、s1[4]的值就是5和6

切片内部实现

切片中首先有一个ptr指针,它指向slice开始的那个元素。有一个len,标记的是切片的长度,我们使用下标的方式对切片取值的时候,最大只能取到下标为len-1的值,如果大于或等于len,就会报错。然后它里边还有一个值cap,它代表的是整个数组从ptr指向的位置开始到结束的长度

切片它可以向后扩展,但是不可以向后扩展。比如s1:=arr[2:6],s1最前边只能看到2,前边的0、1下标对应的值是看不到的

切片的下标不可以超过len(s),向后扩展不可以超过底层数组cap(s)

看一波示例


func learnSlice2() {

arr := [...]int{0,1,2,3,4,5,6,7,8}

s1 := arr[2:6]

s2 := s1[3:5]

fmt.Printf("s1 = %v, len(s1) = %d, cap(s1) = %d", s1, len(s1), cap(s1))

fmt.Println()

fmt.Printf("s2 = %v, len(s2) = %d, cap(s2) = %d", s2, len(s2), cap(s2))

}

输出结果


s1 = [2 3 4 5], len(s1) = 4, cap(s1) = 7

s2 = [5 6], len(s2) = 2, cap(s2) = 4

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 9月14日

数据结构与算法系列之数组

什么是数组?

忘了在哪本书看见过一句话“理解了概念性的东西,你就学会了70%”

回到主题,什么是数组?数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据

概念中有两个关键的地方:

  1. 数组是一种线性数据结构
  2. 数组中存储的是连续的内存空间和相同类型的数据

什么是线性数据结构

有数据结构基础的小伙伴都应该知道,线性结构就是数据排成一条线一样的数据结构,也就意味着它仅有前后两个方向,比如队列、单链表、栈等,也是线性结构

与它相对的就是非线性表,最典型的就是树和图。他们的特点就是并不是只有前后这种关系

连续的内存空间和相同类型的数据

正因为有了这个特性,使得数组可以进行“随机访问”。虽然访问数组中某个元素变得很快,但缺点就是在修改(删除、插入)数组的时候,操作会变得很麻烦,因为要保证数组内存空间的连续性,所以不得不进行繁琐的数据移动

假设有一个长度为5的int类型的数组var a [5]int,假设给这个数组分配的内存空间首地址是1000,则这个数组分配的内存空间为1000~1019,看下图

操作系统会为每一个内存单眼分配一个地址,通过这个地址来访问内存中的数据。当操作系统需要随机访问数组中的某一个元素时,它会通过下边这个寻址公式来计算出某个元素的存储地址

a[i]_address = base_address + i * data_type_size

data_type_size:表示数组中每个元素的大小。比如int类型,它占用的是4个字节,所以这里data_type_size就是4

数组和链表的区别是什么

通过上边对数组的介绍,可以看出来,数组适合查找操作。但是查找的时间复杂度并不为O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是O(logn)。所以,数组支持随机访问,根据下标随机访问的时间复杂度为O(1)

数组相关操作

插入元素

数组头部插入元素

在数组的头部插入元素,为了保证空间的连续性,需要将数组中所有的元素向后移一位,然后将待插入元素放入到首部位置

代码实现

function insertIntoHead($elem, $arr)
    {
        echo "原始数组:".PHP_EOL;
        print_r($arr);

        $i = 0;
        $len = count($arr);
        while ($i < $len) {
            $arr[$len-$i] = $arr[$len-$i-1];
            $i++;
        }

        $arr[0] = $elem;

        echo "头部插入元素之后结果:".PHP_EOL;
        print_r($arr);
    }

数组中间插入元素

在数组的中间某个位置插入元素,需要将待插入位置以后的元素均向后移动一位

代码实现

function insertIntoMid($elem, $position, $arr)
    {
        echo "原始数组:".PHP_EOL;
        print_r($arr);
        $len = count($arr);

        $i = $position-1;
        $value = $arr[$i];
        $arr[$i] = $elem;
        $head = $i+1;
        $offset = $position-1;

        while ($i < $len) {
            $arr[$len-$i+$offset] = $arr[$len-$i-1+$offset];
            $i++;
        }
        $arr[$head] = $value;

        echo "头部插入元素之后结果:".PHP_EOL;
        print_r($arr);
    }

数组尾部插入元素

在尾部插入元素,不需要移动元素,直接放在当前的末尾元素后边即可

删除元素

数组头部删除元素

删除数组头部元素,将所有的元素向前移动一位即可

代码实现:

function delHead($arr)
{
        echo "删除前:".PHP_EOL;
        print_r($arr);

        for ($i=0; $i<count($arr)-1; $i++) {
            $arr[$i] = $arr[$i+1];
        }
        unset($arr[count($arr)-1]);

        echo "删除后".PHP_EOL;
        print_r($arr);
}

数组中间删除元素

将待删除元素后边的所有元素向前一定一位

代码实现:

function delMid($position, $arr)
{
        echo "删除前:".PHP_EOL;
        print_r($arr);

        $len = count($arr);
        for ($i=$position-1; $i<$len-1; $i++)   {
            $arr[$i] = $arr[$i+1];
        }
        unset($arr[$len-1]);
        
        echo "删除后".PHP_EOL;
        print_r($arr);
}

数组尾部删除元素

直接删除即可,无需移动数组中的元素

如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为(1+2+…n)/n=O(n)。删除元素也是同理

为什么大多数编程语言中,数组要从0开始编号,而不是从1开始呢?

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。前面也说到,如果用a来表示数组的首地址,a[0]就是偏移为0的位置,也就是首地址。a[k]就表示偏移k个 type_size 的位置,所以计算a[k]的内存地址只需要用这个公式

a[k]_address = base_address + k * type_size

但是,如果数组从1开始计数,那我们计算数组元素a[k]的内存地址就会变为

a[k]_address = base_address + (k-1)*type_size

对比两个公式,我们不难发现,从1开始编号,每次随机访问数组元素都多了一次减法运算,对于CPU来说,就是多了一次减法指令

数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从0开始编号,而不是从1开始

参考:
《数据结构与算法之美》
《零基础学数据结构》

查看原文

赞 2 收藏 0 评论 0

书旅 发布了文章 · 9月2日

计算机网络基础(二十二)---传输层-套接字与套接字编程

套接字与套接字编程

套接字

在之前的文章中有说到,通过端口(Port)可以唯一的标识不同的网络进程。如果有一个进程在使用网络的话,那肯定是会占用一个端口的,计算机就是通过这个端口来区分不通的网络进程的

端口(Port)使用16比特位表示(0~65535)。由端口以及IP就可以指定网络中某一台主机的具体进程是哪一个「IP:Port」。关于IP和端口的组合,有一个名字叫:套接字(Socket)

套接字(Socket)是抽象的概念,表示TCP连接的一端(我们知道TCP是端到端(点到点)的通信,两个端点之间会有一个TCP连接来进行通信,这个套接字就可以表示通信的一端)

通过套接字可以进行数据发送或接收。很多时候对网络编程的时候,实际上就是对套接字的编程,通过套接字来进行数据的发送和接收

因为TCP连接是由两端所组成的,因此就可以表示为两个套接字,通过这两个套接字就可以指定唯一的一个TCP连接,而套接字又可以表示为IP和端口的组合(一个IP可以有多个套接字,因为它可能会有不同的端口)

TCP
={Socket1:Socket2}
={{IP:Port}:{IP:Port}}

如果平时对套接字进行编程的话,很多时候都是将这个架构看做是C/S架构。客户端和服务端通过TCP连接连接起来,不管是客户端还是服务端,都会使用一个Socket来进行数据的发送和接收

C/S架构的TCP通信过程(左边为服务端、右边为客户端)

网络套接字与域套接字的区别

网络套接字

对于网络套接字,不管是跨计算机还是在同一台计算机,如果使用网络套接字的话,数据都会经过网络中的协议栈

域套接字

域套接字主要是通过域套接字文件来进行通信的。如果通过域套接字来进行通信的话,数据就不需要经过协议栈。所以,如果是单机的通信,推荐使用域套接字进行通信,因为它处理流程简单,而且不经过协议栈,对系统的消耗比较小。如果是跨机器或跨网络的通信,就必须得使用网络套接字进行通信

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 8月26日

计算机网络基础(二十一)---传输层-TCP连接的四次挥手

文章内容概览

TCP的四次挥手

上一篇文章中分享了TCP的三次握手,本文是相反的过程,是对TCP连接的释放

TCP四次挥手过程

还是假设这里有一个发送方结算机和一个接收方计算机,纵向为时间轴。连接正常的时候,双方是可以一直进行数据传输的。假设数据传输完成了,此时就会进行TCP连接的释放。假设发送方主动的进行了连接的释放

第一次挥手

发送方发送第一次挥手的报文,报文内容:

FIN=1:该标记表示需要释放连接

seq=u:同步自己的序列号给接收方

此时发送方就进入了连接结束的第一个等待状态(FIN-WAIT-1)

第二次挥手

接收方在收到发送方的断开连接请求之后,它也会发送一个报文去确认,确认对方给我发送的序列号我已经收到了,确认报文内容是:

ACK=1:表示这个报文已经确认

seq=v:同步自身的序列号

ack=u+1:确认号是u+1,表示接收方期望接收到接发送方的序列号是u+1的数据

发送方接收到确认报文之后,就进入了连接结束的第二个等待状态(FIN-WAIT-2)。而接收方在发送了第一个确认报文之后就进入了关闭等待状态(CLOSE-WAIT)

这个时候其实接收方还是可以进行数据的发送的,因为释放连接的请求是发送方发起的,表示说发送方的数据发送完成了,但是接收方可能还没有发送完成

第三次挥手

接收方发送完第一个确认报文之后,又会发送一个新的报文,这个报文会携带FIN=1的标记,表示它也可以进行连接释放了,并且里边会携带一个ack,表示重复的对发送方发送的序列号进行确认,该报文中的完整内容:

FIN=1:该标记表示需要释放连接,是一个释放连接的请求

ACK=1:表示确认报文已经收到

seq=w:给发送方同步自己的序列号

ack=u+1:确认号是u+1,表示接收方期望接收到接发送方的序列号是u+1的数据

第四次挥手

发送方接收到接收方的确认报文之后,又会发送一个确认报文,确认接收方发送的报文我已经收到了,此时可以释放掉连接了

在接收方发送断开连接的请求到发送方的确认报文被接收方收到这之间,接收方处于最后确认状态(LAST-ACK)。是为了确认发送方已经接收到了连接释放的报文,此时发送方进入了等待计时器状态(TIME-WAIT)。发送方会在这个时间等待状态中等待一段时间,确保这段时间没有出现任何的问题,此时才进入关闭状态(CLOSE)

以上便是四次挥手的过程

等待计时器

等待计时器,它会等待2MSL(MSL(MAX Segment Lifetime)最长报文段寿命),通常MSL是设置成2min的

我们知道每一个TCP连接都会占用一个端口,在一个连接状态中,如果想启用另外一个网络进程去复用这个端口的话是不行的,因为这个端口已经被占用了。在等待计时器这个状态中,连接是不会释放的,也就是不会释放当前占用的端口。只有在等待计时器状态结束之后才会释放这个端口

其实平时如果在进行TCP编程的时候,会发现,如果你主动的释放了这个连接,然后马上复用这个端口,其实是不行的。主要是因为主动释放的这一方进入了等待计时器状态,在这个状态中,是不会释放占用的端口的,需要等计时器结束

为什么需要等待计时器?为什么是2MSL?

只要发送方发送了第四次挥手的报文之后,就进入可等待状态,在进入等待的时候,最后一个报文是没有进行确认的。这个等待计时器主要是为了确保发送方的ACK可以到达接收方

2MSL是报文可以在网络中存活的最长的时间,如果在2MSL的时间里,第四次挥手的报文没有被接收方接收到的话,接收方就会认为,我发送的第二次报文(也就是第三次挥手的报文)没有被发送方接收到,因此接收方会把第三次挥手的报文再发送一次,也就是重复一次第三次挥手。因此发送方会重新的构造一个报文,再次进行第四次挥手,这就是等待计时器的作用,它主要是为了确保第四次挥手的报文可以正确的到达对方,如果没到达,接收方就会重新发送一次第三次挥手的报文

等待计时器其实还有一个作用就是:确保当前连接的所有报文都已经过期了(因为最后一个确认断开的报文都已经过期了,其它的报文肯定也已经过期了)

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 8月20日

计算机网络基础(二十)---传输层-TCP连接的三次握手

文章内容概览

TCP的三次握手

TCP标记

TCP标记是TCP首部的其中一个字段。TCP标记占6个比特位,每位都有不同的含义

对于三次握手,主要关注下边三个标记

TCP三次握手过程

假设有一个发送方计算机和一个接收方计算机,纵向为时间轴

第一次握手

假设首先是发送方主动和接收方建立连接,所以,发送方会第一次发送一个报文(此时SYN=1,表示这是一个连接请求的报文,seq=x是同步发送方自己的序列号)

第二次握手

接收方在接收到连接请求后,也就打开TCP连接,同时它也会发送一个报文,这个报文是第二次握手。报文信息中有:

  • SYN=1:表示是一个连接请求
  • ACK=1:表示对序列号的确认
  • ack=x+1:小写的ack表示的是确认号。这里的ack=x+1,表示接受方期望收到的是x+1这个序列号的值
  • seq=y:同时接收方发送的报文中也会携带自己的序列号,也就是seq=y
第三次握手

发送方接收到报文之后,会进行回应,回应中的报文内容:

  • ACK=1:表示这个报文的确认号是有效的
  • seq=x+1:发送方所携带的序列号,表示的是,当前发送方发送的数据序列号是x+1
  • ack=y+1:确认号是y+1,表示发送方期望接收到接收方的序列号是y+1的数据

通过这三次的握手,TCP的连接就建立起来了

三次握手中关键的信息

  • 第一次和第二次握手都有SYN标记,表示这是一个连接的请求
  • 第二次和第三次握手都有ack标记,对于ack这个标记,它其实是先对连接双方的序列号进行同步。比如说,通过两次的ack同步,发送方已经知道了接收方的ack是什么了,同时,接收方也知道了发送方的ack是什么了,通过三次握手,它们不仅仅将连接建立起来,并且也同步了各自的序号

在三次握手的时间轴中,不同的时间,接收方和发送方有不同的状态

  • 在接收方没有接收到数据之前,它一直处于监听状态(Listen)
  • 发送方在第一个报文发送出去,到接收到第一个报文的响应之间,属于同步已发送状态(SYNC-SENT),表示已经将SYN发送出去了,并且等待对方的SYN信息
  • 从接收方发送第一个报文,到接收到第二个报文之间,属于同步已接收状态(SYNC-RCVD),表示发送方发送给我的SYN信息,我已经收到了
  • 然后发送方就进入建立连接(ESTABLISHED)的状态了
  • 对发送方来说,只要第二次握手成功之后,发送方就建立起连接了。但是对接收方来说,只有接收到发送方的第三次握手之后,才是建立连接的状态(ESTABLISHED)

双方对于建立连接状态的时间是不一样的,发送方只要在第二次握手成功之后,就变成了建立连接的状态。但是对接收方来说,只有接收到发送方的第三次握手之后,才是建立连接的状态。双方都进入建立连接的状态之后就可以进行数据的传输了

为什么发送方要发出第三个确认报文呢?为什么两次不行?

结论:避免已经失效的连接请求报文传送到对方,引起错误

假设此时有一个发送方计算机和一个接收方计算机。首先发送方需要发送一个建立连接的请求报文(第一次握手),假设第一次握手的报文在网络中传输很久才到达接收方,因为发送了很久,所以,发送方很久都没有收到接收方的确认消息。发送方就会认为第一个报文已经超时了,所以,发送方就会第二次发送同样的报文

假设第二次发送的报文,很快就到达了对方,接收方在收到第二次的连接请求报文之后,就会进行回应,并且建立起它们之间的连接。那么,对于发送方发送的第一次的请求报文,就应该是一个失效的请求报文,因为它的功能已经被第二次的连接请求所完成了。所以,对于第一次发送的请求连接报文,在网络中游荡了很久,其实就是一个失效的请求报文了,没有作用了

如果发送方发送的两次连接请求都建立起连接了会怎么样?

首先考虑第二次请求的报文,这个报文是提前到达接收方的,接收方会对它进行一个回应,回应确认之后,就建立起连接了(因为我们是假设两次握手就建立起连接

现在考虑第一次发送的连接请求,如果两次握手就建立连接的话,对于失效的请求,它也会建立起连接,因为只要接收方回应了,就表示连接已经建立了

这样就会导致,同样的请求发送了两次,就会建立两个TCP连接的情况。这种情况是错误的,所以说,两次握手是不正确的

三次握手是如何解决两次握手导致的问题?

对于两次握手,只要接收方回应了,就表示连接建立了。而对于三次握手来说,第一个确认报文会首先到达发送方,然后发送方再发送一个确认报文(第三次握手),此时才算建立起连接

现在来考虑那个比较慢到达接收方的连接请求报文,这个报文,接收方也会发送一个确认报文给发送方(第二次握手)。但是发送方已经进行第三次握手了,因此发送方对于第二次的确认消息会忽略掉,并不会进行任何的操作。这样,第一次比较慢到达的连接请求就不会建立起连接,这就避免了两次握手所导致的错误

上边就是三次握手的作用,它避免了失效的请求到达对方,并且引发不应该有的错误

查看原文

赞 0 收藏 0 评论 0

书旅 发布了文章 · 8月18日

计算机网络基础(十九)---传输层-TCP的拥塞控制

文章内容概览

TCP的拥塞控制

当网络中的数据报文过多的时候,就会造成网络的拥塞

网络拥塞的根源

  • 一条数据链路经过非常多的设备
  • 数据链路的各个部分都可能成为网络传输的瓶颈(网络中各种路由器的性能可能不一样、或者传输媒介性能有差别)
  • 网络对一些硬件设备的性能要求,大于可用资源,因此就导致了拥塞

TCP的拥塞控制和TCP的流量控制有什么区别?

  • 流量控制考虑点对点的通信量控制(主要是通过窗口来控制通信量,考虑接收方的接收性能)
  • 拥塞控制考虑整个网络,是全局性的考虑(它会感知到整个网络是否发生拥塞)

拥塞控制是一个很庞大的问题,因为它考虑到了整个网络,并且对于拥塞控制,很难有最优解。这里只对拥塞控制有一个简单的认识

如果要进行拥塞控制,首先需要有一个方法去判断网络是否发生拥塞。判断的方法简单粗暴,如果发送方发送的报文发生了超时,就认为网络发生了拥塞。但是,通过报文超时来判断网络是否一定拥塞是不成立的

如果在传输的某一个阶段,把光纤给断了,这个也会导致报文超时,这时就不是因为拥塞所造成的了,而是网络故障所造成的。所以,报文超时只是判断网络拥塞的一个方法(下边的内容先不考虑网络故障的情况)

拥塞控制的两个算法

慢启动算法
  • 由小到大逐渐增加发送的数据量
  • 每收到一个确认报文就加一(假如第一次收到了1个确认报文,下一次就发送2个报文;如果第二次收到2个确认报文,下一次就发送4个报文,依次1、2、4、8)

可以看到发送的报文是按指数增长的,指数增长的增长速率是非常快的。慢启动算法,它的指数增长会有一个阈值,称为慢启动阈值(ssthresh),增长到这个慢启动阈值之后就不再增长了。增长到这个阈值之后,它就会进行第二个算法

拥塞避免算法
  • 维护一个拥塞窗口的变量(这个变量大于慢启动阈值)
  • 只要网络不拥塞(即只要报文不超时),就试探着增大拥塞窗口(每次加一)

假设慢启动到达了阈值(假设是16),此时就会启动拥塞避免算法,它会试探着将拥塞窗口调大,如果16个报文都收到了确认,它就会再发送17个报文,如果没有发生超时,下一次就会发送18个报文。一直这样一个一个的调大,直到发生拥塞。这就是拥塞避免算法

拥塞避免算法可以保证在网络不发生拥塞的情况下,更多的发送数据

这是一张慢启动算法和拥塞避免算法的图(纵坐标:每一次发送数据报文的数量;横坐标:发送的轮次)

在到达阈值之前,数据报文的数量是指数增长的。当数据报文的数量达到阈值的时候就会启动拥塞避免算法,之后数据报文的数量就是线性增长的

查看原文

赞 1 收藏 1 评论 0

书旅 发布了文章 · 8月13日

计算机网络基础(十八)---传输层-TCP的流量控制

文章内容概览

TCP协议的流量控制

流量控制是TCP协议特有的功能,对于UDP或者其它的一些协议,是没有流量控制

流量控制,简单的来说就是,接收方希望发送方将数据发送的慢一些。一般来说,我们是希望越快越好,但是,还是需要考虑一些实际的情况。比如接收方不能那么快的去接收很大的流量,所以希望发送方的流量慢一些。这就是流量控制

  • 流量控制指让发送方发送速率不要太快
  • 流量控制是使用滑动窗口来实现的

在TCP首部中有窗口这个字段,它占16个比特位,用来指明允许对方发送的数据量。在可靠传输的基本原理这篇文章中有结合确认号和窗口进行了一个运算。比如说,假设确认号是501,窗口大小是1000,就表示说,发送方可以发送501~1500这个范围的1000个字节的数据,这个就是窗口所起到的作用。那滑动窗口是怎么做到流量控制的?

假设现在有一个发送方计算机和一个接收方计算机,从上往下是它们之间交互的时间轴

  • 假设发送方发送了一个序列号为1的数据,发送数据的大小是100个字节
  • 发送方还可以进行第二次发送,此时发送的数据的序列号就应该是101,也假设发送数据的大小是100字节
  • 此时接收方已经接收到了200个字节的数据,假设此时接收方发送了一个确认消息,确认号是201,201表示的就是期待接收到的下一个字节的序号,并且发送的确认消息中还有一个窗口的大小,假设是300,表示告知发送方还可以发送300个字节的数据。确认消息中的ACK标记为1
  • 发送方在知道了窗口大小为300之后,它就可以继续发送300个字节的数据。首先它可能就会发送序列号为201的100个字节的数据,此时发送方还能再发200个字节的数据
  • 假设此时发送方发送了序列号为301的200个字节的数据,此时接收方就可以进行确认了,确认说,它已经接收到了601序列号之前的所有数据了,此时窗口大小为0,也就是说发送方不能再进行数据发送了

以上就是通过窗口大小控制对方发送速率

假如接收方发送了窗口为0的消息之后,它马上对接收到的数据进行处理,处理之后交给应用层,一段时间之后,接收方就又可以接收信息的消息了。此时,接收方就会向发送方发送一个消息,告诉它说,当前我的窗口是1000,也就是可以接收1000个字节的数据。发送方在收到这个消息之后,发送方又会进行数据的封装,并且将数据发送给接收方。这个就是接收方通过调整窗口的大小来告知发送方可以继续的发送数据

考虑一个特殊情况

假设接收方在通知发送方,它的窗口为1000的消息在传输过程中丢失了。这种情况会导致什么样的后果?

对于发送方:发送方会一直等待,因为它还是以为接收方的窗口为0,所以它一直等待接收方的窗口调大

对于接收方:接收方已经将窗口调大的消息告诉发送方了,理论上,发送方在收到消息之后,会将信息的消息发送给接收方。因此,接收方也会一直等待

所以,因为窗口数据报文的丢失,导致发送方和接收方都会一直的在等待,形成死锁的局面。此时可能就会有疑问,TCP不是可靠传输的吗?这个消息为什么会丢失呢?

其实在讨论TCP的可靠传输时,主要是从数据的角度去考虑的。也就是说,对于TCP的可靠传输,都是对数据的确认。比如序列号、以及确认号都是对数据的字节进行确认的,对于特殊的消息,比如窗口的大小,其实是没有超时重传机制的。因此就会出现上边提到的死锁局面

坚持定时器

要处理上边出现的死锁情况,就需要TCP中的第二个定时器,坚持定时器

  • 当发送方接收到窗口为0的消息,则启动坚持定时器
  • 坚持定时器每隔一段时间发送一个窗口探测报文(用来询问窗口有没有增大,这样就可以解决因发送窗口大小的消息丢失导致的死锁局面)

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 10 次点赞
  • 获得 5 枚徽章 获得 0 枚金徽章, 获得 1 枚银徽章, 获得 4 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 3月10日
个人主页被 1k 人浏览