ARTS 第16周

ARTS 第16周分享

[TOC]

Algorithm

实现链表模拟栈

[参考代码]

package main

import "fmt"

type intNode struct {
    front   *intNode
    roar    *intNode
    element int
}

type myList struct {
    head intNode
}

func NewIntNode(num int) intNode {
    return intNode{element:num}
}

func NewMyList() myList {
    return myList{head:intNode{}}
}

func (ll *myList) add(node intNode) {
    tmp := &ll.head
    for tmp.roar != nil {
        tmp = tmp.roar
    }
    node.front = tmp
    tmp.roar = &node
}

func (ll *myList) list()  {
    tmp := &ll.head

    if tmp.roar == nil {
        fmt.Println("empty list")
        return
    }
    tmp = tmp.roar
    
    for tmp != nil {
        fmt.Printf("%d\t", tmp.element)
        tmp = tmp.roar
    }
}

func (ll *myList) getLast() int {
    tmp := &ll.head

    if tmp.roar == nil {
        fmt.Println("empty list")
        return -1
    }
    for tmp.roar != nil {
        tmp = tmp.roar
    }
    return tmp.element
}

func (ll *myList) delete(num int) bool {
    //preTmp := &ll.head
    //tmp := preTmp.roar
    tmp := ll.head.roar
    if tmp == nil {
        return false
    }
    for tmp != nil {
        if tmp.element == num {
            tmp.front.roar = tmp.roar
            if tmp.roar != nil {
                tmp.roar.front = tmp.front
            }
            return true
        }
        tmp = tmp.roar
    }
    return false
}

func (ll *myList) reDelete(num int) bool {
    tmp := &ll.head

    if tmp.roar == nil {
        return false
    }

    for tmp.roar != nil {
        tmp = tmp.roar
    }

    for tmp != &ll.head {
        if tmp.element == num {
            tmp.front.roar = tmp.roar
            if tmp.roar != nil {
                tmp.roar.front = tmp.front
            }
            return true
        }
        tmp = tmp.front
    }
    return false
}

func (ll *myList) isEmpty() bool {
    return ll.head.roar == nil
}

type ListStack struct {
    stacks myList
}

func NewListStack() ListStack {
    return ListStack{stacks:NewMyList()}
}

func (s *ListStack) isEmpty() bool {
    return s.stacks.isEmpty()
}

func (s *ListStack) push(num int) {
    s.stacks.add(NewIntNode(num))
}

func (s *ListStack) pop() int {
    res := s.stacks.getLast()
    s.stacks.reDelete(res)
    return res
}

func (s *ListStack) list() {
    if s.stacks.isEmpty() {
        fmt.Println("empty list")
        return
    }

    s.stacks.list()
}

func (s *ListStack) peek() int {
    return s.stacks.getLast()
}

Review

Learning to Use Go Reflection： https://medium.com/capital-one-tech/learning-to-use-go-reflection-822a0aed74b7

主要讲解与反射有关的所有操作，以及注意事项

• The difference between the kind and the type can be tricky to understand, but think of it this way. If you define a struct named Foo, the kind is struct and the type is Foo.

• If your variable is a pointer, map, slice, channel, or array, you can find out the contained type by using varType.Elem().

• If your variable is a struct, you can use reflection to get the number of fields in the struct, and get back each field’s structure contained in a reflect.StructField struct. The reflect.StructField gives you the name, order, type, and struct tags on a fields.

• Name() returns the name of the type. Some types, like a slice or a pointer, don’t have names and this method returns an empty string.

• you can also use reflection to read, set, or create values.

  • First you need to use refVal := reflect.ValueOf(var) to create a reflect.Value instance for your variable.
  • If you want to be able to use reflection to modify the value, you have to get a pointer to the variable with refPtrVal := reflect.ValueOf(&var);
  • if you don’t, you can read the value using reflection, but you can’t modify it.

• If you want to modify a value, remember it has to be a pointer, and you have to dereference the pointer first. You use refPtrVal.Elem().Set(newRefVal) to make the change, and the value passed into Set() has to be a reflect.Value too.

• If you want to create a new value, you can do so with the function call newPtrVal := reflect.New(varType), passing in a reflect.Type. This returns a pointer value that you can then modify. using Elem().Set() as described above.

• Finally, you can go back to a normal variable by calling the Interface() method.

