底层数据结构 type hchan struct { qcount uint // total data in the queue dataqsiz uint // size of the circular queue buf unsafe.Pointer // points to an array of dataqsiz elements elemsize uint16 closed uint32 elemtype *_type // element type sendx uint // send index recvx uint // receive index recvq waitq // list of recv waiters sendq waitq // list of send...阅读全文
去年开始写文章的第一篇就是关于 defer，名字比较文艺：《Golang 之轻松化解 defer 的温柔陷阱》，还被吐槽了。因为这篇文章，到《Go 夜读》讲了一期。不过当时纯粹是应用层面的，也还没有跳进 Go 源码这个大坑，文章看着比较清新，也没有大段的源码解析。 自从听了曹大在《Go 夜读》分享的 Go 汇编，以及研读了阿波张的 Go 调度器源码分析的文章后，各种源码、汇编满天飞…… 上次欧神写了一篇《Go GC 20 问》，全文也没有一行源码，整体读下来很畅快。今天这篇也来尝试一下这种写法，不过，我们先从一个小的主题开始：defer 链表是如何被遍历并执行的。 关于 defer 的源码分析文章，网络上也有很多。不过，很少有能完全说明白这个话题的，除了阿波张的。 我们知道，为了在退出函数前...阅读全文
基本概念 定义：零个或者多个数据元素的有限序列，在复杂的线性表中，一个数据元素可以由若干个数据项组成。 直接前驱元素：若线性表记为(a1a2a3...an),则表中a2领先于a3，则称a2是a3的直接前驱元素，且有且仅有一个直接前驱元素 直接后继元素：称a3是a2的直接后继元素，且有且仅有一个直接后继元素 线性表的长度：线性表的元素个数n，为线性表的长度，随着线性表插入和删除操作，该值是变动的，线性表的存储长度一般小于数组的长度 数组的长度：存放线性表的存储空间的长度，存储分配后这个值一般是不变的 空表：长度n为0时，该线性表为空表 地址：存储器的每个存储单元都有自己在内存的编号，简称为地址 线性表的存储 顺序存储结构 线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素...阅读全文
数组是一种线性数据结构。 特点： - 一组连续的内存空间，来存储一组具有相同类型的数据。 时间复杂度： - 查找： O(1) - 插入： O(n) - 删除： O(n) 代码实现： 定义基本的数组结构： type Array struct { data []int length uint } func NewArray(capacity uint) *Array { if capacity == 0 { return nil } return &Array{ data: make([]int, capacity, capacity), length: 0, } } 数组的长度： func (this *Array) Len() uint { return this.length } 是否越界...阅读全文
Golang: 思路：先得出链表长度，然后就可以对k做处理，打个比方，链表长度5，那么k=6与k=1的情况就是一致的，但是我最后代码写的还是很复杂，不做参考吧。 代码如下： func rotateRight(head *ListNode, k int) *ListNode { if k==0||head==nil||head.Next==nil { return head } length,temp:=0,head for temp.Next!=nil{ temp=temp.Next length++ } length++ var res *ListNode last,i:=temp,0 temp=head k=k%length if k==0 { return head }else { l...阅读全文
分区是hive存放数据的一种方式。将列值作为目录来存放数据，就是一个分区。这样查询时使用分区列进行过滤，只需根据列值直接扫描对应目录下的数据，不扫描其他不关心的分区，快速定位，提高查询效率。分动态和静态分区两种： 1.静态分区：若分区的值是确定的，那么称为静态分区。新增分区或者是加载分区数据时，已经指定分区名。 createtableifnotexistsday_part1( uidint, unamestring ) partitionedby(yearint,monthint) rowformatdelimitedfieldsterminatedby'' ; ##加载数据指定分区 loaddatalocalinpath'/root/Desktop/student.txt'intotabl...阅读全文
使用TCMalloc(Thread-Caching Malloc)当内存管理器 以下翻译自tcmalloc.html 动机 相对于glibc2.3 malloc, 在2.8GHz P4上，ptmalloc2需要大概300ns执行一个malloc/free 操作，TCMalloc只需要50ns 多线程时，可减少锁竞争. 小对象基本都是无锁，对于大对象，ptmalloc2也使用每个线程一个arena,但是在不同的arena上分配大对象时内存不会复用而会重新去申请内存 TCMalloc在小对象上也是空间高效的，对N个8字节对象只需要N81.01bytes,而ptmalloc2每个对象使用4字节头,也就是12字节,对齐到8字节的倍数，从而使用了16N个字节 预览 TCMalloc为每个线程分配一个线...阅读全文
声明 下面的分析均基于Golang1.14版本。 以下数据结构均做了裁剪，只留了部分调度密切相关的重要结构。 一、G的定义 裁剪了大部分字段，后面填坑把其它字段的作用及用途整理。 type g struct { stack stack // offset known to runtime/cgo G的栈信息含栈的起始和终止地址 m *m // current m; offset known to arm liblink 运行时绑定的M sched gobuf // 运行时的上下文 goid int64 // g id 唯一的标识id } type stack struct { lo uintptr hi uintptr } type gobuf struct { sp uintptr // ...阅读全文
Golang: 思路：搬运我的题解 这题在第一次做的时候嫌麻烦，直接用数组解决了，时间百分百，空间百分之五，还是有些不满意的，就用双指针重新写了下，然后来到了双百效率 思路在代码里有提及，就不再详述了，简单说一下这里替换的含义 1->4->3->2->5->2, x = 3 发生替换的时候 p1 p2 p3 1->4->3->2->5->2 这里怎么替换，就是： 先从原链表里提取出p3， 然后将p3插到p1及p1后面的元素之间， 更新p1，更新p3 代码如下： func partition(head *ListNode, x int) *ListNode { if head==nil||head.Next==nil { return head } //什么时候需要替换呢？ //当我找到某个元...阅读全文
Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node. Example 1: Input: [1,2,3,4,5] Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judge's serialization of this node is [3,4,5]). Note that we returned a...阅读全文
Golang 的 1.13 版本 与 1.14 版本对 defer 进行了两次优化，使得 defer 的性能开销在大部分场景下都得到大幅降低，其中到底经历了什么原理？ 这是因为这两个版本对 defer 各加入了一项新的机制，使得 defer 语句在编译时，编译器会根据不同版本与情况，对每个 defer 选择不同的机制，以更轻量的方式运行调用。 堆上分配 在 Golang 1.13 之前的版本中，所有 defer 都是在堆上分配，该机制在编译时会进行两个步骤： 在 defer 语句的位置插入 runtime.deferproc，当被执行时，延迟调用会被保存为一个 _defer 记录，并将被延迟调用的入口地址及其参数复制保存，存入 Goroutine 的调用链表中。 在函数返回之前的位置插入 r...阅读全文
Golang 的 1.13 版本 与 1.14 版本对 defer 进行了两次优化，使得 defer 的性能开销在大部分场景下都得到大幅降低，其中到底经历了什么原理？ 这是因为这两个版本对 defer 各加入了一项新的机制，使得 defer 语句在编译时，编译器会根据不同版本与情况，对每个 defer 选择不同的机制，以更轻量的方式运行调用。 堆上分配 在 Golang 1.13 之前的版本中，所有 defer 都是在堆上分配，该机制在编译时会进行两个步骤： 在 defer 语句的位置插入 runtime.deferproc，当被执行时，延迟调用会被保存为一个 _defer 记录，并将被延迟调用的入口地址及其参数复制保存，存入 Goroutine 的调用链表中。 在函数返回之前的位置插入 r...阅读全文
Golang: 思路：组合题，先反转链表，再让它们相加，再反转回来即可。针对题目提到的进阶，可以先将两个链表拷贝下来做大数加法，再赋值回去或者新开一条链表 代码如下： func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { l1 = reverseList(l1) l2 = reverseList(l2) temp:=addTwoLinkedLists(l1,l2) return reverseList(temp) } //两个链表相加，使用的某大佬的代码 func addTwoLinkedLists(l1 *ListNode, l2 *ListNode) *ListNode { var temp = &ListNode{} va...阅读全文
Golang: 思路：既然是链表的插入排序，那就按照题意来，做插入排序 代码如下： func insertionSortList(head *ListNode) *ListNode { if head==nil||head.Next==nil { return head } temp1:=head res:=head temp2:=head.Next temp1.Next=nil for temp2!=nil{ //预留下一个点 tNext:=temp2.Next temp2.Next=nil var p1 *ListNode p2:=res for p2!=nil&&temp2.Val>p2.Val{ p1=p2 p2=p2.Next } temp2.Next=p2 if p1==nil ...阅读全文
Golang: 思路：这题O(1)空间复杂度，其实只需要拆分成两个链表，然后连接下就好了 代码如下： func oddEvenList(head *ListNode) *ListNode { nd1,nd2:=&ListNode{Val:0},&ListNode{Val:0} node1,node2,temp,flag:=nd1,nd2,head,0 for temp!=nil{ if flag%2==0{ node1.Next=temp node1=node1.Next }else{ node2.Next=temp node2=node2.Next } temp=temp.Next flag++ } node2.Next=nil node1.Next=nd2.Next return nd1...阅读全文
Golang 的 1.13 版本 与 1.14 版本对 defer 进行了两次优化，使得 defer 的性能开销在大部分场景下都得到大幅降低，其中到底经历了什么原理？ 这是因为这两个版本对 defer 各加入了一项新的机制，使得 defer 语句在编译时，编译器会根据不同版本与情况，对每个 defer 选择不同的机制，以更轻量的方式运行调用。 堆上分配 在 Golang 1.13 之前的版本中，所有 defer 都是在堆上分配，该机制在编译时会进行两个步骤： 在 defer 语句的位置插入 runtime.deferproc，当被执行时，延迟调用会被保存为一个 _defer 记录，并将被延迟调用的入口地址及其参数复制保存，存入 Goroutine 的调用链表中。 在函数返回之前的位置插入 r...阅读全文
Golang: 思路：这题的难点也在字符串的处理，但大部分的语言都提供类似的函数了，如果我们想提取字符串里的所有单词，使用正则是很好的途径，自己去分割字符串，处理标点符号，反而没什么意思。 代码如下： func mostCommonWord(paragraph string, banned []string) string { reg:=regexp.MustCompile("\\w+") mp1,mp2:=make(map[string]int),make(map[string]int) for _,v:=range banned{ mp1[v]=1 } if reg!=nil { strs:=reg.FindAllString(paragraph,-1) for _,v:=range s...阅读全文
Golang: 思路：链表，这题最简单的思路是，链表存进数组，然后一次性解决。再复杂一点就是，链表从中间分开，后半部分反转，然后再和前半部分依照特定规律合并。这里给简单思路，个人觉得这题没必要追求空间复杂度。 代码如下： func reorderList(head *ListNode) { node:=head if node==nil||node.Next==nil||node.Next.Next==nil{ return } var arr []*ListNode arr=append(arr, head) length:=1 for node.Next!=nil{ length++ node=node.Next arr=append(arr, node) } for i:=0;i
Golang: 思路：这题是分配糖果的进阶篇，分配链表，这题为了实现简单，没那么在乎空间复杂度，因此最终结果空间复杂度效率较低，也算是在预期之内。 代码如下： func splitListToParts(root *ListNode, k int) []*ListNode { node1:=root var nodes []*ListNode for node1!=nil{ nodes=append(nodes,node1) node1=node1.Next } if len(nodes)
