2

我需要创建一个整数列表，并能够快速添加、删除和查找该列表中的项目。虽然我可以创建一个包含它们的字符串和一个处理添加/删除/定位的函数，但如果 Go 可以为我处理它显然更有意义。我查看了容器/列表，它似乎并不完全合适，但也许我错了。

为了快速实现某些东西，我使用的是整数数组，但这远非理想，我需要找到更好的解决方案。该列表可能最多包含 1,000 个值。

有人可以建议在 Go 中处理此问题的“最佳”方法吗？一个例子值 1000 字。

4

3 回答 3

4

您的问题没有“最佳”方式，因为您没有说明您想做什么或哪种表现对您很重要。数据结构的问题在于，每个结构的性能都取决于环境。一般来说，我会说整数切片对于 1000 个条目的性能相当好，而且使用起来并不难。Nick 提出的解决方案也很有吸引力，因为它O(1)为您的值提供了查找时间（平均！），而不是 数组中的O(n)（未排序）或 （排序）搜索时间。O(log n)

按照您的建议，Go 提供了一些操作来实现[]int商店：

  • 得到：x[i]
  • insert : x[i] = jor x = append(x, j)or 使用排序插入
  • 删除：x = append(x[:i], x[i+1:]...)
  • search：如果你使用了排序插入，你可以使用sort.SearchInts，否则你需要循环和线性搜索。

有关切片的更多操作，请参见此处。

以下示例 ( playground ) 为您提供[]int 了O(log n)搜索和O(n)插入的时间。按索引检索、删除和设置当然是O(1).

type Ints []int

// Insert v so that ints is sorted
func (ints *Ints) Append(v int) {
    i := sort.SearchInts(*ints, v)
    *ints = append((*ints)[:i], append([]int{v}, (*ints)[i:]...)...)
}

// Delete by index
func (ints *Ints) Delete(i int) {
    *ints = append((*ints)[:i], (*ints)[i+1:]...)
}

func (ints Ints) Search(v int) (int, bool) {
    i := sort.SearchInts(ints, v)
    return i, i < len(ints) && ints[i] == v
}

data := make(Ints, 0, 1000)
data.Append(100)
index,ok := data.Search(10)

正如您在示例中看到的Append，根据大小搜索插入新值的位置，有效地按升序对切片的内容进行排序。这使得通过 使用二分搜索成为可能sort.SearchInts，将搜索时间从 减少O(n)到O(log n)。随之而来的是在插入时进行排序的成本，而这又是通过搜索插槽来完成的，O(log n)在最坏的情况下这会花费成本。因此，插入也是O(log n)如此。

于 2013-04-13T00:30:19.183 回答
3

为了保持简单，我会使用map。地图非常快速、高效且内置。

（游乐场链接）

package main

import "fmt"

func main() {
    // Make our collection of integers
    xs := make(map[int]bool)

    // Add some things to the collection
    xs[1] = true
    xs[2] = true
    xs[3] = true

    // Find them
    if xs[2] {
        fmt.Println("Found 2")
    } else {
        fmt.Println("Didn't Find 2")
    }
    if xs[8] {
        fmt.Println("Found 8")
    } else {
        fmt.Println("Didn't Find 8")
    }

    // Delete them
    delete(xs, 2)

    // List them
    for x := range xs {
        fmt.Println("Contents", x)
    }
}

哪个生产

找到 2
没找到 8
内容 3
内容 1

此解决方案的唯一缺点可能是整数没有按任何特定顺序保存，这对您的应用程序可能很重要，也可能不重要。

于 2013-04-12T20:17:05.873 回答
0

这实际上更像是一个抽象的数据结构问题。答案取决于您的用例。对于一般情况（看看append等），一片整数会很好，但是如果你想找到比 O(n) 更好的项目，那么你会希望它们被排序，并且插入到排序int[]中的情况最糟糕O(n) iirc 的情况。

所以问题是您要优化、索引、添加、删除或搜索哪个？

于 2013-04-12T18:48:53.620 回答