20160321:TP:Go:Map:Objects

Introduction

Dans la session d'aujourd'hui nous allons travailler sur les hashmap et les objets.

Pour l'architecture nous prendrons les mêmes conventions que pour le TP de la semaine dernière, nous allons juste créer un nouveau répertoire tutorial20160321 sous le répertoire gowork/src.

Compter les mots

• Cible: tutorial20160321/word_count

Ce premier exercice consiste à utiliser une hashmap pour compter les mots d'un text.

Compter avec une hashmap

• écrire la fonction suivante:

/*
   WordCount(words) build a map of each distinct words appearing in the string
   slice words and attach the number of occurrences of each words.
*/
func WordCount(words []string) (wc map[string]int)

Ouvrir un fichier et le découper

Pour tester notre fonction, il nous faut un text déjà découper en mot. Pour ça nous allons charger le comptenu d'un fichier et le découper sur les espaces. Les fonctions suivantes nous serons fortement utiles (voir la doc … )

• os.Open(fname)
• ioutils.ReadAll(reader)
• strings.Fields(str)

• écrire la fonction suivante:

/*
   LoadFile(fname) opens the file fname, reads the content and split it into
   words.
*/
func LoadFile(fname string) (words []string)

Aller plus loin (bonus)

La fonction strings.Fields(str) divise notre string sur les caractères considérés comme des espaces mais elle ne gère pas la ponctuation. Vous pouvez essayer d'améliorer le découpage des mots en tenant compte de la ponctuation.

Tester

Pour tester, vous allez regrouper votre code dans un seul fichier sous la forme suivante:

package main
 
import (
	"fmt"
	"io/ioutil"
	"os"
	"strings"
)
 
func WordCount(words []string) (wc map[string]int) {
	/* FIX ME */
}
 
func LoadFile(fname string) (words []string) {
	/* FIX ME */
}
 
func main() {
	if len(os.Args) < 2 {
		panic("Missing argument")
	}
	wc := WordCount(LoadFile(os.Args[1]))
	fmt.Println(wc)
}

Objets et interfaces

• Cible: tutorial20160321/ordered_set

Pour cette partie nous allons implémenter des ensembles triés (ordered set.) Nous allons en profiter pour aborder 3 notions: les objets, les interfaces et les tests semi-automatiques de go (avec la commande go test).

Principe

Une implémentation simple d'ensembles triés s'appuie sur un vecteur trié accompagné des opérations classiques d'ajout, suppression et quelques opérations ensemblistes comme l'union ou la différence.

Les opérations d'ajout, de suppression et de recherche s'appuie sur une implémentation de la recherche par dichotomie (binary search) qui renvoie la position de l'élément s'il est présent et renvoie la position du plus petit élément plus grand que l'élément recherché sinon. Cette opération nous permet d'effectuer plus simplement et plus efficacement une insertion triée.

L'union s'appuie sur une variante de la fusion de tableaux triés qui n'ajoute qu'une fois les éléments présents dans les deux tableaux.

Structure globale

Nous allons créer 2 fichiers dans le package ordered_set

• set.go: le code concret de nos ensembles
• set_test.go: le code des tests (attention le suffix _test est important.)

Nous n'utiliserons pas de package main pour les tests, mais la commande go test qui va exploiter le code dans set_test.go pour ça.

Interface

Nous voulons des ensembles génériques qui ne soient pas spécifiques à un type donné. Pour ça nous allons utiliser la notion d'interface de Go.

Pour faire un ensemble trié, nous avons juste besoin d'une fonction qui dit si un élément est plus petit qu'un autre et une fonction qui dit si deux éléments sont égaux.

On définit donc l'interface suivante:

/*
OrderedType interface: describes comparable value
 
Comparable value provides:
  x.Less(y) returns true if x < y
  x.Equals(y) returns true if x == y
*/
type OrderedType interface {
	Less(OrderedType) bool
	Equals(OrderedType) bool
}

Maintenant, si on définit un type et qu'on lui attache les opérations Less et Equals il pourra être vu comme respectant cette interface.

Voici juste un petit exemple avec des entiers (issue de set_test.go.)

type OrderedInt int
 
func (x OrderedInt) Equals(y OrderedType) bool {
	switch y_ := y.(type) {
	case OrderedInt:
		return x == y_
	default:
		return false
	}
}
 
func (x OrderedInt) Less(y OrderedType) bool {
	switch y_ := y.(type) {
	case OrderedInt:
		return x < y_
	default:
		return false
	}
}

Notre implémentation d'ensemble travaillera donc avec un vecteur de OrderedType et utilisera les méthodes Less et Equals.

Implémentation

Voici le squelette pour le fichier set.go:

// ordered_set: a simple generic set implementation
package ordered_set
 
/*
OrderedType interface: describes comparable value
 
Comparable value provides:
  x.Less(y) returns true if x < y
  x.Equals(y) returns true if x == y
*/
type OrderedType interface {
	Less(OrderedType) bool
	Equals(OrderedType) bool
}
 
// uniq_merge(s1, s2) returns a merge of sorted list s1 and s2 without doublon
func uniq_merge(s1, s2 []OrderedType) (r []OrderedType) {
	/* FIX ME */
}
 
// Set: an ordered set of OrderedType elements
type Set []OrderedType
 
