bin.h

#ifndef LIGHTGBM_BIN_H_
#define LIGHTGBM_BIN_H_
 
#include <LightGBM/meta.h>
 
#include <LightGBM/utils/common.h>
#include <LightGBM/utils/file_io.h>
 
 
#include <vector>
#include <functional>
#include <unordered_map>
#include <sstream>
 
namespace LightGBM {
 
enum BinType {
  NumericalBin,
  CategoricalBin
};
 
enum MissingType {
  None,
  Zero,
  NaN
};
 
struct HistogramBinEntry {
public:
  double sum_gradients = 0.0f;
  double sum_hessians = 0.0f;
  data_size_t cnt = 0;
  inline static void SumReducer(const char *src, char *dst, int type_size, comm_size_t len) {
    comm_size_t used_size = 0;
    const HistogramBinEntry* p1;
    HistogramBinEntry* p2;
    while (used_size < len) {
      // convert
      p1 = reinterpret_cast<const HistogramBinEntry*>(src);
      p2 = reinterpret_cast<HistogramBinEntry*>(dst);
      // add
      p2->cnt += p1->cnt;
      p2->sum_gradients += p1->sum_gradients;
      p2->sum_hessians += p1->sum_hessians;
      src += type_size;
      dst += type_size;
      used_size += type_size;
    }
  }
};
 
class BinMapper {
public:
  BinMapper();
  BinMapper(const BinMapper& other);
  explicit BinMapper(const void* memory);
  ~BinMapper();
 
  bool CheckAlign(const BinMapper& other) const {
    if (num_bin_ != other.num_bin_) {
      return false;
    }
    if (missing_type_ != other.missing_type_) {
      return false;
    }
    if (bin_type_ == BinType::NumericalBin) {
      for (int i = 0; i < num_bin_; ++i) {
        if (bin_upper_bound_[i] != other.bin_upper_bound_[i]) {
          return false;
        }
      }
    } else {
      for (int i = 0; i < num_bin_; i++) {
        if (bin_2_categorical_[i] != other.bin_2_categorical_[i]) {
          return false;
        }
      }
    }
    return true;
  }
 
  inline int num_bin() const { return num_bin_; }
  inline MissingType missing_type() const { return missing_type_; }
  inline bool is_trivial() const { return is_trivial_; }
  inline double sparse_rate() const { return sparse_rate_; }
  void SaveBinaryToFile(const VirtualFileWriter* writer) const;
  inline double BinToValue(uint32_t bin) const {
    if (bin_type_ == BinType::NumericalBin) {
      return bin_upper_bound_[bin];
    } else {
      return bin_2_categorical_[bin];
    }
  }
  size_t SizesInByte() const;
  inline uint32_t ValueToBin(double value) const;
 
  inline uint32_t GetDefaultBin() const {
    return default_bin_;
  }
  void FindBin(double* values, int num_values, size_t total_sample_cnt, int max_bin, int min_data_in_bin, int min_split_data, BinType bin_type,
               bool use_missing, bool zero_as_missing);
 
  static int SizeForSpecificBin(int bin);
 
  void CopyTo(char* buffer) const;
 
  void CopyFrom(const char* buffer);
 
  inline BinType bin_type() const { return bin_type_; }
 
  inline std::string bin_info() const {
    if (bin_type_ == BinType::CategoricalBin) {
      return Common::Join(bin_2_categorical_, ":");
    } else {
      std::stringstream str_buf;
      str_buf << std::setprecision(std::numeric_limits<double>::digits10 + 2);
      str_buf << '[' << min_val_ << ':' << max_val_ << ']';
      return str_buf.str();
    }
  }
 
private:
  int num_bin_;
  MissingType missing_type_;
  std::vector<double> bin_upper_bound_;
  bool is_trivial_;
  double sparse_rate_;
  BinType bin_type_;
  std::unordered_map<int, unsigned int> categorical_2_bin_;
  std::vector<int> bin_2_categorical_;
  double min_val_;
  double max_val_;
  uint32_t default_bin_;
};
 
class OrderedBin {
public:
  virtual ~OrderedBin() {}
 
  virtual void Init(const char* used_indices, data_size_t num_leaves) = 0;
 
  virtual void ConstructHistogram(int leaf, const score_t* gradients,
    const score_t* hessians, HistogramBinEntry* out) const = 0;
 
