Для обоснования распараллеливания алгоритма выполним примерную оценку ее временной сложности.
Если записать структуру циклов для выполнения этапа вычисления центров кластеров по формуле (3) на псевдокоде, получим:
Для каждого кластера{
Для каждого терма кластера{
Для каждого объекта{
}
}
}
Время выполнения линейно зависит от количества кластеров, количества термов и количества объектов. Для разбиения массива данных из 100 документов, 1000 уникальных термов на 10 кластеров потребуется 10· 1000·100=1·106 итераций. Для разбиения на 15 кластеров для этого же набора объектов потребуется уже 15· 1000·100=1.5·106. Количество итераций возрастает линейно.
Структура циклов для этапа вычисления матрицы принадлежности по формуле (4):
для каждого объекта {
для каждого кластера {
для каждого кластера {
для каждого терма{
}
}
}
}
Как видно из этого кода, время его выполнения линейно зависит от количества объектов и термов и имеет квадратичную зависимость от числа кластеров. Для выполнения этого этапа необходимы вложенные циклы до третьего уровня. Таким образом, например, для разбиения массива данных из 100 документов, 1000 уникальных термов на 10 кластеров потребуется 1000· 10·10·100=1·107 итераций. Для разбиения на 15 кластеров для этого же набора объектов потребуется уже 1000· 15·15·100=2.25·107. Количество итераций возрастает более чем в 2 раза.
И, наконец, вычисление целевой функции по формуле (1):
Для каждого кластера{
Для каждого ресурса{
Для каждого терма{
}
}
}
Время выполнения линейно зависит от количества кластеров, количества объектов.
Как видно из приведенных выше формул в каждом из этапов присутствуют вложенные циклы до 3-го — 4-го уровня вложенности.
Для больших массивов данных при запуске алгоритма на компьютере с многоядерном процессором или на вычислительном кластере имеет смысл выполнять эти итерации в отдельных потоках, сокращая тем самым временную сложность алгоритма. Один из вариантов распределения этих итераций по потокам приведен ниже.
