dre93205 2017-03-25 22:38
浏览 72

在Golang中实现数据结构

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:

  1. What basic type should I use in my own array type?
  2. Can I somehow reallocate the memory (increment/decrement the length) without operating on capacity?
  3. 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?
  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
    • ¥15 matlab数字图像处理频率域滤波
    • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
    • ¥15 ELGamal和paillier计算效率谁快?
    • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
    • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
    • ¥15 Arcgis相交分析无法绘制一个或多个图形
    • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
    • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
    • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)