feature_histogram.hpp 35.7 KB
Newer Older
1
2
3
4
/*!
 * Copyright (c) 2016 Microsoft Corporation. All rights reserved.
 * Licensed under the MIT License. See LICENSE file in the project root for license information.
 */
Guolin Ke's avatar
Guolin Ke committed
5
6
7
#ifndef LIGHTGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_
#define LIGHTGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_

8
#include <LightGBM/bin.h>
Guolin Ke's avatar
Guolin Ke committed
9
#include <LightGBM/dataset.h>
10
#include <LightGBM/utils/array_args.h>
Guolin Ke's avatar
Guolin Ke committed
11

12
#include <algorithm>
13
#include <cmath>
14
15
16
17
18
19
#include <cstring>
#include <memory>
#include <utility>
#include <vector>

#include "split_info.hpp"
Guolin Ke's avatar
Guolin Ke committed
20

21
namespace LightGBM {
Guolin Ke's avatar
Guolin Ke committed
22

Guolin Ke's avatar
Guolin Ke committed
23
class FeatureMetainfo {
24
public:
Guolin Ke's avatar
Guolin Ke committed
25
  int num_bin;
Guolin Ke's avatar
Guolin Ke committed
26
  MissingType missing_type;
27
  int8_t offset = 0;
Guolin Ke's avatar
Guolin Ke committed
28
  uint32_t default_bin;
Guolin Ke's avatar
Guolin Ke committed
29
  int8_t monotone_type;
Guolin Ke's avatar
Guolin Ke committed
30
  double penalty;
Guolin Ke's avatar
Guolin Ke committed
31
  /*! \brief pointer of tree config */
Guolin Ke's avatar
Guolin Ke committed
32
  const Config* config;
33
  BinType bin_type;
Guolin Ke's avatar
Guolin Ke committed
34
};
Guolin Ke's avatar
Guolin Ke committed
35
36
37
38
/*!
* \brief FeatureHistogram is used to construct and store a histogram for a feature.
*/
class FeatureHistogram {
39
public:
Guolin Ke's avatar
Guolin Ke committed
40
  FeatureHistogram() {
Guolin Ke's avatar
Guolin Ke committed
41
    data_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
42
  }
Guolin Ke's avatar
Guolin Ke committed
43

Guolin Ke's avatar
Guolin Ke committed
44
45
46
  ~FeatureHistogram() {
  }

Guolin Ke's avatar
Guolin Ke committed
47
48
49
50
51
  /*! \brief Disable copy */
  FeatureHistogram& operator=(const FeatureHistogram&) = delete;
  /*! \brief Disable copy */
  FeatureHistogram(const FeatureHistogram&) = delete;

Guolin Ke's avatar
Guolin Ke committed
52
53
54
55
56
  /*!
  * \brief Init the feature histogram
  * \param feature the feature data for this histogram
  * \param min_num_data_one_leaf minimal number of data in one leaf
  */
57
  void Init(hist_t* data, const FeatureMetainfo* meta) {
Guolin Ke's avatar
Guolin Ke committed
58
59
    meta_ = meta;
    data_ = data;
60
    if (meta_->bin_type == BinType::NumericalBin) {
61
      find_best_threshold_fun_ = std::bind(&FeatureHistogram::FindBestThresholdNumerical, this, std::placeholders::_1
62
        , std::placeholders::_2, std::placeholders::_3, std::placeholders::_4, std::placeholders::_5, std::placeholders::_6);
63
64
    } else {
      find_best_threshold_fun_ = std::bind(&FeatureHistogram::FindBestThresholdCategorical, this, std::placeholders::_1
65
        , std::placeholders::_2, std::placeholders::_3, std::placeholders::_4, std::placeholders::_5, std::placeholders::_6);
66
    }
67
    rand_ = Random(meta_->config->extra_seed);
Guolin Ke's avatar
Guolin Ke committed
68
69
  }

70
  hist_t* RawData() {
Guolin Ke's avatar
Guolin Ke committed
71
    return data_;
Guolin Ke's avatar
Guolin Ke committed
72
73
74
75
76
77
  }
  /*!
  * \brief Subtract current histograms with other
  * \param other The histogram that want to subtract
  */
  void Subtract(const FeatureHistogram& other) {
78
79
    for (int i = 0; i < (meta_->num_bin - meta_->offset) * 2; ++i) {
      data_[i] -= other.data_[i];
Guolin Ke's avatar
Guolin Ke committed
80
81
    }
  }
82

Guolin Ke's avatar
Guolin Ke committed
83
  void FindBestThreshold(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint,
84
    SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
85
    output->default_left = true;
Guolin Ke's avatar
Guolin Ke committed
86
    output->gain = kMinScore;
Guolin Ke's avatar
Guolin Ke committed
87
    find_best_threshold_fun_(sum_gradient, sum_hessian + 2 * kEpsilon, num_data, min_constraint, max_constraint, output);
Guolin Ke's avatar
Guolin Ke committed
88
    output->gain *= meta_->penalty;
89
90
  }

Guolin Ke's avatar
Guolin Ke committed
91
  void FindBestThresholdNumerical(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint,
92
    SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
93
    is_splittable_ = false;
Guolin Ke's avatar
Guolin Ke committed
94
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
95
      meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
96
    double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
97
98
99
100
101
    int rand_threshold = 0;
    if (meta_->num_bin - 2 > 0){
      rand_threshold = rand_.NextInt(0, meta_->num_bin - 2);
    }
    bool is_rand = meta_->config->extra_trees;
Guolin Ke's avatar
Guolin Ke committed
102
103
    if (meta_->num_bin > 2 && meta_->missing_type != MissingType::None) {
      if (meta_->missing_type == MissingType::Zero) {
104
105
106
107
108
109
110
111
        if (is_rand) {
          FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, true, false, rand_threshold);
          FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, true, false, rand_threshold);
        }
        else {
          FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, true, false, rand_threshold);
          FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, true, false, rand_threshold);
        }
Guolin Ke's avatar
Guolin Ke committed
112
      } else {
113
114
115
116
117
118
119
        if (is_rand) {
          FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, true, rand_threshold);
          FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, false, true, rand_threshold);
        } else {
          FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, true, rand_threshold);
          FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, 1, false, true, rand_threshold);
        }
