Почему списки редко используются в Go?

Ответ 1

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

Поскольку я не получил четкого ответа на этот вопрос (хотя я принял один ответ), я сейчас собираюсь ответить на него сам, основываясь на том, что я узнал, так как я спросил его:

Есть ли способ создать массив/срез в Go без жесткого кодирования размер массива?

Да. Срезки не требуют жесткого кодированного массива slice из:

var sl []int = make([]int,len,cap)

Этот код выделяет срез sl размером len с емкостью cap - len и cap - переменными, которые могут быть назначены во время выполнения.

Почему list.List игнорируется?

Похоже, что главные причины list.List кажутся мало привлекательными в Go:

• Как было объяснено в ответе @Nick Craig-Wood, существует практически ничего, что можно сделать со списками, которые невозможно сделать с ломтиками, часто более эффективно и с более чистым, более элегантный синтаксис. Например, конструкция диапазона:

  for i:=range sl {
    sl[i]=i
  }
  

  не может использоваться со списком - требуется стиль C для цикла. И в во многих случаях синтаксис стиля набора С++ должен использоваться со списками: push_back и т.д.

• Возможно, что более важно, list.List не сильно типизирован - он очень похож на списки и словари Python, которые позволяют смешивать различные типы вместе в коллекции. Кажется, это противоречит к подходу Go к вещам. Go - очень строго типизированный язык - например, неявные преобразования типов никогда не допускаются в Go, даже upCast от int до int64 должен быть явный. Но все методы list.List принимают пустые интерфейсы - все идет.

  Одна из причин, по которой я отказался от Python и переехал в Go, такого рода слабость в системе типа Python, хотя Python утверждает, что он "сильно типизирован" (ИМО это не так). Go list.List кажется быть своего рода "дворняжкой", родившейся от С++ vector<T> и Python's List() и, возможно, немного неуместен в самом Go.

Меня не удивит, если в какой-то момент в не слишком отдаленном будущем мы найдем list.List, устаревший в Go, хотя, возможно, он останется, для размещения тех редких ситуаций, когда, даже используя хорошие методы проектирования, проблему лучше всего решить с помощью коллекции, которая имеет различные типы. Или, возможно, это там, чтобы обеспечить "мост" для разработчиков семейств C, чтобы устроиться с Go до того, как они изучат нюансы кусочков, которые уникальны для Go, AFAIK. (В некоторых отношениях срезы кажутся похожими на классы потоков в С++ или Delphi, но не полностью.)

Несмотря на то, что я пришел из фона Delphi/С++/Python, в моем первоначальном контакте с Go я обнаружил, что list.List более знаком, чем фрагменты Go, так как я стал более комфортным с Go, я вернулся и изменил все мои списки на срезы. Я еще ничего не нашел, что slice и/или map не позволяют мне делать, так что мне нужно использовать list.List.

Ответ 2

Почти всегда, когда вы думаете о списке, используйте вместо этого ломтик в Go. Ломтики динамически изменяются. В основе их лежит смежный фрагмент памяти, который может изменять размер.

Они очень гибкие, как вы увидите, если вы читаете страницу SliceTricks wiki.

Вот выдержка: -

Копировать

b = make([]T, len(a))
copy(b, a) // or b = append([]T(nil), a...)

Вырезать

a = append(a[:i], a[j:]...)

Удалить

a = append(a[:i], a[i+1:]...) // or a = a[:i+copy(a[i:], a[i+1:])]

Удалить без сохранения порядка

a[i], a = a[len(a)-1], a[:len(a)-1]

Pop

x, a = a[len(a)-1], a[:len(a)-1]

Нажмите

a = append(a, x)

Обновить. Вот ссылка на сообщение в блоге о срезах из самой команды go, что неплохо объясняет взаимосвязь между срезами и массивами и внутренними срезами.

Ответ 3

Я думаю, потому что не так много сказать о них, поскольку пакет container/list является довольно понятным, как только вы впитаете то, что является главным идиомом Go для работы с общими данными.

В Delphi (без дженериков) или в C вы сохраните указатели или TObject в списке, а затем вернете их к реальным типам при получении из списка. В С++ списки STL являются шаблонами и, следовательно, параметризуются по типу, а в С# (эти дни) списки являются общими.

В Go container/list хранятся значения типа interface{}, который является специальным типом, способным представлять значения любого другого (реального) типа, сохраняя пару указателей: один для информации о типе содержащегося значения, и указатель на значение (или значение напрямую, если размер не превышает размер указателя). Поэтому, когда вы хотите добавить элемент в список, вы просто это делаете, поскольку параметры функции типа interface{} принимают значения coo любого типа. Но когда вы извлекаете значения из списка и что нужно работать с их реальными типами, вы должны либо набирать тип, либо на них переключаться типами - оба подхода - это просто разные способы сделать практически то же самое.

Вот пример, взятый из здесь:

package main

import ("fmt" ; "container/list")

func main() {
    var x list.List
    x.PushBack(1)
    x.PushBack(2)
    x.PushBack(3)

    for e := x.Front(); e != nil; e=e.Next() {
        fmt.Println(e.Value.(int))
    }
}

Здесь мы получаем значение элемента с помощью e.Value(), а затем вводим его как int тип исходного вставленного значения.

Вы можете читать утверждения типа и переключатели типов в "Эффективном ходу" или в любой другой вводной книге. В документации пакета container/list содержится сводка всех поддерживаемых списков методов.

Ответ 4

Обратите внимание, что фрагменты Go можно развернуть с помощью встроенной функции append(). Хотя для этого иногда требуется создать копию массива поддержки, это не произойдет каждый раз, так как Go будет превышать размер нового массива, давая ему большую емкость, чем сообщаемая длина. Это означает, что последующая операция добавления может быть выполнена без другой копии данных.

В то время как у вас больше копий данных, чем с эквивалентным кодом, реализованным со связанными списками, вы устраняете необходимость выделения элементов в списке по отдельности и необходимости обновления указателей Next. Для многих применений реализация на основе массива обеспечивает лучшую или достаточно хорошую производительность, поэтому это подчеркивается на языке. Интересно, что стандартный тип list Python также поддерживается массивом и имеет аналогичные характеристики производительности при добавлении значений.

Тем не менее, есть случаи, когда связанные списки являются лучшим выбором (например, когда вам нужно вставлять или удалять элементы из начала/середины длинного списка), и поэтому предоставляется стандартная реализация библиотеки. Я предполагаю, что они не добавили каких-либо специальных языковых функций для работы с ними, потому что эти случаи встречаются реже, чем те, где используются срезы.

Ответ 5

Если срез слишком часто обновляется (удалять, добавлять элементы в случайных местоположениях), смежность памяти срезов будет иметь отличное соотношение кэш-памяти по сравнению со связанными списками.

Ответ 6

От: https://groups.google.com/forum/#!msg/golang-nuts/mPKCoYNwsoU/tLefhE7tQjMJ

It depends a lot on the number of elements in your lists,
 whether a true list or a slice will be more efficient
 when you need to do many deletions in the 'middle' of the list.

#1
The more elements, the less attractive a slice becomes. 

#2
When the ordering of the elements isn't important,
 it is most efficient to use a slice and
 deleting an element by replacing it by the last element in the slice and
 reslicing the slice to shrink the len by 1
 (as explained in the SliceTricks wiki)

Так
использовать срез
1. Если порядок элементов в списке не важен, вам нужно удалить, просто используйте List swap для удаления элемента с последним элементом и повторного среза на (length-1)
2. когда элементы больше (что еще больше означает)

There are ways to mitigate the deletion problem --
e.g. the swap trick you mentioned or
just marking the elements as logically deleted.
But it impossible to mitigate the problem of slowness of walking linked lists.

Так
использовать срез
1. Если вам нужна скорость в обход