So I have to implement some data structures in a language compiled to native-code. I did that in C++, but now I wanted to try another language, that I didn't worked with before. I chose golang
. First data structure would be an array (capable of dynamic append, removal, etc.) In C++ I got something like this:
class array{
int n;
int *t;
.
.
.
}
So n
is the number of elements and *t
is a pointer to an array, which would be created in a constructor. I wrote append
, pop_back
, remove
, find
methods and so on. Now when I switch to golang, my first attempt was to create a struct
something like this:
type array struct {
n int
...
}
and well I didn't know what should be here instead of dots. So I did some reading (got Brian W. Kernighan book) and I found about 2 data types : arrays
and slices
. I found a piece of code for appending to the array (take an array, resize it (n+1) and insert a value). I tested it, works (I tested it on a built-in slice
type). Now when I would have my own array type I don't know if I should use slice
, or maybe something else. I have this piece of code, which would measure the times for Append()
operation, depending on the number of elements:
package main
import (
"fmt"
"time"
)
type array struct {
n int
}
func Append(slice []int, element int) []int {
n := len(slice)
total := len(slice) + 1
if total > cap(slice) {
// Reallocate. Grow to 1.5 times the new size, so we can still grow.
newSize := total*3/2 + 1
newSlice := make([]int, total, newSize)
copy(newSlice, slice)
slice = newSlice
}
slice = slice[:total]
slice[n] = element
return slice
}
func main() {
var seconds int64 = 0
sizes := [5]int64{1000, 5000, 10000, 50000, 100000}
for i := 0; i < 5; i++ {
var j int64
for j = 0; j < 100; j++ {
array := make([]int, sizes[i], sizes[i]+1)
start := time.Now()
array = Append(array, 1)
elapsed := time.Since(start)
seconds += int64(elapsed)
}
seconds = seconds/100
fmt.Println(seconds)
seconds = 0
}
fmt.Println("The end")
}
I always do array := make([]int, sizes[i], sizes[i]+1)
cuz I don't want to make capacity changing and copying be relevant here. As far as I know there should be no difference if array has 1000 elements or 100000 - the time should be approximately the same, but the results I've got are different :
1810
1589
46
99
244
The end
The times differ. Now my questions are:
- What basic type should I use in my own array type?
- Can I somehow reallocate the memory (increment/decrement the length) without operating on capacity?
- Is there a way to change this algorithm to make its computional complexity
O(1)
, so it doesn't matter how many arguments are there?