是否有Python的bisect模块的Go模拟？

Question

我正在寻找Go 中的Python bisect模块的开箱即用的实现.我需要的只是找到一个位置,用于从左侧和右侧插入排序数组中的项目.

我知道实现背后的逻辑,但我不想重新发明它的所有边缘情况.

Answer 1

是.sort.Search()是你想要的.它需要一个长度和一个比较函数,并返回函数返回true的第一个索引.链接文档中的示例包括:

i := sort.Search(len(data), func(i int) bool { return data[i] >= x })

这设置i为第一个值>=x 的索引(或者len(data)如果没有项是>=x),那么它就像bisect.bisect_left()在Python中一样.改变它以>获得类似的东西bisect_right.

Python函数还将搜索列表中的范围; 要做类似的事情,你可以搜索切片的子切片,Search如果需要原始切片的索引,则将其起始偏移量添加到索引返回.还有其他方法,但这似乎简单易读.

虽然对于Python列表也是如此,但插入到排序切片中的是O(n),即,它的平均速度是两倍数据的两倍.对于许多目的而言,这仍然很好(很多时候你有一个小列表或几个插入),但当然你不能无限期地扩展.如果您要插入大量项目,例如列表大小的很大一部分,您可以将它们全部附加,然后排序.对于具有对数时间插入,删除等的一般排序集合,例如,总是存在github.com/cznic/b任意数量的数据库事物.