  virtual void ConstructHistogram(int leaf, const score_t* gradients, HistogramBinEntry* out) const = 0;
 
  virtual void Split(int leaf, int right_leaf, const char* is_in_leaf, char mark) = 0;
 
  virtual data_size_t NonZeroCount(int leaf) const = 0;
};
 
class BinIterator {
public:
  virtual uint32_t Get(data_size_t idx) = 0;
  virtual uint32_t RawGet(data_size_t idx) = 0;
  virtual void Reset(data_size_t idx) = 0;
  virtual ~BinIterator() = default;
};
 
class Bin {
public:
  virtual ~Bin() {}
  virtual void Push(int tid, data_size_t idx, uint32_t value) = 0;
 
 
  virtual void CopySubset(const Bin* full_bin, const data_size_t* used_indices, data_size_t num_used_indices) = 0;
  virtual BinIterator* GetIterator(uint32_t min_bin, uint32_t max_bin, uint32_t default_bin) const = 0;
 
  virtual void SaveBinaryToFile(const VirtualFileWriter* writer) const = 0;
 
  virtual void LoadFromMemory(const void* memory,
    const std::vector<data_size_t>& local_used_indices) = 0;
 
  virtual size_t SizesInByte() const = 0;
 
  virtual data_size_t num_data() const = 0;
 
  virtual void ReSize(data_size_t num_data) = 0;
 
  virtual void ConstructHistogram(
    const data_size_t* data_indices, data_size_t num_data,
    const score_t* ordered_gradients, const score_t* ordered_hessians,
    HistogramBinEntry* out) const = 0;
 
  virtual void ConstructHistogram(data_size_t num_data,
    const score_t* ordered_gradients, const score_t* ordered_hessians,
    HistogramBinEntry* out) const = 0;
 
  virtual void ConstructHistogram(const data_size_t* data_indices, data_size_t num_data,
                                  const score_t* ordered_gradients, HistogramBinEntry* out) const = 0;
 
  virtual void ConstructHistogram(data_size_t num_data,
                                  const score_t* ordered_gradients, HistogramBinEntry* out) const = 0;
 
  virtual data_size_t Split(uint32_t min_bin, uint32_t max_bin,
    uint32_t default_bin, MissingType missing_type, bool default_left, uint32_t threshold,
    data_size_t* data_indices, data_size_t num_data,
    data_size_t* lte_indices, data_size_t* gt_indices) const = 0;
 
  virtual data_size_t SplitCategorical(uint32_t min_bin, uint32_t max_bin,
                            uint32_t default_bin, const uint32_t* threshold, int num_threshold,
                            data_size_t* data_indices, data_size_t num_data,
                            data_size_t* lte_indices, data_size_t* gt_indices) const = 0;
 
  virtual OrderedBin* CreateOrderedBin() const = 0;
 
  virtual void FinishLoad() = 0;
 
  static Bin* CreateBin(data_size_t num_data, int num_bin,
    double sparse_rate, bool is_enable_sparse, double sparse_threshold, bool* is_sparse);
 
  static Bin* CreateDenseBin(data_size_t num_data, int num_bin);
 
  static Bin* CreateSparseBin(data_size_t num_data, int num_bin);
};
 
inline uint32_t BinMapper::ValueToBin(double value) const {
  if (std::isnan(value)) {
    if (missing_type_ == MissingType::NaN) {
      return num_bin_ - 1;
    } else {
      value = 0.0f;
    }
  }
  if (bin_type_ == BinType::NumericalBin) {
    // binary search to find bin
    int l = 0;
    int r = num_bin_ - 1;
    if (missing_type_ == MissingType::NaN) {
      r -= 1;
    }
    while (l < r) {
      int m = (r + l - 1) / 2;
      if (value <= bin_upper_bound_[m]) {
        r = m;
      } else {
        l = m + 1;
      }
    }
    return l;
  } else {
    int int_value = static_cast<int>(value);
    // convert negative value to NaN bin
    if (int_value < 0) {
      return num_bin_ - 1;
    }
    if (categorical_2_bin_.count(int_value)) {
      return categorical_2_bin_.at(int_value);
    } else {
      return num_bin_ - 1;
    }
  }
}
 
}  // namespace LightGBM
 
#endif   // LightGBM_BIN_H_