我正在尝试解决一个编码挑战,即必须从与输入字符串匹配的文本文件中打印所有字谜。程序必须尽可能快地执行。工作代码:
package main
import (
"bufio"
"fmt"
"log"
"os"
"sort"
"strings"
"time"
)
func timeTrack(start time.Time, name string) {
elapsed := time.Since(start)
log.Printf("%s took %s", name, elapsed)
}
func SortString(w string) string {
s := strings.Split(w, "")
sort.Strings(s)
return strings.Join(s, "")
}
func FindWord(dict map[string]string, w string) {
if val, ok := dict[w]; ok {
fmt.Println("Found anagrams: ", val)
}
}
func main() {
defer timeTrack(time.Now(), "factorial")
file_fullpath := os.Args[1]
anagram_word := os.Args[2]
f, err := os.Open(file_fullpath)
defer f.Close()
if err != nil {
panic(err)
}
scanner := bufio.NewScanner(f)
scanner.Split(bufio.ScanLines)
var txtlines = make(map[string]string)
for scanner.Scan() {
k := scanner.Text()
v := SortString(k)
txtlines[v] += string(k) + ","
}
FindWord(txtlines, SortString(anagram_word))
}
目前,我把它降到了大约 160 毫秒。
显然使用 Array 会比 Map 更有效,但是需要将原始单词打印到控制台。
有什么办法可以提高创建 map 的效率吗?
最佳答案
TL;DR:peterSO 比 strom73 快 10 倍。
斯特罗姆73:
$ go build strom73.go && ./strom73 "/usr/share/dict/words" "restful"
Found anagrams: fluster,restful,
2019/02/26 02:50:47 anagrams took 150.733904ms
$
彼得苏:
$ go build peterso.go && ./peterso "/usr/share/dict/words" "restful"
Found anagrams: [restful fluster]
2019/02/26 02:50:52 anagrams took 15.093098ms
$
不提供测试用例。
XY 问题是询问您尝试的解决方案而不是您的实际问题: The XY Problem 。
如果我们查看 Wikipedia - Anagram,我们会看到:字谜是通过重新排列不同单词或短语的字母而形成的单词或短语,通常只使用一次所有原始字母。例如,“ Restful ”=“慌乱”、“葬礼”=“真正的乐趣”、“铁路安全”=“童话故事”。
为了解决 Go 中的这个问题,我们使用 Go 测试包基准工具来衡量性能。例如,字母值的总和、字母值的排序和整体算法。我们不懈地剖析每一行代码以提高性能。我们从最便宜的开始订购字谜测试。例如,排序字母很昂贵,所以我们首先检查字母的数量,然后是简单的字母总和,以低成本过滤掉许多非字谜。
我们需要一些东西来充当字谜文本文件。 Linux 单词词典文件 (
/usr/share/dict/words
) 很容易获得,但仅限于单个单词。它使用大写和小写。详尽的基准测试令人筋疲力尽。 yield 递减规律已经确立。目前速度提高十倍就足够了。
peterso.go:
package main
import (
"bufio"
"fmt"
"io"
"log"
"os"
"sort"
"strings"
"time"
)
func findAnagrams(find string, text io.Reader) []string {
find = strings.ToLower(find)
findSum := 0
findRunes := []rune(find)
j := 0
for i, r := range findRunes {
if r != ' ' {
findSum += int(r)
if i != j {
findRunes[j] = r
}
j++
}
}
findRunes = findRunes[:j]
sort.Slice(findRunes, func(i, j int) bool { return findRunes[i] < findRunes[j] })
findStr := string(findRunes)
anagrams := []string{find}
s := bufio.NewScanner(text)
for s.Scan() {
word := strings.ToLower(s.Text())
wordSum := 0
wordRunes := []rune(word)
j := 0
for i, r := range wordRunes {
if r != ' ' {
wordSum += int(r)
if i != j {
wordRunes[j] = r
}
j++
}
}
wordRunes = wordRunes[:j]
if len(wordRunes) != len(findRunes) {
continue
}
if wordSum != findSum {
continue
}
sort.Slice(wordRunes, func(i, j int) bool { return wordRunes[i] < wordRunes[j] })
if string(wordRunes) == findStr {
if word != find {
anagrams = append(anagrams, word)
}
}
}
if err := s.Err(); err != nil {
panic(err)
}
return anagrams
}
func timeTrack(start time.Time, name string) {
elapsed := time.Since(start)
log.Printf("%s took %s", name, elapsed)
}
func main() {
defer timeTrack(time.Now(), "anagrams")
textPath := os.Args[1]
findWord := os.Args[2]
text, err := os.Open(textPath)
if err != nil {
panic(err)
}
defer text.Close()
anagrams := findAnagrams(findWord, text)
fmt.Println("Found anagrams: ", anagrams)
}
关于file - 如何优化在 Go 中从文本文件中查找字谜,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/54873920/