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

Я новичок в Go и очень рад этому. Но на всех языках, с которыми я активно работал: Delphi, C #, C ++, Python - списки очень важны, потому что их можно динамически изменять размер, в отличие от массивов.

В Golang действительно есть list.Listструктура, но я вижу очень мало документации по ней - будь то в Go By Example или в трех моих книгах по Go - Summerfield, Chisnal и Balbaert - все они тратят много времени на массивы, срезы и затем переходите к картам. В примерах исходного кода я также практически не использую list.List.

Также кажется, что, в отличие от Python, RangeList не поддерживается - большой недостаток IMO. Я что-то упускаю?

Срезы, безусловно, хороши, но они все равно должны основываться на массиве с жестко заданным размером. Вот где на помощь приходит List. Есть ли способ создать массив / фрагмент в Go без жестко заданного размера массива? Почему список игнорируется?

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

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

Вот отрывок: -

Копировать

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]

Поп

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

От себя

a = append(a, x)

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

Я задал этот вопрос несколько месяцев назад, когда впервые начал изучать 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 для цикла. И во многих случаях синтаксис стиля коллекции C ++ должен использоваться со списками: push_backи т. Д.

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

  Одна из причин, по которой я отказался от Python и перешел на Go, - это слабость такого рода в системе типов Python, хотя Python утверждает, что он «строго типизирован» (IMO это не так). Go list.Listкажется чем-то вроде «дворняги», порожденным C ++ vector<T>и Python List(), и, возможно, немного неуместен в самом Go.

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

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

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

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

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

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

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тип исходного вставленного значения.

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

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

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

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

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

Выступление Скотта Мейера о важности кеширования .. https://www.youtube.com/watch?v=WDIkqP4JbkE

list.Listреализован в виде двусвязного списка. Списки на основе массивов (векторы в C ++ или фрагменты в golang) являются лучшим выбором, чем связанные списки в большинстве случаев, если вы не часто вставляете их в середину списка. Амортизированная временная сложность для добавления составляет O (1) как для списка массивов, так и для связанного списка, даже если список массивов должен увеличивать емкость и копировать существующие значения. Списки массивов имеют более быстрый произвольный доступ, меньший объем памяти и, что более важно, удобны для сборщика мусора из-за отсутствия указателей внутри структуры данных.

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

Это во многом зависит от количества элементов в ваших списках,
 будет ли более эффективным истинный список или срез
 когда вам нужно сделать много удалений в «середине» списка.

# 1
Чем больше элементов, тем менее привлекательным становится ломтик. 

# 2
Когда порядок элементов не важен,
 наиболее эффективно использовать срез и
 удаление элемента путем замены его последним элементом в срезе и
 перерезать ломтик, чтобы уменьшить линзу на 1
 (как описано в вики SliceTricks)

Поэтому
используйте срез
1. Если порядок элементов в списке не важен, и вам нужно удалить, просто
используйте List, замените элемент, который нужно удалить, последним элементом и повторно срежьте срез на (длина-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's impossible to mitigate the problem of slowness of walking linked lists.

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