Guolin Ke's avatar
Guolin Ke committed
120
      }
121
    } else {
122
123
124
125
126
      if (is_rand) {
        FindBestThresholdSequence<true>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, false, rand_threshold);
      } else {
        FindBestThresholdSequence<false>(sum_gradient, sum_hessian, num_data, min_constraint, max_constraint, min_gain_shift, output, -1, false, false, rand_threshold);
      }
Guolin Ke's avatar
Guolin Ke committed
127
128
129
130
      // fix the direction error when only have 2 bins
      if (meta_->missing_type == MissingType::NaN) {
        output->default_left = false;
      }
Guolin Ke's avatar
Guolin Ke committed
131
    }
Guolin Ke's avatar
Guolin Ke committed
132
    output->gain -= min_gain_shift;
Guolin Ke's avatar
Guolin Ke committed
133
134
135
    output->monotone_type = meta_->monotone_type;
    output->min_constraint = min_constraint;
    output->max_constraint = max_constraint;
Guolin Ke's avatar
Guolin Ke committed
136
  }
137

138
  void FindBestThresholdCategorical(double sum_gradient, double sum_hessian, data_size_t num_data,
139
140
    double min_constraint, double max_constraint,
    SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
141
    output->default_left = false;
142
    double best_gain = kMinScore;
143
    data_size_t best_left_count = 0;
ChenZhiyong's avatar
ChenZhiyong committed
144
145
    double best_sum_left_gradient = 0;
    double best_sum_left_hessian = 0;
Guolin Ke's avatar
Guolin Ke committed
146
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian, meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step);
147

Guolin Ke's avatar
Guolin Ke committed
148
    double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
ChenZhiyong's avatar
ChenZhiyong committed
149
    bool is_full_categorical = meta_->missing_type == MissingType::None;
150
    int used_bin = meta_->num_bin - 1 + is_full_categorical;
ChenZhiyong's avatar
ChenZhiyong committed
151

Guolin Ke's avatar
Guolin Ke committed
152
    std::vector<int> sorted_idx;
Guolin Ke's avatar
Guolin Ke committed
153
154
    double l2 = meta_->config->lambda_l2;
    bool use_onehot = meta_->num_bin <= meta_->config->max_cat_to_onehot;
155
156
    int best_threshold = -1;
    int best_dir = 1;
157
    const double cnt_factor = num_data / sum_hessian;
158
159
    if (use_onehot) {
      for (int t = 0; t < used_bin; ++t) {
160
161
162
        const auto grad = GET_GRAD(data_, t);
        const auto hess = GET_HESS(data_, t);
        data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
163
        // if data not enough, or sum hessian too small
164
165
166
        if (cnt < meta_->config->min_data_in_leaf
          || hess < meta_->config->min_sum_hessian_in_leaf) continue;
        data_size_t other_count = num_data - cnt;
167
        // if data not enough
Guolin Ke's avatar
Guolin Ke committed
168
        if (other_count < meta_->config->min_data_in_leaf) continue;
ChenZhiyong's avatar
ChenZhiyong committed
169

170
        double sum_other_hessian = sum_hessian - hess - kEpsilon;
171
        // if sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
172
        if (sum_other_hessian < meta_->config->min_sum_hessian_in_leaf) continue;
ChenZhiyong's avatar
ChenZhiyong committed
173

174
        double sum_other_gradient = sum_gradient - grad;
175
        // current split gain
176
177
178
        double current_gain = GetSplitGains(sum_other_gradient, sum_other_hessian, grad, hess + kEpsilon,
          meta_->config->lambda_l1, l2, meta_->config->max_delta_step,
          min_constraint, max_constraint, 0);
179
        // gain with split is worse than without split
ChenZhiyong's avatar
ChenZhiyong committed
180
        if (current_gain <= min_gain_shift) continue;
181
182

        // mark to is splittable
ChenZhiyong's avatar
ChenZhiyong committed
183
        is_splittable_ = true;
184
        // better split point
ChenZhiyong's avatar
ChenZhiyong committed
185
        if (current_gain > best_gain) {
186
          best_threshold = t;
187
188
189
          best_sum_left_gradient = grad;
          best_sum_left_hessian = hess + kEpsilon;
          best_left_count = cnt;
ChenZhiyong's avatar
ChenZhiyong committed
190
          best_gain = current_gain;
191
192
193
194
        }
      }
    } else {
      for (int i = 0; i < used_bin; ++i) {
195
        if (Common::RoundInt(GET_HESS(data_, i) * cnt_factor) >= meta_->config->cat_smooth) {
196
197
198
199
200
          sorted_idx.push_back(i);
        }
      }
      used_bin = static_cast<int>(sorted_idx.size());

Guolin Ke's avatar
Guolin Ke committed
201
      l2 += meta_->config->cat_l2;
202
203

      auto ctr_fun = [this](double sum_grad, double sum_hess) {
Guolin Ke's avatar
Guolin Ke committed
204
        return (sum_grad) / (sum_hess + meta_->config->cat_smooth);
205
206
      };
      std::sort(sorted_idx.begin(), sorted_idx.end(),
207
208
209
        [this, &ctr_fun](int i, int j) {
          return ctr_fun(GET_GRAD(data_, i), GET_HESS(data_, i)) < ctr_fun(GET_GRAD(data_, j), GET_HESS(data_, j));
        });
210
211
212
213
214

      std::vector<int> find_direction(1, 1);
      std::vector<int> start_position(1, 0);
      find_direction.push_back(-1);
      start_position.push_back(used_bin - 1);
Guolin Ke's avatar
Guolin Ke committed
215
      const int max_num_cat = std::min(meta_->config->max_cat_threshold, (used_bin + 1) / 2);
216
217
218
219
220
221
      int max_threshold = std::max(std::min(max_num_cat, used_bin) - 1, 0);
      int rand_threshold = 0;
      if (max_threshold > 0) {
        rand_threshold = rand_.NextInt(0, max_threshold);
      }
      
222
223
224
225
      is_splittable_ = false;
      for (size_t out_i = 0; out_i < find_direction.size(); ++out_i) {
        auto dir = find_direction[out_i];
        auto start_pos = start_position[out_i];
Guolin Ke's avatar
Guolin Ke committed
226
        data_size_t min_data_per_group = meta_->config->min_data_per_group;
227
228
229
230
231
232
233
        data_size_t cnt_cur_group = 0;
        double sum_left_gradient = 0.0f;
        double sum_left_hessian = kEpsilon;
        data_size_t left_count = 0;
        for (int i = 0; i < used_bin && i < max_num_cat; ++i) {
          auto t = sorted_idx[start_pos];
          start_pos += dir;
234
235
236
          const auto grad = GET_GRAD(data_, t);
          const auto hess = GET_HESS(data_, t);
          data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
237

238
239
240
241
          sum_left_gradient += grad;
          sum_left_hessian += hess;
          left_count += cnt;
          cnt_cur_group += cnt;
242

Guolin Ke's avatar
Guolin Ke committed
243
          if (left_count < meta_->config->min_data_in_leaf
244
            || sum_left_hessian < meta_->config->min_sum_hessian_in_leaf) continue;
245
          data_size_t right_count = num_data - left_count;
Guolin Ke's avatar
Guolin Ke committed
246
          if (right_count < meta_->config->min_data_in_leaf || right_count < min_data_per_group) break;
247
248

          double sum_right_hessian = sum_hessian - sum_left_hessian;
Guolin Ke's avatar
Guolin Ke committed
249
          if (sum_right_hessian < meta_->config->min_sum_hessian_in_leaf) break;
250
251
252
253
254
255

          if (cnt_cur_group < min_data_per_group) continue;

          cnt_cur_group = 0;

          double sum_right_gradient = sum_gradient - sum_left_gradient;
256
257
258
259
260
261
262
263
264
265
266
267
268
269
          if (!meta_->config->extra_trees || i == rand_threshold) {
            double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
                                                meta_->config->lambda_l1, l2, meta_->config->max_delta_step,
                                                min_constraint, max_constraint, 0);
            if (current_gain <= min_gain_shift) continue;
            is_splittable_ = true;
            if (current_gain > best_gain) {
              best_left_count = left_count;
              best_sum_left_gradient = sum_left_gradient;
              best_sum_left_hessian = sum_left_hessian;
              best_threshold = i;
              best_gain = current_gain;
              best_dir = dir;
            }
270
          }
ChenZhiyong's avatar
ChenZhiyong committed
271
        }
272
273
      }
    }
