时间戳

首页 > 解决方案 > 如何优化从 Go 中的文本文件中查找字谜

file - 如何优化从 Go 中的文本文件中查找字谜

问题描述

我正在尝试解决一个编码挑战，即必须从与输入字符串匹配的文本文件中打印所有字谜。程序必须尽可能快地执行。工作代码：

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 更高效，但需要将原始单词打印到控制台。

有什么方法可以提高创建地图的效率吗？

标签： filegoanagram

解决方案

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
$

如何优化从 Go 中的文本文件中查找字谜

我正在尝试解决一个编码挑战，即必须从与输入字符串匹配的文本文件中打印所有字谜。程序必须尽可能快地执行。

目前，我将它降低到大约 160 毫秒。

没有提供测试用例。

XY 问题是询问您尝试的解决方案，而不是您的实际问题：XY 问题。

如果我们查看维基百科 -字谜，我们会看到：字谜是通过重新排列不同单词或短语的字母而形成的单词或短语，通常只使用所有原始字母一次。例如，“宁静”=“慌乱”，“葬礼”=“真正的乐趣”，“铁路安全”=“童话”。

为了解决 Go 中的这个问题，我们使用 Go 测试包基准测试工具来测量性能。例如，字母值的总和、字母值的排序以及整体算法。我们不懈地剖析每一行代码以提高性能。我们从最便宜的开始订购字谜测试。例如，对字母进行排序很昂贵，所以我们首先检查字母的数量，然后对字母进行简单的求和以廉价地过滤掉许多非字谜。

我们需要一些东西来充当字谜文本文件。Linux 词典文件 ( /usr/share/dict/words) 很容易获得，但仅限于单个单词。它使用大写和小写。

详尽的基准测试令人筋疲力尽。收益递减规律已经开始。现在，速度提高十倍就足够了。

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)
}

推荐阅读