Задача: “Подсчет статистики”

Суть задачи заключается в том, чтобы подсчитать статистику встречаемости символов алфавита A в строке s.

Пример. Дан алфавит \(A = \{a, b, c\}\) и имеется строка \(s = acaaabba\). Тогда статистика \(S = \{a: 5, b: 2, c: 1\}\). Задача решается очевидным способом путем однократного сканирования строки (т.е. трудоемкость линейная). Немного усложним задачу — заметим, что статистику можно считать по частям, т.е. она обладает аддитивным свойством. Пусть

\[s = s1 + s2 = acaa + abba.\]

Тогда общая статистика

\[S = S1 + S2 = \{a: 3, b: 0, c: 1\} + \{a: 2, b: 2, c: 0\} = \{a: 5, b: 2, c: 1\},\]

что совпадает с первым результатом.

Строкой может выступать массив чисел, текст, пиксели изображения. Любой файл независимо от его природы можно рассматривать как массив байт. Поэтому для любого файла можно считать статистику для алфавита \(A = \{0, 1, 2,..., 255\}\). Аддитивность статистики позволяет выполнять вычисления параллельно. В настоящее время это актуально в связи с широким распространением многоядерных процессоров.

Общий подход к решению таких задач:

1. Разбить задачу на независимые подзадачи (поделить строку на части)
2. Решить подзадачи с максимальной степенью параллельности (запустить сбор статистики для каждой части строки)
3. Собрать общий результат из результатов подзадач (просуммировать полученные статистики)

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

Для решения можно воспользоваться любыми языками программирования с поддержкой параллелизма. Для решения на С++ рекомендуется использовать библиотеку Intel Threading Building Blocks. Очень интересно сравнить производительность С++ и Java.