Как оптимизировать поиск анаграмм из текстового файла в Go - PullRequest
Новая
       73

Как оптимизировать поиск анаграмм из текстового файла в Go

0 голосов
/ 25 февраля 2019

Я пытаюсь решить проблему кодирования, при которой необходимо распечатать все анаграммы из текстового файла, соответствующего входной строке.Программа должна выполняться максимально быстро.Рабочий код: 

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 мс.

Очевидно, что использование массива было бы более эффективным, чем Map, но есть требование напечатать оригинальное слово наконсоль.

Есть ли способ повысить эффективность создания карты?

1 Ответ

0 голосов
/ 26 февраля 2019

TL; DR: peterSO в 10 раз быстрее, чем strom73 .

strom73: 

$ go build strom73.go && ./strom73 "/usr/share/dict/words" "restful"
Found anagrams:  fluster,restful,
2019/02/26 02:50:47 anagrams took 150.733904ms
$

peterSO: 

$ 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 .

Если мы посмотрим на Википедия - Анаграмма , мы увидим: Анаграммуэто слово или фраза, сформированная путем перестановки букв другого слова или фразы, как правило, используя все оригинальные буквы ровно один раз.Примеры: "restful" = "fluster", "funeral" = "real fun", "rail safety" = "сказки".

Чтобы решить эту проблему в 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)
}
...