分类目录归档:编程基础

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