go语言二分查找溢出,go 二分查找算法

Go语言 排序与搜索切片

Go语言标准库中提供了sort包对整型，浮点型，字符串型切片进行排序，检查一个切片是否排好序，使用二分法搜索函数在一个有序切片中搜索一个元素等功能。

创新互联专注于企业成都全网营销、网站重做改版、北辰网站定制设计、自适应品牌网站建设、H5开发、购物商城网站建设、集团公司官网建设、外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为北辰等各大城市提供网站开发制作服务。

关于sort包内的函数说明与使用，请查看

在这里简单讲几个sort包中常用的函数

在Go语言中，对字符串的排序都是按照字节排序，也就是说在对字符串排序时是区分大小写的。

二分搜索算法

Go语言中提供了一个使用二分搜索算法的sort.Search(size,fn)方法：每次只需要比较㏒₂n个元素，其中n为切片中元素的总数。

sort.Search(size,fn)函数接受两个参数：所处理的切片的长度和一个将目标元素与有序切片的元素相比较的函数，该函数是一个闭包，如果该有序切片是升序排列，那么在判断时使用 有序切片的元素 = 目标元素。该函数返回一个int值，表示与目标元素相同的切片元素的索引。

在切片中查找出某个与目标字符串相同的元素索引

Golang二分法查找

使用二分查找需要数组是有序的。

比如在升序排列的数组中，将数组中间位置的数据与目标数据比较，如果相等则查找成功；否则按照中间位置把数组分为两部分，如果中间位置大于目标数据，则在前半部分中以取中心点的方式继续比较，否则查找后半部分。

Go语言使用 map 时尽量不要在 big map 中保存指针

不知道你有没有听过这么一句：在使用 map 时尽量不要在 big map 中保存指针。好吧，你现在已经听过了：）为什么呢？原因在于 Go 语言的垃圾回收器会扫描标记 map 中的所有元素，GC 开销相当大，直接GG。

这两天在《Mastering Go》中看到 GC 这一章节里面对比 map 和 slice 在垃圾回收中的效率对比，书中只给出结论没有说明理由，这我是不能忍的，于是有了这篇学习笔记。扯那么多，Show Your Code

这是一个简单的测试程序，保存字符串的 map 和 保存整形的 map GC 的效率相差几十倍，是不是有同学会说明明保存的是 string 哪有指针？这个要说到 Go 语言中 string 的底层实现了，源码在 src/runtime/string.go里，可以看到 string 其实包含一个指向数据的指针和一个长度字段。注意这里的是否包含指针，包括底层的实现。

Go 语言的 GC 会递归遍历并标记所有可触达的对象，标记完成之后将所有没有引用的对象进行清理。扫描到指针就会往下接着寻找，一直到结束。

Go 语言中 map 是基于 数组和链表 的数据结构实现的，通过 优化的拉链法 解决哈希冲突，每个 bucket 可以保存 8 对键值，在 8 个键值对数据后面有一个 overflow 指针，因为桶中最多只能装 8 个键值对，如果有多余的键值对落到了当前桶，那么就需要再构建一个桶（称为溢出桶），通过 overflow 指针链接起来。

因为 overflow 指针的缘故，所以无论 map 保存的是什么，GC 的时候就会把所有的 bmap 扫描一遍，带来巨大的 GC 开销。官方 issues 就有关于这个问题的讨论， runtime: Large maps cause significant GC pauses #9477

无脑机翻如下：

如果我们有一个map [k] v，其中k和v都不包含指针，并且我们想提高扫描性能，则可以执行以下操作。

将“ allOverflow [] unsafe.Pointer”添加到 hmap 并将所有溢出存储桶存储在其中。 然后将 bmap 标记为noScan。 这将使扫描非常快，因为我们不会扫描任何用户数据。

实际上，它将有些复杂，因为我们需要从allOverflow中删除旧的溢出桶。 而且它还会增加 hmap 的大小，因此也可能需要重新整理数据。

最终官方在 hmap 中增加了 overflow 相关字段完成了上面的优化，这是具体的 commit 地址。

下面看下具体是如何实现的，源码基于 go1.15，src/cmd/compile/internal/gc/reflect.go 中

