Я пытаюсь оптимизировать код алгоритма кластеризации, который в значительной степени полагается на вычисления log (x), как часть дивергенции Дженсена-Шеннона между двумя векторами вероятности. Согласно моему профилировщику, 65% времени выполнения тратится на сам журнал (x).
У меня есть ряд предположений относительно характера данных, с которыми я работаю, и они могут помочь в разработке оптимизация, но пока не удалось заставить что-то работать. Это моя установка:
- Мои данные изначально представлены с использованием векторов натуральных чисел. Я не могу делать предположения о верхних границах количества векторов, значений в векторах или суммы значений в векторах. Однако в 90% случаев значения в векторах находятся в диапазоне от 1 до 100 и в сумме не превышают 1000. Было бы здорово найти оптимизацию для 90% случаев, а в остальных 10% - для используйте текущее решение.
- Векторы нормализованы с использованием нормы L1.
- Нормализованные векторы усредняются случайным образом для получения относительно небольшого набора векторов центроидов (например, 50 центроидов из 50000 нормализованных векторов).
- Векторы controid обновляются во время выполнения алгоритма путем удаления / добавления к ним нормализованных векторов.
- JS -расхождение вычисляется между вектором центроида и нормализованным вектором.
В настоящее время в моем коде используются представления с плавающей запятой двойной точности для нормализованных векторов и центроидов . Следовательно, все вычисления журнала в JS -дивергенции применяются к значениям в (0, 1].
То, что я пытался сделать до сих пор:
- Переключиться на рациональное число представление: вместо нормализации исходных векторов путем деления натуральных чисел на их сумму, я сохраняю сумму как отдельное значение для каждого вектора. Эта сумма является знаменателем, который будет использоваться при вычислениях с этим вектором. Использование рациональных чисел может помочь для оптимизации вычисления журнала, поскольку log (a / b) = log (a) - log (b). И поскольку и a, и b являются натуральными числами, log (a) и log (b) могут быть предварительно вычислены с помощью поиска таблицу и быстро вызывается во время выполнения. Однако это направление не сработало, потому что векторы нужно усреднять (см. 3 выше), а центроиды необходимо обновлять (см. 4 выше). Поскольку каждый вектор имеет свой знаменатель (его L1-norm), вычисление общего знаменателя для большого набора векторов (как часть суммирования / вычитания векторов) является дорогостоящим и легко переполняет uint64. * 1 024 *
- Переключиться на представление с фиксированной точкой: я попытался использовать 2 ^ 32 в качестве общего знаменателя для всех векторов, представляя каждое значение a / b как x / 2 ^ 32 (x = (int) round (a / б * 2 ^ 32, 0)). Хотя это удовлетворяет всем требованиям, таблица поиска в итоге составляет около 200 МБ (на самом деле это набор таблиц с разной плотностью для разных поддиапазонов в (0,1], но это помимо сути). В результате это не может быть хранятся в кэше и должны храниться в ОЗУ. Медленный произвольный доступ к ОЗУ делает использование таблицы поиска медленнее, чем прямое вычисление журнала в представлении с плавающей запятой. См. this для другого попытаться использовать таблицу поиска для экономии времени вычислений, которая не удалась по той же причине, что и моя попытка. Переключение на гораздо меньшую таблицу, которая может поместиться в кеш L3, приводит к менее точному представлению чисел, что недостаточно для моего потребности (разница между log (a / b) и log (x / 2 ^ y) слишком велика).
В настоящее время у меня нет идей, как действовать дальше, и я был бы рад чтобы услышать о новых направлениях для оптимизации расчета журнала в этой настройке или для улучшения направлений, которые я уже пробовал.
Спасибо