dense_bin.hpp 9.27 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
8
9
10
#ifndef LIGHTGBM_IO_DENSE_BIN_HPP_
#define LIGHTGBM_IO_DENSE_BIN_HPP_

#include <LightGBM/bin.h>

#include <cstdint>
11
12
#include <cstring>
#include <vector>
Guolin Ke's avatar
Guolin Ke committed
13
14
15

namespace LightGBM {

Guolin Ke's avatar
Guolin Ke committed
16
17
18
19
template <typename VAL_T>
class DenseBin;

template <typename VAL_T>
20
class DenseBinIterator: public BinIterator {
Nikita Titov's avatar
Nikita Titov committed
21
 public:
Guolin Ke's avatar
Guolin Ke committed
22
23
24
  explicit DenseBinIterator(const DenseBin<VAL_T>* bin_data, uint32_t min_bin, uint32_t max_bin, uint32_t default_bin)
    : bin_data_(bin_data), min_bin_(static_cast<VAL_T>(min_bin)),
    max_bin_(static_cast<VAL_T>(max_bin)),
Guolin Ke's avatar
Guolin Ke committed
25
    default_bin_(static_cast<VAL_T>(default_bin)) {
Guolin Ke's avatar
Guolin Ke committed
26
    if (default_bin_ == 0) {
27
      offset_ = 1;
Guolin Ke's avatar
Guolin Ke committed
28
    } else {
29
      offset_ = 0;
Guolin Ke's avatar
Guolin Ke committed
30
31
    }
  }
32
  inline uint32_t RawGet(data_size_t idx) override;
Guolin Ke's avatar
Guolin Ke committed
33
34
  inline uint32_t Get(data_size_t idx) override;
  inline void Reset(data_size_t) override { }
Nikita Titov's avatar
Nikita Titov committed
35
36

 private:
Guolin Ke's avatar
Guolin Ke committed
37
38
39
40
  const DenseBin<VAL_T>* bin_data_;
  VAL_T min_bin_;
  VAL_T max_bin_;
  VAL_T default_bin_;
41
  uint8_t offset_;
Guolin Ke's avatar
Guolin Ke committed
42
};
Guolin Ke's avatar
Guolin Ke committed
43
/*!
Hui Xue's avatar
Hui Xue committed
44
* \brief Used to store bins for dense feature
Guolin Ke's avatar
Guolin Ke committed
45
46
47
* Use template to reduce memory cost
*/
template <typename VAL_T>
48
class DenseBin: public Bin {
Nikita Titov's avatar
Nikita Titov committed
49
 public:
Guolin Ke's avatar
Guolin Ke committed
50
  friend DenseBinIterator<VAL_T>;
Guolin Ke's avatar
Guolin Ke committed
51
  explicit DenseBin(data_size_t num_data)
Guolin Ke's avatar
Guolin Ke committed
52
    : num_data_(num_data), data_(num_data_, static_cast<VAL_T>(0)) {
Guolin Ke's avatar
Guolin Ke committed
53
54
55
56
57
58
59
60
61
  }

  ~DenseBin() {
  }

