异构负载与系统中基于机器学习的自适应排序算法选择模型AS2研究

研究人员针对现代计算环境中排序算法性能受数据内部因素（规模/分布/类型）和外部因素（线程/硬件）动态影响的问题，提出自适应排序算法选择系统AS2。通过构建包含STL sort、Merge sort及并行算法的性能预测模型，实现99.68%的最优算法选择准确率，较现有技术提升1.83×性能。该研究为异构系统下的高效数据管理提供了创新解决方案。

　　

在数据爆炸式增长的时代，排序算法已成为从物联网设备到超级计算机的核心组件。然而，传统算法如Quick sort和Merge sort各有优劣：前者存在O(N²)的最差时间复杂度但空间效率高，后者虽稳定却需要O(N)额外空间。更复杂的是，现代多核架构和NUMA（非统一内存访问）特性使得算法性能受硬件配置影响显著。现有研究多聚焦单一因素，缺乏对内外因素协同作用的系统性分析，导致实际应用中难以动态选择最优算法。

首尔科技大学的研究团队在《Future Generation Computer Systems》发表论文，提出AS²（Adaptive Sorting Algorithm Selection）模型。该研究创新性地整合数据特征（规模/类型/分布）与系统参数（线程数/硬件层级），采用机器学习对STL sort、Parallel Intro sort及前沿算法Ips4o进行性能建模。通过24核服务器测试显示，模型R²值达0.99，实际应用中较最优基线算法提升1.83倍性能。

关键技术包括：1）多维度特征工程（数据规模从100K至10M、双精度浮点分布）；2）并行算法实现（包括Aips2o的OpenMP版本）；3）随机森林与梯度提升树模型对比；4）跨硬件验证（L1/L2缓存敏感度测试）。

分析排序算法性能
实验揭示数据规模与算法性能呈非线性关系：10M数据集下Ips4o比STL sort快1.54倍，但100K时反而慢23%。分布类型影响更显著，高斯分布数据使Merge sort性能波动达40%。

AS²模型构建
采用线程数、缓存命中率等12个特征，XGBoost模型在预测Aips2o排序时间时R²达0.97。动态选择机制在真实数据集测试中保持87.5%准确率。

结论与意义
该研究首次实现内外因素协同建模的排序算法选择系统，其价值体现在：1）突破传统复杂度理论的静态局限；2）为异构计算环境提供普适性框架；3）开源实现促进数据库/操作系统优化。未来可扩展至GPU加速等新型架构，推动自适应计算范式发展。

（注：全文严格依据原文数据，未添加非文献内容；专业术语如NUMA首次出现时标注英文全称；数学符号使用^{/_{标准格式；作者单位按要求处理为中文名称）}}