274

275
    if (is_splittable_) {
Guolin Ke's avatar
Guolin Ke committed
276
      output->left_output = CalculateSplittedLeafOutput(best_sum_left_gradient, best_sum_left_hessian,
277
278
        meta_->config->lambda_l1, l2, meta_->config->max_delta_step,
        min_constraint, max_constraint);
279
280
281
282
      output->left_count = best_left_count;
      output->left_sum_gradient = best_sum_left_gradient;
      output->left_sum_hessian = best_sum_left_hessian - kEpsilon;
      output->right_output = CalculateSplittedLeafOutput(sum_gradient - best_sum_left_gradient,
283
284
285
        sum_hessian - best_sum_left_hessian,
        meta_->config->lambda_l1, l2, meta_->config->max_delta_step,
        min_constraint, max_constraint);
286
287
288
      output->right_count = num_data - best_left_count;
      output->right_sum_gradient = sum_gradient - best_sum_left_gradient;
      output->right_sum_hessian = sum_hessian - best_sum_left_hessian - kEpsilon;
Guolin Ke's avatar
Guolin Ke committed
289
      output->gain = best_gain - min_gain_shift;
290
291
292
      if (use_onehot) {
        output->num_cat_threshold = 1;
        output->cat_threshold = std::vector<uint32_t>(1, static_cast<uint32_t>(best_threshold));
ChenZhiyong's avatar
ChenZhiyong committed
293
      } else {
294
295
296
297
298
299
300
301
302
303
304
305
        output->num_cat_threshold = best_threshold + 1;
        output->cat_threshold = std::vector<uint32_t>(output->num_cat_threshold);
        if (best_dir == 1) {
          for (int i = 0; i < output->num_cat_threshold; ++i) {
            auto t = sorted_idx[i];
            output->cat_threshold[i] = t;
          }
        } else {
          for (int i = 0; i < output->num_cat_threshold; ++i) {
            auto t = sorted_idx[used_bin - 1 - i];
            output->cat_threshold[i] = t;
          }
ChenZhiyong's avatar
ChenZhiyong committed
306
307
        }
      }
Guolin Ke's avatar
Guolin Ke committed
308
309
310
      output->monotone_type = 0;
      output->min_constraint = min_constraint;
      output->max_constraint = max_constraint;
311
    }
312
313
  }

