Exercism v3 launches on Sept 1st 2021. Learn more! 🚀🚀🚀
Avatar of rootulp

rootulp's solution

to Parallel Letter Frequency in the Go Track

Published at Jun 05 2020 · 0 comments
Instructions
Test suite
Solution

Note:

This exercise has changed since this solution was written.

Count the frequency of letters in texts using parallel computation.

Parallelism is about doing things in parallel that can also be done sequentially. A common example is counting the frequency of letters. Create a function that returns the total frequency of each letter in a list of texts and that employs parallelism.

Concurrency vs Parallelism

Go supports concurrency via "goroutines" which are started with the go keyword. It is a simple, lightweight and elegant way to provide concurrency support and is one of the greatest strengths of the language.

You may notice that while this exercise is called Parallel letter frequency you don't see the term "Parallel" used very often in Go. Gophers prefer to use the term Concurrent to describe the management of multiple independent goroutines ("processes" or "threads" in other language contexts). Although these terms are often used interchangeably Gophers like to be technically correct and use "concurrent" when discussing the seemingly simultaneous executions of goroutines.

While we can plan for our programs to run in parallel, and at times they may appear to run in parallel, without strict knowledge of the execution context of our code all we can guarantee is that processes will run concurrently. In other words they may be executing sequentially faster than we can distinguish but not strictly simultaneously.

For more take a look at The Go Blog's post: Concurrency is not parallelism.

Concurrency Resources

If you are new to the concurrency features in Go here are some resources to get you started. We recommend looking over these before starting this exercise:

For a really deep dive you can try the book Concurrency in Go by @kat-co.

Coding the solution

Look for a stub file having the name parallel_letter_frequency.go and place your solution code in that file.

Running the tests

To run the tests run the command go test from within the exercise directory.

If the test suite contains benchmarks, you can run these with the --bench and --benchmem flags:

go test -v --bench . --benchmem

Keep in mind that each reviewer will run benchmarks on a different machine, with different specs, so the results from these benchmark tests may vary.

Further information

For more detailed information about the Go track, including how to get help if you're having trouble, please visit the exercism.io Go language page.

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

parallel_letter_frequency_test.go

package letter

import (
	"reflect"
	"testing"
)

// In the separate file frequency.go, you are given a function, Frequency(),
// to sequentially count letter frequencies in a single text.
//
// Perform this exercise on parallelism using Go concurrency features.
// Make concurrent calls to Frequency and combine results to obtain the answer.

var (
	euro = `Freude schöner Götterfunken
Tochter aus Elysium,
Wir betreten feuertrunken,
Himmlische, dein Heiligtum!
Deine Zauber binden wieder
Was die Mode streng geteilt;
Alle Menschen werden Brüder,
Wo dein sanfter Flügel weilt.`

	dutch = `Wilhelmus van Nassouwe
ben ik, van Duitsen bloed,
den vaderland getrouwe
blijf ik tot in den dood.
Een Prinse van Oranje
ben ik, vrij, onverveerd,
den Koning van Hispanje
heb ik altijd geëerd.`

	us = `O say can you see by the dawn's early light,
What so proudly we hailed at the twilight's last gleaming,
Whose broad stripes and bright stars through the perilous fight,
O'er the ramparts we watched, were so gallantly streaming?
And the rockets' red glare, the bombs bursting in air,
Gave proof through the night that our flag was still there;
O say does that star-spangled banner yet wave,
O'er the land of the free and the home of the brave?`
)

func OriginalFrequency(s string) FreqMap {
	m := FreqMap{}
	for _, r := range s {
		m[r]++
	}
	return m
}

func TestConcurrentFrequency(t *testing.T) {
	seq := OriginalFrequency(euro + dutch + us)
	con := ConcurrentFrequency([]string{euro, dutch, us})
	if !reflect.DeepEqual(con, seq) {
		t.Fatal("ConcurrentFrequency wrong result")
	}
}

func TestSequentialFrequency(t *testing.T) {
	oSeq := OriginalFrequency(euro + dutch + us)
	seq := Frequency(euro + dutch + us)
	if !reflect.DeepEqual(oSeq, seq) {
		t.Fatal("Frequency wrong result")
	}
}

func BenchmarkSequentialFrequency(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Frequency(euro + dutch + us)
	}
}

func BenchmarkConcurrentFrequency(b *testing.B) {
	for i := 0; i < b.N; i++ {
		ConcurrentFrequency([]string{euro, dutch, us})
	}
}
package letter

// FreqMap records the frequency of each rune in a given text.
type FreqMap map[rune]int

// Frequency counts the frequency of each rune in a given text and returns this
// data as a FreqMap.
func Frequency(s string) FreqMap {
	m := FreqMap{}
	for _, r := range s {
		m[r]++
	}
	return m
}

// ConcurrentFrequency counts the frequency of each rune in texts (concurrently)
// and returns a FreqMap.
func ConcurrentFrequency(texts []string) FreqMap {
	freqMaps := make(chan FreqMap, len(texts))

	for _, text := range texts {
		go func(t string, c chan<- FreqMap) {
			c <- Frequency(t)
		}(text, freqMaps)
	}

	result := make(FreqMap)

	// Merge freqMaps into result
	for range texts {
		freqMap := <-freqMaps
		for r, count := range freqMap {
			result[r] += count
		}
	}

	return result
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?