  void Push(int, data_size_t idx, uint32_t value) override {
    data_[idx] = static_cast<VAL_T>(value);
  }

Guolin Ke's avatar
Guolin Ke committed
62
63
64
65
66
67
68
  void ReSize(data_size_t num_data) override {
    if (num_data_ != num_data) {
      num_data_ = num_data;
      data_.resize(num_data_);
    }
  }

Guolin Ke's avatar
Guolin Ke committed
69
  BinIterator* GetIterator(uint32_t min_bin, uint32_t max_bin, uint32_t default_bin) const override;
Guolin Ke's avatar
Guolin Ke committed
70

71
72
73
74
75
76
77
78
79
  void ConstructHistogram(const data_size_t* data_indices, data_size_t start, data_size_t end,
    const score_t* ordered_gradients, const score_t* ordered_hessians,
    HistogramBinEntry* out) const override {

    const data_size_t prefetch_size = 32 / sizeof(VAL_T);
    for (data_size_t i = start; i < end; i++) {
      if (i + prefetch_size < end) {
        PREFETCH_T0(data_.data() + data_indices[i + prefetch_size]);
      }
80
81
82
83
84
85
86
      const VAL_T bin = data_[data_indices[i]];
      out[bin].sum_gradients += ordered_gradients[i];
      out[bin].sum_hessians += ordered_hessians[i];
      ++out[bin].cnt;
    }
  }

87
88
89
90
91
92
93
94
  void ConstructHistogram(data_size_t start, data_size_t end,
    const score_t* ordered_gradients, const score_t* ordered_hessians,
    HistogramBinEntry* out) const override {
    const data_size_t prefetch_size = 32 / sizeof(VAL_T);
    for (data_size_t i = start; i < end; ++i) {
      if (i + prefetch_size < end) {
        PREFETCH_T0(data_.data() + i + prefetch_size);
      }
95
96
97
98
      const VAL_T bin = data_[i];
      out[bin].sum_gradients += ordered_gradients[i];
      out[bin].sum_hessians += ordered_hessians[i];
      ++out[bin].cnt;
Guolin Ke's avatar
Guolin Ke committed
99
    }
Guolin Ke's avatar
Guolin Ke committed
100
101
  }

102
103
104
105
106
107
108
109
  void ConstructHistogram(const data_size_t* data_indices, data_size_t start, data_size_t end,
    const score_t* ordered_gradients,
    HistogramBinEntry* out) const override {
    const data_size_t prefetch_size = 32 / sizeof(VAL_T);
    for (data_size_t i = start; i < end; ++i) {
      if (i + prefetch_size < end) {
        PREFETCH_T0(data_.data() + data_indices[i + prefetch_size]);
      }
110
111
112
113
114
115
      const VAL_T bin = data_[data_indices[i]];
      out[bin].sum_gradients += ordered_gradients[i];
      ++out[bin].cnt;
    }
  }

116
117
118
119
120
121
122
123
  void ConstructHistogram(data_size_t start, data_size_t end,
    const score_t* ordered_gradients,
    HistogramBinEntry* out) const override {
    const data_size_t prefetch_size = 32 / sizeof(VAL_T);
    for (data_size_t i = start; i < end; ++i) {
      if (i + prefetch_size < end) {
        PREFETCH_T0(data_.data() + i + prefetch_size);
      }
124
125
126
      const VAL_T bin = data_[i];
      out[bin].sum_gradients += ordered_gradients[i];
      ++out[bin].cnt;
127
128
129
    }
  }

Guolin Ke's avatar
Guolin Ke committed
130
  data_size_t Split(
Guolin Ke's avatar
Guolin Ke committed
131
    uint32_t min_bin, uint32_t max_bin, uint32_t default_bin, MissingType missing_type, bool default_left,
Guolin Ke's avatar
Guolin Ke committed
132
    uint32_t threshold, data_size_t* data_indices, data_size_t num_data,
133
    data_size_t* lte_indices, data_size_t* gt_indices) const override {
Guolin Ke's avatar
Guolin Ke committed
134
135
    if (num_data <= 0) { return 0; }
    VAL_T th = static_cast<VAL_T>(threshold + min_bin);
136
137
    const VAL_T minb = static_cast<VAL_T>(min_bin);
    const VAL_T maxb = static_cast<VAL_T>(max_bin);
Guolin Ke's avatar
Guolin Ke committed
138
    VAL_T t_default_bin = static_cast<VAL_T>(min_bin + default_bin);
Guolin Ke's avatar
Guolin Ke committed
139
140
    if (default_bin == 0) {
      th -= 1;
Guolin Ke's avatar
Guolin Ke committed
141
      t_default_bin -= 1;
Guolin Ke's avatar
Guolin Ke committed
142
    }
Guolin Ke's avatar
Guolin Ke committed
143
144
    data_size_t lte_count = 0;
    data_size_t gt_count = 0;
Guolin Ke's avatar
Guolin Ke committed
145
146
    data_size_t* default_indices = gt_indices;
    data_size_t* default_count = &gt_count;
147
148
    if (missing_type == MissingType::NaN) {
      if (default_bin <= threshold) {
149
150
151
        default_indices = lte_indices;
        default_count = &lte_count;
      }
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
      data_size_t* missing_default_indices = gt_indices;
      data_size_t* missing_default_count = &gt_count;
      if (default_left) {
        missing_default_indices = lte_indices;
        missing_default_count = &lte_count;
      }
      for (data_size_t i = 0; i < num_data; ++i) {
        const data_size_t idx = data_indices[i];
        const VAL_T bin = data_[idx];
        if (bin < minb || bin > maxb || t_default_bin == bin) {
          default_indices[(*default_count)++] = idx;
        } else if (bin == maxb) {
          missing_default_indices[(*missing_default_count)++] = idx;
        } else if (bin > th) {
          gt_indices[gt_count++] = idx;
        } else {
          lte_indices[lte_count++] = idx;
169
170
171
        }
      }
    } else {
172
      if ((default_left && missing_type == MissingType::Zero) || (default_bin <= threshold && missing_type != MissingType::Zero)) {
173
174
175
176
177
        default_indices = lte_indices;
        default_count = &lte_count;
      }
      for (data_size_t i = 0; i < num_data; ++i) {
        const data_size_t idx = data_indices[i];
178
        const VAL_T bin = data_[idx];
Guolin Ke's avatar
Guolin Ke committed
179
        if (bin < minb || bin > maxb || t_default_bin == bin) {
180
          default_indices[(*default_count)++] = idx;
181
        } else if (bin > th) {
182
183
184
185
          gt_indices[gt_count++] = idx;
        } else {
          lte_indices[lte_count++] = idx;
        }
Guolin Ke's avatar
Guolin Ke committed
186
187
188
189
      }
    }
    return lte_count;
  }
Guolin Ke's avatar
Guolin Ke committed
190

Guolin Ke's avatar
Guolin Ke committed
191
  data_size_t SplitCategorical(
192
    uint32_t min_bin, uint32_t max_bin, uint32_t default_bin,
193
    const uint32_t* threshold, int num_threahold, data_size_t* data_indices, data_size_t num_data,
194
195
196
197
198
199
    data_size_t* lte_indices, data_size_t* gt_indices) const override {
    if (num_data <= 0) { return 0; }
    data_size_t lte_count = 0;
    data_size_t gt_count = 0;
    data_size_t* default_indices = gt_indices;
    data_size_t* default_count = &gt_count;
200
    if (Common::FindInBitset(threshold, num_threahold, default_bin)) {
201
202
203
204
205
206
207
208
      default_indices = lte_indices;
      default_count = &lte_count;
    }
    for (data_size_t i = 0; i < num_data; ++i) {
      const data_size_t idx = data_indices[i];
      const uint32_t bin = data_[idx];
      if (bin < min_bin || bin > max_bin) {
        default_indices[(*default_count)++] = idx;
209
      } else if (Common::FindInBitset(threshold, num_threahold, bin - min_bin)) {
210
211
212
213
214
215
216
217
        lte_indices[lte_count++] = idx;
      } else {
        gt_indices[gt_count++] = idx;
      }
    }
    return lte_count;
  }

Guolin Ke's avatar
Guolin Ke committed
218
219
220
221
222
223
224
225
226
  data_size_t num_data() const override { return num_data_; }