• interface底层有两部分：type 和 value，我们统称为pair。

  • type是interface变量的一个指针，指向的值的类型信息
  • value是interface变量的另外一个指针，指向的实际的值

• 接口的值是一个两个字长度的数据结构，

  • 第一个字包含一个指向内部表结构的指针，这个内部表里存储的有实体类型的信息以及相关联的方法集
  • 第二个字包含的是一个指向存储的实体类型值的指针。
  • 所以接口的值结构其实是两个指针，这也可以说明接口其实一个引用类型。

• 官方对Elem()的解释是：Elem returns the value that the interface v contains

• 我们可以通过Elem()来让我们某些不可取址的value变为addressable

• 如果要修改“反射类型对象”，其值必须是“可写的”、“可址的”

• 可以调用Elem方法找到这个指针指向的值

Tips

快速创建.gitignore文件的网站：https://www.gitignore.io/

• 只需输入一个开放所需的环境，语言，就可以立即生成响应的.gitignore文档

git 拉取远程指定分支 到本地：

git checkout -b 本地分支名 origin/远程分支名

share

Java 垃圾回收：https://mp.weixin.qq.com/s/Pj0HHwHG5NJhduYOf6R8xQ

GC解决的问题：能不能写一段程序实现这块功能，每次创建，释放控件的时候复用这段代码，而无需重复的书写呢？

• 引用计数算法（Reachability Counting）是通过在对象头中分配一个空间来保存该对象被引用的次数（Reference Count）。

  • 如果该对象被其它对象引用，则它的引用计数加1，如果删除对该对象的引用，那么它的引用计数就减1，当该对象的引用计数为0时，那么该对象就会被回收。

  • 引用计数算法是将垃圾回收分摊到整个应用程序的运行当中了，而不是在进行垃圾收集时，要挂起整个应用的运行，直到对堆中所有对象的处理都结束。因此，采用引用计数的垃圾收集不属于严格意义上的"Stop-The-World"的垃圾收集机制。

  • 缺点：如果他们相互引用着对方，导致它们的引用计数永远都不会为0，通过引用计数算法，也就永远无法通知GC收集器回收它们。

• 可达性分析算法（Reachability Analysis）的基本思路是，通过一些被称为引用根节点（GC Roots）的对象作为起点，从这些节点开始向下搜索，搜索走过的路径被称为引用链（Reference Chain)，当一个对象到 GC Roots 没有任何引用链相连时（即从 GC Roots 节点到该节点不可达），则证明该对象是不可用的。

  • 通过可达性算法，成功解决了引用计数所无法解决的问题-“循环依赖”，只要你无法与 GC Root 建立直接或间接的连接，系统就会判定你为可回收对象。
  • 那这样就引申出了另一个问题，哪些属于 GC Root。// java方面就不记录了

• 标记清除算法（Mark-Sweep）是最基础的一种垃圾回收算法，它分为2部分，先把内存区域中的这些对象进行标记，哪些属于可回收标记出来，然后把这些垃圾拎出来清理掉。

  • 但它存在一个很大的问题，那就是内存碎片。

• 复制算法（Copying）是在标记清除算法上演化而来，解决标记清除算法的内存碎片问题。

  • 它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用过的内存空间一次清理掉。
  • 缺点是只能利用一半的内存空间。

• 标记整理算法（Mark-Compact）标记过程仍然与标记 --- 清除算法一样，但后续步骤不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，再清理掉端边界以外的内存区域。

  • 标记整理算法一方面在标记-清除算法上做了升级，解决了内存碎片的问题，也规避了复制算法只能利用一半内存区域的弊端。
  • 缺点：它对内存变动更频繁，需要整理所有存活对象的引用地址，在效率上比复制算法要差很多。

• 分代收集算法分代收集算法（Generational Collection）严格来说并不是一种思想或理论，而是融合上述3种基础的算法思想，而产生的针对不同情况所采用不同算法的一套组合拳。

  • 对象存活周期的不同将内存划分为几块。一般是把 Java 堆分为新生代和老年代，这样就可以根据各个年代的特点采用最适当的收集算法。
    • 在新生代中，每次垃圾收集时都发现有大批对象死去，只有少量存活，那就选用复制算法，只需要付出少量存活对象的复制成本就可以完成收集。
    • 而老年代中因为对象存活率高、没有额外空间对它进行分配担保，就必须使用标记-清理或者标记 --- 整理算法来进行回收。

