ARTS 第21周

作者: 陈卧虫 | 来源:发表于2019-08-25 14:44 被阅读0次

ARTS 第21周分享

[TOC]

Algorithm

242. Valid Anagram

[easy]

[题目描述]

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Way One:

[解题思路]

将字符串按照每个字符的值的大小排序，
比较两个byte slice 是否相等

[参考代码]

type myBytes []byte

func (my myBytes) Len() int {
    return len(my)
}

func (my myBytes) Less(i int, j int) bool {
    return my[i] < my[j]
}

func (my myBytes) Swap(i int,j int) {
    my[i], my[j] = my[j], my[i]
}

func isAnagram(s, t string) bool {
    //* 将字符串按照每个字符的值的大小排序，比较两个byte slice 是否相等
    // 1. 将连个字符串进行排序

    if len(s) != len(t) {
        return false
    }

    sByte, tByte := make(myBytes, len(s)), make(myBytes, len(s))
    for i:=0;i < len(s) ; i++ {
        sByte[i] = s[i]
        tByte[i] = t[i]
    }

    sort.Sort(sByte)
    sort.Sort(tByte)
    s = string(sByte)
    t = string(tByte)

    // 2. 比较大小
    if s== t {
        return true
    }
    return false
}

Way Two:

[解题思路]

通过一个长度为26的映射表，用来代表26个字母，（我用[]int代替），遍历s和t中的每一个字符，s负责加1，t负责减1
如果最后的表中，每一个字母的个数为零则相等，不为零则不相等

[参考代码]

func isAnagram(s, t string) bool {
    // 通过一个长度为26的hash表，遍历s和t，s负责加，t负责减，
    // 如果最后结果为零则相等，不为零则不相等
    if len(s) != len(t) {
        return false
    }

    res := make([]int, 26)
    for i := 0; i < len(s); i++ {
        res[s[i]-'a']++
        res[t[i]-'a']--
    }

    for i:=0; i<26; i++ {
        if res[i] != 0 {
            return false
        }
    }
    return true
}

Review

Using Go Modules： https://blog.golang.org/using-go-modules

go.mod 只能出现在模块的根目录中
go command 通过使用列于在 go.mod 中特定的依赖，来解决路径依赖问题
当发现某个导入的包在你的任何模块中都没有提供， go command 就会自动为你搜索包含了这个包的模块，并将这个模块的最新版本添加到 go.mod中
只有直接依赖模块才会被记录到 go.mod中(如果直接依赖的模块中依赖了另一个模块，即间接依赖是不会被记录在go.mod中)
由于添加一个直接依赖通常也会添加一个间接的依赖，使用go list -m all就能显示当前的模块以及它的所有依赖
一个语义化版本包含三部分：主版本号.次版本号.修订号( major, minor, and patch)
- 主版本号(major)：当你做了不兼容的 API 修改
- 次版本号(minor)：当你做了向下兼容的功能性新增
- 修订号(补丁，patch)：当你做了向下兼容的问题修正
通常，传递给go get的每一个参数可以是具体的版本，默认类@latest，它可以解析为之前定义的最新版
当导入同一个模块的不同主版本时将会使用不同的模块路径，比如当导入rsc.io/quote的 V3版时，模块路径不再是rsc.io/quote，而是rsc.io/quote/V3。

这种思想被称为语义化版本导入，它给了不兼容的版本（主版本）不同的命名。
go comand 只允许导入任意一个模块路径的一个版本，也就是说每一个主版的中的一个
- 在一项目中：允许导入同一个模块的不同主版本，不允许导入同一个模块的不同副版本或者修订版

Tips

GO MODULE的使用方式

发布版本：Go 1.11
开启方式： GO111MODULE=on
- GO111MODULE=off，go命令行将不会支持module功能，寻找依赖包的方式将会沿用旧版本那种通过vendor目录或者GOPATH模式来查找。
- GO111MODULE=on，go命令行会使用modules，而一点也不会去GOPATH目录下查
- GO111MODULE=auto，默认值，go命令行将会根据当前目录来决定是否启用module功能。这种情况下可以分为两种情形：
  当前目录在GOPATH/src之外且该目录包含go.mod文件
  当前文件在包含go.mod文件的目录下面。
项目启用了 go modules 之后，引用包必须跟 go mod 文件第一行包名一样
当modules 功能启用时，依赖包的存放位置变更为$GOPATH/pkg，允许同一个package多个版本并存，且多个项目可以共享缓存的 module。
初始化Module：在GOPATH 目录之外新建一个目录，并使用go mod init 初始化生成go.mod 文件
go.mod文件一旦创建后，它的内容将会被go toolchain全面掌控。go toolchain会在各类命令执行时，比如go get、go build、go mod等修改和维护go.mod文件。
go.mod 提供了module, require、replace和exclude 四个命令
module 语句指定包的名字（路径）
require 语句指定的依赖项模块
replace 语句可以替换依赖项模块
exclude 语句可以忽略依赖项模块
go module 安装 package 的原則是先拉最新的 release tag，若无tag则拉最新的commit，详见 Modules官方介绍。 go 会自动生成一个 go.sum 文件来记录 dependency tree
- 可以使用命令 go list -m -u all 来检查可以升级的package
- 使用go get -u need-upgrade-package 升级后会将新的依赖版本更新到go.mod
- 也可以使用 go get -u 升级所有依赖
go modules 是一个版本化依赖管理系统，版本需要遵循一些规则，比如版本号需要遵循以下格式：

vX.Y.Z 是我们仓库打的标签版本，也就是 go modules 是根据仓库标签来确定版本号的，因此我们发布版本时，需要给我们的仓库打上一个标签版本号。

Go scheduler: https://mp.weixin.qq.com/s/Brby6D7d1szUIBjcD_8kfg