314
  void GatherInfoForThreshold(double sum_gradient, double sum_hessian,
315
    uint32_t threshold, data_size_t num_data, SplitInfo* output) {
316
317
    if (meta_->bin_type == BinType::NumericalBin) {
      GatherInfoForThresholdNumerical(sum_gradient, sum_hessian, threshold,
318
        num_data, output);
319
320
    } else {
      GatherInfoForThresholdCategorical(sum_gradient, sum_hessian, threshold,
321
        num_data, output);
322
323
324
325
    }
  }

  void GatherInfoForThresholdNumerical(double sum_gradient, double sum_hessian,
326
327
    uint32_t threshold, data_size_t num_data,
    SplitInfo* output) {
328
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
329
330
      meta_->config->lambda_l1, meta_->config->lambda_l2,
      meta_->config->max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
331
    double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
332
333

    // do stuff here
334
    const int8_t offset = meta_->offset;
335
336
337
338
339
340

    double sum_right_gradient = 0.0f;
    double sum_right_hessian = kEpsilon;
    data_size_t right_count = 0;

    // set values
341
342
    bool use_na_as_missing = false;
    bool skip_default_bin = false;
343
344
    if (meta_->missing_type == MissingType::Zero) {
      skip_default_bin = true;
345
    } else if (meta_->missing_type == MissingType::NaN) {
346
347
348
      use_na_as_missing = true;
    }

349
350
    int t = meta_->num_bin - 1 - offset - use_na_as_missing;
    const int t_end = 1 - offset;
351
    const double cnt_factor = num_data / sum_hessian;
352
353
    // from right to left, and we don't need data in bin0
    for (; t >= t_end; --t) {
354
      if (static_cast<uint32_t>(t + offset) < threshold) { break; }
355
356

      // need to skip default bin
357
      if (skip_default_bin && (t + offset) == static_cast<int>(meta_->default_bin)) { continue; }
358
359
360
361
362
363
      const auto grad = GET_GRAD(data_, t);
      const auto hess = GET_HESS(data_, t);
      data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
      sum_right_gradient += grad;
      sum_right_hessian += hess;
      right_count += cnt;
364
365
366
367
368
    }
    double sum_left_gradient = sum_gradient - sum_right_gradient;
    double sum_left_hessian = sum_hessian - sum_right_hessian;
    data_size_t left_count = num_data - right_count;
    double current_gain = GetLeafSplitGain(sum_left_gradient, sum_left_hessian,
369
370
371
372
373
      meta_->config->lambda_l1, meta_->config->lambda_l2,
      meta_->config->max_delta_step)
      + GetLeafSplitGain(sum_right_gradient, sum_right_hessian,
        meta_->config->lambda_l1, meta_->config->lambda_l2,
        meta_->config->max_delta_step);
374
375
376
377

    // gain with split is worse than without split
    if (std::isnan(current_gain) || current_gain <= min_gain_shift) {
      output->gain = kMinScore;
378
      Log::Warning("'Forced Split' will be ignored since the gain getting worse. ");
379
      return;
380
    }
381
382
383
384

    // update split information
    output->threshold = threshold;
    output->left_output = CalculateSplittedLeafOutput(sum_left_gradient, sum_left_hessian,
385
386
      meta_->config->lambda_l1, meta_->config->lambda_l2,
      meta_->config->max_delta_step);
387
388
389
390
    output->left_count = left_count;
    output->left_sum_gradient = sum_left_gradient;
    output->left_sum_hessian = sum_left_hessian - kEpsilon;
    output->right_output = CalculateSplittedLeafOutput(sum_gradient - sum_left_gradient,
391
392
393
      sum_hessian - sum_left_hessian,
      meta_->config->lambda_l1, meta_->config->lambda_l2,
      meta_->config->max_delta_step);
394
395
396
397
398
399
400
401
402
    output->right_count = num_data - left_count;
    output->right_sum_gradient = sum_gradient - sum_left_gradient;
    output->right_sum_hessian = sum_hessian - sum_left_hessian - kEpsilon;
    output->gain = current_gain;
    output->gain -= min_gain_shift;
    output->default_left = true;
  }

  void GatherInfoForThresholdCategorical(double sum_gradient, double sum_hessian,
403
    uint32_t threshold, data_size_t num_data, SplitInfo* output) {
404
405
406
    // get SplitInfo for a given one-hot categorical split.
    output->default_left = false;
    double gain_shift = GetLeafSplitGain(
407
408
409
      sum_gradient, sum_hessian,
      meta_->config->lambda_l1, meta_->config->lambda_l2,
      meta_->config->max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
410
    double min_gain_shift = gain_shift + meta_->config->min_gain_to_split;
411
412
413
414
415
416
417
    bool is_full_categorical = meta_->missing_type == MissingType::None;
    int used_bin = meta_->num_bin - 1 + is_full_categorical;
    if (threshold >= static_cast<uint32_t>(used_bin)) {
      output->gain = kMinScore;
      Log::Warning("Invalid categorical threshold split");
      return;
    }
418
419
420
421
    const double cnt_factor = num_data / sum_hessian;
    const auto grad = GET_GRAD(data_, threshold);
    const auto hess = GET_HESS(data_, threshold);
    data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
422

Guolin Ke's avatar
Guolin Ke committed
423
    double l2 = meta_->config->lambda_l2;
424
    data_size_t left_count = cnt;
425
    data_size_t right_count = num_data - left_count;
426
    double sum_left_hessian = hess + kEpsilon;
427
    double sum_right_hessian = sum_hessian - sum_left_hessian;
428
    double sum_left_gradient = grad;
429
430
431
    double sum_right_gradient = sum_gradient - sum_left_gradient;
    // current split gain
    double current_gain = GetLeafSplitGain(sum_right_gradient, sum_right_hessian,
432
433
434
435
436
      meta_->config->lambda_l1, l2,
      meta_->config->max_delta_step)
      + GetLeafSplitGain(sum_left_gradient, sum_left_hessian,
        meta_->config->lambda_l1, l2,
        meta_->config->max_delta_step);
437
438
    if (std::isnan(current_gain) || current_gain <= min_gain_shift) {
      output->gain = kMinScore;
439
      Log::Warning("'Forced Split' will be ignored since the gain getting worse. ");
440
441
442
443
      return;
    }

    output->left_output = CalculateSplittedLeafOutput(sum_left_gradient, sum_left_hessian,
444
445
      meta_->config->lambda_l1, l2,
      meta_->config->max_delta_step);
446
447
448
449
    output->left_count = left_count;
    output->left_sum_gradient = sum_left_gradient;
    output->left_sum_hessian = sum_left_hessian - kEpsilon;
    output->right_output = CalculateSplittedLeafOutput(sum_right_gradient, sum_right_hessian,
450
451
      meta_->config->lambda_l1, l2,
      meta_->config->max_delta_step);
452
453
454
455
456
457
458
459
460
    output->right_count = right_count;
    output->right_sum_gradient = sum_gradient - sum_left_gradient;
    output->right_sum_hessian = sum_right_hessian - kEpsilon;
    output->gain = current_gain - min_gain_shift;
    output->num_cat_threshold = 1;
    output->cat_threshold = std::vector<uint32_t>(1, threshold);
  }


Guolin Ke's avatar
Guolin Ke committed
461
462
463
464
  /*!
  * \brief Binary size of this histogram
  */
  int SizeOfHistgram() const {
465
    return (meta_->num_bin - meta_->offset) * KHistEntrySize;
Guolin Ke's avatar
Guolin Ke committed
466
467
468
469
470
  }

  /*!
  * \brief Restore histogram from memory
  */
Guolin Ke's avatar
Guolin Ke committed
471
  void FromMemory(char* memory_data) {
472
    std::memcpy(data_, memory_data, (meta_->num_bin - meta_->offset) * KHistEntrySize);
Guolin Ke's avatar
Guolin Ke committed
473
474
475
476
477
478
479
480
481
482
483
484
  }

  /*!
  * \brief True if this histogram can be splitted
  */
  bool is_splittable() { return is_splittable_; }

  /*!
  * \brief Set splittable to this histogram
  */
  void set_is_splittable(bool val) { is_splittable_ = val; }

485
486
487
488
489
490
491
492
493
494
495
496
  static double ThresholdL1(double s, double l1) {
    const double reg_s = std::max(0.0, std::fabs(s) - l1);
    return Common::Sign(s) * reg_s;
  }

  static double CalculateSplittedLeafOutput(double sum_gradients, double sum_hessians, double l1, double l2, double max_delta_step) {
    double ret = -ThresholdL1(sum_gradients, l1) / (sum_hessians + l2);
    if (max_delta_step <= 0.0f || std::fabs(ret) <= max_delta_step) {
      return ret;
    } else {
      return Common::Sign(ret) * max_delta_step;
    }
Guolin Ke's avatar
Guolin Ke committed
497
498
  }

499
private:
Guolin Ke's avatar
Guolin Ke committed
500
  static double GetSplitGains(double sum_left_gradients, double sum_left_hessians,
501
502
503
    double sum_right_gradients, double sum_right_hessians,
    double l1, double l2, double max_delta_step,
    double min_constraint, double max_constraint, int8_t monotone_constraint) {
504
505
    double left_output = CalculateSplittedLeafOutput(sum_left_gradients, sum_left_hessians, l1, l2, max_delta_step, min_constraint, max_constraint);
    double right_output = CalculateSplittedLeafOutput(sum_right_gradients, sum_right_hessians, l1, l2, max_delta_step, min_constraint, max_constraint);
Guolin Ke's avatar
Guolin Ke committed
506
507
508
509
510
511
512
513
    if (((monotone_constraint > 0) && (left_output > right_output)) ||
      ((monotone_constraint < 0) && (left_output < right_output))) {
      return 0;
    }
    return GetLeafSplitGainGivenOutput(sum_left_gradients, sum_left_hessians, l1, l2, left_output)
      + GetLeafSplitGainGivenOutput(sum_right_gradients, sum_right_hessians, l1, l2, right_output);
  }

Guolin Ke's avatar
Guolin Ke committed
514
  /*!
515
  * \brief Calculate the output of a leaf based on regularized sum_gradients and sum_hessians
Guolin Ke's avatar
Guolin Ke committed
516
517
518
519
  * \param sum_gradients
  * \param sum_hessians
  * \return leaf output
  */
520
  static double CalculateSplittedLeafOutput(double sum_gradients, double sum_hessians, double l1, double l2, double max_delta_step,
521
    double min_constraint, double max_constraint) {
522
    double ret = CalculateSplittedLeafOutput(sum_gradients, sum_hessians, l1, l2, max_delta_step);
Guolin Ke's avatar
Guolin Ke committed
523
524
525
526
527
528
    if (ret < min_constraint) {
      ret = min_constraint;
    } else if (ret > max_constraint) {
      ret = max_constraint;
    }
    return ret;
Guolin Ke's avatar
Guolin Ke committed
529
  }
Guolin Ke's avatar
Guolin Ke committed
530

Guolin Ke's avatar
Guolin Ke committed
531
532
533
534
535
536
  /*!
  * \brief Calculate the split gain based on regularized sum_gradients and sum_hessians
  * \param sum_gradients
  * \param sum_hessians
  * \return split gain
  */
537
538
539
  static double GetLeafSplitGain(double sum_gradients, double sum_hessians, double l1, double l2, double max_delta_step) {
    double output = CalculateSplittedLeafOutput(sum_gradients, sum_hessians, l1, l2, max_delta_step);
    return GetLeafSplitGainGivenOutput(sum_gradients, sum_hessians, l1, l2, output);
Guolin Ke's avatar
Guolin Ke committed
540
541
542
543
544
545
  }

  static double GetLeafSplitGainGivenOutput(double sum_gradients, double sum_hessians, double l1, double l2, double output) {
    const double sg_l1 = ThresholdL1(sum_gradients, l1);
    return -(2.0 * sg_l1 * output + (sum_hessians + l2) * output * output);
  }
Guolin Ke's avatar
Guolin Ke committed
546

547
  template<bool is_rand>
Guolin Ke's avatar
Guolin Ke committed
548
  void FindBestThresholdSequence(double sum_gradient, double sum_hessian, data_size_t num_data, double min_constraint, double max_constraint,
549
                                 double min_gain_shift, SplitInfo* output, int dir, bool skip_default_bin, bool use_na_as_missing, int rand_threshold) {
550
    const int8_t offset = meta_->offset;
Guolin Ke's avatar
Guolin Ke committed
551
552
553
554
555
556

    double best_sum_left_gradient = NAN;
    double best_sum_left_hessian = NAN;
    double best_gain = kMinScore;
    data_size_t best_left_count = 0;
    uint32_t best_threshold = static_cast<uint32_t>(meta_->num_bin);
557
    const double cnt_factor = num_data / sum_hessian;
Guolin Ke's avatar
Guolin Ke committed
558
559
560
561
562
    if (dir == -1) {
      double sum_right_gradient = 0.0f;
      double sum_right_hessian = kEpsilon;
      data_size_t right_count = 0;

563
564
      int t = meta_->num_bin - 1 - offset - use_na_as_missing;
      const int t_end = 1 - offset;
Guolin Ke's avatar
Guolin Ke committed
565
566
567
568

      // from right to left, and we don't need data in bin0
      for (; t >= t_end; --t) {
        // need to skip default bin
569
        if (skip_default_bin && (t + offset) == static_cast<int>(meta_->default_bin)) { continue; }
Guolin Ke's avatar
Guolin Ke committed
570

571
572
573
574
575
576
        const auto grad = GET_GRAD(data_, t);
        const auto hess = GET_HESS(data_, t);
        data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
        sum_right_gradient += grad;
        sum_right_hessian += hess;
        right_count += cnt;
Guolin Ke's avatar
Guolin Ke committed
577
        // if data not enough, or sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
578
        if (right_count < meta_->config->min_data_in_leaf
579
          || sum_right_hessian < meta_->config->min_sum_hessian_in_leaf) continue;
Guolin Ke's avatar
Guolin Ke committed
580
581
        data_size_t left_count = num_data - right_count;
        // if data not enough
Guolin Ke's avatar
Guolin Ke committed
582
        if (left_count < meta_->config->min_data_in_leaf) break;
Guolin Ke's avatar
Guolin Ke committed
583
584
585

        double sum_left_hessian = sum_hessian - sum_right_hessian;
        // if sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
586
        if (sum_left_hessian < meta_->config->min_sum_hessian_in_leaf) break;
Guolin Ke's avatar
Guolin Ke committed
587
588

        double sum_left_gradient = sum_gradient - sum_right_gradient;
589
590
591
592
593
594
595
        if (!is_rand || t - 1 + offset == rand_threshold) {
          // current split gain
          double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
                                              meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step,
                                              min_constraint, max_constraint, meta_->monotone_type);
          // gain with split is worse than without split
          if (current_gain <= min_gain_shift) continue;
Guolin Ke's avatar
Guolin Ke committed
596

597
598
599
600
601
602
603
604
605
606
607
          // mark to is splittable
          is_splittable_ = true;
          // better split point
          if (current_gain > best_gain) {
            best_left_count = left_count;
            best_sum_left_gradient = sum_left_gradient;
            best_sum_left_hessian = sum_left_hessian;
            // left is <= threshold, right is > threshold.  so this is t-1
            best_threshold = static_cast<uint32_t>(t - 1 + offset);
            best_gain = current_gain;
          }
Guolin Ke's avatar
Guolin Ke committed
608
609
        }
      }
ChenZhiyong's avatar
ChenZhiyong committed
610
    } else {
Guolin Ke's avatar
Guolin Ke committed
611
612
613
614
615
      double sum_left_gradient = 0.0f;
      double sum_left_hessian = kEpsilon;
      data_size_t left_count = 0;

      int t = 0;
616
      const int t_end = meta_->num_bin - 2 - offset;
Guolin Ke's avatar
Guolin Ke committed
617

618
      if (use_na_as_missing && offset == 1) {
Guolin Ke's avatar
Guolin Ke committed
619
620
621
        sum_left_gradient = sum_gradient;
        sum_left_hessian = sum_hessian - kEpsilon;
        left_count = num_data;
622
        for (int i = 0; i < meta_->num_bin - offset; ++i) {
623
624
625
626
627
628
          const auto grad = GET_GRAD(data_, i);
          const auto hess = GET_HESS(data_, i);
          data_size_t cnt = static_cast<data_size_t>(Common::RoundInt(hess * cnt_factor));
          sum_left_gradient -= grad;
          sum_left_hessian -= hess;
          left_count -= cnt;
Guolin Ke's avatar
Guolin Ke committed
629
630
631
632
        }
        t = -1;
      }

Guolin Ke's avatar
Guolin Ke committed
633
634
      for (; t <= t_end; ++t) {
        // need to skip default bin
635
        if (skip_default_bin && (t + offset) == static_cast<int>(meta_->default_bin)) { continue; }
Guolin Ke's avatar
Guolin Ke committed
636
        if (t >= 0) {
637
638
639
          sum_left_gradient += GET_GRAD(data_, t);
          sum_left_hessian += GET_HESS(data_, t);
          left_count += static_cast<data_size_t>(Common::RoundInt(GET_HESS(data_, t) * cnt_factor));
Guolin Ke's avatar
Guolin Ke committed
640
        }
Guolin Ke's avatar
Guolin Ke committed
641
        // if data not enough, or sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
642
        if (left_count < meta_->config->min_data_in_leaf
643
          || sum_left_hessian < meta_->config->min_sum_hessian_in_leaf) continue;
Guolin Ke's avatar
Guolin Ke committed
644
645
        data_size_t right_count = num_data - left_count;
        // if data not enough
Guolin Ke's avatar
Guolin Ke committed
646
        if (right_count < meta_->config->min_data_in_leaf) break;
Guolin Ke's avatar
Guolin Ke committed
647
648
649

        double sum_right_hessian = sum_hessian - sum_left_hessian;
        // if sum hessian too small
Guolin Ke's avatar
Guolin Ke committed
650
        if (sum_right_hessian < meta_->config->min_sum_hessian_in_leaf) break;
Guolin Ke's avatar
Guolin Ke committed
651
652

        double sum_right_gradient = sum_gradient - sum_left_gradient;
653
654
655
656
657
658
659
        if (!is_rand || t + offset == rand_threshold) {
          // current split gain
          double current_gain = GetSplitGains(sum_left_gradient, sum_left_hessian, sum_right_gradient, sum_right_hessian,
                                              meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step,
                                              min_constraint, max_constraint, meta_->monotone_type);
          // gain with split is worse than without split
          if (current_gain <= min_gain_shift) continue;
Guolin Ke's avatar
Guolin Ke committed
660

661
662
663
664
665
666
667
668
669
670
          // mark to is splittable
          is_splittable_ = true;
          // better split point
          if (current_gain > best_gain) {
            best_left_count = left_count;
            best_sum_left_gradient = sum_left_gradient;
            best_sum_left_hessian = sum_left_hessian;
            best_threshold = static_cast<uint32_t>(t + offset);
            best_gain = current_gain;
          }
Guolin Ke's avatar
Guolin Ke committed
671
672
673
674
675
676
677
678
        }
      }
    }

    if (is_splittable_ && best_gain > output->gain) {
      // update split information
      output->threshold = best_threshold;
      output->left_output = CalculateSplittedLeafOutput(best_sum_left_gradient, best_sum_left_hessian,
679
680
        meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step,
        min_constraint, max_constraint);
Guolin Ke's avatar
Guolin Ke committed
681
682
683
684
      output->left_count = best_left_count;
      output->left_sum_gradient = best_sum_left_gradient;
      output->left_sum_hessian = best_sum_left_hessian - kEpsilon;
      output->right_output = CalculateSplittedLeafOutput(sum_gradient - best_sum_left_gradient,
685
686
687
        sum_hessian - best_sum_left_hessian,
        meta_->config->lambda_l1, meta_->config->lambda_l2, meta_->config->max_delta_step,
        min_constraint, max_constraint);
Guolin Ke's avatar
Guolin Ke committed
688
689
690
691
      output->right_count = num_data - best_left_count;
      output->right_sum_gradient = sum_gradient - best_sum_left_gradient;
      output->right_sum_hessian = sum_hessian - best_sum_left_hessian - kEpsilon;
      output->gain = best_gain;
Guolin Ke's avatar
Guolin Ke committed
692
      output->default_left = dir == -1;
Guolin Ke's avatar
Guolin Ke committed
693
694
695
    }
  }

