用自监督学习提升少样本代码时间复杂度预测效果
TCProF: Time-Complexity Prediction SSL Framework
- 提出TCProF框架，融合数据增强与符号模块的自监督学习
- 在少样本场景下性能比自训练提升60%以上
- 适合资源受限下的代码分析与算法优化研究者
时间复杂度是衡量算法执行所需时间的理论指标。实际开发中，开发者在资源有限条件下编写代码片段，准确计算代码时间复杂度成为关键任务。然而，精确判定代码时间复杂度在理论上不可判定。近年来，研究转向构建代码时间复杂度预测数据集并开展初步实验。本文聚焦于仅提供少量标注样本的低资源场景，首次提出TCProF：一种面向低资源设置的时间复杂度预测自监督学习框架。该框架通过整合数据增强、符号模块和协同训练机制，显著提升性能，相较自训练方法实现超过60%的改进。我们还对TCProF、ChatGPT与Gemini-Pro进行了详尽对比分析，全面评估了本方法的有效性。代码已开源：https://github.com/peer0/few-shot-tc。
原文摘要 · Abstract (English)
Time complexity is a theoretic measure to determine the amount of time the algorithm needs for its execution. In reality, developers write algorithms into code snippets within limited resources, making the calculation of a code's time complexity a fundamental task. However, determining the precise time complexity of a code is theoretically undecidable. In response, recent advancements have leaned toward deploying datasets for code time complexity prediction and initiating preliminary experiments for this challenge. We investigate the challenge in low-resource scenarios where only a few labeled instances are given for training. Remarkably, we are the first to introduce TCProF: a Time-Complexity Prediction SSL Framework as an effective solution for code time complexity prediction in low-resource settings. TCProF significantly boosts performance by integrating our augmentation, symbolic modules, and a co-training mechanism, achieving a more than 60% improvement over self-training approaches. We further provide an extensive comparative analysis between TCProF, ChatGPT, and Gemini-Pro, offering a detailed evaluation of our approach. Our code is at https://github.com/peer0/few-shot-tc.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。