Blogs

数据结构与算法

排序

Insertion Sort 插入排序

将元素不断插入已经排序好的 array 中

  • 起始只有一个元素5，其本身是一个有序序列
  • 后续元素插入有序序列中，即不断交换，直到找到第一个比其小的元素
BestAvgWorst
O(n)O(n^2)O(n^2)

缺点

  • 平均和最坏情况的时间复杂度高达 O(n^2)

优点

  • 最好情况时间复杂度为O(n)

总结：插入排序平均和最坏情况时间复杂度都是 O(n^2)

Quick Sort 快速排序

代码优化

高质量编程

编写的代码能够达到正确可靠、简洁清晰的目标可称为高质量代码

  • 各种边界条件是否考虑完备
  • 异常情况处理，稳定性保证
  • 易读易维护

编程原则

简单性

  • 消除“多余的复杂性”，以简单清晰的逻辑编写代码
  • 不理解的代码无法修复改进 可读性
  • 代码是写给人看的，而不是机器
  • 编写可维护代码的第一步是确保代码可读 生产力
  • 团队整体工作效率非常重要

编写规范

注释

公共符号始终要注释

Go语言

基础语法

  • 变量
    • var 变量名 = 值
    • int（数据类型） 变量名 = 值
    • 变量名 := 值
  • 常量
    • const 变量名 = 值
    • const 变量名 数据类型 = 值

判断 IF 

package main  
  
import "fmt"  
  
func main() {  
    if 7%2 == 0 {  
       fmt.Println("7 is even")  
    } else {  
       fmt.Println("7 is odd")  
    }  
  
    if 8%4 == 0 {  
       fmt.Println("8 is divisible by 4")  
    }  
  
    if num := 9; num < 0 {  
       fmt.Println(num, "is negative")  
    } else if num < 10 {  
       fmt.Println(num, "has l digit")  
    } else {  
       fmt.Println(num, "has multiple digits")  
    }  
}

循环 For

在 Go 中没有 while 和 do while，只有 for 循环

RDBMS

ACID

ACID：

  • 原子性( tomicity):事务是一个不可再分割的工作单元,事务中的操作要么都发生，要么都不发生。
  • 一致性( onsistency):数据库事务不能破坏关系数据的完整性以及业务逻辑上的一致性，每个操作都必须是合法的。
  • 隔离性( solation):多个事务并发访问时,事务之间是隔离的,一个事务不应该影响其它事务运行效果，类似于串行操作。
  • 持久性(Curability):在事务完成以后，该事务所对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。

模型

1960s，传统的文件系统已经不能满足人们的需要，数据库管理系统(DBMS)应运而生DBMS:按照某种数据模型来组织、存储和管理数据的仓库。所以通常按照数据模型的特点将传统数据库系统分成网状数据库、层次数据库和关系数据库三类。

网状模型

把每个数据作为一个节点，构成一个网状的结构，每个父节点可以有多个子节点，一个子节点也可以有多个父节点，多对多

层次模型

层次模型是一个树形模型，层次模型和网状模型特别相像，最大的不同是每个父节点可以有多个子节点，但每个子节点只能有一个父节点，一对多

关系模型

数据库

ARID磁盘阵列

Q : 单机存储系统怎么做到高性能/高性价比/高可靠性

A : R(edundant) A(array) I(nexpensive) D(isks)

ARID的使用背景

  • 单块大容量磁盘的价格 > 多块小容量磁盘
  • 单块磁盘的写入性能 < 多块磁盘的并发写入功能
  • 单块磁盘的容错能力有限，不够安全

常见ARID方案

  • RAID 0
    • 多块磁盘简单组合
    • 数据条带化存储，提高磁盘带宽
    • 没有额外的容错设计 例如一条1G的数据1被拆成两条512M数据，分别写道磁盘1和磁盘2上，然后磁盘1和磁盘2的第一个512M共同组成数据1
  • RAID 1
    • 一块磁盘对应着一块额外的磁盘
    • 真实空间利用率仅50%
    • 容错能力强 RAID 1和RAID 0是两个极端，把一条数据copy一份放在两个磁盘上
  • RAID 0 + 1
    • 结合了 RAID 0 和 RAID 1
    • 真实空间利用率只有50%
    • 容错能力强，写入宽带好 例如说，现在有四块磁盘，可以把它两两组成一个 RAID 0，然后再把组成的单元用 RAID 1 组成起来或者组成 RAID 1，然后再用 RAID 0 组成起来，虽然空间利用率还是只有50%，但是还用上了 RAID 1 的条带化写入，并发存储，写入带宽能翻几倍。

数据库

关系 = 集合 = 任意元素组成的若干有序偶对反应了事物间的关系