Created
March 9, 2017 10:27
-
-
Save alextanhongpin/29b1107b7a937c4d556bfa0338ba9e14 to your computer and use it in GitHub Desktop.
optimized version of isogram for golang
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
// Run the following command | |
// $ time go run main.go | |
// Golang Benchmark | |
// real 0m8.102s | |
// user 0m1.004s | |
// sys 0m0.504s | |
// Python Benchmark | |
// real 0m0.782s | |
// user 0m0.617s | |
// sys 0m0.099s | |
import ( | |
"bufio" | |
"fmt" | |
"io" | |
"log" | |
"os" | |
"runtime" | |
"strings" | |
"sync" | |
"sync/atomic" | |
) | |
// Before | |
// real 0m1.124s | |
// user 0m0.971s | |
// sys 0m0.159s | |
// After | |
// real 0m0.442s | |
// user 0m1.017s | |
// sys 0m0.084s | |
func main() { | |
f, err := os.Open("/usr/share/dict/words") | |
if err != nil { | |
log.Fatal(err) | |
} | |
defer f.Close() | |
reader, writer := io.Pipe() | |
wordC := make(chan string, 1024) | |
var wg sync.WaitGroup | |
var total uint64 = 0 | |
wg.Add(runtime.NumCPU()) | |
for i := 0; i < runtime.NumCPU(); i++ { | |
go func() { | |
var count uint64 = 0 | |
for word := range wordC { | |
if IsIsogram(word) { | |
count += 1 | |
} | |
} | |
atomic.AddUint64(&total, count) | |
wg.Done() | |
}() | |
} | |
go func() { | |
scanner := bufio.NewScanner(reader) | |
for scanner.Scan() { | |
wordC <- scanner.Text() | |
} | |
close(wordC) | |
}() | |
go func() { | |
_, err := io.Copy(writer, f) | |
if err != nil { | |
log.Fatal(err) | |
} | |
writer.Close() | |
}() | |
wg.Wait() | |
fmt.Printf("%d isograms found!", total) | |
} | |
func IsIsogram(s string) bool { | |
if s == "" { | |
return false | |
} | |
// Create a map to store the unique characters | |
d := make(map[rune]int) | |
for _, r := range strings.ToLower(s) { | |
// Set unique characters | |
d[r] += 1 | |
} | |
// Now we have a map of the unique characters | |
// In order to get an Array of the keys, we loop | |
var o []string | |
for k, _ := range d { | |
o = append(o, string(k)) | |
} | |
// Array `o` now contains the unique strings | |
// Check how many times the strings are repeated | |
repeat := int(len(s) / len(o)) | |
// Now check if each unique characters have the same amount | |
for _, v := range d { | |
if v != repeat { | |
return false | |
} | |
} | |
return true | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment