Создание параллельного счетчика слов в Go

Question

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

Моя первоначальная попытка выполнить эту задачу была следующей:

Реализация 1

func WordCount(words []string, startWord int, endWord int, waitGroup *sync.WaitGroup, freqsChannel chan<- map[string]int) {
    freqs := make(map[string]int)
    for i := startWord; i < endWord; i++ {
        word := words[i]
        freqs[word]++
    }
    freqsChannel <- freqs
    waitGroup.Done()
}

func ParallelWordCount(text string) map[string]int {
    // Split text into string array of the words in text.
    text = strings.ToLower(text)
    text = strings.ReplaceAll(text, ",", "")
    text = strings.ReplaceAll(text, ".", "")
    words := strings.Fields(text)
    length := len(words)
    threads := 28
    freqsChannel := make(chan map[string]int, threads)

    var waitGroup sync.WaitGroup
    waitGroup.Add(threads)
    defer waitGroup.Wait()

    wordsPerThread := length / threads // always rounds down
    wordsInLastThread := length - (threads-1)*wordsPerThread
    startWord := -wordsPerThread
    endWord := 0
    for i := 1; i <= threads; i++ {
        if i < threads {
            startWord += wordsPerThread
            endWord += wordsPerThread
        } else {
            startWord += wordsInLastThread
            endWord += wordsInLastThread
        }
        go WordCount(words, startWord, endWord, &waitGroup, freqsChannel)
    }
    freqs := <-freqsChannel
    for i := 1; i < threads; i++ {
        subFreqs := <-freqsChannel
        for word, count := range subFreqs {
            freqs[word] += count
        }
    }
    return freqs
}

Согласнодля моего ассистента по обучению это не было хорошим решением, так как предварительная обработка текстового файла, выполняемая

text = strings.ToLower(text)
text = strings.ReplaceAll(text, ",", "")
text = strings.ReplaceAll(text, ".", "")
words := strings.Fields(text)

в ParallelWordCount, противоречит идее параллельной обработки.

Теперь, чтобы это исправить, я перевел ответственность за обработку текстового файла в массив слов в функцию WordCount, которая вызывается в отдельных программах для разных частей текстового файла.Ниже приведен код для моей второй реализации.

Реализация 2

func WordCount(text string, waitGroup *sync.WaitGroup, freqsChannel chan<- map[string]int) {
    freqs := make(map[string]int)
    text = strings.ToLower(text)
    text = strings.ReplaceAll(text, ",", "")
    text = strings.ReplaceAll(text, ".", "")
    words := strings.Fields(text)
    for _, value := range words {
        freqs[value]++
    }
    freqsChannel <- freqs
    waitGroup.Done()
}

func splitCount(str string, subStrings int, waitGroup *sync.WaitGroup, freqsChannel chan<- map[string]int) {
    if subStrings != 1 {
        length := len(str)
        charsPerSubstring := length / subStrings
        i := 0
        for str[charsPerSubstring+i] != ' ' {
            i++
        }
        subString := str[0 : charsPerSubstring+i+1]
        go WordCount(subString, waitGroup, freqsChannel)
        splitCount(str[charsPerSubstring+i+1:length], subStrings-1, waitGroup, freqsChannel)
    } else {
        go WordCount(str, waitGroup, freqsChannel)
    }
}

func ParallelWordCount(text string) map[string]int {
    threads := 28
    freqsChannel := make(chan map[string]int, threads)

    var waitGroup sync.WaitGroup
    waitGroup.Add(threads)
    defer waitGroup.Wait()

    splitCount(text, threads, &waitGroup, freqsChannel)

    // Collect and return frequences
    freqs := <-freqsChannel
    for i := 1; i < threads; i++ {
        subFreqs := <-freqsChannel
        for word, count := range subFreqs {
            freqs[word] += count
        }
    }
    return freqs
}

Среднее время выполнения этой реализации составляет 3 мс по сравнению со старым средним значением 5 мс,но тщательно ли я рассмотрел проблему, поднятую моим ассистентом, или во втором варианте также не используются все преимущества параллельной обработки для эффективного подсчета слов текстового файла?

Answer 1

Вопросы реализации 2

1. В методе splitCount(), что если общая длина строки меньше 28. Тем не менее, он будет вызывать wordcount(), равный количеству слов.
2. Кроме того, произойдет сбой, так как мы выполняем waitgroup.done 28 раз в этом сценарии.
3. Рекурсивный вызов splitWord() делает его медленным. Мы должны разделить и вызвать в цикле
4. Число потоков не должно быть всегда 28, поскольку мы не знаем, сколько слов в строке.

Попытается разработать более оптимизированный подход и обновит ответ.

Answer 2

Две вещи, которые я вижу:

• Второй пример лучше, поскольку вы разбили разбор текста и подсчет слов на несколько процедур. Одна вещь, которую вы можете попробовать - не считать слова в методе WordCount, а просто вставить их в канал и увеличить их в главном счетчике. Вы можете проверить, быстрее ли это, я не уверен. Кроме того, проверьте веер шаблон для более подробной информации.
• Параллельная обработка может все еще не использоваться полностью, потому что я не верю, что у вас доступно 28 процессорных ядер :). Количество ядер определяет, сколько WordCount подпрограмм работает параллельно, остальные будут распределяться одновременно на основе доступных ресурсов (доступных ядер ЦП). Здесь - отличная статья, объясняющая это.