  /*! \brief not ordered bin for dense feature */
  OrderedBin* CreateOrderedBin() const override { return nullptr; }

  void FinishLoad() override {}

  void LoadFromMemory(const void* memory, const std::vector<data_size_t>& local_used_indices) override {
    const VAL_T* mem_data = reinterpret_cast<const VAL_T*>(memory);
Guolin Ke's avatar
Guolin Ke committed
227
    if (!local_used_indices.empty()) {
Guolin Ke's avatar
Guolin Ke committed
228
229
230
231
232
233
234
235
236
237
      for (int i = 0; i < num_data_; ++i) {
        data_[i] = mem_data[local_used_indices[i]];
      }
    } else {
      for (int i = 0; i < num_data_; ++i) {
        data_[i] = mem_data[i];
      }
    }
  }

238
  void CopySubset(const Bin* full_bin, const data_size_t* used_indices, data_size_t num_used_indices) override {
Guolin Ke's avatar
Guolin Ke committed
239
    auto other_bin = dynamic_cast<const DenseBin<VAL_T>*>(full_bin);
240
241
242
243
244
    for (int i = 0; i < num_used_indices; ++i) {
      data_[i] = other_bin->data_[used_indices[i]];
    }
  }

245
246
  void SaveBinaryToFile(const VirtualFileWriter* writer) const override {
    writer->Write(data_.data(), sizeof(VAL_T) * num_data_);
Guolin Ke's avatar
Guolin Ke committed
247
248
249
250
251
252
  }

  size_t SizesInByte() const override {
    return sizeof(VAL_T) * num_data_;
  }

253
254
255
  DenseBin<VAL_T>* Clone() override;

 private:
Guolin Ke's avatar
Guolin Ke committed
256
  data_size_t num_data_;
Guolin Ke's avatar
Guolin Ke committed
257
  std::vector<VAL_T> data_;
258
259
260

  DenseBin<VAL_T>(const DenseBin<VAL_T>& other)
    : num_data_(other.num_data_), data_(other.data_){}
Guolin Ke's avatar
Guolin Ke committed
261
262
};

263
template<typename VAL_T>
264
DenseBin<VAL_T>* DenseBin<VAL_T>::Clone() {
265
266
267
  return new DenseBin<VAL_T>(*this);
}

Guolin Ke's avatar
Guolin Ke committed
268
template <typename VAL_T>
Guolin Ke's avatar
Guolin Ke committed
269
270
271
uint32_t DenseBinIterator<VAL_T>::Get(data_size_t idx) {
  auto ret = bin_data_->data_[idx];
  if (ret >= min_bin_ && ret <= max_bin_) {
272
    return ret - min_bin_ + offset_;
Guolin Ke's avatar
Guolin Ke committed
273
274
  } else {
    return default_bin_;
Guolin Ke's avatar
Guolin Ke committed
275
276
  }
}
277

278
279
280
281
282
template <typename VAL_T>
inline uint32_t DenseBinIterator<VAL_T>::RawGet(data_size_t idx) {
  return bin_data_->data_[idx];
}

Guolin Ke's avatar
Guolin Ke committed
283
template <typename VAL_T>
Guolin Ke's avatar
Guolin Ke committed
284
285
286
BinIterator* DenseBin<VAL_T>::GetIterator(uint32_t min_bin, uint32_t max_bin, uint32_t default_bin) const {
  return new DenseBinIterator<VAL_T>(this, min_bin, max_bin, default_bin);
}
Guolin Ke's avatar
Guolin Ke committed
287

Guolin Ke's avatar
Guolin Ke committed
288
}  // namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
289
#endif   // LightGBM_IO_DENSE_BIN_HPP_