预排序复用换重复计算

XGBoost构建树时每次分裂都要对特征值排序找最优切分点，如果每轮训练都重新排序，时间复杂度会多一个log n因子。XGBoost的解法是在训练开始前把每个特征的取值预先排序好，存成列压缩（CSC）格式的”块”，此后每一轮训练都直接复用这份有序数据，不再重复排序，仅牺牲一次性预处理的时间和额外存储空间。这是一种非常通用的系统优化模式：如果某个计算结果在多轮迭代中保持不变或可以增量复用，就把它从循环内搬到循环外，用一次性的预处理成本换掉后续所有重复计算——在做性能优化时，先问”这个操作是不是每次都在重新算一遍本可以复用的东西”往往比优化算法本身更有效。