golang por que não temos uma estrutura de dados definida [fechado]

129

Estou tentando resolver o exercício "O idioma de programação go" 1.4, que exige que eu tenha um conjunto. Posso criar um tipo de conjunto, mas por que o idioma não vem com um? como vieram do google, onde a goiaba também se originou, por que os designers de idiomas não optaram por adicionar suporte a estruturas de dados fundamentais? por que forçar seus usuários a criar suas próprias implementações para algo tão básico como um conjunto?

data-structures go set anjanb
fonte
11
hmmm. querendo saber por que os votos negativos? Eu sou do mundo java, onde tivemos um set quase desde o começo, mesmo sem genéricos. Então, acho esse comportamento um pouco bizarro
anjanb

Respostas:

83

Em parte, porque o Go não possui genéricos (então você precisaria de um tipo de conjunto para cada tipo ou recuaria na reflexão, o que é bastante ineficiente).

Em parte, porque se tudo o que você precisa é "adicionar / remover elementos individuais a um conjunto" e "relativamente eficiente em termos de espaço", você pode obter um pouco disso simplesmente usando a map[yourtype]bool(e defina o valor truepara qualquer elemento no conjunto ) ou, para obter mais eficiência de espaço, você pode usar uma estrutura vazia como valor e usar _, present = the_setoid[key]para verificar a presença.

Vatine
fonte
1
Além disso, parece estar no espírito de Go simplesmente escrever em seu próprio código, "inserindo" o conjunto em outro código ou defina seu próprio tipo de conjunto, quando necessário. De qualquer forma, usar, por exemplo, um std :: set <T> em C ++ está sempre acontecendo como parte de uma implementação de função ou da implementação de alguma outra estrutura de dados. Portanto, basta implementar essa outra estrutura de dados diretamente usando mapas e fatias e quaisquer outros componentes necessários, mas sem nenhum conjunto interno. Cada uso de um conjunto está indo para usá-lo de forma ligeiramente diferente de qualquer maneira :)
Bjarke Ebert
1
Mas geralmente você realmente não precisa de um conjunto <Foo> por si só, usa um conjunto <Foo> como parte da implementação de algo maior. Eu já vi toneladas de código em que as coisas que você precisa fazer para incluir um componente "reutilizável" são muito piores do que apenas evitar a necessidade. Então, aqui temos um conjunto <Foo>, que funciona lá, precisa de um conjunto <Bar>, oops, ainda temos covariância, ou que tal criar um WrapperFactory para fazer essa coisa parecer com essa coisa etc. Talvez essa outra função realmente precisa de uma interface que possa verificar a associação, por isso não envie um conjunto <Foo>.
Bjarke Ebert
42
Portanto, se ele não possui genéricos, como o mapa 'genérico' é implementado?
Fermin Silva 26/05
26
Observe que se você deseja salvar bytes, pode usar em map[T]struct{}vez de map[T]bool.
Emersion 24/05
4
Dê uma olhada em emersion.fr/blog/2017/sets-in-go
emersion
69

Um dos motivos é que é fácil criar um conjunto a partir do mapa:

s := map[int]bool{5: true, 2: true}
_, ok := s[6] // check for existence
s[8] = true // add element 
delete(s, 2) // remove element

União

s_union := map[int]bool{}
for k, _ := range s1{
    s_union[k] = true
}
for k, _ := range s2{
    s_union[k] = true
}

Interseção

s_intersection := map[int]bool{}
for k,_ := range s1 { 
  if s2[k] {
    s_intersection[k] = true
  }
}

Não é realmente difícil implementar todas as outras operações definidas.

Salvador Dalí
fonte
10
Verificar a existência é simplesmente indexar o mapa. Como, se não estiver, o valor zero (que é false) indica isso corretamente. Não é necessário o idioma vírgula-ok para o teste.
icza 01/12/2015
2
A implementação para interseção é semelhante à diferença.
Musiphil
1
@Kittsil obrigado. Atualizada.
Salvador Dali
34
É mais ideal usar em map[int]struct{}vez de bool, porque uma estrutura vazia ocupa 0 bytes na memória. Eu escrevi recentemente uma essência para este gist.github.com/bgadrian/cb8b9344d9c66571ef331a14eb7a2e80
BG Adrian
13
Isso não é tão fácil. Ter que escrever esse código em todos os lugares em que você precisa usar um conjunto me parece ridículo hoje em dia. O suporte a coleções deve ser fornecido em qualquer idioma. Pense que uma resposta melhor é que o Go ainda não é tão maduro. Tenho certeza de que haverá bibliotecas para cobrir isso em breve.
Stef
5

Como escreveu Vatine: Como o go go carece de genéricos, ele deveria fazer parte da linguagem e não da biblioteca padrão. Para isso, você teria que poluir o idioma com as palavras-chave definidas, união, interseção, diferença, subconjunto ...

A outra razão é que não está claro qual é a implementação "correta" de um conjunto:

  1. Existe uma abordagem funcional:

    func IsInEvenNumbers(n int) bool {
    if n % 2 == 0 {
        return true
    }
   return false
}

Este é um conjunto de todas as ints pares. Possui uma pesquisa muito eficiente e a união, interseção, diferença e subconjunto podem ser facilmente realizados pela composição funcional.

  1. Ou você faz uma abordagem semelhante à que Dali mostrou.

Um mapa não tem esse problema, pois você armazena algo associado ao valor.

0x434D53
fonte
2
Para lidar com conjuntos de integração, Pascal sobrecarrega vários operadores binários (dois argumentos): +para união, -diferença, *interseção, <=subconjunto, >=superconjunto, =igualdade, <>desigualdade e inassociação. Portanto, no Go, seria apenas uma única nova palavra-chave - in. Por outro lado, os conjuntos internos de Pascal funcionam apenas em "ordinais" - ou seja, qualquer tipo que tenha uma representação subjacente de um valor inteiro de algum tamanho.
Kostix
9
O fato de haver várias maneiras de implementar um conjunto não impediu muitos outros idiomas de fornecê-los.
augurar
@ kostix: Go pode até usar a sintaxe s[key](como se sfosse a map[T]bool) em vez de key in s.
Musiphil
2
Alguma razão para não voltar simplesmente n % 2 == 0?
João Andrade
4

Outra possibilidade é usar conjuntos de bits, para os quais existe pelo menos um pacote ou você pode usar o pacote grande embutido . Nesse caso, basicamente você precisa definir uma maneira de converter seu objeto em um índice.

Will Fitzgerald
fonte
1
Devo observar que escrevi a versão original do pacote de bits mencionado acima.
Will Fitzgerald