什么是负载均衡 https://mp.weixin.qq.com/s/ykL2yj00ZaxhloOd2In9eA

• 问题：如果这个服务器挂了（这种情况随时都可能发生的)，那么用户的请求就会得不到响应，将无法访问该网站，这就是著名的单点故障问题

• 负载均衡器一般根据两个因素来决定要将请求转发到哪个服务器。

  1. 确保所选择的后端服务器是正常工作的，能给对用户的请求做出响应；
  2. 根据预先设置的负载均衡算法从健康服务器池中进行选择。

• 负载均衡算法决定了后端的哪些健康服务器会被选中

  1. 轮询：为第一个请求选择健康池中的第一个后端服务器，然后按顺序往后依次选择，直到最后一个，然后循环。
  2. 最小连接：优先选择连接数最少，也就是压力最小的后端服务器，在会话较长的情况下可以考虑采取这种方式。
  3. 散列：根据请求源的 IP 的散列（hash）来选择要转发的服务器。这种方式可以一定程度上保证特定用户能连接到相同的服务器。如果你的应用需要处理状态而要求用户能连接到和之前相同的服务器，可以考虑采取这种方式。

• 想要解决负载均衡器的单点故障问题，可以将第二个负载均衡器连接到第一个上，从而形成一个集群。

• 由于 DNS 更改通常会在较长的时间才能生效，因此需要有一种能灵活解决 IP 地址重新映射的方法，比如浮动 IP（floating IP）。这样域名可以保持和相同的 IP 相关联，而 IP 本身则能在服务器之间移动。

kmp算法： https://mp.weixin.qq.com/s/K-xfv-D-Rz0gjVrcyv51cw

• Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。

• KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

  • 可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）

• 按照下面的公式算出向后移动的位数：
  移动位数 = 已匹配的字符数 - 对应的部分匹配值

• 《部分匹配表》是如何产生的。首先，要了解两个概念："前缀"和"后缀"

  • "前缀"指除了最后一个字符以外，一个字符串的全部头部组合
  • "后缀"指除了第一个字符以外，一个字符串的全部尾部组合
  • "部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度
  • "部分匹配"的实质是，有时候，字符串头部和尾部会有重复

• 搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

本周阅读

第三周：1, 2, 4, 5, 6, 7
Golang 大杀器之跟踪剖析 trace: https://mp.weixin.qq.com/s/KV31IhihzcSznna8928iwg // mac 测试该功能乱码，结束测试
go并发GOMAXPROCS 环境变量： https://mp.weixin.qq.com/s/tHRrjvzFN93JGnlCMp3vcg 
Go 运行时会分配一个单核的逻辑处理器去处理所有在程序中创建的协程。
通过设置 GOMAXPROCS 环境变量或者 runtime 方法来添加逻辑处理器
我们能为调度器增加逻辑处理器并不意味着我们需要它。这就是为什么 Go 开发组会设置默认为一个单核逻辑处理器的原因

Java 垃圾回收: https://mp.weixin.qq.com/s/Pj0HHwHG5NJhduYOf6R8xQ
如何成为优秀的领导者: https://mp.weixin.qq.com/s/V_dkRX3hhV7Y_ORrDuKEew

有趣的 “切蛋糕“ 问题: https://mp.weixin.qq.com/s/reTcC_XO2ArDattFqeQ0oA

应用部署: https://www.kancloud.cn/kancloud/web-application-with-golang/44131

什么是 BF 算法: https://mp.weixin.qq.com/s/FH8cMDpzosvLDIdqIK0l3w
什么是负载均衡: https://mp.weixin.qq.com/s/ykL2yj00ZaxhloOd2In9eA
KMP算法: https://mp.weixin.qq.com/s/K-xfv-D-Rz0gjVrcyv51cw
二叉搜索树: https://mp.weixin.qq.com/s/1007EoZcZKBcJTH8kTwGXv2j
Go语言参数传递是传值还是传引用：https://www.flysnow.org/2018/02/24/golang-function-parameters-passed-by-value.html

Learning to Use Go Reflection： https://medium.com/capital-one-tech/learning-to-use-go-reflection-822a0aed74b7