Блог

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

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

Ниже приведен код, который использует мьютекс, чтобы избежать описанной паники во время выполнения, но также не позволяет параллельно считать слова.

 func WordCount(words []string, startWord int, endWord int, freqs map[string]int, waitGroup *sync.WaitGroup, mutex *sync.Mutex) {
    mutex.Lock()
    for i := startWord; i < endWord; i   {
        word := words[i]
        freqs[word]  
    }
    mutex.Unlock()
    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)

    freqs := make(map[string]int)

    var mutex sync.Mutex
    var waitGroup sync.WaitGroup
    waitGroup.Add(2)
    defer waitGroup.Wait()

    threads := 2
    wordsPerThread := length / threads // always rounds down
    wordsInLastThread := length - (threads-1)*wordsPerThread
    startWord := -wordsPerThread
    var endWord int
    for i := 1; i <= threads; i   {
        if i < threads {
            startWord  = wordsPerThread * i
            endWord  = wordsPerThread * i
        } else {
            startWord  = wordsInLastThread
            endWord  = wordsInLastThread
        }
        go WordCount(words, startWord, endWord, freqs, amp;waitGroup, amp;mutex)
    }

    return freqs
}
  

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

Чтобы прояснить основную логику того, что я пытаюсь сделать, я включил приведенный ниже пример. ConcurrentSum Функция возвращает сумму элементов в массиве путем одновременного вычисления нижней и верхней половин массива. В моем случае я хочу параллельно подсчитывать слова в разных частях моего текстового файла и, в конечном счете, объединить количество слов в единую карту количества слов, представляющую весь документ.

 func sum(a []int, res chan<- int) {
    var sum int
    for i := 0; i < len(a); i   {
        sum  = a[i]
    }
    res <- sum
}

// concurrently sum the array a.
func ConcurrentSum(a []int) int {
    n := len(a)
    ch := make(chan int)
    go sum(a[:n/2], ch)
    go sum(a[n/2:], ch)
    return <-ch   <-ch
}
  

Я полагаю, вы могли бы создать массив карт, каждая из которых используется для каждого процесса, а затем читать на каждой карте, используя список, чтобы отслеживать слова, которые вы уже посчитали. Предполагая, что каждое слово является ключом к подсчитанному количеству раз, вот как это выглядит. Параллельная обработка здесь может быть не лучшим выбором, учитывая параллелизм, поскольку для реального увеличения производительности все должно храниться отдельно. Если у вас есть место для хранения, то вы наверняка можете использовать список и получить в худшем случае O (N) эффективность от интеграции карт. Вам нужно будет сохранить интеграцию карт в одном потоке или одном процессе.