通过注释可以看出，如果 map 中保存的键值都不包含指针（通过 Haspointers 判断），就使用一个 uintptr 类型代替 bucket 的指针用于溢出桶 overflow 字段，uintptr 类型在 GO 语言中就是个大小可以保存得下指针的整数，不是指针，就相当于实现了 将 bmap 标记为 noScan， GC 的时候就不会遍历完整个 map 了。随着不断的学习，愈发感慨 GO 语言中很多模块设计得太精妙了。

差不多说清楚了，能力有限，有不对的地方欢迎留言讨论，源码位置还是问的群里大佬 _

GO语言（十一）：开始使用多模块工作区

本教程介绍 Go 中多模块工作区的基础知识。使用多模块工作区，您可以告诉 Go 命令您正在同时在多个模块中编写代码，并轻松地在这些模块中构建和运行代码。

在本教程中，您将在共享的多模块工作区中创建两个模块，对这些模块进行更改，并在构建中查看这些更改的结果。

本教程需要 go1.18 或更高版本。使用go.dev/dl中的链接确保您已在 Go 1.18 或更高版本中安装了 Go 。

首先，为您要编写的代码创建一个模块。

1、打开命令提示符并切换到您的主目录。

在 Linux 或 Mac 上：

在 Windows 上：

2、在命令提示符下，为您的代码创建一个名为工作区的目录。

3、初始化模块

我们的示例将创建一个hello依赖于 golang.org/x/example 模块的新模块。

创建你好模块：

使用 . 添加对 golang.org/x/example 模块的依赖项go get。

在 hello 目录下创建 hello.go，内容如下：

现在，运行 hello 程序：

在这一步中，我们将创建一个go.work文件来指定模块的工作区。

在workspace目录中，运行：

该go work init命令告诉为包含目录中模块的工作空间go创建一个文件 。go.work./hello

该go命令生成一个go.work如下所示的文件：

该go.work文件的语法与go.mod相同。

该go指令告诉 Go 应该使用哪个版本的 Go 来解释文件。它类似于文件中的go指令go.mod 。

该use指令告诉 Go在进行构建时hello目录中的模块应该是主模块。

所以在模块的任何子目录中workspace都会被激活。

2、运行工作区目录下的程序

在workspace目录中，运行：

Go 命令包括工作区中的所有模块作为主模块。这允许我们在模块中引用一个包，即使在模块之外。在模块或工作区之外运行go run命令会导致错误，因为该go命令不知道要使用哪些模块。

接下来，我们将golang.org/x/example模块的本地副本添加到工作区。然后，我们将向stringutil包中添加一个新函数，我们可以使用它来代替Reverse.

在这一步中，我们将下载包含该模块的 Git 存储库的副本golang.org/x/example，将其添加到工作区，然后向其中添加一个我们将从 hello 程序中使用的新函数。

1、克隆存储库

在工作区目录中，运行git命令来克隆存储库：

2、将模块添加到工作区

该go work use命令将一个新模块添加到 go.work 文件中。它现在看起来像这样：

该模块现在包括example.com/hello模块和 `golang.org/x/example 模块。

这将允许我们使用我们将在模块副本中编写的新代码，而不是使用命令stringutil下载的模块缓存中的模块版本。

3、添加新功能。

我们将向golang.org/x/example/stringutil包中添加一个新函数以将字符串大写。

将新文件夹添加到workspace/example/stringutil包含以下内容的目录：

4、修改hello程序以使用该功能。

修改workspace/hello/hello.go的内容以包含以下内容：

从工作区目录，运行

Go 命令在go.work文件指定的hello目录中查找命令行中指定的example.com/hello模块 ，同样使用go.work文件解析导入golang.org/x/example。

go.work可以用来代替添加replace 指令以跨多个模块工作。

由于这两个模块在同一个工作区中，因此很容易在一个模块中进行更改并在另一个模块中使用它。

现在，要正确发布这些模块，我们需要发布golang.org/x/example 模块，例如在v0.1.0. 这通常通过在模块的版本控制存储库上标记提交来完成。发布完成后，我们可以增加对 golang.org/x/example模块的要求hello/go.mod：

这样，该go命令可以正确解析工作区之外的模块。