Различия между ломтиком и контейнером / списком - PullRequest
Новая
       6

Различия между ломтиком и контейнером / списком

0 голосов
/ 26 мая 2018

Я только начинаю с Go и у меня возникает ситуация, когда мне нужно создать набор сущностей, размер / длина которых известен только во время выполнения.Сначала я подумал, что использование списка было бы неплохо, но вскоре понял, что срезы - это идиоматическая структура данных в Go.Любопытно, я написал следующие тесты 

package main

import (
    "container/list"
    "testing"
)

var N = 10000000

func BenchmarkSlices(B *testing.B) {
    s := make([]int, 1)
    for i := 0; i < N; i += 1 {
        s = append(s, i)
    }
}

func BenchmarkLists(B *testing.B) {
    l := list.New()
    for i := 0; i < N; i += 1 {
        l.PushBack(i)
    }
}

, которые дали мне 

BenchmarkSlices-4       2000000000               0.03 ns/op
BenchmarkLists-4               1        1665489308 ns/op

Учитывая, что append создаст новый массив и скопирует все данные из старого в новыйКогда старый массив заполнится, я ожидал, что списки будут работать лучше, чем срезы в примере выше.Однако мои ожидания явно ошибочны, и я пытаюсь понять, почему.

Я написал следующее, чтобы немного лучше понять, как append создает новые массивы, когда это необходимо: 

package main

import "fmt"

func describe(s []int) {
    fmt.Printf("len = %d, cap = %d\n", len(s), cap(s))
}

func main() {
    s := make([]int, 2)
    for i := 0; i < 15; i += 1 {
        fmt.Println(i)
        describe(s)
        s = append(s, i)
    }
}

, который дал мне 

0
len = 2, cap = 2
1
len = 3, cap = 4
2
len = 4, cap = 4
3
len = 5, cap = 8
4
len = 6, cap = 8
5
len = 7, cap = 8
6
len = 8, cap = 8
7
len = 9, cap = 16
8
len = 10, cap = 16
9
len = 11, cap = 16
10
len = 12, cap = 16
11
len = 13, cap = 16
12
len = 14, cap = 16
13
len = 15, cap = 16
14
len = 16, cap = 16

На данный момент я могу только догадываться, почему срезы работают лучше, чем списки, - это то, что выделение памяти для нового массива с двойным размером и копирование всех данных происходит быстреечем выделение памяти для одного элемента каждый раз, когда происходит вставка.Правильно ли мое предположение?Я что-то упустил?

1 Ответ

0 голосов
/ 26 мая 2018

Вы неправильно выполняете тесты.Сначала вы должны настроить исходную структуру данных, а затем запустить сопоставляемую операцию столько раз, сколько указывает экземпляр testing.B.

Я заменил ваш код на: 

var N = 1

func BenchmarkSlices(B *testing.B) {
    s := make([]int, 1)
    for n := 0; n < B.N; n++ {
        for i := 0; i < N; i++ {
            s = append(s, i)
        }
    }
}

func BenchmarkLists(B *testing.B) {
    l := list.New()
    for n := 0; n < B.N; n++ {
        for i := 0; i < N; i++ {
            l.PushBack(i)
        }
    }
}

И получилэтот результат: 

BenchmarkSlices-4       100000000               14.3 ns/op
BenchmarkLists-4         5000000               275 ns/op

По крайней мере, на этот раз разница кажется разумной и не такой, как триллион раз.

Обратите внимание, что я также заменил значение N на 1, чтобы ns/op фактически означает nanoseconds per operation, а не nanoseconds per N operations.Однако это также может повлиять на результаты.

Теперь на ваш вопрос: связанные списки, реализованные в Go, несут дополнительные затраты по сравнению с простым добавлением еще одного int к предварительно выделенному слайсу: нужен метод спискачтобы создать новый элемент , оберните ваше значение в interface{} и переназначьте некоторые указатели.

Между тем добавление к фрагменту, который не исчерпал свою емкость, приведет к нескольким инструкциямна уровне ЦП: переместите int в область памяти, увеличьте длину среза, и все готово.

Существует также тот факт, что нижележащий распределитель может перераспределить срез на месте, что позволяет избежатьнужно вообще скопировать существующие базовые элементы массива.

...