Вычислительные затраты на агрегирование

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

Обозначим затраты на выполнение агрегирования множества по i -му измерению, как .

Очевидно, что

Для формирования множества агрегатов A₀₁₁ в случае с тремя простыми измерениями для каждой комбинации менеджеров и месяцев необходимо просуммировать исходные значения показателей по направлению стрелки 1 (рис. 15) n_р -1 раз. Таким образом, с учётом того, что i(Р) =1, i(M)=2, i(T) =3 – порядковые номера измерений, затраты на выполнение агрегирования от A₀₁₁ до A₀₁₁ определяются как

C(1, A₁₁₁) = (n_р - 1)n_mn_t.

Аналогично при формировании множеств агрегатов A₁₀₁ и A₁₁₀ на основании исходных значений показателей получим соответственно затраты

C(2, A₁₁₁) = n_c n_t (n_m - 1),

C(2, A₁₁₁) = n_c n_m (n_t –1).

Получение множества A₀₀₁ возможно двумя способами:

· агрегирование множества A₁₀₁ по измерению видов товара (по стрелке 4);

· агрегирование множества A₀₁₁ по измерению менеджеров (по стрелке 5);

Очевидно, что затраты на эти операции различны и равны соответственно

C (1, A ₁₀₁) = (n_р -1) n_t,

C (2, A ₀₁₁) = (n_m -1) n_t.

Рассмотрим расчет затраты на агрегирование в общем случае с иерархическими измерениями. Для этого используем следующее утверждение.

Утверждение 1. Пусть существует иерархия с l * уровнями, где n_l – количество членов на l -ом уровне и n_l <= n_{l +1}, l =1… l *-1. Тогда количество элементарных операций суммирования значений показателя, соответствующих l +1-му уровню, с целью получения агрегированных значений показателя l -го уровня равно

n_{l +1}- n_l.

В примере с двумя иерархическими (рис. 16) измерениями для получения агрегированных значений показателя по каждой комбинации менеджеров и месяцев (А ₂₂) необходимо провести агрегацию множества исходных A₃₂ данных по временному измерению: от A ₃₂ до А ₂₂ по 1-му измерению. Для этой операции необходимо для каждого менеджера просуммировать значения показателя по дням с целью получения показателя по месяцам (согласно утверждению) n _1,3 - n _1,2 раз. Таким образом,

C (1, A ₃₂) = (n _1,3 – n _1,2) n _2,2 = n _1,3 n _2,2 - n _1,2 n _2,2 = a ₃₂ - a ₂₂.

Аналогично затраты на агрегацию значений показателя в разрезе менеджеров и кварталов по временному измерению с целью получения агрегатов только по менеджерам равны

C (1, A ₁₂) = (n _1,1 – n _1,0) n _2,2 = (n _1,1 – 1) n _2,2 = n _1,1 n _2,2 - n _2,2 = a ₁₂ - a ₀₂,

Обобщая выше описанные примеры, можно сформулировать вывод, что при суммировании множеств агрегатов по i -му измерению с l_i -го на l_i -1 уровень необходимо для каждой комбинации из членов текущих уровней всех остальных m -1 измерений провести n_i,li – n_i,li-1 элементарных операций суммирования. Таким образом, получаем

, где l_i = 1…l_i*.

Используя (5а) и (6), преобразуем эту формулу в следующий вид:

(8)

Дата добавления: 2015-07-26