Guolin Ke's avatar
Guolin Ke committed
696
  const FeatureMetainfo* meta_;
Guolin Ke's avatar
Guolin Ke committed
697
  /*! \brief sum of gradient of each bin */
698
  hist_t* data_;
Guolin Ke's avatar
Guolin Ke committed
699
  bool is_splittable_ = true;
700
701
  /*! \brief random number generator for extremely randomized trees */
  Random rand_;
702

Guolin Ke's avatar
Guolin Ke committed
703
  std::function<void(double, double, data_size_t, double, double, SplitInfo*)> find_best_threshold_fun_;
Guolin Ke's avatar
Guolin Ke committed
704
};
Guolin Ke's avatar
Guolin Ke committed
705
class HistogramPool {
706
public:
Guolin Ke's avatar
Guolin Ke committed
707
708
709
710
  /*!
  * \brief Constructor
  */
  HistogramPool() {
Guolin Ke's avatar
Guolin Ke committed
711
712
    cache_size_ = 0;
    total_size_ = 0;
Guolin Ke's avatar
Guolin Ke committed
713
714
715
716
717
718
719
720
721
722
723
  }
  /*!
  * \brief Destructor
  */
  ~HistogramPool() {
  }
  /*!
  * \brief Reset pool size
  * \param cache_size Max cache size
  * \param total_size Total size will be used
  */
Guolin Ke's avatar
Guolin Ke committed
724
  void Reset(int cache_size, int total_size) {
Guolin Ke's avatar
Guolin Ke committed
725
726
727
728
729
730
731
732
733
    cache_size_ = cache_size;
    // at least need 2 bucket to store smaller leaf and larger leaf
    CHECK(cache_size_ >= 2);
    total_size_ = total_size;
    if (cache_size_ > total_size_) {
      cache_size_ = total_size_;
    }
    is_enough_ = (cache_size_ == total_size_);
    if (!is_enough_) {
734
735
736
      mapper_.resize(total_size_);
      inverse_mapper_.resize(cache_size_);
      last_used_time_.resize(cache_size_);
Guolin Ke's avatar
Guolin Ke committed
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
      ResetMap();
    }
  }
  /*!
  * \brief Reset mapper
  */
  void ResetMap() {
    if (!is_enough_) {
      cur_time_ = 0;
      std::fill(mapper_.begin(), mapper_.end(), -1);
      std::fill(inverse_mapper_.begin(), inverse_mapper_.end(), -1);
      std::fill(last_used_time_.begin(), last_used_time_.end(), 0);
    }
  }

752
  void DynamicChangeSize(const Dataset* train_data, bool is_hist_colwise, const Config* config, int cache_size, int total_size) {
Guolin Ke's avatar
Guolin Ke committed
753
    if (feature_metas_.empty()) {
754
      uint64_t bin_cnt_over_features = 0;
Guolin Ke's avatar
Guolin Ke committed
755
756
757
      int num_feature = train_data->num_features();
      feature_metas_.resize(num_feature);
      for (int i = 0; i < num_feature; ++i) {
Guolin Ke's avatar
Guolin Ke committed
758
        feature_metas_[i].num_bin = train_data->FeatureNumBin(i);
759
        bin_cnt_over_features += static_cast<uint64_t>(feature_metas_[i].num_bin);
Guolin Ke's avatar
Guolin Ke committed
760
        feature_metas_[i].default_bin = train_data->FeatureBinMapper(i)->GetDefaultBin();
Guolin Ke's avatar
Guolin Ke committed
761
        feature_metas_[i].missing_type = train_data->FeatureBinMapper(i)->missing_type();
Guolin Ke's avatar
Guolin Ke committed
762
        feature_metas_[i].monotone_type = train_data->FeatureMonotone(i);
Guolin Ke's avatar
Guolin Ke committed
763
        feature_metas_[i].penalty = train_data->FeaturePenalte(i);
Guolin Ke's avatar
Guolin Ke committed
764
        if (train_data->FeatureBinMapper(i)->GetMostFreqBin() == 0) {
765
          feature_metas_[i].offset = 1;
Guolin Ke's avatar
Guolin Ke committed
766
        } else {
767
          feature_metas_[i].offset = 0;
Guolin Ke's avatar
Guolin Ke committed
768
        }
Guolin Ke's avatar
Guolin Ke committed
769
        feature_metas_[i].config = config;
770
        feature_metas_[i].bin_type = train_data->FeatureBinMapper(i)->bin_type();
Guolin Ke's avatar
Guolin Ke committed
771
      }
772
      Log::Info("Total Bins %d", bin_cnt_over_features);
Guolin Ke's avatar
Guolin Ke committed
773
    }
Guolin Ke's avatar
Guolin Ke committed
774
    int old_cache_size = static_cast<int>(pool_.size());
Guolin Ke's avatar
Guolin Ke committed
775
    Reset(cache_size, total_size);
Guolin Ke's avatar
Guolin Ke committed
776
777
778
779
780

    if (cache_size > old_cache_size) {
      pool_.resize(cache_size);
      data_.resize(cache_size);
    }
781
    int num_total_bin = static_cast<int>(train_data->NumTotalBin());
Guolin Ke's avatar
Guolin Ke committed
782

783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
    std::vector<int> offsets;
    if (is_hist_colwise) {
      int offset = 0;
      for (int j = 0; j < train_data->num_features(); ++j) {
        offset += train_data->SubFeatureBinOffset(j);
        offsets.push_back(offset);
        auto num_bin = train_data->FeatureNumBin(j);
        if (train_data->FeatureBinMapper(j)->GetMostFreqBin() == 0) {
          num_bin -= 1;
        }
        offset += num_bin;
      }
    } else {
      num_total_bin = 1;
      for (int j = 0; j < train_data->num_features(); ++j) {
        offsets.push_back(num_total_bin);
        num_total_bin += train_data->FeatureBinMapper(j)->num_bin();
        if (train_data->FeatureBinMapper(j)->GetMostFreqBin() == 0) {
          num_total_bin -= 1;
        }
      }
    }
805
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
806
    #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
807
    for (int i = old_cache_size; i < cache_size; ++i) {
808
      OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
809
      pool_[i].reset(new FeatureHistogram[train_data->num_features()]);
810
      data_[i].resize(num_total_bin * 2);
Guolin Ke's avatar
Guolin Ke committed
811
      for (int j = 0; j < train_data->num_features(); ++j) {
812
        pool_[i][j].Init(data_[i].data() + offsets[j] * 2, &feature_metas_[j]);
Guolin Ke's avatar
Guolin Ke committed
813
      }
814
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
815
    }
816
    OMP_THROW_EX();
817
    train_data_ = train_data;
Guolin Ke's avatar
Guolin Ke committed
818
819
  }

Guolin Ke's avatar
Guolin Ke committed
820
  void ResetConfig(const Config* config) {
Guolin Ke's avatar
Guolin Ke committed
821
    int size = static_cast<int>(feature_metas_.size());
822
    #pragma omp parallel for schedule(static, 512) if (size >= 1024)
Guolin Ke's avatar
Guolin Ke committed
823
    for (int i = 0; i < size; ++i) {
Guolin Ke's avatar
Guolin Ke committed
824
      feature_metas_[i].config = config;
825
826
      feature_metas_[i].monotone_type = train_data_->FeatureMonotone(i);
      feature_metas_[i].penalty = train_data_->FeaturePenalte(i);
Guolin Ke's avatar
Guolin Ke committed
827
828
    }
  }
Guolin Ke's avatar
Guolin Ke committed
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
  /*!
  * \brief Get data for the specific index
  * \param idx which index want to get
  * \param out output data will store into this
  * \return True if this index is in the pool, False if this index is not in the pool
  */
  bool Get(int idx, FeatureHistogram** out) {
    if (is_enough_) {
      *out = pool_[idx].get();
      return true;
    } else if (mapper_[idx] >= 0) {
      int slot = mapper_[idx];
      *out = pool_[slot].get();
      last_used_time_[slot] = ++cur_time_;
      return true;
    } else {
845
      // choose the least used slot
Guolin Ke's avatar
Guolin Ke committed
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
      int slot = static_cast<int>(ArrayArgs<int>::ArgMin(last_used_time_));
      *out = pool_[slot].get();
      last_used_time_[slot] = ++cur_time_;

      // reset previous mapper
      if (inverse_mapper_[slot] >= 0) mapper_[inverse_mapper_[slot]] = -1;

      // update current mapper
      mapper_[idx] = slot;
      inverse_mapper_[slot] = idx;
      return false;
    }
  }

