| 1377 | |
| 1378 | template<EPenaltyType PenaltyType> |
| 1379 | class TFeatureBin : public IFeatureBin { |
| 1380 | public: |
| 1381 | TFeatureBin(ui32 binStart, ui32 binEnd, TFeatureItreator featuresStart) |
| 1382 | : IFeatureBin(binStart, binEnd, featuresStart) |
| 1383 | { |
| 1384 | UpdateBestSplitProperties(); |
| 1385 | } |
| 1386 | |
| 1387 | TFeatureBin Split() { |
| 1388 | if (!CanSplit()) { |
| 1389 | throw yexception() << "Can't add new split"; |
| 1390 | } |
| 1391 | TFeatureBin left = TFeatureBin(BinStart, BestSplit, FeaturesStart); |
| 1392 | BinStart = BestSplit; |
| 1393 | UpdateBestSplitProperties(); |
| 1394 | return left; |
| 1395 | } |
| 1396 | |
| 1397 | private: |
| 1398 | double CalcSplitScore(ui32 splitPos) const { |
| 1399 | Y_ASSERT(splitPos >= BinStart && splitPos <= BinEnd); |
| 1400 | if (splitPos == BinStart || splitPos == BinEnd) { |
| 1401 | return -std::numeric_limits<double>::infinity(); |
| 1402 | } |
| 1403 | const double leftPartScore = -Penalty<PenaltyType>(static_cast<double>(splitPos - BinStart)); |
| 1404 | const double rightPartScore = -Penalty<PenaltyType>(static_cast<double>(BinEnd - splitPos)); |
| 1405 | const double currBinScore = -Penalty<PenaltyType>(static_cast<double>(BinEnd - BinStart)); |
| 1406 | return leftPartScore + rightPartScore - currBinScore; |
| 1407 | } |
| 1408 | |
| 1409 | inline void UpdateBestSplitProperties() { |
| 1410 | const int mid = BinStart + (BinEnd - BinStart) / 2; |
| 1411 | float midValue = *(FeaturesStart + mid); |
| 1412 | |
| 1413 | const ui32 lb = static_cast<ui32>( |
| 1414 | LowerBound(FeaturesStart + BinStart, FeaturesStart + mid, midValue) - FeaturesStart |
| 1415 | ); |
| 1416 | const ui32 ub = static_cast<ui32>( |
| 1417 | UpperBound(FeaturesStart + mid, FeaturesStart + BinEnd, midValue) - FeaturesStart |
| 1418 | ); |
| 1419 | |
| 1420 | const double scoreLeft = CalcSplitScore(lb); |
| 1421 | const double scoreRight = CalcSplitScore(ub); |
| 1422 | BestSplit = scoreLeft >= scoreRight ? lb : ub; |
| 1423 | BestScore = BestSplit == lb ? scoreLeft : scoreRight; |
| 1424 | } |
| 1425 | }; |
| 1426 | |
| 1427 | template<typename TWeightType, EPenaltyType penaltyType> |
| 1428 | class TWeightedFeatureBin : public IFeatureBin { |