I need to create a list of integers and to be able to quickly add, delete, and find items in that list. While I could create a string containing them and a function to handle the add/delete/locate, it obviously makes more sense if Go can handle it for me. I looked at container/list and it appeared not entirely suitable, but maybe I'm wrong.
To very quickly implement something, I am using an integer array, however that is far from ideal, and I need to find a better solution. The list will probably hold up to 1,000 values.
Can someone please advise the "best" way to handle this in Go? An example is worth 1,000 words.
In the interest of keeping it simple I would use a map. Maps are very fast, efficient and built in.
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)
}
}
Which produces
Found 2 Didn't Find 8 Contents 3 Contents 1
Possibly the only disadvantage of this solution is that the integers aren't kept in any particular order, which may or may not be important to your application.
This is really more of an abstract data structure question. The answer depends on your use case. A slice of ints would do fine for the general case (look at append and such), but if you want finding items to be better than O(n) then you'll want them to be sorted, and insertion into a sorted int[] has a worst case of O(n) iirc.
So the question is which do you want to optimize, index, add, remove, or search?
There is no 'best' way to your question as you don't state what you would like to do or what sort of performance is important to you. The problem with data structures is, that every structure performs better or worse depending on the circumstances. Generally I would say that an integer slice would perform reasonably well for 1000 entries and is not so hard to use. Also the solution Nick proposed is appealing, as it offers you O(1) lookup time (average!) for your values instead of O(n) (unsorted) or O(log n) (sorted) search time in an array.
Go offers some operations to implement a []int store as you proposed:
x[i]x[i] = j or x = append(x, j) or use sorted insertionx = append(x[:i], x[i+1:]...)sort.SearchInts, otherwise you need to loop and search linearly.For more operations on slices see here.
The following example (playground) offers you a []int with O(log n) time for searching and O(n) for insertion. Retrieval, deletion and setting by index is, of course, 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)
As you can see in the example, Append searches for the place to insert the new value in, depending on the size, effectively sorting the contents of the slice in ascending order. This makes it possible to use binary search via sort.SearchInts, reducing the search time from O(n) to O(log n). With that comes the cost to sort while inserting, which in turn is done by searching for a slot, which costs O(log n) in worst case. Therefore, inserting is O(log n) as well.