  /*!
  * \brief Move data from one index to another index
  * \param src_idx
  * \param dst_idx
  */
  void Move(int src_idx, int dst_idx) {
    if (is_enough_) {
      std::swap(pool_[src_idx], pool_[dst_idx]);
      return;
    }
    if (mapper_[src_idx] < 0) {
      return;
    }
    // get slot of src idx
    int slot = mapper_[src_idx];
    // reset src_idx
    mapper_[src_idx] = -1;

    // move to dst idx
    mapper_[dst_idx] = slot;
    last_used_time_[slot] = ++cur_time_;
    inverse_mapper_[slot] = dst_idx;
  }
883

884
private:
Guolin Ke's avatar
Guolin Ke committed
885
  std::vector<std::unique_ptr<FeatureHistogram[]>> pool_;
886
  std::vector<std::vector<hist_t, Common::AlignmentAllocator<hist_t, kAlignedSize>>> data_;
Guolin Ke's avatar
Guolin Ke committed
887
  std::vector<FeatureMetainfo> feature_metas_;
Guolin Ke's avatar
Guolin Ke committed
888
889
890
891
892
893
894
  int cache_size_;
  int total_size_;
  bool is_enough_ = false;
  std::vector<int> mapper_;
  std::vector<int> inverse_mapper_;
  std::vector<int> last_used_time_;
  int cur_time_ = 0;
895
  const Dataset* train_data_;
Guolin Ke's avatar
Guolin Ke committed
896
897
};

Guolin Ke's avatar
Guolin Ke committed
898
}  // namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
899
#endif   // LightGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_