auto_seeder.h

Go to the documentation of this file.

#pragma once
 
#include <cstddef>
#include <cstdint>
#include <variant>
 
#include "clustering/kmeans/policy/afkmc2_seeder.h"
#include "clustering/kmeans/policy/greedy_kmpp_seeder.h"
#include "clustering/math/thread.h"
#include "clustering/ndarray.h"
 
namespace clustering::kmeans {
 
enum class AutoSeederMode { kSingleRun, kBestOf };

template <class T, AutoSeederMode Mode = AutoSeederMode::kSingleRun> class AutoSeeder {
public:
#ifdef CLUSTERING_KMEANS_AFKMC2_N_THRESHOLD
  static constexpr std::size_t afkmc2NThreshold = CLUSTERING_KMEANS_AFKMC2_N_THRESHOLD;
#else
  static constexpr std::size_t afkmc2NThreshold = 500000;
#endif

  static constexpr std::size_t afkmc2KFloor = AfkMc2Seeder<T>::kFloor;
#ifdef CLUSTERING_KMEANS_AFKMC2_BEST_OF_N_THRESHOLD
  static constexpr std::size_t afkmc2BestOfNThreshold =
      CLUSTERING_KMEANS_AFKMC2_BEST_OF_N_THRESHOLD;
#else
  static constexpr std::size_t afkmc2BestOfNThreshold = 5000;
#endif
 
#ifdef CLUSTERING_KMEANS_AFKMC2_BEST_OF_D_THRESHOLD
  static constexpr std::size_t afkmc2BestOfDThreshold =
      CLUSTERING_KMEANS_AFKMC2_BEST_OF_D_THRESHOLD;
#else
  static constexpr std::size_t afkmc2BestOfDThreshold = 8;
#endif
 
#ifdef CLUSTERING_KMEANS_AFKMC2_BEST_OF_K_FLOOR
  static constexpr std::size_t afkmc2BestOfKFloor = CLUSTERING_KMEANS_AFKMC2_BEST_OF_K_FLOOR;
#else
  static constexpr std::size_t afkmc2BestOfKFloor = 16;
#endif
 
#ifdef CLUSTERING_KMEANS_AFKMC2_BEST_OF_WORK_THRESHOLD
  static constexpr std::size_t afkmc2BestOfWorkThreshold =
      CLUSTERING_KMEANS_AFKMC2_BEST_OF_WORK_THRESHOLD;
#else
  static constexpr std::size_t afkmc2BestOfWorkThreshold = 80000;
#endif

  static constexpr std::size_t afkmc2ChainLengthDefault = AfkMc2Seeder<T>::chainLengthDefault;

  void run(const NDArray<T, 2> &X, std::size_t k, std::uint64_t seed, math::Pool pool,
           NDArray<T, 2> &outCentroids) {
    const std::size_t n = X.dim(0);
    const std::size_t d = X.dim(1);
    ensureShape(n, d, k);
    std::visit([&](auto &s) { s.run(X, k, seed, pool, outCentroids); }, m_held);
  }
 
private:
  void ensureShape(std::size_t n, std::size_t d, std::size_t k) {
    if (n == m_lastN && d == m_lastD && k == m_lastK) {
      return;
    }
    if (shouldUseAfkmc2(n, d, k)) {
      if (!std::holds_alternative<AfkMc2Seeder<T>>(m_held)) {
        m_held.template emplace<AfkMc2Seeder<T>>();
      }
    } else {
      if (!std::holds_alternative<GreedyKmppSeeder<T>>(m_held)) {
        m_held.template emplace<GreedyKmppSeeder<T>>();
      }
    }
    m_lastN = n;
    m_lastD = d;
    m_lastK = k;
  }
 
  [[nodiscard]] static constexpr bool shouldUseAfkmc2(std::size_t n, std::size_t d,
                                                      std::size_t k) noexcept {
    const bool largeKEnvelope = (n >= afkmc2NThreshold) && (k >= afkmc2KFloor);
    if constexpr (Mode == AutoSeederMode::kBestOf) {
      const bool bestOfEnvelope = (n >= afkmc2BestOfNThreshold) && (d >= afkmc2BestOfDThreshold) &&
                                  (k >= afkmc2BestOfKFloor) &&
                                  (n >= ((afkmc2BestOfWorkThreshold + d - 1) / d));
      return largeKEnvelope || bestOfEnvelope;
    } else {
      (void)d;
      return largeKEnvelope;
    }
  }
 
  std::variant<GreedyKmppSeeder<T>, AfkMc2Seeder<T>> m_held{
      std::in_place_type<GreedyKmppSeeder<T>>};
  std::size_t m_lastN = 0;
  std::size_t m_lastD = 0;
  std::size_t m_lastK = 0;
};
 
} // namespace clustering::kmeans