Conjuntos em Go 1.28

Porque conjuntos são muito úteis, e como serão as coleções Set no Go 1.28

Transcript

1. Conjuntos em Go 1.28 Luciano Ramalho luciano@ramalho.org github/codeberg: @ramalho
2. Meu melhor trabalho (até hoje): Fluent Python Publicado em 9 idiomas, 2 edições (2015, 2022) • Python idiomático, explorando o design da linguagem e sua biblioteca padrão •
3. Luciano Ramalho • Membro da ação Bartz v. Anthropic – • • • E assinante do Claude Code Principal consultant na Thoughtworks (2015-2023) Revisor técnico da edição brasileira do GOPL (2016) Co-fundador do Garoa Hacker Clube (desde 2010)
4. Exemplo: unigo
5. unigo: um exemplo simples e prático • Inspirado no comando uniq, que elimina linhas duplicadas • Diferença importante: • – uniq só elimina duplicatas que ocorrem em linhas sucessivas (necessário fazer sort antes) – unigo elimina todas as linhas duplicadas e preserva a ordem relativa Usando uma busca linear, unigo é inviável: custo O(n²)
7. unigo em O(n)
8. Padrão tradicional: map[string]struct{} 1 // writeUnique copies input to output, 2 // keeping only the first occurrence of each line. 3 func writeUnique(input io.Reader, output io.Writer) error { 4 lines := bufio.NewScanner(input) 5 buf := bufio.NewWriter(output) 6 7 seen := make(map[string]struct{}) 8 for lines.Scan() { 9 line := lines.Text() 10 if _, dup := seen[line]; !dup { // look it up... 11 seen[line] = struct{}{} // ...then store it 12 fmt.Fprintln(buf, line) 13 } 14 } 15 16 // Report read error if it happens; flush always 17 return cmp.Or(lines.Err(), buf.Flush()) 18 }
9. Outro padrão tradicional: map[string]bool 1 // writeUnique copies input to output, 2 // keeping only the first occurrence of each line. 3 func writeUnique(input io.Reader, output io.Writer) error { 4 lines := bufio.NewScanner(input) 5 buf := bufio.NewWriter(output) 6 7 seen := make(map[string]bool) 8 for lines.Scan() { 9 line := lines.Text() 10 if !seen[line] { // zero value false means "not seen"... 11 seen[line] = true // ...then store it 12 fmt.Fprintln(buf, line) 13 } 14 } 15 16 // Report read error if it happens; flush always 17 return cmp.Or(lines.Err(), buf.Flush()) 18 }
10. Futuro: set.Set[string] 1 // writeUnique copies input to output, 2 // keeping only the first occurrence of each line. 3 func writeUnique(input io.Reader, output io.Writer) error { 4 lines := bufio.NewScanner(input) 5 buf := bufio.NewWriter(output) 6 7 seen := make(set.Set[string]) 8 for lines.Scan() { 9 line := lines.Text() 10 if seen.Insert(line) { // true when set changed 11 fmt.Fprintln(buf, line) 12 } 13 } 14 15 // Report read error if it happens; flush always 16 return cmp.Or(lines.Err(), buf.Flush()) 17 }
11. // unigo-map seen := make(map[string]struct{}) for lines.Scan() { line := lines.Text() if _, dup := seen[line]; !dup { seen[line] = struct{}{} fmt.Fprintln(buf, line) } } As três variantes // unigo-mapbool seen := make(map[string]bool) for lines.Scan() { line := lines.Text() if !seen[line] { seen[line] = true fmt.Fprintln(buf, line) } } // unigo-set seen := make(set.Set[string]) for lines.Scan() { line := lines.Text() if seen.Insert(line) { fmt.Fprintln(buf, line) } }
13. O gargalo de von Neumann
15. Ecos do passado • Em 2018 apresentei “Prática de Conjuntos” na GopherCon Brasil: – • "Porquê e como implementar um tipo Set em Go" Esta é uma atualização profunda, abordando os tipos Set no pacote de coleções do Go 1.28 vintage 2018
17. vintage 2018
18. vintage 2018
19. vintage 2023 Desde Desde oo Go Go 1.21: 1.21: Contains[S Contains[S ~[]E, ~[]E, EE comparable](s comparable](s S, S, vv E) E) bool bool
24. Conjuntos e Lógica
25. Ainda não descobriram um ramo da matemática que não possa ser formalizado pela teoria dos conjuntos. Thomas Forster Logic Induction and Sets p. 167
30. Álgebra de conjuntos no mundo real
31. Operações da álgebra de conjuntos • Essencial: e ∈ S • Muito úteis na prática: – S ∩ Z (interseção) – S ∪ Z (união) – S ∖ Z (diferença) – S ⊆ Z (subconjunto) • Popular: ContainsAll (todos os elementos de S pertencem a Z)
32. Implementação de conjuntos • Invariante: elementos devem ser únicos – • e ∈ S (teste de pertencimento): – • Elementos precisam ser comparáveis e hashable Espera-se que seja O(1) em uma implementação razoável O teste de pertencimento em tempo constante viabiliza ganhos de desempenho importantes ao implementar as demais operações
33. vintage 2018
34. APIs limitadas APIs abrangentes vintage 2018
35. APIs limitadas • A maioria dos métodos opera com um elemento de cada vez – ex.: incluir/remover elemento, iteração • • Poucos ou nenhum método processa conjuntos inteiros (interseção, união etc.) Exemplo do Gargalo de von Neumann
36. Evolução das APIs de sets • • Linguagens incorporando mais operações da álgebra de conjuntos Exemplo: ECMAScript 2025 Set.intersection, Set.union, Set.difference, Set.symmetricDifference, Set.isSubsetOf, Set.isSupersetOf, Set.isDisjointFrom
37. A proposta collections para o Go 1.28
38. O grupo de trabalho Go Collections foi formado no final de 2025 com o objetivo de trazer estruturas de dados de coleção comuns para a biblioteca padrão, norteado pelos princípios familiares de pragmatismo e simplicidade do Go. … Este trabalho busca adicionar vários dos tipos de dados mais importantes à biblioteca padrão e estabelecer convenções para suas APIs e para as APIs de futuras adições. Alan Donovan Go issue #80590
39. Go Collections Working Group • Jonathan Amsterdam • Alan Donovan • Robert Griesemer • Daniel Martí • Roger Peppe • Keith Randall • Ian Lance Taylor 👋
40. proposal: container/...: generic collection types • ☂ Umbrella issue https://github.com/golang/go/issues/80590 • 6 novos tipos concretos de coleções • 1 nova interface Hasher (já no Go 1.27) • 3 novas interfaces abstratas para coleções em geral, sets, e maps
41. Os 7 componentes propostos 1)hash/maphash.Hasher interface padrão que suporta funções de hash customizadas e relações de equivalência para tipos de dados arbitrários (definida no Go 1.27) 2)container/hash.Map[K,V] um map baseado em hash que usa funções de hash customizadas. 3)container/hash.Set[T] a um conjunto baseado em Set, na mesma linha do hash.Map 4)container/heap/v2.Heap uma API genérica de heap binário para substituir o heap existente na biblioteca padrão (que é difícil de usar).
42. Os 7 componentes propostos 5)container/set.Set[T] representado de forma transparente como map[T]struct{}, suportando operações de conjunto usuais, como União e Interseção. "Esperamos que se torne o conjunto padrão na maioria das novas APIs em Go." 6)container/mapset funções auxiliares (união, interseção, etc.) para manipular conjuntos legados como conjuntos em código existente cuja API não pode ser alterada. set.Set encapsula essa API. 7)container/ordered.Map[K,V] um mapa que preserva a ordem de inserção das chaves.
43. Source tree (WIP) • • • • • • • • • • • • • • Open Cls (unmerged) identified by #issue • • • • • • • • • • • • • go/src/ ├── hash/ │ └── maphash/ │ └── hasher.go ├── maps/ │ └── maps.go ├── container/ │ ├── container_test.go │ ├── set/ │ │ └── set.go │ ├── mapset/ │ │ └── mapset.go │ ├── hash/ │ │ ├── map.go │ │ └── set.go │ ├── heap/ │ │ ├── heap.go │ │ └── v2/ │ │ └── heap.go │ ├── list/ │ │ └── list.go │ ├── ordered/ │ │ └── ordered.go │ └── ring/ │ └── ring.go │ = Hasher interface, in Go 1.27 (#70471) ★ added Identical (#78456), used by mapset ★✚ abstract interfaces (unexported) ★✚ the new canonical set (#69230) ★✚ helpers for map-based sets (#77052) ★✚ hash.Map, uses maphash.Hasher (#69559) ★✚ hash.Set, same approach (#80584) = existing, pre-generics ? generic, more ergonomic Heap (#77397) = existing ? tree-based ordered.Map/Set (#60630) = existing
44. • • • • • • • • • • • • • • • go/src/ ├── hash/ │ └── maphash/ │ └── hasher.go ├── maps/ │ └── maps.go ├── container/ ├── container/ │ ├── container_test.go │ ├── set/ │ │ └── set.go │ ├── mapset/ │ │ └── mapset.go │ ├── hash/ │ │ ├── map.go │ │ └── set.go Interfaces abstratas Não exportadas, mas apresentadas como modelos para novos tipos de coleções
45. Comentário em container/container_test.go // The following interfaces define the abstract data types for // collections in Go. They are expressed using F-bounded polymorphic // interfaces to achieve covariant parameter/result specialization, // and may be used as constraint types in generic functions. // // These interfaces are not yet published, but may be included in a // future Go release once we have experience of whether these methods // are necessary and sufficient.
46. Comentário em container/container_test.go // As interfaces a seguir definem os tipos abstratos de dados para // coleções em Go. Elas são expressas utilizando interfaces polimórficas // com F-bound (F-bounded polymorphism) para permitir a especialização // covariante de parâmetros e resultados, e podem ser usadas como // restrições de tipo em funções genéricas. // // Essas interfaces ainda não foram publicadas, mas podem ser incluídas // em uma versão futura do Go, assim que tivermos experiência suficiente // para determinar se esses métodos são necessários e suficientes.
47. A interface _AbstractSet • • • • • • • • • • • • • • • • • • • • • 1 // _AbstractSet models a set S of elements E, 2 // such as *hash.Set, or set.Set. 3 type _AbstractSet[E any, S _AbstractSet[E, S]] interface { 4 _AbstractCollection[E, S] 5 6 Insert(E) bool 7 InsertAll(iter.Seq[E]) bool 8 Equal(S) bool 9 All() iter.Seq[E] 10 Delete(E) bool 11 DeleteAll(iter.Seq[E]) bool 12 DeleteFunc(func(E) bool) bool 13 Intersection(S) S 14 IntersectionWith(S) 15 Intersects(S) bool 16 Union(S) S 17 UnionWith(S) 18 Difference(S) S 19 DifferenceWith(S) 20 SymmetricDifference(S) S 21 SymmetricDifferenceWith(S) 22 }
48. 1 // _AbstractSet models a set S of elements E, 2 // such as *hash.Set, or set.Set. 3 type _AbstractSet[E any, S _AbstractSet[E, S]] interface { 4 _AbstractCollection[E, S] 5 6 Insert(E) bool 7 InsertAll(iter.Seq[E]) bool 8 Equal(S) bool 9 All() iter.Seq[E] 10 Delete(E) bool 11 DeleteAll(iter.Seq[E]) bool 12 DeleteFunc(func(E) bool) bool 13 Intersection(S) S 14 IntersectionWith(S) 15 Intersects(S) bool 16 Union(S) S 17 UnionWith(S) 18 Difference(S) S 19 DifferenceWith(S) 20 SymmetricDifference(S) S 21 SymmetricDifferenceWith(S) 22 } 👈 👈 devolvem bool para 👈 👈 indicar 👈 mudança
49. 1 // _AbstractSet models a set S of elements E, 2 // such as *hash.Set, or set.Set. 3 type _AbstractSet[E any, S _AbstractSet[E, S]] interface { 4 _AbstractCollection[E, S] 5 6 Insert(E) bool 7 InsertAll(iter.Seq[E]) bool 8 Equal(S) bool 9 All() iter.Seq[E] 10 Delete(E) bool 11 DeleteAll(iter.Seq[E]) bool 12 DeleteFunc(func(E) bool) bool 13 Intersection(S) S 14 IntersectionWith(S) 15 Intersects(S) bool 16 Union(S) S 17 UnionWith(S) 18 Difference(S) S 19 DifferenceWith(S) 20 SymmetricDifference(S) S 21 SymmetricDifferenceWith(S) 22 } 👈 operações da álgebra 👈 de conjuntos 👈 👈 devolvem um novo Set
50. 1 // _AbstractSet models a set S of elements E, 2 // such as *hash.Set, or set.Set. 3 type _AbstractSet[E any, S _AbstractSet[E, S]] interface { 4 _AbstractCollection[E, S] 5 6 Insert(E) bool 7 InsertAll(iter.Seq[E]) bool 8 Equal(S) bool 9 All() iter.Seq[E] 10 Delete(E) bool 11 DeleteAll(iter.Seq[E]) bool 12 DeleteFunc(func(E) bool) bool 13 Intersection(S) S 14 IntersectionWith(S) 15 Intersects(S) bool 16 Union(S) S 17 UnionWith(S) 18 Difference(S) S 19 DifferenceWith(S) 20 SymmetricDifference(S) S 21 SymmetricDifferenceWith(S) 22 } 👈 👈 👈 modificam o próprio set (in-place)
51. _AbstractSet: declaração auto-referente! // _AbstractSet models a set S of elements E, // such as *hash.Set, or set.Set. type _AbstractSet[E any, S _AbstractSet[E, S]] interface { 🙀
52. A classe Enum é, na verdade, uma classe genérica definida como Enum<T extends Enum<T>>. Essa definição circular é, provavelmente, a definição de tipo genérico mais intrigante que você encontrará. Especialistas em teoria de tipos nos garantem que isso é perfeitamente válido e significativo — e que simplesmente não devemos pensar muito a respeito —, pelo que somos gratos. Ken Arnold, James Gosling, David Holmes The Java Programming Language, 4th Edition Citado em Generics Considered Harmful por Ken Arnold (https://tgo.li/25)
53. Uma boa explicação informal • Polimorfismo F-Bounded: Builders com Segurança de Tipo em Java, por Pradeep Samuel (publicado em 9 de março de 2026) – Como uma restrição de tipo autorreferencial resolve um problema real de herança, por que o próprio Enum do Java utiliza esse mesmo truque e o que tudo isso significa na prática. https://www.fbounded.com/blog/f-bounded-polymorphism/
54. _AbstractSet é F-bounded // _AbstractSet models a set S of elements E, // such as *hash.Set, or set.Set. type _AbstractSet[E any, S _AbstractSet[E, S]] interface { • • • Esta é a notação em Go para uma interface polimórfica F-bounded Fornece a variável de tipo S para as assinaturas de operações genéricas da álgebra de conjuntos Limita o tipo concreto de S a um subtipo de _AbstractSet
55. 1 // _AbstractSet models a set S of elements E, 2 // such as *hash.Set, or set.Set. 3 type _AbstractSet[E any, S _AbstractSet[E, S]] interface { 4 _AbstractCollection[E, S] 5 6 Insert(E) bool 7 InsertAll(iter.Seq[E]) bool 8 Equal(S) bool 9 All() iter.Seq[E] 10 Delete(E) bool 11 DeleteAll(iter.Seq[E]) bool 12 DeleteFunc(func(E) bool) bool 13 Intersection(S) S 14 IntersectionWith(S) 15 Intersects(S) bool 16 Union(S) S 17 UnionWith(S) 18 Difference(S) S 19 DifferenceWith(S) 20 SymmetricDifference(S) S 21 SymmetricDifferenceWith(S) 22 } 👈 usos da variável S 👈 👈 como tipo de retorno 👈
56. _AbstractMap também é F-bounded 1 // _AbstractMap models a mapping M from keys K to values V, 2 // such as *hash.Map or *ordered.Map. 3 type _AbstractMap[K, V any, M _AbstractMap[K, V, M]] interface { 4 _AbstractCollection[K, M] 5 6 Set(K, V) (V, bool) 7 SetAll(iter.Seq2[K, V]) bool 8 Get(K) (V, bool) 9 At(K) V 10 All() iter.Seq2[K, V] 11 Keys() iter.Seq[K] 12 Values() iter.Seq[V] 13 Delete(K) (V, bool) 14 DeleteAll(iter.Seq[K]) bool 15 DeleteFunc(func(K, V) bool) bool 16 }
57. _AbstractCollection, a interface-base 1 // _AbstractCollection models a collection C of elements E, 2 // such as *hash.Map, *hash.Set, *ordered.Map, or set.Set. 3 type _AbstractCollection[E any, C _AbstractCollection[E, C]] interface { 4 Clear() 5 Clone() C 6 Contains(E) bool 7 ContainsAll(iter.Seq[E]) bool 8 Len() int 9 String() string 10 } Tanto _AbstractSet como _AbstractMap embutem _AbstractCollection
58. Abaixo das interfaces em container_test.go // These types define the fundamental operations that need to be // implemented by all set and map types. Their naming, signature, and // semantic conventions should be followed wherever possible when // defining new collection types. // ... // // Map.Set should replace an existing entry with an equivalent key. // This follows the built-in map: https://go.dev/play/p/pkH8kkFTuEg. // // The "plural" functions {Contains,Delete,Insert,Set}All are // sufficiently important that they belong as methods; they // also compute a convenient bool result.
59. Abaixo das interfaces em container_test.go // Estes tipos definem as operações fundamentais que precisam ser // implementadas por todos os tipos de conjunto (set) e mapa (map). // Suas convenções de nomenclatura, assinatura e semântica devem ser // seguidas sempre que possível ao definir novos tipos de coleção. // ... // // Map.Set deve substituir uma entrada existente que tenha uma chave // equivalente. Isso segue o comportamento do mapa nativo: // https://go.dev/play/p/pkH8kkFTuEg. // // As funções "plurais" {Contains,Delete,Insert,Set}All são // importantes o suficiente para serem implementadas como métodos; // elas também retornam um resultado booleano útil.
60. Testes estáticos container_test.go 1 // -- conformance -2 3 // This is a static compilation test of various symmetries, 4 // expressed using F-bounded polymorphic interfaces to 5 // achieve covariant parameter/result specialization. 6 7 var _ _AbstractSet[int, set.Set[int]] = make(set.Set[int]) 8 9 var _ _AbstractSet[int, *hash.Set[int]] = new(hash.Set[int]) Este teste verifica que o compilador aceita atribuir set.Set e hash.Set a uma variável _ do tipo _AbstractSet
61. Função genérica em container_test.go 1 // Take removes and returns an arbitrary element from a set. 2 // It returns zero if the set was empty. 3 func Take[S _AbstractSet[E, S], E any](set S) (e E, found bool) { 4 for e = range set.All() { 5 found = true 6 set.Delete(e) // may fail for NaN 7 break 8 } 9 return 10 } Take devolve um elemento do tipo E (declarado em _AbstractSet[E, S]) e um bool
62. Implementação de set.Set[T]
63. • • • • • • • • • • • • • • • go/src/ ├── hash/ │ └── maphash/ │ └── hasher.go ├── maps/ │ └── maps.go ├── container/ ├── container/ │ ├── container_test.go │ ├── set/ │ │ └── set.go │ ├── mapset/ │ │ └── mapset.go │ ├── hash/ │ │ ├── map.go │ │ └── set.go set.Set[T] Veja o código-fonte da proposta em /vendored no repositório GitHub ramalho/sets-in-go
64. set.Set delega tudo para funções de mapset 1 package set 2 3 import ( 4 "mapset" // proposed mapset in Go 1.28 5 "iter" 6 "maps" 7 ) 8 9 // A Set[E] is a set of elements of type E. 10 type Set[E comparable] map[E]struct{} 11 12 // Collect creates a new set containing the elements of the sequence. 13 func Collect[E comparable](seq iter.Seq[E]) Set[E] { 14 return Set[E](mapset.Collect(seq)) 15 } Métodos de uma linha que apenas invocam funções de mapset
65. • • • • • • • • • • • • • • • go/src/ ├── hash/ │ └── maphash/ │ └── hasher.go ├── maps/ │ └── maps.go ├── container/ ├── container/ │ ├── container_test.go │ ├── set/ │ │ └── set.go │ ├── mapset/ │ │ └── mapset.go │ ├── hash/ │ │ ├── map.go │ │ └── set.go mapset.go funções para usar um mapa legado como um conjunto
66. mapset.go não define nenhum tipo com nome • • • • • • • • • • • • • • • • • • 1 package mapset 2 3 import ( 4 "iter" 5 ) 6 7 // Collect returns a new set containing the elements of the sequence. 8 func Collect[K comparable](seq iter.Seq[K]) map[K]struct{} { 9 return collect[K, struct{}](seq) 10 } 11 12 /// ... 13 14 func collect[K comparable, V bool | struct{}](seq iter.Seq[K]) map[K]V { 15 x := make(map[K]V) 16 InsertAll(x, seq) 17 return x 18 }
67. set.Collect versus set.Of 1 // Collect creates a new set containing the elements of the sequence. 2 func Collect[E comparable](seq iter.Seq[E]) Set[E] { 3 return Set[E](mapset.Collect(seq)) 4 } 5 6 // Of creates a new set containing the elements of the sequence. 7 func Of[E comparable](elems ...E) map[E]struct{} { 8 return Set[E](mapset.Of(elems...)) 9 } • • set.Collect recebe iter.Set[E]; set.Of recebe ...E set.Collect devolve Set[E]; set.Of devolve map[E]struct{} – Sinal de WIP! (trabalho em andamento)
68. Implementation of mapset.Collect 1 // Collect returns a new set containing the elements of the sequence. 2 func Collect[K comparable](seq iter.Seq[K]) map[K]struct{} { 3 return collect[K, struct{}](seq) 4 } 5 6 // CollectBool returns a new set containing the elements of the sequence. 7 // The map values are all "true". 8 func CollectBool[K comparable](seq iter.Seq[K]) map[K]bool { 9 return collect[K, bool](seq) 10 } 11 12 func collect[K comparable, V bool | struct{}](seq iter.Seq[K]) map[K]V { 13 x := make(map[K]V) 14 InsertAll(x, seq) 15 return x 16 }
69. Implementação de mapset.Insert{All} 1 // Insert adds elem element to the set. 2 // If the set values are boolean, the value 'true' is used. 3 // It reports whether len(x) changed. 4 func Insert[M ~map[K]V, K comparable, V bool | struct{}](x M, elem K) bool { 5 pre := len(x) 6 insert(x, elem) 7 return len(x) != pre 8 } 9 10 // InsertAll adds each element of the addenda sequence to the set. 11 // If the set values are boolean, the value 'true' is used. 12 // It reports whether len(x) changed. 13 func InsertAll[M ~map[K]V, K comparable, V bool | struct{}](x M, addenda iter.Seq[K]) bool { 14 pre := len(x) 15 for k := range addenda { 16 insert(x, k) 17 } 18 return len(x) != pre 19 }
70. Implementação de mapset.insert 1 func insert[M ~map[K]V, K comparable, V bool | struct{}](m M, k K) { 2 // Choose the distinguished "present" value (true or struct{}{}). 3 // This compiles to a load from .rodata. 4 var present V 5 if _, ok := any(present).(bool); ok { 6 present = any(true).(V) 7 } 8 9 // This is the canonical insertion operation. 10 // All maps created by this API use only the 11 // distinguished 'present' value for the result type. 12 m[k] = present 13 }
71. Implementação de set.Intersection{With} 1 // Intersection returns new map containing the intersection of x and y. 2 func (x Set[E]) Intersection(y Set[E]) Set[E] { 3 return mapset.Intersection(x, y) 4 } 5 6 /// ... 7 // -- in-place binary updates -8 9 // IntersectionWith updates x to the [Intersection] of x and y. 10 func (x Set[E]) IntersectionWith(y Set[E]) { 11 mapset.IntersectionWith(x, y) 12 }
72. Implementação de mapset.Intersection (1) 1 // Intersection returns new map containing the intersection of x and y. 2 func Intersection[MX ~map[K]VX, MY ~map[K]VY, K comparable, VX, VY bool | struct{}](x MX, y MY) MX { 3 z := make(MX) 4 5 if maps.Same(x, y) { 6 copy(z, x) 7 return z 8 } 9 10 // Iterate over the smaller of the two maps... continues...
73. Implementação de mapset.Intersection (2) 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 } // Iterate over the smaller of the two maps. if len(x) < len(y) { for k := range x { if Contains(y, k) { insert(z, k) } } } else { for k := range y { if Contains(x, k) { insert(z, k) } } } return z
74. Um pouco sobre hash.Set[T]
75. Porquê hash.Map[K,V] e hash.Set[V] • • • • Mapas nativos exigem chaves comparable (suportam operador ==) e uma função de hash embutida no runtime. Isso também impõe limitações aos valores em set.Set[V]. Os tipos container/hash.Map[K,V] e container/hash.Set[V] do Go 1.28 suportam testes de igualdade e funções de hash personalizados. Exemplos: – um conjunto de `big.Int`, – um mapa com chaves do tipo string que não diferenciam maiúsculas de minúsculas.
76. Algoritmo de hash table
77. Algortimo de hash table (simplificado) Python set
78. Set visível: exibe o estado da hash table Python
79. A tabela de hash começa com 8 buckets Python
80. Para inserir “Alice” • Computar o hash da string: 93a4771ea9a10722 • Determinar bucket (hash % 8 = 2) • Bucket vazio: colocar hash e valor no bucket Python
81. Inserir “Bob”: cai num bucket vazio Python
82. Inserir “Carla”: outro bucket vazio Python
83. Inserir “Diego”: mais um bucket vazio Python
84. Inserir “Elise”: bucket ocupado por “Diego” • Colisão de índice: índice aponta para um hash diferente – incrementar índice até encontrar um bucket vazio (com wrap) Python
85. Inserir “Fred” dispara a ampliação da tabela • • Buckets vazios ajudam a minimizar o número de colisões Ao reinserir os itens na nova tabela, a ordem pode mudar Python
86. v.union(iterável) • Cria um novo set com a união dos elementos de v mais os itens do iterável Python
87. Implementação proposta para hash.Set[T] no Go 1.28
88. • • • • • • • • • • • • • • • go/src/ ├── hash/ │ └── maphash/ │ └── hasher.go ├── maps/ │ └── maps.go ├── container/ ├── container/ │ ├── container_test.go │ ├── set/ │ │ └── set.go │ ├── mapset/ │ │ └── mapset.go │ ├── hash/ │ │ ├── map.go │ │ └── set.go Tipos Map e Set com suporte a hashers customizados
89. Como customizar Hash e Equal • • • Invariante: o hash de objetos iguais tem que ser igual Crie uma struct que implementa a interface maphash.Hasher introduzida no Go 1.27 em hash/maphash/maphash.go Passe a struct a um construtor. Propostos no Go 1.28: – hash/map.NewMap – hash/set.NewSet func NewSet[E any](hasher maphash.Hasher[E]) *Set[E] {
90. • • • • • • • • • • • • • • • go/src/ ├── hash/ │ └── maphash/ │ └── hasher.go ├── maps/ │ └── maps.go ├── container/ ├── container/ │ ├── container_test.go │ ├── set/ │ │ └── set.go │ ├── mapset/ │ │ └── mapset.go │ ├── hash/ │ │ ├── map.go │ │ └── set.go A interface Hasher
91. A interface maphash.Hasher no Go 1.27 1 package maphash 2 3 // A Hasher defines the interface between a hash-based container 4 // and its elements. It provides a hash function and an equivalence 5 // relation over values of type T, enabling those values to be 6 // inserted in hash tables and similar data structures. 7 // 8 // ...more than 100 lines of comments... 9 10 type Hasher[T any] interface { 11 Hash(*Hash, T) 12 Equal(x, y T) bool 13 }
92. Exemplo: Hasher case-insentive 1 // CaseInsensitive is a Hasher[string] whose 2 // equivalence relation ignores letter case. 3 type CaseInsensitive struct{} 4 5 func (CaseInsensitive) Hash(h *Hash, s string) { 6 h.WriteString(strings.ToLower(s)) 7 } 8 9 func (CaseInsensitive) Equal(x, y string) bool { 10 // (We avoid strings.EqualFold as it is not 11 // consistent with ToLower for all values.) 12 return strings.ToLower(x) == strings.ToLower(y) 13 }
93. Finalmentes
94. Conteúdo obrigatório sobre IA • • • Para desenvolvedores que utilizam agentes: O vocabulário preciso da álgebra de conjuntos é útil para instruir agentes, em qualquer linguagem de programação. Para programadores cidadãos: Aprender álgebra de conjuntos e o modelo relacional pode ser a melhor base para especificar sistemas para agentes Para todos: Exija seu tempo de volta. Tempo não é dinheiro; é o seu tempo de viver!
95. Vitasuco de conhecimento SAM ALTMAN: Vamos fazer um vitasuco Quem pode contribuir com frutas? TODOS: Legal, aqui estão minhas frutas! SAM ALTMAN: O vitasuco está pronto. Custa $ 20 o copo! TODOS: Mas você usou nossas frutas para fazê-lo! SAM ALTMAN: Não usei, não! Cadê suas frutas? Me mostre!
96. Não esqueça de Aaron Swartz • Co-criador do RSS e do Markdown • Co-fundador do Reddit • • • • Aaron foi preso em 2011 por baixar em massa artigos científicos do JSTOR Sua vida foi destruída pelo Departamento de Justiça dos EUA Ele não compartilhou os artigos com ninguém. O que iria fazer com eles? Talvez treinar um modelo?
97. Uma solução regulatória • Qualquer operador de LLM que se recuse a divulgar todas as fontes externas utilizadas no treinamento deve disponibilizar o modelo e seus pesos como código aberto. • Radical demais? • É apenas justo e bom senso. • Sem isso, acabou o copyright.
98. Pontos principais • • • • A álgebra de conjuntos oferece soluções simples e eficientes para tarefas comuns de processamento de dados. Conjuntos e outras coleções na futura versão Go 1.28 servem de base para o design de coleções genéricas. Os novos conjuntos e mapas baseados em Hasher são mais flexíveis, podem usar types arbitrárias como elementos ou chaves. O código-fonte de Go apresentado aqui ainda não foi integrado e pode sofrer alterações! Slides: https://speakerdeck.com/ramalho