Устанавливает структуру данных в Голанге

69

Мне действительно нравится golang golang, но может кто-нибудь объяснить, в чем смысл того, что разработчики оставили базовую структуру данных, такую ​​как наборы из стандартной библиотеки?

Cobie
источник
8
Язык на самом деле называется Go, а не Golang
Jozefg
92
Но «Голанг» более доступен для поиска
Мэтт
18
Способ более поиска. Погуглив "go set" возвращает изображения деревянной доски с черно-белыми кусочками.
Даг Ричардсон

Ответы:

68

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

Честно говоря, я думаю, что это тоже немного упущение, однако, глядя на Perl, история точно такая же. В Perl вы получаете списки и хеш-таблицы, в Go вы получаете массивы, фрагменты и карты. В Perl вы обычно используете хеш-таблицу для любых проблем, связанных с набором, то же самое применимо к Go.

пример

чтобы подражать множеству целых в Go, мы определяем карту:

set := make(map[int]bool)

Добавить что-либо так же просто, как:

i := valueToAdd()
set[i] = true

Удалить что-то просто

delete(set, i)

И потенциальная неловкость этой конструкции легко абстрагируется:

type IntSet struct {
    set map[int]bool
}

func (set *IntSet) Add(i int) bool {
    _, found := set.set[i]
    set.set[i] = true
    return !found   //False if it existed already
}

И удалить и получить можно определить аналогично, у меня есть полная реализация здесь . Основным недостатком здесь является тот факт, что у Go нет дженериков. Однако это можно сделать interface{}в том случае, если вы приведете результаты get.

jozefg
источник
3
Вот моя немного пересмотренная версия с методами Contains и Size: play.golang.org/p/tDdutH672-
Rick-777
19
Вместо map[int]boolодного можно использовать map[int]struct{}вместо. Я предпочитаю последнее.
pepper_chico
20
map[int]struct{}.. struct{}занимает 0 байтов.
Бупати Раджа
2
github.com/fatih/set - это моя реализация на основе карт и пустых структур. Это потокобезопасный и имеет простой API.
Фатих Арслан
6
С map[int]struct{}вами нельзя сделать, if mymap["key"] {чтобы проверить на членство. Google рекомендует использоватьbool (поиск «Набор может быть реализован»).
Тимммм
3

Я думаю, что это связано с golangпростотой. setы стать очень полезным с difference, intersection, union, issubsetи так далее .. методы. Возможно, golangкоманда почувствовала, что это слишком много для одной структуры данных. Но в противном случае «тупой набор» , который только имеет add, containsи removeможет быть легко тиражироваться с , mapкак объяснено @jozefg.

Akavall
источник
я не согласен. набор в основном используется для проверки членства и семантики уникальности. реализация набора была бы совершенно полезна без этих методов. При этом они также тривиальны для реализации.
Седат Капаноглу
2

Предыдущий ответ работает ТОЛЬКО ЕСЛИ ключ встроенного типа. Чтобы дополнить предыдущий ответ, вот способ реализовать набор, элементы которого являются пользовательскими типами:

package math

// types

type IntPoint struct {
    X, Y int
}

// set implementation for small number of items
type IntPointSet struct {
    slice []IntPoint 
}

// functions

func (p1 IntPoint) Equals(p2 IntPoint) bool {
    return (p1.X == p2.X) && (p1.Y == p2.Y)
}

func (set *IntPointSet) Add(p IntPoint) {
    if ! set.Contains(p) {
        set.slice = append(set.slice, p)
    }
}

func (set IntPointSet) Contains(p IntPoint) bool {
  for _, v := range set.slice {
    if v.Equals(p) {
      return true
    }
  }
  return false
}

func (set IntPointSet) NumElements() int {
    return len(set.slice)
}

func NewIntPointSet() IntPointSet {
  return IntPointSet{(make([]IntPoint, 0, 10))}
}
amahfouz
источник
8
«работает ТОЛЬКО ЕСЛИ ключ встроенного типа» неправильно . type mySet map[IntPoint]boolработает на отлично Все, что требуется от типа ключа, используемого в карте, - это наличие ==и!= . Равенство типов структур хорошо определено, ваш Equalsметод должен быть справедливым p1 == p2.
Дейв С
1
Это правда, что равенство для структур четко определено, но если структура содержит карты или фрагменты в виде полей, они будут сравниваться по ссылке, а не по значению. Это может быть не то, что вы хотите.
Хаим-Лейб Халберт
1
С этим решением я не согласен, потому что Containsзанимает линейное время, но aMap[]требует постоянного времени, независимо от количества членов. Лучшим решением было бы создать внутри себя уникальный ключ, основанный на содержимом каждого члена, и использовать запросы постоянного времени, которые mapпредоставляет тип. Существуют и более быстрые решения, которые учитывают поведение кэша и т. Д.
Хаим-Лейб Халберт