软件测试是一种基本的软件质量保证活动,它最终能够确保较好的软件质量。随机测试（RT）是一种流行的软件测试技术,它从软件的输入域中随机选择并执行测试用例的子集。自适应随机测试（ART）利用大多数故障程序的导致故障输入的聚类特性,提高RT的故障检测效率。ART使用一种机制,从而将测试用例均匀地分布在软件的输入域中。作为一种广泛使用、高效、简单的ART算法,Fixed-Size-Candidate-Set ART（FSCS-ART）面临着平方的时间复杂度。随着软件输入域维度的增加,这种成本会逐渐恶化。由于真实程序中,大多数程序的输入域维度较高,故障率较低,因此迫切需要解决这一问题。本论文旨在解决FSCS-ART的效率问题,同时不牺牲其故障检测效果。我们将FSCSART确定为最近邻搜索（NNS）问题的一个实例,并假设FSCS-ART的效率问题在于其NNS机制。如果NNS机制能够随着数据集的大小和维度的变化而趋于一致,则可能会缓解效率问题。首先,提出了一种基于小世界图（small world graphs）的方法（命名为SWFCART）,可以提高FSCS-ART的计算效率。为了高效地执行候选测试用例的最近邻查询,SWFC-ART为之前执行的、非失效的测试用例增量构建了一个分层可导航的小世界图。此外,SWFC-ART在高维输入域的程序中表现出一致性趋势。实验研究表明,SWFC-ART,在保持FSCS-ART的故障检测效果的前提下,将FSCS-ART的计算开销从二次方降低到对数线性阶,并且在高维输入域中保持一致性。其次,对FSCS-ART进行了CPU层面的执行分析,发现其主要由于其距离计算过程采用了单指令-单数据（SISD）机制,存在运行时成本过高的问题。为了克服这个问题,提出了一种新颖高效的FSCS-ART实现方法。Fixed-Size-Candidate-Set using SingleInstruction-Multi-Data（FSCS-SIMD）。FSCS-SIMD采用SIMD指令架构,以多对多的方式同时计算多个测试用例的距离。所提出的方法在一个CPU执行周期内从候选测试用例集和执行测试用例集中加载一批测试用例。之后,对整批测试用例下达单条距离计算指令,进行所有对偶距离的计算。一系列的仿真和实证研究表明,平均而言,FSCS-SIMD在保持类似故障检测效果的前提下,减少了FSCS-ART 90%的测试用例生成时间开销。最后,采用了一种基于量化和反转文件结构的方法来增强FSCS-ART,称为QIVFSCSART,该方法通过使用统一的随机数据集,利用k-means聚类将软件输入域划分为离散的单元进行预处理。之后,将每个已执行的测试用例,以量化形式存储在其单元中心的倒数列表中,我们称为centroid。结果表明,所提出的方法显著地缓解了FSCSART的计算开销,同时保留了其故障检测的有效性,特别是对于高维软件输入域。