Go scheduler 的主要功能是针对在处理器上运行的 OS 线程分发可运行的 Goroutine
Go调度器GPM：

G：Goroutine，实际上我们每次调用 go func 就是生成了一个 G。
P：处理器，一般为处理器的核数，可以通过 GOMAXPROCS 进行修改。
M：OS 线程

这三者交互实际来源于 Go 的 M: N 调度模型，也就是 M 必须与 P 进行绑定，然后不断地在 M 上循环寻找可运行的 G 来执行相应的任务
当我们执行 go func() 时，实际上就是创建一个全新的 Goroutine，我们称它为 G。新创建的 G 会被放入 P 的本地队列（Local Queue）或全局队列（Global Queue）中，准备下一步的动作。
唤醒或创建 M 以便执行 G。M不断地进行事件循环寻找在可用状态下的 G 进行执行任务
全局和本地这两类队列，其实在功能上来讲都是用于存放正在等待运行的 G，但是不同点在于，本地队列有数量限制，不允许超过 256 个。并且在新建 G 时，会优先选择 P 的本地队列，如果本地队列满了，则将 P 的本地队列的一半的 G 移动到全局队列，这其实可以理解为调度资源的共享和再平衡。
steal 行为，这是用来做什么的呢，我们都知道当你创建新的 G 或者 G 变成可运行状态时，它会被推送加入到当前 P 的本地队列中。但其实当 P 执行 G 完毕后，它也会 “干活”，它会将其从本地队列中弹出 G，同时会检查当前本地队列是否为空，如果为空会随机的从其他 P 的本地队列中尝试窃取一半可运行的 G 到自己的名下。
自旋线程的这个说法，是因为 Go Scheduler 的设计者在考虑了 “OS 的资源利用率” 以及 “频繁的线程抢占给 OS 带来的负载” 之后，提出了 “Spinning Thread” 的概念。也就是当 “自旋线程” 没有找到可供其调度执行的 Goroutine 时，并不会销毁该线程，而是采取 “自旋” 的操作保存了下来。虽然看起来这是浪费了一些资源，但是考虑一下 syscall 的情景就可以知道，比起 “自旋"，线程间频繁的抢占以及频繁的创建和销毁操作可能带来的危害会更大。

hash冲突

定义：不同的值，hash得到相同的结果，造成冲突

解决方法：

开放定址法

从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。
在开放定址法中解决冲突的方法有：线行探查法、平方探查法、双散列函数探查法。
开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。
再哈希法
这种方法是同时构造多个不同的哈希函数：Hi=RH1（key） i=1，2，…，k。当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
链地址法（hash table）
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

主键和外键

定义：

主键：唯一标识一条记录，不能有重复，不允许为空。
外键：表的外键是另一表的主键，外键是可以有重复的，可以是空值。
索引：该字段没有重复值，但可以有一个空值。

作用：

主键：用来保证数据完整性
外键：用来和其他表建立联系用 (关联修改，主键和外键就是起约束作用)
索引：用来提高查询排序的速度

个数：

主键：主键只能有一个。
外键：一个表可以有多个外键。
索引：一个表可以有多个唯一索引。

外键取值规则：空值或参照的主键值
(1)插入非空值时，如果主键值中没有这个值，则不能插入。
(2)更新时，不能改为主键表中没有的值。
(3)删除主键表记录时，可以在建外键时选定外键记录一起联删除还是拒绝删除。
(4)更新主键记录时，同样有级联更新和拒绝执行的选择。

标记清除算法(Mark And Sweep)

此算法主要有两个主要的步骤：

第一步，找出不可达的对象，然后做上标记。第二步，回收标记好的对象。
需要额外注意：mark and sweep算法在执行的时候，需要程序暂停！即stop the world。也就是说，这段时间程序会卡在哪儿。故中文翻译成卡顿。
还存在一些问题：标记需要扫描整个heap, 清除数据会产生heap碎片, mark-and-sweep 算法会暂停整个程序

本周阅读

第三周：1,  4, 5, 6
websocket: https://mp.weixin.qq.com/s/gasQHCRj5RutsBe0zbSTFg
用 GODEBUG 看调度跟踪: https://mp.weixin.qq.com/s/Brby6D7d1szUIBjcD_8kfg
java打日志: https://mp.weixin.qq.com/s/OO6lhyfEJZApFst3St5TWw
深入理解 Go map：初始化和访问元素： https://mp.weixin.qq.com/s/_ySv1v8kacvPjwqm2Z8B-Q
解决哈希冲突的常用方法分析： https://www.jianshu.com/p/4d3cb99d7580
为什么 MySQL 索引要使用 B+树而不是其它树形结构？比如 B树？https://mp.weixin.qq.com/s/H2EjokOX0HHJtGYS2lbLUA

SQL的主键和外键的作用： https://www.jianshu.com/p/394f8aa724f4

图解Golang的GC算法: https://juejin.im/post/5c8525666fb9a049ea39c3e6

Go Modules详解:  http://objcoding.com/2018/09/13/go-modules/   // Good article
go mod 使用: https://juejin.im/post/5c8e503a6fb9a070d878184a
跳出Go module的泥潭:  https://colobu.com/2018/08/27/learn-go-module/
Using Go Modules: https://blog.golang.org/using-go-modules  // Good Article

ARTS 第21周

ARTS 第21周分享

Algorithm

242. Valid Anagram

[easy]

[题目描述]

Example 1:

[解题思路]

[参考代码]

[解题思路]

[参考代码]

Review

Tips

share

Go scheduler: https://mp.weixin.qq.com/s/Brby6D7d1szUIBjcD_8kfg

hash冲突

主键和外键

标记清除算法(Mark And Sweep)

本周阅读

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读