// NewSet() creates a new empty set
func NewSet() *Set {
	var s *Set
	*s = make([]OrderedType, 0)
	return s
}
 
// s.bfind(x) returns expected position of x
// if x is not present, returns position of first element not smaller than x
func (s *Set) bfind(x OrderedType) (pos int) {
	/* FIX ME */
}
 
// s.Mem(x) returns true if x is in the set
func (s *Set) Mem(x OrderedType) bool {
	p := s.bfind(x)
	return p < len(*s) && x.Equals((*s)[p])
}
 
// s.Add(x) add x to set s, returns true if x wasn't there, false otherwise
func (s *Set) Add(x OrderedType) bool {
	/* FIX ME */
}
 
// s.Remove(x) removes x from s
// returns true if x was in the set, false otherwise
func (s *Set) Remove(x OrderedType) bool {
	/* FIX ME */
}
 
// s.Union(s2) adds elements from s2 to s
func (s *Set) Union(s2 *Set) {
	*s = uniq_merge(*s, *s2)
}
 
// s.Difference(s2) removes all elements of s2 from s
func (s *Set) Difference(s2 *Set) {
	/* FIX ME */
}

Pour la fonction d'ajout: vous utiliserez bfind pour trouvez la position d'insertion de l'élément (et vérifier au passage s'il n'est pas déjà présent et pour décaller les cases vers la droite, vous pourrez utiliser la stratégie suivante:

	// Shift all cells from position p to the end by 1 cell to the right
	*s = append(*s, nil)                // add an empty cell at the end
	copy((*s)[p+1:], (*s)[p:len(*s)-1]) // shift element with copy

Tests

Pour les tests, nous allons utiliser les possibilités de tests automatisés de Go. Dans le répertoire d'un package, les fichiers finissants par _test.go sont ignorés lors de la compilation du package, par contre ils vont être utilisés si vous appelez go test. Dans ce cas là, Go compile votre package avec les fichiers de tests et appelle une par une toutes les fonctions dont le nom a la forme suivante: TestXxx(t) (noter l'emplois des majuscule qui est important.) Le paramètre des ces fonctions est un pointeur sur le type testing.T (voir la doc du package en question) qui fournit des opérations vous permettant de construire des logs pour votre tests et d'indiquer qu'un test à échouer. Notons que les logs ne sont affichés que si le test échoue.

Je vous fourni un début de tests, à vous de le compléter pour tester toutes les opérations.

package ordered_set
 
import (
	"math/rand"
	"testing"
)
 
type OrderedInt int
 
func (x OrderedInt) Equals(y OrderedType) bool {
	switch y_ := y.(type) {
	case OrderedInt:
		return x == y_
	default:
		return false
	}
}
 
func (x OrderedInt) Less(y OrderedType) bool {
	switch y_ := y.(type) {
	case OrderedInt:
		return x < y_
	default:
		return false
	}
}
 
func isSet(s Set) bool {
	i := 0
	for ; i < len(s)-1 && s[i].Less(s[i+1]) && !s[i].Equals(s[i+1]); i++ {
	}
	return i >= len(s)-1
}
 
func present(s Set, x OrderedType) bool {
	for _, v := range s {
		if x.Equals(v) {
			return true
		}
	}
	return false
}
 
func TestSet_Add_fixed(t *testing.T) {
	tmp := Set(make([]OrderedType, 0))
	var s *Set
	s = &tmp
	for i := 0; i < 100; i++ {
		n := OrderedInt(i)
		if !s.Add(n) {
			t.Fatal("Adding not present element should not return false")
		}
		if len(*s) != i+1 {
			t.Fatal("Set length does not match")
		}
		if !present(*s, n) {
			t.Fatal("Added element not in the set")
		}
		if !isSet(*s) {
			t.Log("set:", *s)
			t.Fatal("Ill formed set (not sorted or contains doublons)")
		}
	}
	if !isSet(*s) {
		t.Log("set:", *s)
		t.Fatal("Ill formed set (not sorted or contains doublons)")
	}
}
 
func TestSet_Add_random(t *testing.T) {
	tmp := Set(make([]OrderedType, 0))
	var s *Set
	s = &tmp
	size := 0
	for i := 0; i < 100; i++ {
		n := OrderedInt(rand.Intn(1000))
		if s.Add(n) {
			size += 1
		}
		if len(*s) != size {
			t.Fatal("Set length does not match")
		}
		if !present(*s, n) {
			t.Fatal("Added element not in the set")
		}
	}
	if !isSet(*s) {
		t.Log("set:", *s)
		t.Fatal("Ill formed set (not sorted or contains doublons)")
	}
}
 
func TestSet_Mem(t *testing.T) {
	s := Set(make([]OrderedType, 100))
	for i := 0; i < 100; i += 1 {
		n := OrderedInt(2 * i)
		s[i] = n
	}
	for i := 0; i < 100; i += 1 {
		n := OrderedInt(2 * i)
		if !s.Mem(n) {
			t.Log(s)
			t.Errorf("set.Mem(%d): unable to find present value\n", 2*i)
		}
	}
	for i := -1; i < 2; i++ {
		n := OrderedInt(i*201 + 1)
		if s.Mem(n) {
			t.Log(s)
			t.Errorf("set.Mem(%d): found not present value\n", 201*i+1)
		}
 
	}
}