英文:
Is there a Go analog of Python's bisect module?
问题
我正在寻找一个现成的在Go语言中实现Python的bisect模块的方法。我只需要找到在一个有序数组中插入元素的位置，从左边和右边分别找。
我知道实现的逻辑，但是我不想重新发明轮子，包括其中的所有边界情况。
英文:
I am looking for an out-of-the-box implementation of Python's bisect module in Go. All that I need is to find a position for inserting an item in a sorted array from the left and from the right.
I know the logic behind the implementation, but I do not want to reinvent the wheel with all of its edge cases.
答案1
得分: 20
是的。sort.Search() 是你想要的。它接受一个长度和一个比较函数，并返回函数返回 true 的第一个索引。链接文档中的示例包括：
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
这将把 i 设置为第一个值 >= x 的索引（如果没有项 >= x，则设置为 len(data)），所以它类似于 Python 中的 bisect.bisect_left()。将其更改为 > 可以得到类似于 bisect_right 的结果。
Python 的函数还可以在列表的范围内搜索；要做类似的事情，你可以搜索切片的子切片，并将其起始偏移量添加到 Search 返回的索引中，如果你需要一个原始切片的索引。还有其他方法，但这似乎简单而易读。
尽管这也适用于 Python 列表，但在已排序的切片中插入是 O(n) 的，即在两倍数据上平均慢两倍。如果项数或插入数较小，你可能可以避免“糟糕”的复杂性。如果你添加了一堆然后搜索一堆，你可以将所有内容添加到末尾，排序一次，然后进行所有搜索，摊销排序的成本。
但对于通用的有序集合，无论你以什么顺序执行插入、删除、搜索等操作，它们都需要对数时间，你可能需要使用有序集合或数据库工具。有很多选择，但一些简单的“入门级”选项是 github.com/cznic/b 和 github.com/mattn/go-sqlite3。
英文:
Yes. sort.Search() is what you want. It takes a length and a comparison function, and returns the first index for which the function returns true. The example in the linked docs includes:
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
That sets i to the index of the first value >= x (or to len(data) if no items are >= x), so it's like bisect.bisect_left() in Python. Change it to > to get something like bisect_right.
The Python functions will also search through a range within a list; to do something similar, you could search a subslice of your slice, and add its starting offset to the index Search returns if you need an index into the original slice. There are other ways, but that seems simple and readable.
Though this is also true of Python lists, insertion into a sorted slice is O(n), i.e., it averages twice as slow on twice as much data. If either the number of items or the number of inserts is small you might get away the "bad" complexity. If you add a bunch then search a bunch, you could add everything to the end, sort once, then do all your searches, amortizing the cost of the sort.
But for general-purpose sorted collections where inserts, deletes, searches, etc. take logarithmic time regardless of what order you do them in, you may want to turn to tools for ordered collections or databases. There are lots of options, but a couple easy 'starter' ones are github.com/cznic/b and github.com/mattn/go-sqlite3.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论