list是一个双向链表。该结构具有链表的所有功能。 type Element type Element struct { Value interface{} //在元素中存储的值 } func (e *Element) Next() *Element //返回该元素的下一个元素，如果没有下一个元素则返回nil func (e *Element) Prev() *Element//返回该元素的前一个元素，如果没有前一个元素则返回nil。 type List func New() *List //返回一个初始化的list func (l *List) Back() *Element //获取list l的最后一个元素 func (l *List) Front() *Element //获取lis...阅读全文
slice可以动态添加项（使用append()函数），但是没有删除项的函数。变通方法，可以使用slice重新组合的方式删除一个或多个项，slice是引用类型，存的是指针，性能上不会有太多影响，示例如下：package mainimport "fmt"func main() { s := []int{11, 22, 33, 44, 55, 66} // 原始slice i := 2 // 待删除项索引 s = append(s[:i], s[i+1:]...) // 最后面的“...”不能省略 fmt.Println(s) // 数据结果 [11 22 44 55 66]} 有人回答的很好： 这样是可以实现。不过从slice这种数据结构来看，本身并不适合做删除操作。抛开语言，只谈数据结构，我们...阅读全文
在 python 中实现队列或者栈非常简单，用list就可以用来做一个简单的栈和队列，如下 # 队列操作 queue = [] # 入队 由于有append 我们从列表尾入队 列表头出队 queue.append(1) queue.append(2) queue.append(3) # 现在队列的情况是[1,2,3]，可以用list的pop方法出队 queue.pop(0) # 栈的操作跟队列类似 stack = [] # 入栈 stack.append(1) # 出栈和队列的区别在于 都是在列表尾部操作 stack.pop() 那么，在 golang 中我们要怎么实现这种简单的队列和栈呢。这个基本和 python 很类似。 // 初始化 var queue []int var stack ...阅读全文
一.单链表基本概念单链表是一种顺序存储的结构。 有一个头结点，没有值域，只有连域，专门存放第一个结点的地址。 有一个尾结点，有值域，也有链域，链域值始终为NULL。 所以，在单链表中为找第i个结点或数据元素，必须先找到第i - 1 结点或数据元素，而且必须知道头结点，否者整个链表无法访问。关于链表的概念，此处不细讲了，具体的内容，大家可以自行查找相关数据结构资料.本文主要通过Golang实现链表的几种常见操作:判断是否为空的单链表单链表的长度从头部添加元素从尾部添加元素在指定位置添加元素删除指定元素删除指定位置的元素查看是否包含某个元素遍历所有元素二.实现代码以及代码注释1. 定义结构体package linkedList import "fmt" type Object interface...阅读全文
作者：达达 来源：http://1234n.com/?post/yzsrwa 最近一段时间对《仙侠道》的服务端进行了一系列针对GC的调优，这里跟各位分享一下调优的经验。 游戏第一次上线的时候，大部分精力都投入在做cpuprof和memprof找性能瓶颈和内存泄漏上，没有关注过Go的GC运行情况。 有一次cpuprof里的scanblock调用所占的比例让我注意到Go的GC所带来的性能消耗，记得那份cpuprof里，scanblock调用占到49%。也就是说有一半的CPU时间浪费在了GC上。 于是我开始研究如何进行优化，过程中免不了要分析数据，经过一番搜索，我好到了GOGCTRACE这个环境变量。 用法类似这样： GOGCTRACE=1 ./my_go_program 2> log_file ...阅读全文
一、什么是队列数据结构里的队列就是模仿现实中的排队。如上图中狗狗排队上厕所，新来的狗狗排到队伍最后，最前面的狗狗撒完尿走开，后面的跟上。可以看出队列有两个特点：（1） 新来的都排在队尾；（2） 最前面的办理业务后离队，后面一个跟上。根据特点，计算机砖家就归纳以下队列结构。队列简称FIFO，含义自己体会。二、队列的结构继续大卫哥的拆卸手。队列拆成容器和链表，分别用结构和单链表实现，如上图。三、接口说明及实现1、Init初始化队列，其实是初始化里面单链表。func (queue *Queue) Init() {lst := new(List)(*queue).list = lstlst.Init()}2、Enqueue有尿的小狗狗排队。func (queue *Queue) Enqueu...阅读全文
最近公司项目，换到了golang 下面来开发，遇到了redis存储链表的问题,困扰了我好几天，后面静下心来，好好读了一下源码，发现官方的例子,最终还是羊毛出在羊身上 c, err := dial() if err != nil { panic(err) } defer c.Close() var p1, p2 struct { Title string `redis:"title"` Author string `redis:"author"` Body string `redis:"body"` } p1.Title = "Example" p1.Author = "Gary" p1.Body = "Hello" if _, err := c.Do("HMSET", redis.Args{...阅读全文
// Go 语言切片是对数组的抽象。切片的单词来源于可以对其他数组和切片进行片段截取 // Go 数组的长度不可改变，在特定场景中这样的集合就不太适用， // Go中提供了一种灵活，功能强悍的内置类型切片("动态数组"), // 与数组相比切片的长度是不固定的，可以追加元素， // 在追加时可能使切片的容量增大。 package main import "fmt" func main() { // 切片的长度和容量 var numbers = make([]int, 3, 5) //用make创建切片 printSlice(numbers) // 空（nil）切片 // 切片在未初始化时默认是nil，长度是0，容量也是0 var numbers1 []int printSlice(numbe...阅读全文
golang的map实现并不是像c++一样使用红黑树，而是使用了hashmap，用数组来实现。 详细的实现后续补充，这里先做个备忘。 在iterate整个map的时候，使用delete是安全的。这跟c++是不一样的，c++在delete的时候，会导致整棵树发生变化，所以不能在迭代的时候删除元素。 那为什么golang的map是安全的呢，从源码来看，golang的map使用了桶的概念，元素是被hash到桶存储，每个桶预设是存储八个kv,而且在头部有一个uint8 tophash[8]的结构，存储每个key的高八位（即hash(key) » (64 - 8)），如果该位置未被放置元素，则有一个特殊的标志Empty。在插入删除的时候，首先会比较该uint8跟hash(key)是否相等。当然，桶还利...阅读全文
一、Go语言中的range Go 语言中 range 关键字用于 for循环中迭代数组(array)、切片(slice)、链表(channel)或集合(map)的元素； 在数组和切片中它返回元素的索引值， 在集合中返回 key-value 对的 key 值。 二、代码举例 package main import "fmt" func main() { //这是我们使用range去求一个slice的和。使用数组跟这个很类似 nums := []int{2, 3, 4} sum := 0 for _, num := range nums { sum += num } fmt.Println("sum:", sum) //在数组上使用range将传入index和值两个变量。上面那个例子我们不需要使...阅读全文
数据结构和算法是计算机科学的重要组成部分。虽然有时候它们看起来很吓人，但大多数算法都有简单的解释。同样，当问题能用算法来解释清楚的时候，算法的学习和应用也会很有趣。 这篇文章的目标读者是那些对链表感到不舒服的人，或者那些想要看到并学习如何用 Golang 构建一个链表的人。我们将看到如何通过一个（稍微）实际的例子来实现它们，而不是简单的理论和代码示例。 在此之前，让我们来谈谈一些理论。 ## 链表 链表是比较简单的数据结构之一。维基百科关于链接列表的文章指出： > 在计算机科学中，链表是数据元素的线性集合，其中线性顺序不是由它们在内存中的物理位置所给出的。相反，每个元素指向下一个元素。它是由一组节点组成的数据结构，它们共同代表一个序列。在最简单的形式下，每个节点都由数据和一个指向下个节点的引...阅读全文
生成器 在Python中我们可以使用yield关键字来让一个函数成为生成器，在Go中我们可以使用信道来制造生成器(一种lazy load类似的东西)。 当然我们的信道并不是简单的做阻塞主线的功能来使用的哦。 下面是一个制作自增整数生成器的例子，直到主线向信道索要数据，我们才添加数据到信道： func xrange() chan int{ // xrange用来生成自增的整数 var ch chan int = make(chan int) go func() { // 开出一个goroutine for i := 0; ; i++ { ch <- i // 直到信道索要数据，才把i添加进信道 } }() return ch } func main() { generator := xrang...阅读全文
说明 上一篇说的是线性表中的顺序存储结构，他的读取复杂度虽然是o(1)，但是它的缺点也很明显，插入和删除需要移动很多元素，而且需要分配一块连续的内存区域 线性表之单链表 单链表在一定程度上解决了一部分上面的问题，而且也不要一大块连续的内存区域，代码如下 package main //线性表中的链式存储结构 //第一个节点为头节点，并不真实保存数据，头节点基本代表了整个链表 import ( "fmt" ) type Elem int type LinkNode struct { Data Elem Next *LinkNode } //生成头节点 func New() *LinkNode { //下面的data可以用来表示链表的长度 return &LinkNode{0, nil} } //...阅读全文
Go tip 是 Go 语言的实验分支，包含了很多尚在讨论，但很有可能会加入 stable 分支的特性。“Go tip 在做什么”（原文地址：What's happening in Go tip）分析总结了 Go 语言尚在开发中的一些重要特性。 本文译自：What's happening in Go tip (2014-01-10) 现在是 2014 年了，刚刚经历了圣诞和新年前夜，Go 团队就已经开始为下一个发布版本而工作了。也因此，“Go tip 在做什么”系列也重开了。 作为这个系列的最新一篇，这篇文章将会有些小调整。最重要的调整是，不会再遵循每周一篇文章的发布周期。一周里可能有几篇文章，也可能一篇都没有。这个调整，一部分由于个人原因，一部分也因为这样可以更灵活的追踪 Go 的改变。这...阅读全文
今天，Mayuyu来介绍Go语言中一个重要的东西，叫做container。具体源码可以参考Go语言的源代码，如下 路径：/usr/local/go/src/pkg/container Github上的路径为：https://github.com/astaxie/gopkg/tree/master/container container的结构如下 可以看出包含三部分：heap，list和ring。下面分别介绍 1. heap heap即为堆，是一种常用的数据结构，在源码里面，提供了接口，在实际使用时需要实现。 下面是一个关于heap使用的实例。 代码： package main import ( "fmt" "container/heap" ) //heap提供了接口，需要自己实现如下方法 t...阅读全文
Go语言——内存管理 参考： 图解 TCMalloc Golang 内存管理 Go 内存管理 问题 内存碎片：避免内存碎片，提高内存利用率。 多线程：稳定性，效率问题。 内存分配 内存划分 arena即为所谓的堆区，应用中需要的内存从这里分配, 大小为512G，为了方便管理把arena区域划分成一个个的page，每个page为8KB,一共有512GB/8KB个页 spans区域存放span的指针，每个指针对应一个page，所以span区域的大小为(512GB/8KB) * 指针大小8byte = 512M bitmap区域大小也是通过arena计算出来512GB / (指针大小(8 byte) * 8 / 2) = 16G，用于表示arena区域中哪些地址保存了对象, 并且对象中哪些地址包含...阅读全文
由于目前golang 没有提供泛型机制，所以通用容器实现基本和 c 类似，golang 用 interface{} 做转接， c 用 void * 转接。 ring 包实现循环双向链表： type Ring struct { next, prev *Ring Value interface{} } 内部导出一个用户可以操作的Value 字段。 heap 包实现 binary heap ： type Interface interface { sort.Interface Push(x interface{}) // add x as element Len() Pop() interface{} // remove and return element Len() - 1. } heap.I...阅读全文
前两天有小伙伴问道是否看过 Go 语言 map 的实现，当时还真没看过，于是就花了一点时间看了一遍 runtime 源码中的 hashmap 实现。map 的底层实现就是一个 hash 表，大体结构上和平时在脑海里的 hash 表差不多，但确实有很多细节(“Devils in the details”)。 hashmap 通过一个 bucket 数组实现，所有元素将被 hash 到数组中的 bucket 中，bucket 填满后，将通过一个 overflow 指针来扩展一个 bucket 出来形成链表，也就是解决冲突问题。这也就是一个基本的 hash 表结构，没什么新奇的东西，下面总结一些细节吧。 注意一个 bucket 并不是只能存储一个 key/value 对，而是可以存储8个 key/...阅读全文
参考来源：https://blog.csdn.net/qq_34337272/article/details/81252853 CAS算法（compare and swap） CAS算法是一种有名的无锁算法。无锁编程，即不使用锁的情况下实现多线程之间的变量同步，也就是在没有线程被阻塞的情况下实现变量的同步，所以也叫非阻塞同步（Non-blocking Synchronization）。CAS算法涉及到三个操作数 需要读写的内存值V 进行比较的值A 拟写入的新值B 当且仅当 V 的值等于 A时，CAS通过原子方式用新值B来更新V的值，否则不会执行任何操作（比较和替换是一个原子操作）。一般情况下是一个自旋操作，即不断的重试。 自旋锁 自旋锁是指当一个线程在获取锁的时候，如果锁已经被其他线程...阅读全文
载请注明出处: 数据结构——Golang实现队列 Golang 1. 介绍 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。 数据结构里的队列就是模仿现实中的排队。 1） 新来的都排在队尾； 2） 最前面的办理业务后离队，后面一个跟上。 根据特点，计算机砖家就归纳以下队列结构。 image.png 2. Golang 实现 2.1. 队列结构 同前文的栈一样，在这里，我把队列拆分为两个部分，容器和链表，容器用结构体实现，链表用单链表，当然大家也可以用其他链表结构，甚至数组来实现。 这里的例子，也是使用单链表实现的。 // Queu...阅读全文
理 我们都知道怎么使用goLang中的map来存储键值对类型的数据，但是它的内部实现是怎么样的？ 其实map是一种HashMap，表面上看它只有键值对结构，实际上在存储键值对的过程中涉及到了数组和链表。HashMap之所以高效，是因为其结合了顺序存储(数组)和链式存储(链表)两种存储结构。数组是HashMap的主干，在数组下有有一个类型为链表的元素。 这是一个简单的HashMap的结构图： HashMap结构 当我们存储一个键值对时，HashMap会首先通过一个哈希函数将key转换为数组下标，真正的key-value是存储在该数组对应的链表里。 HashMap的数组往往是有限的，那当要存储的键值对很多数组不够或者两个键值对哈希运算后的值相同时，不就会有不同的键值对存储在同一个数组下吗？是的，...阅读全文
前几天断断续续的写了3篇关于Go语言内存分配器的文章，分别是Go语言内存分配器设计、Go语言内存分配器-FixAlloc、Go语言内存分配器-MSpan，这3篇主要是本文的前戏，其实所有的内容本可以在一篇里写完的，但内容实在太多了，没精力一口气搞定。本文将把整个内存分配器的架构以及核心组件给详细的介绍一下，当然亲自对照着翻看一下代码才是王道。 内存布局结构图 我把整个核心代码的逻辑给抽象绘制出了这个内存布局图，它基本展示了Go语言内存分配器的整体结构以及部分细节（这结构图应该同样适用于tcmalloc）。从此结构图来看，内存分配器还是有一点小复杂的，但根据具体的逻辑层次可以拆成三个大模块——cache，central，heap，然后一个一个的模块分析下去，逻辑就显得特别清晰明了了。位于结构图...阅读全文
``map``是Go语言中基础的数据结构，在日常的使用中经常被用到。但是它底层是如何实现的呢？ # ``map``的整体结构图 Golang中``map``的底层实现是一个散列表，因此实现``map``的过程实际上就是实现散表的过程。在这个散列表中，主要出现的结构体有两个，一个叫``hmap``(``a header for a go map``)，一个叫``bucket``。这两种结构的样子分别如下所示： hmap:  图中有很多字段，但是便于理解``map``的架构，你只需要关心的只有一个，就是标红的字段：bucke...阅读全文
需求队列的特性较为单一，基本操作即初始化、获取大小、添加元素、移除元素等。最重要的特性就是满足先进先出。实现接下来还是按照以前的套路，一步一步来分析如何利用Go的语法特性实现Queue这种数据结构。定义首先定义每个节点Node结构体，照例Value的值类型可以是任意类型，节点的前后指针域指针类型为nodetype node struct { value interface{} prev *node next *node } 继续定义链表结构，定义出头结点和尾节点的指针，同时定义队列大小size:type LinkedQueue struct { head *node tail *node size int } 大小获取队列大小，只需要获取LinkedQueue中的size大小即可：func ...阅读全文
一、什么是集合集合就是不同对象的无序聚集。那么链表和集合有什么关系呢？我们来变个魔术。如下图是各种颜色组成的链表：下面我们一步步把链表变成集合。第一步砍去链接第二步去掉重复第三步放到一个框里摇一摇就成集合了可以看出集合有这些特点：无序：链表去掉链接，就是去掉元素间有序状态。不重复：去掉重复的玫红色。虽然说集合是一种数学概念，但在实际生活中无处不透露着集合。比如一个班级的学生是一个集合。班级里的男生又是一个集合。二、集合的结构大卫哥这里为了简化概念的描述，继续用单链表来表示集合，但是在对集合做计算的时候单链表并不合适，数据量大的时候它的弊端就会显现，在讲到后面的数据结构和算法的时候，我们再回头来完善前面讲的数据接口的实现。三、接口说明及实现2、Init初始化集合，本质是初始化链表。...阅读全文
## 链表定义 ### 定义错误 ```go import "errors" var ( //ErrIndex 超出列表索引 ErrIndex = errors.New("out of list index") //ErrNotFound 没有找到该元素 ErrNotFound = errors.New("not found this element") ) ``` ### 定义接口 ```go // Comparer 数据接口 type Comparer interface { compare(data interface{}) bool } ``` ### 定义链表结点 ```go // SingleElement 列表结点 type SingleElement struct { Dat...阅读全文
最近看到一篇新闻: 英超再现恐怖食物链!20强相生相克 今年用了14轮，对于足球和英超感兴趣的读者一定了解，所谓食物链是指A队胜过B队，B队胜过C队,……，N队也胜过A队，截止到英超第14轮，根据所有的队伍的胜负关系，一条最大的食物链已经形成，英超20队都加入到这个食物链中，相生相克。 我看到这篇新闻的时候，有一点点程序员的不由自主的想法，能否通过算法检查目前最大的食物链，以及能否将食物链罗列出来？这也算是算法解决实际问题的一个很好的例子吧。 很自然的，可以通过图来表示两队之间的已经比赛的关系，因为我们我们只考虑胜负关系，不考虑平局，所以可以使用有向图来表示。食物链可以单纯用胜或者负来表示，所以我们的有向图中以胜表示两个节点之间的关系。 当然，我对图相关的算法不是很熟悉，所以特地搜了一下相关...阅读全文
一、什么是栈这是杭州地铁1号线线路图。大卫哥考考大家，地铁列车如何调头？我也不卖关子了，列车通常是用“人字轨道”来变换车道。列车先从A轨道开进“人字轨道”里，再从B轨道开出。从A轨道开进去的时候1号车厢是车头，从B开出来的时候4号车厢就变成车头了。所以大家看到地铁前后各一个车头。“人字轨道”有个特点：先进后出，英文简写就是FILO，含义自己体会。计算机专家把“人字轨道”抽象出来，提出了一个叫“栈”的概念。栈和“人字轨道”的特点是一样的FIFO，只不过把车厢换成了数据。接下来，看大卫哥把栈扒的底裤不剩。二、栈的结构大卫哥把栈拆分成容器和链表两块，容器用结构体实现，链表用单链表，当然大家也可以用其他链表结构，甚至数组来实现。三、接口说明及实现1、Init初始化栈，其实就是初始化里面的链...阅读全文
记录一下昨天的面试，感觉是凉了。 字节跳动嘛，早有耳闻面试很难，尤其是算法题部分，所以特地准备了很久算法，没想到最后没有跪在算法，跪在数据库…… 背景 2019届中流985计算机本科，已经保研南京大学，同学帮忙内推暑期实习，时长3个月。目标岗位是后台开发，头条后台用Golang较多，本人没有接触过Golang，对Java比较熟悉。 面试 先自我介绍一下，最近在做什么。打算什么时候开始实习，能实习多久。 对什么语言比较熟悉？Java。 HashMap底层实现，如何扩容。HashMap为什么线程不安全，多个线程同时put时会发生什么？（这里答得不好，没有答到同时put导致链表成环的场景，反而是想到了用迭代器时其他线程对HashMap进行了修改引发的ConcurrentModificationEx...阅读全文
 *Ring //创建一个长度为n的环形链表 func (r *Ring) Do(f func(interface{})) //对链表中任意元素执行f操作，如果f改变了r，则该操作造成的后果是不可预期的。 func (r *Ring) Len() int //求环长度，返回环...阅读全文
链表的数据结构比较线性数组，优点是 可以方便的对任意的位置进行插入和删除。 这一特性使得它很适合于应用在排序等场景下，由于golang目前类库还不是很完善，在java中可以很简单的使用api提供的支持完成对list或者map的排序，在使用go时就没有那么幸运了，可能需要自己去实现。 下面的例子就是使用go package 中的LinkedList实现的排序的链表。 有几个功能特性： 1.支持固定的长度 2.可自定义排序的规则 3.组合LinkedList功能 package codeforfun import ( "container/list" ) type SortedLinkedList struct { *list.List Limit int compareFunc func (o...阅读全文
一、概念介绍下面这副图是我们单链表运煤车队。每节运煤车就是单链表里的元素，每节车厢里的煤炭就是元素中保存的数据。前后车通过锁链相连，作为单链表运煤车，从1号车厢开始，每节车厢都知道后面拉着哪一节车厢，却不知道前面是哪节车厢拉的自己。第一节车厢没有任何车厢拉它，我们就叫它车头，第五节车厢后面拉其他车厢，我们称为车尾。作为单链表它最大的特点就是能随意增加车队的长度，也能随意减少车队的长度。这是比数组公交车最大的优点。二、Go语言实现讲解1、节点每节车厢都由车体、绳索和煤炭构成。在Go语言中表示这种自定义组合体的类型就是结构，当然为了通用性，我们这里要把车厢转换成节点也就是元素，煤炭转换成数据，绳索转换成指针。type Node struct { data Object next *Node ...阅读全文
LRU 通常使用hash map + doubly linked list实现。在Golange中很简单，使用List保存数据,Map来做快速访问即可. 具体实现了下面几个函数: func NewLRUCache(cap int)(*LRUCache) func (lru *LRUCache)Set(k,v interface{})(error) func (lru *LRUCache)Get(k interface{})(v interface{},ret bool,err error) func (lru *LRUCache)Remove(k interface{})(bool) 演示: package main //LRU Cache //author:Xiong Chuan Lian...阅读全文
# 原来**Rus**t的杀手级是区块链！ [区块链2018年最后一件大事！神级跨链项目Polkadot国内首次线上分享大放送！](http://www.mimajike.com/2166/.html...阅读全文
作者：达达来源：http://1234n.com/?post/yzsrwa最近一段时间对《仙侠道》的服务端进行了一系列针对GC的调优，这里跟各位分享一下调优的经验。游戏第一次上线的时候，大部分精力都投入在做cpuprof和memprof找性能瓶颈和内存泄漏上，没有关注过Go的GC运行情况。有一次cpuprof里的scanblock调用所占的比例让我注意到Go的GC所带来的性能消耗，记得那份cpuprof里，scanblock调用占到49%。也就是说有一半的CPU时间浪费在了GC上。于是我开始研究如何进行优化，过程中免不了要分析数据，经过一番搜索，我好到了GOGCTRACE这个环境变量。用法类似这样：GOGCTRACE=1 ./my_go_program 2> log_file 通过这个环境变...阅读全文
由于用户纷纷反应山坡网的打开速度比较慢，所以两天前我们决定把服务器从linode迁移到阿里云。 整个迁移过程非常平滑，基本上一个小时就完成了。而且阿里云的配套设施提供的也很不错，运行状态监控什么的都有。在此向大家推荐阿里云！ 话说由于我们资金有限，就选择了ECS服务器中最低档的一款，512MB内存，2MB带宽。而山坡网上会有很多书籍封面图片，这导致了页面打开的速度并没有想象中提高的多，用户反应速度虽有提升，但不明显。 此时我想到了七牛云存储，虽说知道它已经几个月了，但始终没有正式开始用，总觉得我们挺穷的，云存储这类高端大气上档次的东西一时半会儿估计用不上。但还是抱着学习一下的心思打开它看了看。这一看我就乐疯了。 这……不敢相信啊！二话不说，立马决定把所有书籍封面图片都迁移到云端！ 接着打开七...阅读全文
Go语言标准库概览 九 08 bigwhite技术志 Assert, Blog, Blogger, C, Cpp, Go, Golang, Google, Interface, map, Opensource, Programmer, Reflect, Slice, 切片, 博客, 反射, 容器, 开源, 接口, 断言, 方法, 标准库, 程序员, 结构体, 编程，语言, 编译器 No Comments 本文翻译自Dr.Dobb's的"A Brief Tour of the Go Standard Library"一文。 在Go语言五周系列教程的最后一部分中，我们将带领大家一起来浏览一下Go语言丰富的标准库。 Go标准库包含了大量包，提供了丰富广泛的功能特性。这里提供了概览仅仅是有选择性的且...阅读全文
载请注明出处：数据结构——Golang实现双向链表 Golang 1. 双向链表 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。 结构如下图： image.png 2. Golang 实现 2.1. 相关结构体 首先需要先定义一下链表相关的结构，DoubleObject用于每个节点的数据，为interface{}结构，DoubleNode为链表中的节点，DoubleList双链表，为了多协程读写安全，所以在链表中加了读写锁。 具体定义如下： // 节点数据 type DoubleObject interface{} // 双链表节点 type DoubleNode ...阅读全文
用Golang写一个搜索引擎 猜你喜欢 golang入门-- 一个2D的图形库学习 golang入门--一个简单的http client golang的第一个deadlock LiteJob,一个Golang的本地任务调度器 再次自我黑客马拉松--不用第三方库实现一个基于golang的web service 如何利用golang 反射值来定义一个变量 用Golang写一个搜索引擎 用Golang写一个搜索引擎（0x01） 用Golang写一个搜索引擎（0x02） 用Golang写一个搜索引擎（0x03） 前面已经说了倒排索引的基本原理了，原理非常简单，也很好理解，关键是如何设计第二个倒排表，倒排表的第二列也很好设计，第一列就是关键了，为了满足快速查找的性能，设计第一列的结构，我们需要满足以下...阅读全文
昨天写了一篇Go语言内存分配器设计，记录了一下内存分配器的大体结构。在介绍内存分配器的核心实现前，本文先介绍一下内存分配器中一个工具组件——FixAlloc。FixAlloc称不上是核心组件，只是辅助实现整个内存分配器核心的一个基础工具罢了，由此可以看出FixAlloc还是一个比较重要的组件。引入FixAlloc的目的只是用来分配MCache和MSpan两个特定的对象，所以内存分配器中有spanalloc和cachealloc两个组件（见《Go语言内存分配器设计》的图）。MCache和MSpan两个结构在malloc.h中有定义。 定义在malloc.h文件中的FixAlloc结构如下，比较关键的三个字段是alloc、list和chunk，其他的字段主要都是用来统计一些状态数据的，比如分配了...阅读全文
/*下载工具*/ package main import ( "fmt" //go语言版本的jquery "github.com/PuerkitoBio/goquery" "os" "sync" "strings" //go语言版本的request "github.com/levigross/grequests" "time" "strconv" ) var wg sync.WaitGroup func main() { now := time.Now() initalUrls := []string{"http://www.zngirls.com/girl/18071/album/", } for _, url := range initalUrls { doc, err := goque...阅读全文
go中container中list的使用详解 1. func New() *List{} 初始化一个列表，返回类型为一个list对象 a := list.New() # 在函数内部 a = list.New() 输出： &{{0xc00006a300 0xc00006a300
map 的删除操作 Golang 内置了哈希表，总体上是使用哈希链表实现的，如果出现哈希冲突，就把冲突的内容都放到一个链表里面。 Golang 还内置了delete函数，如果作用于哈希表，就是把 map 里面的 key 删除。 delete(intMap, 1) map 的删除原理 可以直接看源码。 我简单摘几行： func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { b.tophash[i] = empty h.count-- } } } 外层的循环就是在遍历整个 map，删...阅读全文
Go container包 container/list-双向链表-List 基本的数据结构 type Element struct { // Next and previous pointers in the doubly-linked list of elements. // To simplify the implementation, internally a list l is implemented // as a ring, such that &l.root is both the next element of the last // list element (l.Back()) and the previous element of the first list // ...阅读全文
生成器 在Python中我们可以使用yield关键字来让一个函数成为生成器，在Go中我们可以使用信道来制造生成器(一种lazy load类似的东西)。 当然我们的信道并不是简单的做阻塞主线的功能来使用的哦。 下面是一个制作自增整数生成器的例子，直到主线向信道索要数据，我们才添加数据到信道： func xrange() chan int{ // xrange用来生成自增的整数 var ch chan int = make(chan int) go func() { // 开出一个goroutine for i := 0; ; i++ { ch <- i // 直到信道索要数据，才把i添加进信道 } }() return ch } func main() { generator := xrang...阅读全文
MSpan和FixAlloc一样，都是内存分配器的基础工具组件，但和FixAlloc没太大的交集，各自发挥功效而已。span(MSpan简称span)是用来管理一组组page对象，先解释一下page，page就是一个4k大小的内存块而已。span就是将这一个个连续的page给管理起来，注意是连续的page，不是东一个西一个的乱摆设的page。为了直观形象的感受一下span，还是得画个图吧，图形是最好的交流语言。 MSpan结构定义在malloc.h头文件中，代码如下： struct MSpan { MSpan *next; // in a span linked list MSpan *prev; // in a span linked list PageID start; // start...阅读全文
在[先前的博文](https://studygolang.com/articles/12686)中，我们探讨了链表以及如何将它应用于实际应用。在这篇文章中，我们将继续探讨两个相似且功能强大的数据结构。 ## 建模操作和历史 让我们看看 Excel 或 Google 文档，他们是人类发明的最普遍的构成文件的应用程序。我们都使用过它们。 正如你可能知道的，这些应用程序有各种各样对文本的操作。 比如在文本中添加颜色、下划线、各种字体和大小，或者在表格中组织内容。这个列表很长，我们期望从这些工具中得到一个普遍的功能 —— “撤销”和“重做”已经执行了的操作的能力。 你是否考虑过让你做，你将如何规划这样的功能？下面让我们探索一个可以帮助我们完成这样一项任务的数据结构。 
