Article(id=1329419682211278968, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1329419577676641015, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202550901, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=null, receivedDate=1765728000000, receivedDateStr=2025-12-15, revisedDate=1772640000000, revisedDateStr=2026-03-05, acceptedDate=null, acceptedDateStr=null, onlineDate=1794887951662, onlineDateStr=2026-11-17, pubDate=1777564800000, pubDateStr=2026-05-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794887951662, onlineIssueDateStr=2026-11-17, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794887951662, creator=13701087609, updateTime=1794887951662, updator=13701087609, issue=Issue{id=1329419577676641015, tenantId=1146029695717560320, journalId=1324759914146529478, year='2026', volume='63', issue='5', pageStart='1095', pageEnd='1375', issueExtLink='null', onlineDate='null', pubDate='1777564800000', pubDateStr='2026-05-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794887926739, creator='13701087609', updateTime=1794887926739, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext=null, issueFiles=null, downloadFileDto=null}, startPage=1139, endPage=1157, ext={EN=ArticleExt(id=1329419682563600506, articleId=1329419682211278968, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Functional Modeling, Verification and Access Optimization of Adaptive Priority Search Tree, columnId=1329419682488103033, journalTitle=Journal of Computer Research and Development, columnName=Special Issue on Security and Trustworthiness for AI-Enabled Human-Cyber-Physical Systems, runingTitle=null, highlight=null, articleAbstract=

The priority search tree (PST) is a data structure that combines the characteristics of search trees and priority queues, enabling efficient retrieval of high-priority elements while maintaining worst-case search efficiency comparable to that of search trees. Nipkow et al. further modeled and mechanized the verification of PST with a static priority mechanism, laying an important foundation for its formal analysis and subsequent theoretical exploration. However, static priority mechanisms can lead to degraded performance under highly skewed access distributions, limiting their applicability in practice. To overcome this limitation, a functional adaptive priority search tree (FAPST) is proposed. FAPST adopts dynamic priority adjustment based on access frequency and is formally modeled and verified at the formal level to ensure functional correctness and reliability. This structure preserves balance and worst-case efficiency while adaptively responding to access patterns, thereby significantly improving the retrieval of frequently accessed elements. To further address the shifting nature of data hotspots in practical scenarios, a hotspot migration mechanism is introduced. This mechanism incorporates a priority decay strategy to accelerate responses to emerging hotspots and mitigate the stagnation of outdated ones. Experimental results demonstrate that, in both access-sensitive and hotspot-shifting workloads, the formally verified FAPST achieves notable reductions in the number of key function calls of 64.8% and 46.3% respectively, compared with conventional PSTs.

, authors=Zhengkang Zuo1, 2, 3, Chao Zhou1, Yuhan Ke1, Zhen You1, Changjing Wang1, 2, 3, *, authorsList=Zhengkang Zuo, Chao Zhou, Yuhan Ke, Zhen You, Changjing Wang, authorCompany=null, correspAuthors=Changjing Wang, authorNote=

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

born in 2001. Master candidate. Student member of CCF. His main research interest includes formal method

born in 1998. Master candidate. Student member of CCF. His main research interest includes formal method

born in 1982. PhD, associate professor, Master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

, correspAuthorsNote=null, copyrightStatement=Copyright © 2026 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1329419687844229293, articleId=1329419682211278968, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=自适应优先搜索树的函数式建模、验证及访问优化, columnId=1329419682655875195, journalTitle=计算机研究与发展, columnName=面向人机物融合智能系统的安全可信专题, runingTitle=null, highlight=null, articleAbstract=

优先搜索树(priority search tree,PST)是一种融合搜索树与优先队列特性的数据结构,能够在保持搜索树最坏查找效率的基础上,根据数据的优先级判断其重要性,从而实现高优先级数据的快速检索。Nipkow等人对采用静态优先级机制的PST进行了形式化建模与机械化验证,为其理论分析奠定了重要基础。然而,在访问分布高度偏斜的场景下,静态机制易导致检索效率下降。为此,提出一种基于动态优先级思想的函数式自适应优先搜索树(functional adaptive priority search tree,FAPST),与PST相比,FAPST在通过函数式建模与机械化验证确保正确性的同时,能够根据访问分布特征动态调整数据优先级,在维持树结构平衡性与可控最坏查找效率的前提下,有效优化访问敏感数据的查找性能。进一步,针对实际应用中热点数据随时间变化的特点,引入热点转移机制,通过优先级衰减策略提升新热点响应速度,缓解旧热点固化问题。实验评估表明,在访问敏感场景和热点转移场景下,经过形式化验证的FAPST通过动态优先级和热点转移机制有效优化了查询效率,较PST关键函数调用次数分别缩短64.8%、46.3%。

, authors=左正康1, 2, 3, 周超1, 柯雨含1, 游珍1, 王昌晶1, 2, 3, *, authorsList=左正康, 周超, 柯雨含, 游珍, 王昌晶, authorCompany=null, correspAuthors=王昌晶, authorNote=

作者贡献声明

左正康和周超共同提出算法思路和实验方案;周超完成实验并撰写论文;柯雨含整理实验数据并完善实验方案;游珍和王昌晶提出指导意见并修改论文。

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

1998年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

, correspAuthorsNote=
王昌晶()
, copyrightStatement=版权所有 © 2026 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=iuxvJlr1LOfK7QqpUTb59g==, magXml=IAJx3xHWJ7xO0MGcr7zpsw==, pdfUrl=null, pdf=CwXcMucA9Ee6tQKU5vR4Cw==, pdfFileSize=2119062, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=roOB3DVmVgzIZZni9oGenA==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=QfjKrz54fayzLfuc5/K3vw==, mapNumber=null, fund=null)}, authors=[Author(id=1329419688351740088, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zuo803@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419688439820476, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688351740088, language=EN, stringName=Zhengkang Zuo, firstName=Zhengkang, middleName=null, lastName=Zuo, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022
3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022, bio={"content":"

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

"}, bioImg=null, bioContent=

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419688502735037, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688351740088, language=CN, stringName=左正康, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1江西师范大学人工智能学院 南昌 330022
2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
3语言智能研究中心(江西师范大学) 南昌 330022, bio={"img":"psUcz3zf/R++c7w6Bnxaiw==","content":"

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

"}, bioImg=psUcz3zf/R++c7w6Bnxaiw==, bioContent=

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419688167190705, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=2, ext=[AuthorCompanyExt(id=1329419688175579314, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688179773619, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419688259465396, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=3, ext=[AuthorCompanyExt(id=1329419688272048309, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688280436918, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])]), Author(id=1329419688578232511, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419688666312897, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688578232511, language=EN, stringName=Chao Zhou, firstName=Chao, middleName=null, lastName=Zhou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 2001. Master candidate. Student member of CCF. His main research interest includes formal method

"}, bioImg=null, bioContent=

born in 2001. Master candidate. Student member of CCF. His main research interest includes formal method

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419688729227458, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688578232511, language=CN, stringName=周超, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"tVPvwhWRY2QfaOCciOF7YA==","content":"

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

"}, bioImg=tVPvwhWRY2QfaOCciOF7YA==, bioContent=

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419688792142020, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419688892805318, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688792142020, language=EN, stringName=Yuhan Ke, firstName=Yuhan, middleName=null, lastName=Ke, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 1998. Master candidate. Student member of CCF. His main research interest includes formal method

"}, bioImg=null, bioContent=

born in 1998. Master candidate. Student member of CCF. His main research interest includes formal method

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419688972497095, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688792142020, language=CN, stringName=柯雨含, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"tl0XOGPQ+BuFaWs3BBFirA==","content":"

1998年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

"}, bioImg=tl0XOGPQ+BuFaWs3BBFirA==, bioContent=

1998年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419689043800265, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419689123492043, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419689043800265, language=EN, stringName=Zhen You, firstName=Zhen, middleName=null, lastName=You, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 1982. PhD, associate professor, Master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

"}, bioImg=null, bioContent=

born in 1982. PhD, associate professor, Master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419689211572429, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419689043800265, language=CN, stringName=游珍, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"o7/LU4liaBea2cATVLq05A==","content":"

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

"}, bioImg=o7/LU4liaBea2cATVLq05A==, bioContent=

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419689312235727, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=wcj@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329419689400316115, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419689312235727, language=EN, stringName=Changjing Wang, firstName=Changjing, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, *, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022
3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022, bio={"content":"

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

"}, bioImg=null, bioContent=

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419689480007892, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419689312235727, language=CN, stringName=王昌晶, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, *, address=1江西师范大学人工智能学院 南昌 330022
2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
3语言智能研究中心(江西师范大学) 南昌 330022, bio={"img":"IsKWcZoGLF6xQA2t4cB0gQ==","content":"

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

"}, bioImg=IsKWcZoGLF6xQA2t4cB0gQ==, bioContent=

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419688167190705, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=2, ext=[AuthorCompanyExt(id=1329419688175579314, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688179773619, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419688259465396, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=3, ext=[AuthorCompanyExt(id=1329419688272048309, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688280436918, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])])], keywords=[Keyword(id=1329419689589059797, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, orderNo=1, keyword=functional adaptive priority search tree), Keyword(id=1329419689656168662, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, orderNo=2, keyword=dynamic priority), Keyword(id=1329419689723277527, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, orderNo=3, keyword=functional modeling), Keyword(id=1329419689790386392, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, orderNo=4, keyword=mechanical verification), Keyword(id=1329419689865883865, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, orderNo=5, keyword=hotspot migration), Keyword(id=1329419689966547162, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, orderNo=1, keyword=函数式自适应优先搜索树), Keyword(id=1329419690063016155, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, orderNo=2, keyword=动态优先级), Keyword(id=1329419690125930716, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, orderNo=3, keyword=函数式建模), Keyword(id=1329419690184650973, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, orderNo=4, keyword=机械化验证), Keyword(id=1329419690272731358, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, orderNo=5, keyword=热点转移)], refs=[Reference(id=1329419694039216399, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Paulson L C. Computational logic: Its origins and applications[J]. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2018, 474(2210): 20170872, articleTitle=null, refAbstract=null), Reference(id=1329419694097936656, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=Lammich P, Nipkow T. Priority search trees[EB/OL]. [2025-09-10]. https://www.isa-afp.org/browser_info/current/AFP/Priority_Search_Trees/document.pdf, articleTitle=null, refAbstract=null), Reference(id=1329419694156656913, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Massa H, Uhlmann J. Access-adaptive priority search tree[J]. Innovations in Systems and Software Engineering, 2025, 21(4): 1323−1330, articleTitle=null, refAbstract=null), Reference(id=1329419694232154386, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=Nipkow T, Klein G. Concrete Semantics: With Isabelle/HOL[M]. Berlin: Springer, 2021, articleTitle=null, refAbstract=null), Reference(id=1329419694295068947, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=石海鹤, 蓝孙文, 刘日明, 等. 生物序列比对动态规划算法的统一形式化构造与Isabelle验证[J]. 计算机研究与发展, 2025, 62(1): 119−131, articleTitle=null, refAbstract=null), Reference(id=1329419694353789204, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Haihe, Lan Sunwen, Liu Riming, et al. Unified formal construction and Isabelle verification of the dynamic programming algorithms for biological sequence alignment[J]. Journal of Computer Research and Development, 2025, 62(1): 119−131(in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329419694542532885, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Matichuk D, Murray T, Wenzel M. Eisbach: A proof method language for Isabelle[J]. Journal of Automated Reasoning, 2016, 56(3): 261−282, articleTitle=null, refAbstract=null), Reference(id=1329419694605447446, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=McCreight E M. Priority search trees[J]. SIAM Journal on Computing, 1985, 14(2): 257−276, articleTitle=null, refAbstract=null), Reference(id=1329419694668362007, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Alistarh D, Kopinsky J, Li J, et al. The spraylist: A scalable relaxed priority queue[C] //Proc of the 20th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2015: 11−20, articleTitle=null, refAbstract=null), Reference(id=1329419694731276568, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Seidel R, Aragon C R. Randomized search trees[J]. Algorithmica, 1996, 16(4): 464−497, articleTitle=null, refAbstract=null), Reference(id=1329419694802579737, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Icking C, Klein R, Ottmann T. Priority search trees in secondary memory[C] // Proc of Int Workshop on Graph-Theoretic Concepts in Computer Science. Berlin, Springer, 1987: 84−93, articleTitle=null, refAbstract=null), Reference(id=1329419694873882906, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Bronson N G, Casper J, Chafi H, et al. A practical concurrent binary search tree[J]. ACM Sigplan Notices, 2010, 45(5): 257−268, articleTitle=null, refAbstract=null), Reference(id=1329419694932603163, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Natarajan A, Mittal N. Fast concurrent lock-free binary search trees[C] //Proc of the 19th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2014: 317−328, articleTitle=null, refAbstract=null), Reference(id=1329419695003906332, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Afek Y, Kaplan H, Korenfeld B, et al. The CB tree: A practical concurrent self-adjusting search tree[J]. Distributed Computing, 2014, 27(6): 393−417, articleTitle=null, refAbstract=null), Reference(id=1329419695071015197, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Ellen F, Fatourou P, Ruppert E, et al. Non-blocking binary search trees[C] //Proc of the 29th ACM SIGACT-SIGOPS Symp on Principles of Distributed Computing. New York: ACM, 2010: 131−140, articleTitle=null, refAbstract=null), Reference(id=1329419695129735454, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Zhongbin, Yang Luyi, Cui Shiliang, et al. In-queue priority purchase: A dynamic game approach[J]. Queueing Systems, 2021, 97(3): 343−381, articleTitle=null, refAbstract=null), Reference(id=1329419695188455711, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Bose P, Cardinal J, Iacono J, et al. Competitive online search trees on trees[J]. ACM Transactions on Algorithms, 2023, 19(3): 1−19, articleTitle=null, refAbstract=null), Reference(id=1329419695255564576, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Drouin A, Hocking T D, Laviolette F. Maximum margin interval trees [C] //Proc of Advances in Neural Information Processing Systems 30. Red Hook: Curran Associates, Inc., 2017: 4947−4956, articleTitle=null, refAbstract=null), Reference(id=1329419695310090529, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Sleator D D, Tarjan R E. Self-adjusting binary search trees[J]. Journal of the ACM, 1985, 32(3): 652−686, articleTitle=null, refAbstract=null), Reference(id=1329419695373005090, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=王戟, 詹乃军, 冯新宇, 等. 形式化方法概貌[J]. 软件学报, 2019, 30(1): 33−61, articleTitle=null, refAbstract=null), Reference(id=1329419695461085475, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Ji, Zhan Naijun, Feng Xinyu, et al. Overview of formal methods[J]. Journal of Software, 2019, 30(1): 33−61(in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329419695544971556, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=左正康, 柯雨含, 黄箐, 等. Trie+结构函数式建模、机械化验证及其应用[J]. 软件学报, 2024, 35(9): 4242−4264, articleTitle=null, refAbstract=null), Reference(id=1329419695607886117, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Zuo Zhengkang, Ke Yuhan, Huang Qing, et al. Trie+ structural functional modeling, mechanized merification and application[J]. Journal of Software, 2024, 35(9): 4242−4264 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1329419695695966502, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Nipkow T. Verified root-balanced trees [C]//Proc of Asian Symp on Programming Languages and Systems. Cham: Springer, 2017: 255−272, articleTitle=null, refAbstract=null), Reference(id=1329419695763075367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Nipkow T, Brinkop H. Amortized complexity verified[J]. Journal of Automated Reasoning, 2019, 62(3): 367−391, articleTitle=null, refAbstract=null), Reference(id=1329419695872127272, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Hinze R, Paterson R. Finger trees: A simple general-purpose data structure[J]. Journal of Functional Programming, 2006, 16(2): 197−217, articleTitle=null, refAbstract=null), Reference(id=1329419695939236137, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Hirai Y, Yamamoto K. Balancing weight-balanced trees[J]. Journal of Functional Programming, 2011, 21(3): 287−307, articleTitle=null, refAbstract=null), Reference(id=1329419695993762090, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Nipkow T, Sewell T. Proof pearl: Braun trees[C] //Proc of the 9th ACM SIGPLAN Int Conf on Certified Programs and Proofs. New York: ACM, 2020: 18−31, articleTitle=null, refAbstract=null), Reference(id=1329419696052482347, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Nipkow T, Somogyi D. Optimal Binary Search Trees[EB/OL]. [2025-9-10]. https://www.isa-afp.org/browser_info/current/AFP/Optimal_BST/document.pdf, articleTitle=null, refAbstract=null), Reference(id=1329419696119591212, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Eberl M, Haslbeck M W, Nipkow T. Verified analysis of random binary tree structures[J]. Journal of Automated Reasoning, 2020, 64(5): 879−910, articleTitle=null, refAbstract=null), Reference(id=1329419696262197550, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Burns B, Grant B, Oppenheimer D, et al. Borg, omega, and kubernetes[J]. Communications of the ACM, 2016, 59(5): 50−57, articleTitle=null, refAbstract=null), Reference(id=1329419696325112111, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Nygren E, Sitaraman R K, Sun J. The akamai network: A platform for high-performance Internet applications[J]. ACM SIGOPS Operating Systems Review, 2010, 44(3): 2−19, articleTitle=null, refAbstract=null), Reference(id=1329419696379638064, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Knuth D E. The Art of Computer Programming, Volume 3: Sorting and Searching[M]. New York: Addison-Wesley, 1999: 426−458, articleTitle=null, refAbstract=null), Reference(id=1329419696442552625, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=Jacobson V. Congestion avoidance and control[J]. ACM SIGCOMM Computer Communication Review, 1988, 18(4): 314−329, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419688167190705, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=2, ext=[AuthorCompanyExt(id=1329419688175579314, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688179773619, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419688259465396, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=3, ext=[AuthorCompanyExt(id=1329419688272048309, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688280436918, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])], figs=[ArticleFig(id=1329419690394366175, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 1, caption=Organizational chart, figureFileSmall=3bx+Pt6xuhvpq8wZN2LBJA==, figureFileBig=roOB3DVmVgzIZZni9oGenA==, tableContent=null), ArticleFig(id=1329419690457280736, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图1, caption=组织结构图, figureFileSmall=3bx+Pt6xuhvpq8wZN2LBJA==, figureFileBig=roOB3DVmVgzIZZni9oGenA==, tableContent=null), ArticleFig(id=1329419690646024417, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 2, caption=Structural diagram of FAPST, figureFileSmall=seCXmkzyCeq2VxpsGHQD/w==, figureFileBig=n4TwzU6wN5u/LvPLYk4rBA==, tableContent=null), ArticleFig(id=1329419690725716194, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图2, caption=FAPST结构图, figureFileSmall=seCXmkzyCeq2VxpsGHQD/w==, figureFileBig=n4TwzU6wN5u/LvPLYk4rBA==, tableContent=null), ArticleFig(id=1329419690817990883, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 3, caption=Processing pattern of search operation, figureFileSmall=0CKMCry6ZtMVC0NAsubEGQ==, figureFileBig=/IqSdMV5PEwTWZKlMOHjMw==, tableContent=null), ArticleFig(id=1329419690872516836, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图3, caption=查找操作处理模式, figureFileSmall=0CKMCry6ZtMVC0NAsubEGQ==, figureFileBig=/IqSdMV5PEwTWZKlMOHjMw==, tableContent=null), ArticleFig(id=1329419690960597221, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 4, caption=Comparative example of search operations in FAPST and PST, figureFileSmall=5ikGYs7TDT+vmsXVM92xZA==, figureFileBig=AQdkXv/zLZRP9ePsalLFQQ==, tableContent=null), ArticleFig(id=1329419691031900390, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图4, caption=FAPST和PST查找操作实例对比, figureFileSmall=5ikGYs7TDT+vmsXVM92xZA==, figureFileBig=AQdkXv/zLZRP9ePsalLFQQ==, tableContent=null), ArticleFig(id=1329419691099009255, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 5, caption=Proof strategy for element property invariance, figureFileSmall=QMfRGoNp7tV02bPnKdZB5w==, figureFileBig=2vBq3ilwYNP54XaBnf7RsQ==, tableContent=null), ArticleFig(id=1329419691174506728, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图5, caption=元素特性不变证明策略, figureFileSmall=QMfRGoNp7tV02bPnKdZB5w==, figureFileBig=2vBq3ilwYNP54XaBnf7RsQ==, tableContent=null), ArticleFig(id=1329419691270975721, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 6, caption=Proof process of theorem 1, figureFileSmall=RrjVhvRA1ErhbytUx90rqQ==, figureFileBig=6lSnKUE0T5vnSzob/jcIGA==, tableContent=null), ArticleFig(id=1329419691363250410, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图6, caption=定理1的证明过程, figureFileSmall=RrjVhvRA1ErhbytUx90rqQ==, figureFileBig=6lSnKUE0T5vnSzob/jcIGA==, tableContent=null), ArticleFig(id=1329419691447136491, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 7, caption=Proof process of theorem 3, figureFileSmall=UlYtKdKRHbYhDqKGmIa2gA==, figureFileBig=9mG83d8aYjpzF3b/DcHq0w==, tableContent=null), ArticleFig(id=1329419691522633964, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图7, caption=定理3的证明过程, figureFileSmall=UlYtKdKRHbYhDqKGmIa2gA==, figureFileBig=9mG83d8aYjpzF3b/DcHq0w==, tableContent=null), ArticleFig(id=1329419691593937133, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 8, caption=Proof process of theorem 4, figureFileSmall=rq19+LFjzwiXiFgSoDs73A==, figureFileBig=kci1brVNnJtkg7EHLbSyRw==, tableContent=null), ArticleFig(id=1329419691656851695, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图8, caption=定理4的证明过程, figureFileSmall=rq19+LFjzwiXiFgSoDs73A==, figureFileBig=kci1brVNnJtkg7EHLbSyRw==, tableContent=null), ArticleFig(id=1329419691732349169, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 9, caption=Verification process of element property invariance in FAPST insertion operation, figureFileSmall=mAEqwxB+dLJMU2+vYQhn2A==, figureFileBig=vKMq6htEj9ZrGwjMV9Q+RA==, tableContent=null), ArticleFig(id=1329419691799458034, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图9, caption=FAPST插入操作的元素特性不变验证过程, figureFileSmall=mAEqwxB+dLJMU2+vYQhn2A==, figureFileBig=vKMq6htEj9ZrGwjMV9Q+RA==, tableContent=null), ArticleFig(id=1329419691874955507, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 10, caption=Verification process of element property invariance in FAPST deletion operation, figureFileSmall=9DuZTVya78s5cBRhRBSxAw==, figureFileBig=nf3X9WM16EELyp5AhNrl1g==, tableContent=null), ArticleFig(id=1329419692021756148, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图10, caption=FAPST删除操作的元素特性不变验证过程, figureFileSmall=9DuZTVya78s5cBRhRBSxAw==, figureFileBig=nf3X9WM16EELyp5AhNrl1g==, tableContent=null), ArticleFig(id=1329419692097253623, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 11, caption=Proofs process of theorem 9 and theorem 10, figureFileSmall=G1GYSEqeIicmVDe3D+oQOA==, figureFileBig=mRYt+oEQxzMZFKPtvbJzqQ==, tableContent=null), ArticleFig(id=1329419692185334008, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图11, caption=定理9和定理10的证明过程, figureFileSmall=G1GYSEqeIicmVDe3D+oQOA==, figureFileBig=mRYt+oEQxzMZFKPtvbJzqQ==, tableContent=null), ArticleFig(id=1329419692265025785, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 12, caption=Key function call performance of different structures under the K8s task scheduling system (n=30), figureFileSmall=wab3LJ+cFnCIOTMx+jS89Q==, figureFileBig=43WhzJEIT6RXvV2iDZWnmw==, tableContent=null), ArticleFig(id=1329419692340523258, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图12, caption=不同结构在K8s任务调度系统下的关键函数调用表现(n=30), figureFileSmall=wab3LJ+cFnCIOTMx+jS89Q==, figureFileBig=43WhzJEIT6RXvV2iDZWnmw==, tableContent=null), ArticleFig(id=1329419692399243515, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 13, caption=Key function call performance of different structures under the K8s task scheduling system (n=100), figureFileSmall=dpwWIHrYUBExMYSA8aQXrw==, figureFileBig=ho1CMfm+G8C5Dl/FFYqMGw==, tableContent=null), ArticleFig(id=1329419692462158076, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图13, caption=不同结构在K8s任务调度系统下的关键函数调用表现(n=100), figureFileSmall=dpwWIHrYUBExMYSA8aQXrw==, figureFileBig=ho1CMfm+G8C5Dl/FFYqMGw==, tableContent=null), ArticleFig(id=1329419692558627069, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 14, caption=Evolution process of FAPST structure, figureFileSmall=vvf9CBRGZ444AkmamemIJw==, figureFileBig=SyfHSQZoKsvODY3XYplU9g==, tableContent=null), ArticleFig(id=1329419692629930238, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图14, caption=FAPST 结构的演化过程, figureFileSmall=vvf9CBRGZ444AkmamemIJw==, figureFileBig=SyfHSQZoKsvODY3XYplU9g==, tableContent=null), ArticleFig(id=1329419692705427711, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 15, caption=Priority decay strategy, figureFileSmall=zYDd9++vKb/2vgh5TVp8lQ==, figureFileBig=PXFaDgnc4oUgGjjsKYrddw==, tableContent=null), ArticleFig(id=1329419692780925184, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图15, caption=优先级衰退策略, figureFileSmall=zYDd9++vKb/2vgh5TVp8lQ==, figureFileBig=PXFaDgnc4oUgGjjsKYrddw==, tableContent=null), ArticleFig(id=1329419692852228353, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 16, caption=Proof process of theorem 11, figureFileSmall=M65+6fhRxk19j/KRheyrWg==, figureFileBig=SpYzAA2YIjvysblXRCrdlQ==, tableContent=null), ArticleFig(id=1329419692940308738, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图16, caption=定理11的证明过程, figureFileSmall=M65+6fhRxk19j/KRheyrWg==, figureFileBig=SpYzAA2YIjvysblXRCrdlQ==, tableContent=null), ArticleFig(id=1329419693028389123, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 17, caption=Proof process of theorem 12, figureFileSmall=WdRLO/WwOCrZ6On9vNjGYg==, figureFileBig=W6u2k8gdQJZ+5bY2oWQB8g==, tableContent=null), ArticleFig(id=1329419693166801156, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图17, caption=定理12的证明过程, figureFileSmall=WdRLO/WwOCrZ6On9vNjGYg==, figureFileBig=W6u2k8gdQJZ+5bY2oWQB8g==, tableContent=null), ArticleFig(id=1329419693242298629, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 18, caption=Proofs process of theorem 13 and theorem 14, figureFileSmall=xUyvzZqJg0cZJoEIM+SV9Q==, figureFileBig=nOcp6vwVaD0Baf6ru/p86Q==, tableContent=null), ArticleFig(id=1329419693342961926, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图18, caption=定理13和定理14的证明过程, figureFileSmall=xUyvzZqJg0cZJoEIM+SV9Q==, figureFileBig=nOcp6vwVaD0Baf6ru/p86Q==, tableContent=null), ArticleFig(id=1329419693410070791, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Figure 19, caption=Key function call performance of different structures under the CDN caching system, figureFileSmall=uiKunE1U6YQU51XE8asqSQ==, figureFileBig=M5u6g9B0J4qvSCwO+d+dPA==, tableContent=null), ArticleFig(id=1329419693472985352, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=图19, caption=不同结构在CDN缓存系统下的关键函数调用表现, figureFileSmall=uiKunE1U6YQU51XE8asqSQ==, figureFileBig=M5u6g9B0J4qvSCwO+d+dPA==, tableContent=null), ArticleFig(id=1329419693552677129, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Table 1, caption=

Comparison of FAPST and Related Work

, figureFileSmall=null, figureFileBig=null, tableContent=
对比维度FAPST(本文)PST[2]AAPST[3]Splay[22]
节点优先级动态静态动态不支持
形式化验证支持支持不支持支持
最坏时间复杂度O(log n)O(log n)O(log n)O(n)
访问敏感场景支持不支持支持不支持
热点转移场景支持不支持不支持不支持
), ArticleFig(id=1329419693619785994, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=表1, caption=

FAPST与相关工作的对比

, figureFileSmall=null, figureFileBig=null, tableContent=
对比维度FAPST(本文)PST[2]AAPST[3]Splay[22]
节点优先级动态静态动态不支持
形式化验证支持支持不支持支持
最坏时间复杂度O(log n)O(log n)O(log n)O(n)
访问敏感场景支持不支持支持不支持
热点转移场景支持不支持不支持不支持
), ArticleFig(id=1329419693695283467, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Table 2, caption=

Performance Comparison of FAPST, PST and Splay over 10000 Task Searches

, figureFileSmall=null, figureFileBig=null, tableContent=
规模nP(H)/%PST关键函数
调用次数
Splay关键函数
调用次数
FAPST关键函数
调用次数
FAPST较PST调用
次数缩短/%
FAPST较Splay调用
次数缩短/%
303044600678003550020.447.6
306046000534002910036.745.5
309046400311002200052.629.3
1003057300949004390023.553.7
1006059400656003350043.648.9
1009060000352002110064.840.1
), ArticleFig(id=1329419693770780940, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=表2, caption=

在10000次任务查找下FAPST与PST、Splay的性能对比

, figureFileSmall=null, figureFileBig=null, tableContent=
规模nP(H)/%PST关键函数
调用次数
Splay关键函数
调用次数
FAPST关键函数
调用次数
FAPST较PST调用
次数缩短/%
FAPST较Splay调用
次数缩短/%
303044600678003550020.447.6
306046000534002910036.745.5
309046400311002200052.629.3
1003057300949004390023.553.7
1006059400656003350043.648.9
1009060000352002110064.840.1
), ArticleFig(id=1329419693850472717, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=EN, label=Table 3, caption=

Performance Comparison of PST, FAPST, HS-FAPST over 10000 Data Searches

, figureFileSmall=null, figureFileBig=null, tableContent=
规模nP(H)/%PST关键函数
调用次数
FAPST关键函数
调用次数
HS-FAPST关键函数
调用次数
HS-FAPST较PST
调用次数缩短/%
HS-FAPST较FAPST
调用次数缩短/%
1003058300507004970014.82.0
1006059600496004010032.719.2
1009059600453003200046.329.4
), ArticleFig(id=1329419693925970190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, language=CN, label=表3, caption=

在10000次数据查找下PST、FAPST和HS-FAPST的性能对比

, figureFileSmall=null, figureFileBig=null, tableContent=
规模nP(H)/%PST关键函数
调用次数
FAPST关键函数
调用次数
HS-FAPST关键函数
调用次数
HS-FAPST较PST
调用次数缩短/%
HS-FAPST较FAPST
调用次数缩短/%
1003058300507004970014.82.0
1006059600496004010032.719.2
1009059600453003200046.329.4
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202550901, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202550901, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202550901, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202550901, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1777564800000, fullTextJson=null, articleText=null, reference=null)
收藏切换
自适应优先搜索树的函数式建模、验证及访问优化
左正康 1, 2, 3 , 周超 1 , 柯雨含 1 , 游珍 1 , 王昌晶 1, 2, 3, *
计算机研究与发展 | 面向人机物融合智能系统的安全可信专题 2026,63(5): 1139-1157
收起
收藏切换
计算机研究与发展 |面向人机物融合智能系统的安全可信专题 2026 , 63 (5) : 1139 -1157
自适应优先搜索树的函数式建模、验证及访问优化
全屏
[Author(id=1329419688351740088, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=zuo803@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419688439820476, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688351740088, language=EN, stringName=Zhengkang Zuo, firstName=Zhengkang, middleName=null, lastName=Zuo, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022
3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022, bio={"content":"

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

"}, bioImg=null, bioContent=

born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419688502735037, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688351740088, language=CN, stringName=左正康, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, address=1江西师范大学人工智能学院 南昌 330022
2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
3语言智能研究中心(江西师范大学) 南昌 330022, bio={"img":"psUcz3zf/R++c7w6Bnxaiw==","content":"

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

"}, bioImg=psUcz3zf/R++c7w6Bnxaiw==, bioContent=

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419688167190705, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=2, ext=[AuthorCompanyExt(id=1329419688175579314, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688179773619, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419688259465396, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=3, ext=[AuthorCompanyExt(id=1329419688272048309, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688280436918, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])]), Author(id=1329419688578232511, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419688666312897, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688578232511, language=EN, stringName=Chao Zhou, firstName=Chao, middleName=null, lastName=Zhou, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 2001. Master candidate. Student member of CCF. His main research interest includes formal method

"}, bioImg=null, bioContent=

born in 2001. Master candidate. Student member of CCF. His main research interest includes formal method

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419688729227458, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688578232511, language=CN, stringName=周超, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"tVPvwhWRY2QfaOCciOF7YA==","content":"

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

"}, bioImg=tVPvwhWRY2QfaOCciOF7YA==, bioContent=

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419688792142020, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419688892805318, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688792142020, language=EN, stringName=Yuhan Ke, firstName=Yuhan, middleName=null, lastName=Ke, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 1998. Master candidate. Student member of CCF. His main research interest includes formal method

"}, bioImg=null, bioContent=

born in 1998. Master candidate. Student member of CCF. His main research interest includes formal method

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419688972497095, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419688792142020, language=CN, stringName=柯雨含, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"tl0XOGPQ+BuFaWs3BBFirA==","content":"

1998年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

"}, bioImg=tl0XOGPQ+BuFaWs3BBFirA==, bioContent=

1998年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419689043800265, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1329419689123492043, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419689043800265, language=EN, stringName=Zhen You, firstName=Zhen, middleName=null, lastName=You, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022, bio={"content":"

born in 1982. PhD, associate professor, Master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

"}, bioImg=null, bioContent=

born in 1982. PhD, associate professor, Master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419689211572429, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419689043800265, language=CN, stringName=游珍, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学人工智能学院 南昌 330022, bio={"img":"o7/LU4liaBea2cATVLq05A==","content":"

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

"}, bioImg=o7/LU4liaBea2cATVLq05A==, bioContent=

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)])]), Author(id=1329419689312235727, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=wcj@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1329419689400316115, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419689312235727, language=EN, stringName=Changjing Wang, firstName=Changjing, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, *, address=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022
3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022, bio={"content":"

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

"}, bioImg=null, bioContent=

born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

, aboutCorrespAuthor=null), CN=AuthorExt(id=1329419689480007892, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, authorId=1329419689312235727, language=CN, stringName=王昌晶, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, 2, 3, *, address=1江西师范大学人工智能学院 南昌 330022
2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
3语言智能研究中心(江西师范大学) 南昌 330022, bio={"img":"IsKWcZoGLF6xQA2t4cB0gQ==","content":"

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

"}, bioImg=IsKWcZoGLF6xQA2t4cB0gQ==, bioContent=

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1329419688049750190, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=1, ext=[AuthorCompanyExt(id=1329419688058138799, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1329419688074916016, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688049750190, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学人工智能学院 南昌 330022)]), AuthorCompany(id=1329419688167190705, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=2, ext=[AuthorCompanyExt(id=1329419688175579314, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688179773619, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688167190705, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2高性能计算江西省重点实验室(江西师范大学) 南昌 330022)]), AuthorCompany(id=1329419688259465396, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, xref=3, ext=[AuthorCompanyExt(id=1329419688272048309, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022), AuthorCompanyExt(id=1329419688280436918, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1329419682211278968, companyId=1329419688259465396, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=3语言智能研究中心(江西师范大学) 南昌 330022)])])]
左正康1, 2, 3 , 周超1, 柯雨含1, 游珍1, 王昌晶1, 2, 3, *
作者信息
  • 1江西师范大学人工智能学院 南昌 330022
  • 2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
  • 3语言智能研究中心(江西师范大学) 南昌 330022
通讯作者:
王昌晶()
作者简介:

作者贡献声明

左正康和周超共同提出算法思路和实验方案;周超完成实验并撰写论文;柯雨含整理实验数据并完善实验方案;游珍和王昌晶提出指导意见并修改论文。

1980年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信与智能化软件

2001年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

1998年生。硕士研究生。CCF学生会员。主要研究方向为形式化方法

1982年生。博士,副教授,硕士生导师。CCF高级会员。主要研究方向为形式化方法、分布式虚拟现实、并发分布式计算

1977年生。博士,教授,博士生导师。CCF杰出会员。主要研究方向为高可信软件、智能化软件

Functional Modeling, Verification and Access Optimization of Adaptive Priority Search Tree
Zhengkang Zuo1, 2, 3 , Chao Zhou1, Yuhan Ke1, Zhen You1, Changjing Wang1, 2, 3, *
Affiliations
  • 1School of Artificial Intelligence, Jiangxi Normal University, Nanchang 330022
  • 2Jiangxi Provincial Key Laboratory for High Performance Computing (Jiangxi Normal University), Nanchang 330022
  • 3Language Intelligence Research Center (Jiangxi Normal University), Nanchang 330022
  • born in 1980. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interest includes high-confidence and intelligent software

    born in 2001. Master candidate. Student member of CCF. His main research interest includes formal method

    born in 1998. Master candidate. Student member of CCF. His main research interest includes formal method

    born in 1982. PhD, associate professor, Master supervisor. Senior member of CCF. Her main research interests include formal methods, distributed virtual reality, and concurrent distributed computing

    born in 1977. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high-confidence software and intelligent software

出版时间: 2026-05-01 doi: 10.7544/issn1000-1239.202550901
文章导航
收藏切换

优先搜索树(priority search tree,PST)是一种融合搜索树与优先队列特性的数据结构,能够在保持搜索树最坏查找效率的基础上,根据数据的优先级判断其重要性,从而实现高优先级数据的快速检索。Nipkow等人对采用静态优先级机制的PST进行了形式化建模与机械化验证,为其理论分析奠定了重要基础。然而,在访问分布高度偏斜的场景下,静态机制易导致检索效率下降。为此,提出一种基于动态优先级思想的函数式自适应优先搜索树(functional adaptive priority search tree,FAPST),与PST相比,FAPST在通过函数式建模与机械化验证确保正确性的同时,能够根据访问分布特征动态调整数据优先级,在维持树结构平衡性与可控最坏查找效率的前提下,有效优化访问敏感数据的查找性能。进一步,针对实际应用中热点数据随时间变化的特点,引入热点转移机制,通过优先级衰减策略提升新热点响应速度,缓解旧热点固化问题。实验评估表明,在访问敏感场景和热点转移场景下,经过形式化验证的FAPST通过动态优先级和热点转移机制有效优化了查询效率,较PST关键函数调用次数分别缩短64.8%、46.3%。

函数式自适应优先搜索树  /  动态优先级  /  函数式建模  /  机械化验证  /  热点转移

The priority search tree (PST) is a data structure that combines the characteristics of search trees and priority queues, enabling efficient retrieval of high-priority elements while maintaining worst-case search efficiency comparable to that of search trees. Nipkow et al. further modeled and mechanized the verification of PST with a static priority mechanism, laying an important foundation for its formal analysis and subsequent theoretical exploration. However, static priority mechanisms can lead to degraded performance under highly skewed access distributions, limiting their applicability in practice. To overcome this limitation, a functional adaptive priority search tree (FAPST) is proposed. FAPST adopts dynamic priority adjustment based on access frequency and is formally modeled and verified at the formal level to ensure functional correctness and reliability. This structure preserves balance and worst-case efficiency while adaptively responding to access patterns, thereby significantly improving the retrieval of frequently accessed elements. To further address the shifting nature of data hotspots in practical scenarios, a hotspot migration mechanism is introduced. This mechanism incorporates a priority decay strategy to accelerate responses to emerging hotspots and mitigate the stagnation of outdated ones. Experimental results demonstrate that, in both access-sensitive and hotspot-shifting workloads, the formally verified FAPST achieves notable reductions in the number of key function calls of 64.8% and 46.3% respectively, compared with conventional PSTs.

functional adaptive priority search tree  /  dynamic priority  /  functional modeling  /  mechanical verification  /  hotspot migration
左正康, 周超, 柯雨含, 游珍, 王昌晶. 自适应优先搜索树的函数式建模、验证及访问优化. 计算机研究与发展, 2026 , 63 (5) : 1139 -1157 . DOI: 10.7544/issn1000-1239.202550901
Zhengkang Zuo, Chao Zhou, Yuhan Ke, Zhen You, Changjing Wang. Functional Modeling, Verification and Access Optimization of Adaptive Priority Search Tree[J]. Journal of Computer Research and Development, 2026 , 63 (5) : 1139 -1157 . DOI: 10.7544/issn1000-1239.202550901
在应用系统数据规模快速扩张的当下,数据密集型应用对高效检索提出了迫切需求[1]。基于层次化索引的搜索树为应对大规模数据检索问题提供了基础性的解决方案。然而,传统搜索树的设计范式主要依赖于键值的有序排列,在面对数据访问频率存在显著差异的场景时,往往难以实现有针对性的快速检索。而优先搜索树(priority search tree,PST)是一种结合了搜索树和优先队列的新型数据结构,特点是能够根据数据的优先级判断其重要性,从而实现高优先级数据的快速查找。Nipkow等人[2]基于静态优先级进行函数式建模与验证的PST是一种二叉树数据结构,其在保证接近搜索树最坏查找效率的同时,根据数据优先级调整数据存储位置,使高优先级数据更靠近根节点,从而实现高优先级数据的快速访问。然而,在许多高频访问模式动态变化场景中(如新闻资讯热点刷新、电商平台促销商品更迭),数据的优先级往往是变化的,传统的静态PST难以满足实时更新和查询的需求。当数据优先级不可知或低优先级数据被频繁访问时,PST的查找效率将显著下降,限制了其在动态环境中的应用[3]。
为了解决静态PST的局限性,本文提出了一种基于动态优先级思想的函数式自适应优先搜索树(functional adaptive priority search tree,FAPST)。FAPST在结构设计和操作实现中采用了函数式建模,其核心操作通过Isabelle/HOL[4-5] 基于结构和元素不变性进行形式化验证。该方法有效避免了计算过程中的副作用,确保了结构在各种应用场景下的正确性和可靠性[6],为FAPST的广泛应用提供了扎实的理论支撑。在确保结构和操作正确性的基础上,FAPST融合了搜索树和优先级队列的特性[7-9],引入了一种动态可调优先级机制,能够根据访问频率实时更新节点优先级,这种机制通过优化数据布局,提高了对频繁访问数据的检索效率,可适配访问敏感场景。
然而,FAPST在热点频繁转移场景中仍存短板:历史热点优先级未及时衰减,会长期霸占高优先级路径,阻塞新热点的检索通道。新热点优先级提升后,也难以快速抢占高效路径,导致检索延迟,制约了对动态访问模式的适应性。为此,本文在FAPST基础上进一步引入热点转移机制。该机制通过历史热点优先级逐步衰减、新热点快速抢占高优先级路径的策略,实现热点数据平滑转移,缓解路径阻塞。新增机制与原有动态优先级机制协同工作,有效增强了FAPST在访问模式动态变化场景(如突发访问高峰、周期性热点转移)中的表现,使其更适用于网页搜索、智能推荐系统、大数据处理等数据密集型应用[10]。
最终实验结果表明,在访问敏感和热点转移场景下,FAPST通过动态优先级调整与热点转移机制有效优化了算法查询效率,表现出比PST更优的性能和适应性。本文的组织结构如图1所示。根据上述内容,本文的主要贡献总结为3个方面:
1)基于动态优先级思想提出FAPST结构,并对其进行函数式建模与机械化验证。在确保结构与操作正确性的同时,可解决PST优先级固定的局限,优化不同动态场景下的数据访问效率。
2)在访问敏感场景下,针对PST难以适配访问频率动态变化、导致高频数据检索效率受限的问题,FAPST通过其动态优先级调整机制有效提升了算法查询效率,表现出比PST更优的查询效率与动态适应性。
3)在热点转移场景下,针对历史热点优先级固化问题,将热点转移机制融入FAPST,在原有结构上进行扩展并完成热点转移逻辑的建模与验证,有效缓解历史热点滞留导致的新热点上升延迟问题,进一步增强FAPST在动态访问场景中的适应性。
本文主要聚焦FAPST的函数式建模与验证,并与相关搜索树结构进行不同场景的实验对比,本节主要介绍与FAPST相关的研究,包括:搜索树的结构及其变体、搜索树结构的形式化验证。
1)搜索树的结构及其变体。现有关于搜索树的研究多基于命令式编程语言。Bronson等人[11]提出并发树,通过协调函数动态调整树状态以保障多线程环境下的操作效率。文献[12]设计无锁二叉搜索树算法,采用标记边的方式实现对树更新的细粒度控制。Afek等人[13]提出的CB树(counting-based tree)依据节点访问次数设定权重,支持基于访问频率的自适应优化操作。Ellen等人[14]针对异步共享内存系统,设计并实现了一种基于比较与交换操作的非阻塞二叉搜索树,该方案可支持线性化的二叉搜索树,且无需大字长硬件支持。Wang等人[15]提出基于优先队列和自适应行为的动态博弈论模型,用于解决动态系统的排队与资源分配问题。文献[16]扩展经典二叉搜索树至任意树拓扑,引入Steiner闭合树概念并通过两级分解策略优化操作,实现O(log log n)竞争比。文献[17]提出最大间隔区间搜索树,通过最小化间隔判别目标函数学习,并设计对数线性时间最优解计算的动态编程算法。Sleator和Tarjan[18]提出的Splay树通过自调整操作实现O(log n)摊销性能,但最坏查询复杂度为O(n)。文献[3]提出的动态访问搜索树,可根据访问频率动态调整节点优先级,在保持O(log n)最坏查询复杂度的同时降低偏斜访问下的平均查询成本。
然而,上述结构均采用命令式设计,需显式管理状态与副作用,不仅增加代码复杂性和出错概率,还提升了操作形式化验证的难度,给实际应用带来可靠性与可信度风险[19]。
2)搜索树结构的形式化验证。现有搜索树结构的形式化验证主要聚焦于不同类型搜索树上。文献[20]提出优化空间利用率的Trie+结构,在Isabelle中完成函数式建模与验证,并给出支持中英文混合多模式匹配的通用验证规约。文献[21]在函数式编程语境下,完成根平衡搜索树摊销复杂度的形式化验证,提出避免显式对数操作的实现方案并开展竞争性分析。文献[22]给出Splay树的可执行结构,验证其基本属性与摊销性能。Hinze研究2-3指针树[23]的结构与形式属性,证实其支持常数时间摊销访问列表两端。文献[24]确定原始权重平衡搜索树插入/删除操作的旋转有效参数范围,并通过反例构造算法建立完整性。文献[25]以递归函数定义平衡二叉树布朗树的结构,在Isabelle中验证树操作正确性及必要不变性。文献[26]提出固定访问频率下最优二叉搜索树的递归算法并完成形式化验证。文献[27]对随机二叉树进行严格复杂度分析,建模概率分布、期望路径长度等属性并建立数学证明,确保不同插入顺序下关键统计属性的保持。
尽管上述结构的正确性已通过形式化验证,但设计中未纳入数据优先级维度,难以支持基于优先级的高效检索,限制了其在优先级敏感场景的应用。Nipkow等人[2]提出的函数式静态优先级搜索树既明确包含优先级维度,又通过函数式建模与机械化验证保障可靠性,显著提升高优先级数据搜索效率。但该结构存在关键局限:数据优先级固定,在访问频率未知时,频繁访问低优先级数据会导致搜索效率下降。
本文提出了一种基于动态优先级的FAPST,能够根据访问频率实时更新节点优先级,提高了对频繁访问数据的检索效率,并进一步引入热点转移机制优化了数据存储结构,有效解决历史热点滞留与新热点路径阻塞问题,增强FAPST对热点转移场景的适应性。其核心操作在Isabelle中进行了形式化建模和验证,确保了结构正确性与功能正确性。实验结果表明,FAPST在高频访问场景下优于PST,在热点频繁转移场景中更显优势,突显了其在实际应用中的适配性。为明确FAPST的创新价值,本文选取节点优先级机制、形式化验证、最坏情况时间复杂度及动态访问场景适配能力等关键维度,与代表性相关工作进行系统性对比,详见表1。
FAPST是基于函数式建模与机械化验证的动态优先级红黑树结构,在维持结构平衡及可控最坏检索复杂度的基础上,引入自适应优先级机制优化访问敏感数据的检索性能。数据项通过元组分配优先级,可在插入时显式定义,也能依据访问频率自适应调整。本节介绍其函数式建模内容,涵盖数据结构定义及查找、插入、删除3种主要基本操作。
本文借助Isabelle的归纳类型datatype自定义FAPST结构,具体定义为:
$ {{\mathrm{datatype}}}\;\mathrm{tcolor}~=~\mathrm{Red}~|~\text{Black} $
$ \begin{gathered}{t{\mathrm{}}ype}\_{{\mathrm{synonym}}}\;\text{'}\mathrm{k}\;\mathrm{psrbt}=\text{'}\text{'}((\text{'}\mathrm{k}\times \mathrm{nat})\times\\(\text{tcolor}\times (\text{'}\mathrm{k}\times \mathrm{nat})))\text{tree}\text{'}\text{'} 。\end{gathered} $
FAPST结构通过类型别名type_synonym将'k tree重定义为'k psrbt类型,其核心组成包括3个属性:
1)主节点对。每个节点存储一个主键-优先级对,类型为('k × nat),其中'k是键的数据类型,nat表示其优先级。例如,在图2中,根节点存储(4, 1),其中4是键,1是其初始优先级。所有节点的这些键的集合构成了树的主键集。
2)辅助节点对。同样采用('k × nat)类型,用于存储当前子树中的最大优先级信息。例如图2中根节点的辅助对(3, 5)表示该子树中存在键值为3、优先级为5的节点,且5为当前子树的最高优先级。
3)颜色属性(tcolor)。含Red、Black两种取值,用于强制执行红黑树不变性,通过约束规则(规则3-5)保障树的平衡性。
FAPST内部节点需满足五大核心规则,涵盖搜索树、优先级搜索树及红黑树变体的核心性质:
规则1(搜索树性质)FAPST主节点对数据的中序遍历产生一个线性升序的列表。
规则2(优先级性质)辅助节点优先级为当前节点及其子树辅助节点优先级的最大值。
规则3(红黑约束)任意内部节点路径中无连续红色节点。
规则4(黑高一致性)任意内部节点到各叶子节点的路径中,黑色节点数量一致。
规则5(根节点为黑)根节点的颜色为黑色。
FAPST的设计确保查找、插入、删除3个基本操作严格遵循FAPST的3项核心规则:查找操作定位目标数据时,会在遍历中动态提升其优先级;插入操作整合新数据及优先级,兼顾搜索树主节点有序性与辅助节点最大优先级属性;删除操作移除目标数据后,会执行重平衡操作,维持红黑树着色约束、子树优先级一致性、黑色高度一致性等不变性。
在FAPST中,查找操作采用“自顶向下查找,自底向上调整”的双阶段处理模式,如图3所示。自顶向下查找阶段:从根节点递归比较键值,匹配则返回节点,否则按二叉搜索树有序性遍历左/右子树,时间复杂度为O(log n),与标准二叉搜索树一致。自底向上调整阶段:找到目标节点后,通过路径回溯逐层重构搜索路径节点,依据子树状态和优先级信息调整节点颜色与辅助节点对信息,确保满足5项核心不变性,同时实现优先级动态更新。该双阶段机制既保证高效定位数据、维持树结构平衡,又优化后续访问效率。
查找操作在Isabelle中形式化为search函数,参数为'k psrbt类型的FAPST结构和'k(可排序)类型数据,返回('k psrbt * bool)二元组(处理后的树结构,查找是否成功),建模如下:
//FAPST的查找函数
fun search :: " 'k psrbt ⇒ 'k::linorder ⇒ 'k psrbt * bool " where
" search Leaf x = (Leaf, False) "|
" search (Node l((a, b), c, (mk, mp)) r) x = (if cmp mk x = EQ
then (Node l((a, b), c, (mk, Suc mp)) r, True)
else (case cmp x a of
EQ ⇒ (mkNode c (mk, mp) l (a, Suc b) r, True)|
LT ⇒ (mkNode c (mk, mp) (fst(search l x)) (a, b) r, (snd(search l x)))|
GT ⇒ (mkNode c (mk, mp) l (a, b) (fst(search r x)), (snd(search r x))))) "
上述建模中mkNode函数用于重构新FAPST结构,search函数对FAPST结构归纳: 1)匹配空树时返回(Leaf, False)。 2)匹配非空树时,先比对根节点辅助节点的整树最高优先级数据mk与x,若匹配则提升mk优先级并返回(新树, True);否则继续比对根节点主节点数据a,若a与x匹配则提升a优先级并返回(新树, True)。若mk与a均未与x匹配则按x与a的大小递归遍历左右子树,返回子树查找结果构建的新树及查找状态。
图4对比了FAPST与PST对关键字“5”的查找过程:PST需3次比对定位目标节点,且不修改树结构,再次查找仍需相同步骤。FAPST先比对根节点辅助节点(2, 1),不匹配,按主键大小进入右子树再向左子树递归,最终匹配节点(5, 1)并将其优先级提升为(5, 2)。随后系统检查路径是否满足规则2(父节点辅助节点优先级不小于子树最大优先级),因当前节点优先级高于父节点辅助节点,遂向上传递更新父节点及根节点辅助节点为(5, 2),有效缩短后续查找路径。
插入操作将关键字x及其优先级y整合为新FAPST,在Isabelle中形式化为update函数:参数为可排序类型'k、nat类型优先级及'k psrbt类型FAPST,返回'k psrbt类型新结构。其中upd负责递归插入与局部调整,update在其结果基础上通过paint Black保证根节点为黑色。其函数式建模如下:
//FAPST的插入函数
fun upd :: " 'k::linorder ⇒ nat ⇒ 'k psrbt ⇒ 'k psrbt " where
" upd x y Leaf = mkR (x, y) Leaf (x, y) Leaf " |
" upd x y (B _ l (a, b) r) = (case cmp x a of
LT ⇒ baliL (upd x y l) (a, b) r |
GT ⇒ baliR l (a, b) (upd x y r) |
EQ ⇒ mkB (x, y) l (x, y) r) " |
" upd x y (R _ l (a, b) r) = (case cmp x a of
LT ⇒ mkR (a, b) (upd x y l) (a, b) r|
GT ⇒ mkR (a, b) l (a, b) (upd x y r)|
EQ ⇒ mkR (x, y) l (x, y) r) "
definition update :: " 'k::linorder ⇒ nat ⇒ 'k psrbt ⇒ 'k psrbt " where
" update x y t = paint Black (upd x y t) "
插入采用自顶向下递归策略:1)待插入子树为空时,将(x, y)设为节点主/辅助节点信息,节点置为红色;2)子树为非空时,若x已存在则更新其优先级为y,否则递归遍历至空子树执行1)。过程可能破坏规则3和4,需同步执行平衡与颜色调整,调整至根节点时,若根为红色则通过paint操作强制转为黑色,确保满足规则5。
删除操作移除指定键节点并生成新FAPST,在Isabelle中形式化为delete函数:参数为可排序类型'k的键及'k psrbt类型树,返回'k psrbt类型新树。其中del实现递归删除与局部调整,delete在其结果基础上通过paint Black保证根节点为黑色。删除核心思路为:空树直接返回;非空树遍历定位目标节点,通过combine函数合并左右子树完成删除。具体函数式建模如下:
//FAPST的删除函数
fun del :: " 'k::linorder ⇒ 'k psrbt ⇒ 'k psrbt " where
" del x Leaf = Leaf ” |
" del x (Node l ((a, b), (c, _)) r) = (case cmp x a of
LT ⇒ if l ≠ Leaf ∧ color l = Black then baldL (del x l) (a, b) r else mkR (a, b) (del x l) (a, b) r|
GT ⇒ if r ≠ Leaf ∧ color r = Black then baldR l (a, b) (del x r) else mkR (a, b) l (a, b) (del x r)|
EQ ⇒ combine l r) "
definition delete :: " 'k::linorder ⇒ 'k psrbt ⇒ 'k psrbt " where
" delete x t = paint Black (del x t) "
删除通过自顶向下递归执行:1)空树直接返回;2)非空树中,若x存在则递归定位后调用combine合并子树替换目标节点,若不存在则递归至空子树执行1)。操作后需自底向上平衡与颜色调整以满足规则3和4;与插入类似,根节点可能为红色,需通过paint操作强制转黑确保规则5成立。
FAPST操作函数的验证包含终止性证明与正确性验证2个核心层面。对于终止性证明,本文第2节的函数式建模均基于Isabelle的fun与definition机制定义,其终止性已通过内置验证工具自动校验通过。工具采用自动化证明策略,核心是证明存在某一良基关系,使函数递归调用的参数沿该关系严格递减,直至抵达递归基例,确保所有函数在任意有效输入下均能在有限步内终止,而非无限递归。对于正确性验证,本节将依托Isabelle推理能力,通过验证结构特性不变性与元素特性不变性,确保查找、插入、删除操作的正确性。
为确保FAPST结构及其操作的正确性与稳定性,本文在Isabelle中完成FAPST关键不变性的机械化验证。不变性是指操作或状态转换中始终成立的核心约束,是数据结构动态变化的正确性保障。通过形式化定义并验证这些不变性,可确保FAPST操作过程中维持设计核心特征,其验证核心为结构特性不变与元素特性不变2类属性。
1)结构特性不变。结构特性不变确保所有操作(优先级调整、结构重构、路径平衡等)执行前后,树的核心结构规则(规则2~5)始终成立,其形式化定义为结构不变式:
definition inv_rb_apst :: " 'k psrbt ⇒ bool " where
" inv_rb_apst t = (invpst t ∧ invc t ∧ invh t ∧ color t = Black) "
该不变式与规则2~5严格对应:invpst对应规则2(节点辅助信息为自身及子树优先级最大值,且子树递归保持此性质);invc对应规则3(无连续红色节点,且在所有子树中递归成立);invh对应规则4(所有路径黑色节点数量一致);顶层属性color t = Black对应规则5(根节点为黑色)。
2)元素特性不变。元素特性不变是操作功能正确性的核心判据,要求操作后未被直接操作的元素在顺序及取值上保持不变。验证策略如图5所示,将FAPST通过中序遍历转为等价升序列表,对列表执行对应操作,再将直接操作FAPST后中序遍历得到的列表与之比对,通过这种与规则1(中序遍历升序性)相呼应的方式,严格验证元素特性不变性。
上述结构特性不变(规则2~5)与元素特性不变(规则1)构成FAPST完整约束框架,Isabelle机械化验证可确保所有操作执行前后这些核心性质均被严格维持,从而保障结构与操作的正确性和稳定性。
本节围绕FAPST操作过程中的结构特性不变与元素特性不变进行了系统的形式化定义与验证,旨在确保FAPST在不同操作场景下的正确性与一致性。具体而言,本文在Isabelle/HOL中对FAPST的结构属性进行了严格建模,随后针对查找、插入与删除3种基本操作函数开展结构特性不变的机械化验证,确认这些操作不会破坏树的有序性与层次约束。同时,本文对元素特性不变进行了形式化刻画,并逐一验证各操作在执行过程中是否保持数据元素的核心属性与语义稳定性。通过上述多层次的验证分析,为FAPST的函数式建模提供了全面形式化保障。
验证过程解决了三大关键挑战:首先,FAPST操作存在多分支场景,需系统性拆解数据匹配情形以保障验证完备性;其次,查找操作的自适应优先级调整机制可能破坏规则2,引发树结构连锁调整与递归重构,显著提升证明复杂度;最后,为支撑整体验证框架,构建了多层级递进式关键引理体系,需通过逐步搭建辅助引理化解难点,确保验证严谨性。
当FAPST满足规则1(中序有序)与规则2(优先级约束)时,查找操作仅存在成功与失败2种情形,分别由定理1、定理2描述:
定理1. 查找成功。theorem search_rb_priority: "invpst t ⇒ sorted1 (inorder t) ⇒ snd (search t x) ⇒ get_option_value (get_kp (fst (search t x)) x) = Suc (get_option_value (get_kp t x)) "。
定理2. 查找失败。theorem search_rb_priority_no: "invpst t ⇒ sorted1 (inorder t) ⇒ ¬snd (search t x) ⇒ get_option_value (get_kp (fst (search t x)) x) = get_option_value (get_kp t x) "。
定理1描述验证查找成功场景下的优先级调整特性,当搜索树满足规则1与规则2的前提下且查找操作命中关键字x时,目标数据元素优先级将上升1。定理2则验证查找失败场景下的优先级稳定性,若查找操作未匹配到目标元素,则数据元素的优先级保持不变。其中,函数get_option_value用于从option类型单子结构中提取具体值,get_kp用于获取指定键对应的优先级。
图6展示了定理1的证明过程,该定理的证明通过函数归纳展开,平凡分支经auto方法自动化简化后,再拆分左右子树情形。验证依赖分层构造的辅助引理,这些辅助引理为核心推理提供支持以确保证明严谨性,引理1~4的具体描述如下。
引理1. lemma mkNode_Node3: "invpst l ⇒ invpst r ⇒ ∀y ∈ set (tree2 l) ∨ set (tree2 r). snd y ≤ mp ⇒ mk = a ⇒ get_option_value (get_kp (mkNode c (mk, mp) l (a, b) r) a) = b "。
引理1表明,在使用重构函数进行重构后的树中,左右子树均满足规则2,且根节点的辅助节点不高于左右子树中任一节点的优先级,若辅助节点键值等于当前主键a,则get_kp函数可直接返回主键a对应的优先级b。
引理2. lemma invpst_search: "invpst t ⇒ invpst (fst (search t x))"。
引理2表明,在执行查找操作前后,树中辅助节点优先级等于该节点及其子树中所有数据的最大优先级这一性质保持不变,即规则2始终成立。
引理3. lemma get_kp_lt: "invpst l ⇒ invpst r ⇒ ∀y ∈ set (tree2 l) ∨ set (tree2 r). snd y ≤ mp ⇒ mk = x ⇒ x < a ⇒ get_kp (mkNode c (mk, mp) l (a, b) r) x = get_kp l x"。
引理4. lemma get_kp_rt: " invpst l ⇒ invpst r ⇒ ∀y ∈ set (tree2 l). snd y ≤ mp ⇒ l = Leaf ⇒ mk = x ⇒ x < a ⇒ get_kp (mkNode c (mk, mp) l (a, b) r) x = get_kp l x "。
引理3与引理4均表明,若经重构后的树满足以下条件,其左、右子树均符合规则2,查询值x小于当前主键a,右子树中不存在小于x的值,且辅助节点不包含x,则x在整棵树中的优先级与在左子树中的优先级相等。两者的差异在于,引理4的前提条件更为严格,对左子树设定优先级约束,且要求左子树为空节点。
查找操作的结构特性不变:要求操作前后树的核心结构性质保持不变,由定理3形式化描述,其证明依赖引理2、5、6、7细化推理过程。
定理3. 查找的结构特性不变。 theorem rb_apst_search:"inv_rb_apst t ⇒ inv_rb_apst (fst (search t x))"。
定理3表明,若查找操作执行前的FAPST满足结构不变式inv_rb_apst,则操作后得到的FAPST仍保持该不变性。这一性质的保持确保了查找操作不会破坏FAPST的固有结构约束,从而维持了树结构的稳定性与一致性。图7展示了定理3的证明过程,首先展开inv_rb_apst函数定义,将结构不变式的验证目标转化为一组可形式化验证的子性质。通过引理2、5、6和7确立了查找操作过程中关于结构保持、颜色一致性和黑高约束的逻辑推理,最终实现了对该定理的形式化验证。
引理5. lemma invc_search: "invc t ⇒ invc (fst (search t x))"。
引理5指出,在FAPST中,从任一内部节点到叶子节点的路径上不会出现连续的红色节点,并且该性质在查找操作之后仍然保持不变。
引理6. lemma invh_bheight: "invh t ⇒ invh (fst (search t x))"。
引理6表明,在FAPST中,从任一内部节点到其叶子节点的路径上黑色节点的数量一致,并且该属性在查找操作之后依然成立。
引理7. lemma color_search:"color t = Black ⇒ color (fst (search t x)) = Black"。
引理7表明,FAPST的根节点在查找操作前为黑色,操作后仍保持黑色不变。
查找操作的元素特性不变:元素特性不变要求查找操作不修改节点主节点对的数据及相对顺序,由定理4提供核心依据。
定理4. 查找的元素特性不变。 theorem inorder_search: "sorted1 (inorder t) ⇒ map fst (inorder (fst (search t x))) = map fst (inorder t)"。
定理4确保查找后,FAPST中数据元素集合及中序遍历逻辑顺序保持不变,即便树因优先级调整发生内部变化,通过map fst(inorder t)提取的主键序列始终一致,从语义层面保障了数据的完整性与有序性,证明过程如图8所示。
插入操作的结构特性不变:插入操作执行前后,FAPST的结构属性不会被破坏。如定理5,用以描述插入操作对结构稳定性的保持。
定理5. 插入的结构特性不变。 theorem rb_apst_update: "inv_rb_apst t ⇒ inv_rb_apst (update x y t)"。
定理5表明,若操作前FAPST满足结构不变式inv_rb_apst(综合规则2~5),则操作后新树仍维持该不变性。这确保插入操作在引入新元素时,不会破坏FAPST的固有结构约束,保障数据扩展过程中树结构的一致性与稳定性。
插入操作的元素特性不变:该特性要求插入后原有数据的取值、数量及相对顺序不变,仅新增元素被正确纳入,由定理6提供保障。
定理6. 插入的元素特性不变。 theorem inorder_update: "sorted1 (inorder t) ⇒ inorder (update x y t) = upd_list x y (inorder t)"。
定理6确保插入后,FAPST的中序遍历序列与预期更新结果一致。验证策略如图9所示:采用元素特性不变的证明思路,将插入操作后的FAPST中序遍历列表,与经Isabelle引理库验证的upd_list函数模拟插入后得到的列表比对。若两者一致,则可确认插入操作既保持原有元素完整性,又维持逻辑顺序的正确性。
删除操作的结构特性不变:该特性要求删除操作不破坏树的固有结构约束,由定理7形式化验证。
定理7. 删除的结构特性不变。 theorem rb_apst_delete: "inv_rb_apst t ⇒ inv_rb_apst (delete k t)"。
定理7明确,若操作前FAPST满足inv_rb_apst约束(规则2~5),则操作后新树仍维持该不变性。这保证删除操作在移除目标元素时,不违反FAPST的优先级特性、红黑节点约束、黑高一致性及根节点颜色规定,保障树结构动态修改后的稳定性。
删除操作的元素特性不变:该特性要求删除仅移除目标元素,未被操作元素的取值、数量及相对顺序保持不变,由定理8验证。
定理8. 删除操作的元素特性不变。 theorem inorder_delete: "sorted1 (inorder t) ⇒ inorder (delete x t) = del_list x (inorder t)"。
定理8确保删除后FAPST剩余节点的中序遍历序列与预期结果一致。验证策略如图10所示,采用与插入操作同源的抽象层级比对方法:将FAPST删除操作后的中序遍历列表,与经Isabelle引理库验证的del_list函数模拟删除后得到的列表比对。若两者一致,则可确认删除操作仅精准移除目标元素,完整保留数据集合的语义一致性与逻辑顺序。
本文以云原生环境中的Kubernetes(K8s)任务调度系统[28]与内容分发网络(content delivery network, CDN)缓存系统[29]为典型应用,分别对应访问敏感场景和热点转移场景。在K8s任务调度系统中,调度模块负责在集群节点间分配待执行任务,需持续访问任务队列并依据优先级进行排序[28]。在实际运行中,少量高优先级任务在特定时间窗口内被频繁触发,体现显著的时序局部性特征,属于典型的访问敏感场景;在CDN缓存系统中,内容被分发并缓存至边缘节点,以降低源站压力并提升访问时延性能,系统通常通过缓存替换与命中策略维持高命中率[29]。由于内容热度随时间变化,访问重心在不同时间窗口内持续转移,旧热点衰减、新热点产生,形成阶段性更替,具备显著的访问分布动态演化特征,属于典型的热点转移场景。
上述系统日志通常呈现明显的访问集中特征,即少数对象在不同阶段承担主要访问负载。针对该类动态负载环境下静态搜索结构适应能力不足的问题,本节围绕访问敏感场景与热点转移场景2类典型应用,系统展开FAPST的函数式建模、复杂度分析与实验验证,评估其在不同访问偏斜程度下的结构自适应能力;同时,借助Isabelle/HOL的代码生成机制生成Haskell实现,为其工程部署提供实现支撑。
访问敏感场景是指数据访问呈现显著时序局部性特征,即少量对象在短时间内被频繁访问。在云原生环境下的K8s任务调度系统中,少量高优先级或周期性任务会在特定时间窗口内被频繁触发,而多数任务仅偶发执行,体现出典型的访问敏感负载特征。当任务优先级未知或随运行动态变化时,静态搜索结构难以适配访问频率演化,检索路径无法随高频任务累积访问而优化。FAPST在查找过程中动态提升命中节点优先级,并沿路径自底向上调整结构,使高频任务逐步转移至树上层,从而缩短后续访问路径。围绕该类调度负载,将对访问敏感场景进行建模与复杂度分析,并通过实验评估FAPST的自适应优化效果。
在K8s任务调度过程中,访问敏感负载通常表现为对部分高优先级任务的批量调度请求,调度效率高度依赖优先级的动态调整。为刻画该动态调整特征,引入动态优先级机制,并构建查找函数search的序列化扩展模型searchs,用于描述批量调度过程中的结构调整机制,定义如下:
fun searchs :: " 'k psrbt ⇒ 'k::linorder list ⇒ 'k psrbt" where
"searchs t [] = t"|
"searchs t (x#xs) = searchs (fst(search t x)) xs"
searchs输入FAPST结构与待查关键字序列,输出优先级调整后的FAPST:空序列返回原树,非空序列先执行单次查找更新树,再递归处理剩余序列,实现高频关键字累积提权与位置调整。为保障其可靠性,基于单次search操作的正确性,验证其结构与元素特性不变性。
定理9. 批量查找操作的结构特性不变。 theorem rb_apst_searchs: "inv_rb_apst t ⇒ inv_rb_apst(searchs t xs)"。
定理9是searchs的结构稳定性核心保障,若初始FAPST结构t满足结构不变式inv_rb_apst,则处理任意序列xs后仍满足。如图11所示,其证明依托前文search函数的结构不变性,通过访问序列长度归纳,推导批量迭代中结构约束始终成立。
定理10. 批量查找操作的元素特性不变。 theorem inorder_searchs:"sorted1(inorder t) ⇒ map fst (inorder (searchs t xs)) = map fst(inorder t)"。
定理10是searchs操作正确性的形式化保障,若初始FAPST的中序遍历序列有序,则经searchs处理任意关键字序列后,中序遍历取主节点键(map fst)的结果与初始完全一致。如图11所示,其证明依赖前文已验证的search函数及其相关辅助引理。
本节从时间复杂度与空间复杂度2个方面,对FAPST在访问敏感场景下的性能开销进行理论分析。
1)时间复杂度。访问敏感场景的核心特征是任务访问偏斜,少量高频任务占据绝大部分访问请求。在K8s调度场景中,设调度队列中任务规模为n,其中高频触发任务集合为H,规模为 k($|H| $ = k,且k $\ll $ n)。由FAPST满足红黑性质可知,总树高h树高 < 2log(n + 1),任意查找操作的最坏情况时间复杂度为O(log n)。下面分3个阶段进行分析。
①初始阶段。高频任务未转移,存储位置无优势,查找路径长度受总树高约束,此时,高频任务的查找路径长度等于其在树中的实际深度d,且d受总树高约束,满足
$ d\leq {h}_{树高} \lt 2\log (n+1)={O}(\log n) 。 $
由于FAPST的查找时间成本与路径长度成正比,设单次查找的常数成本系数为c,则高频任务子集H的单次查找时间成本可表示为
$ {{cost}}_{初始}=c \times d 。 $
因此,初始阶段单次查找复杂度为O(log n)。
②过渡阶段。高频任务经多次访问优先级提升,逐步向树上层迁移形成高频子树B (B树高h<2log(k+1)),查找路径长度递减,复杂度从O(log n)逐步向O(log k)收敛。设总访问次数为C,前m次访问处于初始阶段(m $\ll $ C,即初始阶段持续的访问次数远少于总访问次数),则累计查找时间复杂度可拆分为初始阶段与过渡阶段2部分:
$ \sum\limits_{i=1}^{{C}}{cost}(i)=\sum\limits_{i=1}^{m}{O}(\log n)+\sum\limits_{i=m+1}^{{C}}{O}(\log k) 。 $
由于 m $\ll $ C,且O(log k) < O(log n)(k $\ll $ n),过渡阶段的累计复杂度逐步由O(log k)主导,整体呈现从O(log n)向O(log k)收敛的趋势。
③稳定阶段。高频任务完全转移至子树B,平均查找复杂度为
$ {{cost}}_{稳定}={P}({H})\times {O}(\log k)+(1-{P}({H}))\times {O}(\log n) 。 $
在典型的访问敏感场景中P(H)→1(高频访问概率较高),复杂度最终趋近O(log k),实现显著优化。
综上对比来看,FAPST与PST虽同为红黑树变体且最坏复杂度均为O(log n),但PST因优先级静态固定,高频任务无法转移,复杂度始终维持O(log n),难以适配访问敏感场景的偏斜特性。而FAPST靠动态优先级驱动高频任务转移,查找复杂度呈“初始O(log n)→过渡收敛→稳定O(log k)”的阶段性特征,精准契合高频任务集中访问的实际需求,最终效率优于PST,这正是其动态优先级机制的核心优化价值。
2)空间复杂度。FAPST在访问敏感负载下的结构调整仅涉及节点优先级更新与局部旋转操作,未引入额外辅助存储结构,其空间复杂度与PST一致,故不再展开。
为验证FAPST在访问敏感场景下的性能表现,围绕K8s任务调度系统的实际运行特征构建实验模型。在K8s调度过程中,调度器需要在待执行任务队列中定位目标任务并完成资源分配。实际运行日志表明,少量高优先级任务会在一定时间窗口内被频繁触发,而多数任务仅偶发调度,呈现明显的访问偏斜特征。为准确刻画这一现实分布特征,实验采用符合幂律分布的访问模型,并基于此自动生成具有不同偏斜程度的数据集:设定全体任务集合为T = {t1, t2, …, tn},其中,高频任务子集为H = {h1, h2, …, hk},全体任务集合T除去H后剩余的一般任务子集部分为S = {s1, s2, …, su},对全体任务的总查找次数为C,其中对高频任务子集的查找次数为CH,对一般任务子集的查找次数为CS,则查找次数之间满足:
$ {C}={{C}}_{{H}}+{{C}}_{{S}} 。 $
高频任务子集H的数据查找次数:
$ {{C}}_{{H}}=\sum\limits_{i=1}^{k}{C}({h}_{i}) 。 $
一般任务子集S的数据查找次数:
$ {{C}}_{{S}}=\sum\limits_{i=1}^{u}{C}({{s}}_{i}) 。 $
本文定义高频任务子集访问概率为:
$ {P}({H})=\frac{{{C}}_{{H}}}{{C}} 。 $
为评估FAPST与PST在该调度负载下的性能差异,本文选取查找过程中的关键函数调用次数作为响应时间度量的指标[30]。函数调用是算法执行的基本单元,核心逻辑(键值比对、优先级判断等)均依托其实现,总次数可直接反映执行路径长度与计算量。在此基础上,通过控制3个核心变量模拟多场景性能,开展算法效率的全面对比。
1)高频任务访问概率P(H)取 30%、60%、90%,对应一般、中等与显著偏斜调度负载。
2)调度队列规模n取30与100,覆盖不同规模的任务池。
3)总任务查找次数C从1000次递增至10000次,观察长期运行下的结构演化趋势。
通过上述参数组合,系统比较不同调度偏斜度、规模和运行周期下FAPST与对比结构的效率表现。
为确保实验结果的可靠性与稳定性,每组实验均独立重复10次,取关键函数调用次数的平均值作为统计结果,以降低随机误差对测量结果的影响。
图12和图13对比展示了在不同调度队列规模与访问偏斜度条件下各结构的性能差异。
1)PST的检索性能受高频任务访问概率影响较小,关键函数调用次数随访问概率提升无显著变化,这与其静态优先级机制无法响应访问模式变化的特性一致,该机制无法响应访问模式的动态变化,导致查找流程难以适配访问偏斜度的调整,体现了静态结构在动态场景下的局限性。
2)Splay树性能呈现明显的偏斜依赖特征:当偏斜度P(H)=30%时效率最低,显著劣于PST和FAPST。随着偏斜度增加,其性能逐步改善,在P(H)=90%时优于PST但仍次于FAPST。这表明Splay树对访问局部性具有一定自适应能力,但结构调整过程波动较大,在中低偏斜调度场景下稳定性不足。
3)FAPST展现出最优的综合性能,当P(H)=30%时已优于对比算法,随着P(H)提升至60%和90%,FAPST的优势逐步扩大,且调度次数越多,效率提升越显著。这一现象源于FAPST的访问驱动优先级调整机制:高频任务被反复调度后逐步转移至树上层,显著缩短后续定位路径。
表2进一步给出了10000次调度请求条件下的性能对比结果。在各访问偏斜度场景中,FAPST均显著优于PST,随着P(H)从30%逐步提升至90%,其性能提升幅度从20%左右持续扩大至64.8%,充分印证了其对动态访问模式的较强适配性;相较于Splay树,FAPST在低偏斜度场景(P(H)≤60%)下优势尤为突出,性能提升超45%,即便在Splay树更擅长的高偏斜度场景(P(H)=90%)中,仍保持约30%的性能领先;且当数据规模从n=30扩大至n=100时,FAPST的性能优势进一步凸显,各场景下提升幅度平均增加约10个百分点,展现出在大规模数据场景中的良好适配潜力。
综上,实验结果验证了FAPST在K8s调度负载下的结构自适应能力:其通过优先级动态调整机制优化搜索路径,在访问偏斜增强与系统规模扩大时性能优势持续提升。相比之下,PST受限于静态优先级机制难以适应访问模式变化,而Splay树虽具备一定自适应性,但在典型偏斜场景下仍逊于FAPST。因此,FAPST为高偏斜动态检索负载提供了更优的解决方案。
热点转移场景是指访问重心随时间窗口持续转移的动态过程,即原有热点逐步降温、新热点不断生成并占据主要访问负载。在CDN缓存系统中,某一阶段的热门内容会集中产生大量请求,而随着关注度变化,访问流量迅速转移至新的内容对象,形成典型的热点转移模式。
FAPST虽通过动态优先级机制缓解了PST的静态优先级适配问题,但其优先级调整主要依赖访问频率累积,缺乏历史热点主动衰减策略。在热点频繁更替环境下,已降温对象可能长期滞留于树结构上层路径,抑制新热点的快速上移。为此,引入热点转移机制,构建HS-FAPST(hotspot migration FAPST),通过历史热点优先级衰退策略,使新热点能够及时占据高优先级路径,避免路径垄断。图14展示了从PST到HS-FAPST的演进过程,后续将围绕CDN缓存负载展开函数式建模、复杂度分析与性能验证。
在CDN缓存系统中,缓存替换与命中效率高度依赖内容访问分布的动态演化。为刻画该动态演化特征,需在FAPST动态优先级机制基础上引入历史热点衰减能力。为此,基于Isabelle对原结构进行扩展,构建融合全局访问感知的HS-FAPST。在保持节点结构不变的前提下,引入周期性优先级衰减策略,使历史热点在访问间隔扩大后逐步降权,从而为新热点腾出上层路径空间。为实现上述机制,扩展数据类型如下:
$ {{\mathrm{type}}}\_{{\mathrm{synonym}}}\;\text{'}\mathrm{k}\;\mathrm{apst}=\text{'}\text{'}\text{'}\mathrm{k}\;\mathrm{psrbt}\times \mathrm{nat}\text{'}\text{'} , $
其中 'k psrbt为原FAPST主体结构,nat类型的全局计数器用于累计自上次衰减后的访问次数,从而实现对衰减时机的统一控制。针对历史热点优先级长期居高不下的问题,设计批量衰减函数tree_div,对全树节点优先级进行同比缩减(递归将优先级更新为原值的一半),具体函数建模如下:
fun tree_div :: " 'k psrbt ⇒ 'k psrbt " where
"tree_div Leaf = Leaf " |
"tree_div (Node l ((a,b), c, (mk, mp)) r) = (Node (tree_div l) ((a, b), c, (mk, mp div 2)) (tree_div r))"
衰减函数tree_div对所有节点优先级进行同比放缩后,不会改变FAPST的原有性质,即便遇到奇偶数并列的情况,也能满足其性质约束。例如,若根节点优先级mp为7、子树某节点mp为6,经衰减后mp均变为3,依旧满足原本的优先级性质(规则1),不需要对经过优先级衰减的FAPST调整节点位置。
在优先级衰减函数tree_div的基础上,定义触发衰减策略的逻辑操作,search_new函数作为扩展接口,在保留search核心功能的基础上,新增全局计数器count与阈值MAX的比较逻辑,实现衰减时机的动态调控,具体函数建模如下:
fun search_new:: "'k apst ⇒ 'k::linorder ⇒ 'k apst" where
"search_new (Leaf, count) x = (Leaf, Suc count)"|
"search_new (t, count) x = (if cmp (Suc count) MAX = GT
then (fst(search (tree_div t) x), 0)
else (fst(search t x), Suc count))"
融合热点转移机制的核心操作由tree_div与search_new协同完成,其优先级动态调控机制如图15所示。tree_div函数承担历史优先级批量衰减的核心功能,其设计受到计算机网络TCP协议中“乘法减小”策略[31]的启发。该策略的主要思想是在网络拥塞时通过“阶跃式减半”快速减少数据发送量,平衡过载避免性能波动。值得注意的是,本文并非对该策略进行简单移植,而是在应用对象与约束条件方面针对FAPST的结构特性进行了定制化适配设计。
在应用对象方面,TCP协议作用于网络层的流量控制,而HS-FAPST的tree_div则面向数据结构内部的优先级调度。具体到本设计,tree_div通过递归遍历FAPST节点,在访问次数触达预设阈值MAX时,将所有节点优先级从当前值P阶跃式衰减至P/2。该操作的核心目标是为潜在的新热点释放优先级资源,从而实现热点数据的平滑转移。为适配不同应用场景,阈值MAX通常依据访问模式(如访问的局部性强度、高频项比例)预先调优,针对不同场景的访问特征,可通过离线分析历史访问数据统计热点数据生命周期,将MAX初始值设为该场景下热点生命周期内平均访问次数的1~1.5倍。
在约束条件方面,TCP的窗口调整仅需遵循协议栈行为约束,而tree_div的操作必须严格遵循FAPST的结构不变式。具体包括:在优先级衰减过程中始终保持树的结构稳定性,避免因节点值突变引发重构抖动;同时,衰减操作与FAPST的优先级性质(规则2)深度协同,确保辅助节点中存储的子树最大优先级同步更新,以维持后续动态调整的准确性。这种在强结构约束下的批量衰减策略,既实现了历史热点的“软退出”,又通过阶跃式降权减少性能开销,适应热点持续更迭场景。
search_new作为热点转移入口,通过全局计数器count与阈值MAX的动态比较调控衰减时机,该逻辑与访问强度深度耦合:访问密集时高频衰减加速历史热点弱化,稀疏时则降低衰减频率以维持结构稳定。具体而言,count未达阈值时随访问递增以保持优先级和提升连续性;触达MAX时先调用tree_div执行整树优先级衰减,再重置计数器并通过search处理当前访问,流程契合FAPST“查找—调整—重构”闭环。tree_div与search_new操作协同实现网络流控到数据结构调度的适配,保障FAPST结构不变式,形成与访问强度耦合的“衰减—提升”动态逻辑。该逻辑可使历史热点在阈值处衰减(优先级降至P/2)后,新热点依托后续访问积累优先级,既为新热点保留上升空间、避免历史热点资源垄断以实现平滑转移,又能平衡资源释放效率与结构稳定性。
HS-FAPST在原有的查找操作基础上新增了优先级衰减及其对应的衰减阈值触发2个关键逻辑。本节基于第4节建立的机械化验证框架,仅需证明新增逻辑与FAPST原有不变性约束的兼容性,即可确保算法在维持正确性的同时,又实现了热点转移特性。
1)结构特性不变。第4节已验证FAPST结构稳定性及基础查找函数对结构不变式(含规则2~5)的保持性,新增逻辑需证明不破坏该不变式,即函数tree_div与search_new的执行不违反原有结构不变式,对其具体描述如定理11~12。
定理11. 衰减操作的结构特性不变。 theorem rb_apst_div: "inv_rb_apst t ⇒ inv_rb_apst (tree_div t)"。
定理12. 触发衰减操作的结构特性不变。 theorem rb_apst_search_new: "inv_apst_new t ⇒ inv_apst_new (search_new t x)"。
定理11验证tree_div仅调整优先级而不破坏树结构,定理12验证search_new与原有结构约束兼容,这2个定理共同保障HS-FAPST结构稳定。图16和图17分别给出定理11和定理12的证明过程。
2)元素特性不变。tree_div与search_new仅修改节点优先级,不影响数据元素的取值、数量及相对顺序。这一性质分别由定理13和定理14验证。
定理13. 衰减操作的元素特性不变。 theorem inorder_div: "sorted1(inorder t) ⇒ inorder (tree_div t) = inorder t"。
定理14. 触发衰减操作的元素特性不变。 theorem inorder_search_new:"sorted1(inorder t) ⇒ map fst (inorder(fst (search_new (t, count) x))) =map fst (inorder t)"。
定理13确保tree_div执行后中序遍历结果不变,保障数据完整性与顺序稳定。定理14确保search_new执行后主节点序列不变,验证其仅调整优先级而不改变元素主节点及排列,从而保障元素特性不变,证明过程如图18所示。
本节从时间复杂度与空间复杂度2个方面,对HS-FAPST在访问敏感场景下的性能开销进行理论分析。
1)时间复杂度。在CDN缓存系统中,内容热度随时间演化,访问重心阶段性迁移。为刻画该动态特征,在访问敏感场景分析基础上,进一步纳入高频数据随时间转移的影响,对HS-FAPST在热点迁移条件下的时间复杂度进行分析。设总任务规模为n,其中高频访问任务集合为H,规模为k($|H| $ = k,且k $\ll $ n)。热点转移周期为Th,优先级衰减阈值为MAX,其中Th与MAX近似相等,以符合FAPST的衰减触发特性。
①快速上升期(0 < t ≤ Th/3)
快速上升期与访问敏感场景的初始阶段类似,高频数据的查找路径长度等于其在树中的实际深度d,设单次查找的常数成本系数为c,则高频数据子集H的单次查找时间成本可表示为:
$ {{cost}}_{上升期}=c\times d 。 $
因此,快速上升期的单次查找时间复杂度受总树高主导,保持为O(log n)。
②优化收敛期(Th/3 < t ≤ 2Th/3)
此时新热点数据已进入树结构的中上层,查找路径显著缩短。此阶段性能由热点数据规模主导,逐步收敛至最优水平,与访问敏感场景类似,查找成本可表示为:
$ {{cost}}_{收敛期}={P}({H})\times {O}(\log k)+(1-{P}({H}))\times {O}(\log n) 。 $
收敛速率受访问概率P(H)影响,当P(H)→1时,查找时间复杂度逼近O(log k)。
③稳定高效期(2Th/3 < t ≤ Th)
新热点数据完全占据优势路径,树结构达到当前周期内的最优布局,性能稳定在最佳水平,查找成本可表示为:
$ {{cost}}_{高效期}={O}(\log k) 。 $
综合3个阶段的表现,HS-FAPST在完整热点转移周期内的平均查找时间复杂度为:
$ {cost}_{\text{HS}}=1/3\times {O}(\log n)+2/3\times {O}(\log k) 。 $
稳定高效期结束后,全局访问计数触达阈值MAX,系统自动触发整树优先级减半操作,解除历史热点路径垄断,为新一轮热点转移创造条件,形成“快速上升—优化收敛—稳定高效”的自适应闭环循环。
理论分析表明,HS-FAPST通过优先级衰减策略实现性能优化,复杂度从O(log n)降至O((1/3)log n + (2/3)log k)。相较于文献[3]中复杂度为O(log n)的非适配方案,在k $\ll $ n时优势显著,为HS-FAPST适配热点转移场景提供理论依据。
2)空间复杂度。在热点转移场景下,HS-FAPST在PST模型之外引入常数规模的全局状态变量,用于控制优先级衰减的触发时机。该扩展未增加额外的存储层级,因此不会改变节点数量及树规模的渐进增长特性。由此,算法在保持与PST相同渐进空间复杂度的前提下,实现了对动态访问负载的适应性增强,未引入额外的空间开销。
为评估HS-FAPST在热点转移负载下的适应能力,本实验以CDN缓存系统的周期性访问特征为背景构建动态访问模型。CDN场景中内容热度呈阶段性变化,访问重心随时间窗口持续转移,因此实验按固定时间窗口重划分高频子集H。每完成500次查找后,根据最新访问统计更新高频集合,以对应缓存周期内的热点更替过程。HS-FAPST中由search_new触发的优先级衰减频率约为1/500,远低于常规访问操作,其额外开销在整体执行过程中占比极小,对实验结果无显著影响。实验固定总访问次数C与高频访问概率P(H),比较PST、FAPST与HS-FAPST在动态热点负载下的执行效率,并以关键函数调用次数作为查找时间的量化指标。
图19展示了3种结构在热点动态转移负载下关键函数调用次数随总查找次数变化的趋势,可得以下结论:
1)PST采用静态优先级,无法响应CDN缓存周期内的热点更替。访问频繁的元素可能因初始优先级较低而长期处于结构低层,导致查找路径难以优化。实验表明PST查找执行效率为3种结构中效率最低的一个,凸显了其在面对动态访问场景时的结构性局限。
2)FAPST虽支持动态优先级调整,但在热点转移场景中,历史热点的高优先级会持续锁定优势位置,导致新热点上升路径缓慢、响应延迟。例如当P(H)=90%时,历史热点对路径的垄断性更强,FAPST的执行效率显著低于HS-FAPST,暴露出难以应对热点快速迭代的缺陷。
3)HS-FAPST通过引入周期性优先级衰减策略,模拟CDN中内容热度随时间自然降温的过程,使历史热点逐步退居次级路径,为新热点释放结构空间。实验结果表明,随查找次数增加(如P(H)=90%场景),与PST、FAPST的差距持续扩大,说明针对性引入热点转移机制,可在一定程度上优化热点转移场景访问效率。
表3从量化维度对3种结构的性能进行了精准对比,在固定10000次数据查找、数据集规模n=100的实验条件下,对比了3种结构在不同访问偏斜度下的查找操作关键函数调用次数。结果显示,随着高频子集访问概率P(H)的上升,HS-FAPST相较于PST和FAPST展现出更显著的效率优势。当P(H)=90%时,HS-FAPST的关键函数调用次数较FAPST缩短约29.4%,较PST缩短约46.3%。
综上,HS-FAPST在动态热点迁移场景中表现出了较强的适应能力,特别是在周期性热点更替的过程中。通过周期性优先级衰减策略,HS-FAPST能够有效缓解历史热点滞留问题,使得新热点能够迅速占据高优先级路径,避免了历史热点对路径的长期占用。实验结果进一步验证了该机制在CDN缓存等动态访问负载场景中的适用性,表明其在高频动态负载下能有效提升查询效率。
在完成FAPST结构的理论分析与形式化验证后,实现形式化模型向工业级可部署代码的转化成为核心环节。本文基于Isabelle/HOL验证框架,生成面向不同访问场景的Haskell实现代码。选取Haskell作为实现语言具备显著的工业化优势,其类型安全以及纯函数式特性与形式化验证模型高度契合,可确保实现代码与验证模型一致;同时,Haskell已在金融、通信等高可靠系统中广泛应用,成熟的工程实践为FAPST在实际部署中提供了稳定基础。本文可通过Code Generation方法中的export_code命令将访问敏感与热点转移场景下的核心算法自动生成为Haskell可执行程序,为进一步应用和工业化打下基础。
FAPST的设计目标是解决PST在动态访问场景中的局限,当访问分布高度偏斜或热点数据随时间变化时,PST因优先级固定易导致检索效率下降,而FAPST通过动态优先级调整、热点转移机制实现自适应优化,同时依托Isabelle完成函数式建模与机械化验证,确保结构正确性及基础操作的最坏时间复杂度为O(log n)。基于这些核心设计与特性,FAPST的适用范围可主要划分为2类。
1)访问敏感场景。访问分布高度偏斜(少量高频数据占主导),FAPST通过动态提升高频数据优先级缩短检索路径,确保调整后结构与数据完整性不变。具体适配场景包括:医疗患者信息高频检索、金融热门标的查询、电商爆款检索等。
2)热点转移场景。热点随时间动态转移,FAPST通过“历史热点衰减+新热点抢占路径”适配需求。经Isabelle/HOL机械化验证,该机制执行后树的结构稳定性、数据完整性及逻辑顺序均保持不变,确保检索逻辑无偏差。适配场景包括:短视频热门更新、监控系统异常追踪、新闻热点迭代等。
同样,FAPST在以下几类场景中仍有优化空间:静态访问模式下,数据访问频率稳定,其动态机制增益有限且存在维护开销,此时PST更具简洁性优势。轻量级检索任务(数据规模/访问频次极低),其函数式结构显复杂,数组、哈希表等轻量结构更高效。此外,访问模式极端抖动时,频繁优先级波动可能影响结构稳定性与调度效率。未来将探索自适应阈值与抖动抑制策略,增强其动态环境鲁棒性。
本文结合PST的研究现状,针对其优先级固定所导致的高频访问项查找性能局限,提出了一种基于动态优先级思想改进的FAPST结构。FAPST在通过函数式建模及机械化验证确保结构及操作正确性与可靠性的同时,通过引入访问频率驱动的优先级演化机制,使节点优先级能够根据访问行为动态更新,从而提升在访问敏感场景下的查找效率。然而,在访问热点频繁变化的应用中,FAPST仍面临历史热点优先级固化导致阻碍新热点快速响应的问题。为进一步提升结构对热点转移的适应能力,本文在原有FAPST基础上引入了热点转移机制,通过历史热点优先级逐步衰减的策略,解决历史热点滞留与新热点路径延迟的矛盾,且该机制的核心操作经形式化验证,确保与原有结构特性的兼容性。
实验结果表明,在访问敏感场景下,FAPST相较于PST在查找效率上展现出一定的改进,引入热点转移机制后,在热点频繁变化的访问负载下,其性能表现进一步优化,初步验证了该结构在复杂动态环境中的适应潜力与应用前景。未来研究可探索将该结构推广至更广泛的应用场景,如多维数据索引、高维检索任务及动态网络拓扑下的数据结构优化问题。

参考文献 引证文献
排序方式:
1
Paulson L C. Computational logic: Its origins and applications[J]. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2018, 474(2210): 20170872
2
Lammich P, Nipkow T. Priority search trees[EB/OL]. [2025-09-10]. https://www.isa-afp.org/browser_info/current/AFP/Priority_Search_Trees/document.pdf
3
Massa H, Uhlmann J. Access-adaptive priority search tree[J]. Innovations in Systems and Software Engineering, 2025, 21(4): 1323−1330
4
Nipkow T, Klein G. Concrete Semantics: With Isabelle/HOL[M]. Berlin: Springer, 2021
5
石海鹤, 蓝孙文, 刘日明, 等. 生物序列比对动态规划算法的统一形式化构造与Isabelle验证[J]. 计算机研究与发展, 2025, 62(1): 119−131
Shi Haihe, Lan Sunwen, Liu Riming, et al. Unified formal construction and Isabelle verification of the dynamic programming algorithms for biological sequence alignment[J]. Journal of Computer Research and Development, 2025, 62(1): 119−131(in Chinese)
6
Matichuk D, Murray T, Wenzel M. Eisbach: A proof method language for Isabelle[J]. Journal of Automated Reasoning, 2016, 56(3): 261−282
7
McCreight E M. Priority search trees[J]. SIAM Journal on Computing, 1985, 14(2): 257−276
8
Alistarh D, Kopinsky J, Li J, et al. The spraylist: A scalable relaxed priority queue[C] //Proc of the 20th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2015: 11−20
9
Seidel R, Aragon C R. Randomized search trees[J]. Algorithmica, 1996, 16(4): 464−497
10
Icking C, Klein R, Ottmann T. Priority search trees in secondary memory[C] // Proc of Int Workshop on Graph-Theoretic Concepts in Computer Science. Berlin, Springer, 1987: 84−93
11
Bronson N G, Casper J, Chafi H, et al. A practical concurrent binary search tree[J]. ACM Sigplan Notices, 2010, 45(5): 257−268
12
Natarajan A, Mittal N. Fast concurrent lock-free binary search trees[C] //Proc of the 19th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2014: 317−328
13
Afek Y, Kaplan H, Korenfeld B, et al. The CB tree: A practical concurrent self-adjusting search tree[J]. Distributed Computing, 2014, 27(6): 393−417
14
Ellen F, Fatourou P, Ruppert E, et al. Non-blocking binary search trees[C] //Proc of the 29th ACM SIGACT-SIGOPS Symp on Principles of Distributed Computing. New York: ACM, 2010: 131−140
15
Wang Zhongbin, Yang Luyi, Cui Shiliang, et al. In-queue priority purchase: A dynamic game approach[J]. Queueing Systems, 2021, 97(3): 343−381
16
Bose P, Cardinal J, Iacono J, et al. Competitive online search trees on trees[J]. ACM Transactions on Algorithms, 2023, 19(3): 1−19
17
Drouin A, Hocking T D, Laviolette F. Maximum margin interval trees [C] //Proc of Advances in Neural Information Processing Systems 30. Red Hook: Curran Associates, Inc., 2017: 4947−4956
18
Sleator D D, Tarjan R E. Self-adjusting binary search trees[J]. Journal of the ACM, 1985, 32(3): 652−686
19
王戟, 詹乃军, 冯新宇, 等. 形式化方法概貌[J]. 软件学报, 2019, 30(1): 33−61
Wang Ji, Zhan Naijun, Feng Xinyu, et al. Overview of formal methods[J]. Journal of Software, 2019, 30(1): 33−61(in Chinese)
20
左正康, 柯雨含, 黄箐, 等. Trie+结构函数式建模、机械化验证及其应用[J]. 软件学报, 2024, 35(9): 4242−4264
Zuo Zhengkang, Ke Yuhan, Huang Qing, et al. Trie+ structural functional modeling, mechanized merification and application[J]. Journal of Software, 2024, 35(9): 4242−4264 (in Chinese)
21
Nipkow T. Verified root-balanced trees [C]//Proc of Asian Symp on Programming Languages and Systems. Cham: Springer, 2017: 255−272
22
Nipkow T, Brinkop H. Amortized complexity verified[J]. Journal of Automated Reasoning, 2019, 62(3): 367−391
23
Hinze R, Paterson R. Finger trees: A simple general-purpose data structure[J]. Journal of Functional Programming, 2006, 16(2): 197−217
24
Hirai Y, Yamamoto K. Balancing weight-balanced trees[J]. Journal of Functional Programming, 2011, 21(3): 287−307
25
Nipkow T, Sewell T. Proof pearl: Braun trees[C] //Proc of the 9th ACM SIGPLAN Int Conf on Certified Programs and Proofs. New York: ACM, 2020: 18−31
26
Nipkow T, Somogyi D. Optimal Binary Search Trees[EB/OL]. [2025-9-10]. https://www.isa-afp.org/browser_info/current/AFP/Optimal_BST/document.pdf
27
Eberl M, Haslbeck M W, Nipkow T. Verified analysis of random binary tree structures[J]. Journal of Automated Reasoning, 2020, 64(5): 879−910
28
Burns B, Grant B, Oppenheimer D, et al. Borg, omega, and kubernetes[J]. Communications of the ACM, 2016, 59(5): 50−57
29
Nygren E, Sitaraman R K, Sun J. The akamai network: A platform for high-performance Internet applications[J]. ACM SIGOPS Operating Systems Review, 2010, 44(3): 2−19
30
Knuth D E. The Art of Computer Programming, Volume 3: Sorting and Searching[M]. New York: Addison-Wesley, 1999: 426−458
31
Jacobson V. Congestion avoidance and control[J]. ACM SIGCOMM Computer Communication Review, 1988, 18(4): 314−329
2026年第63卷第5期
68
29
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202550901
  • 接收时间:2025-12-15
  • 首发时间:2026-11-17
  • 出版时间:2026-05-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2025-12-15
  • 修回日期:2026-03-05
基金
作者信息
    1江西师范大学人工智能学院 南昌 330022
    2高性能计算江西省重点实验室(江西师范大学) 南昌 330022
    3语言智能研究中心(江西师范大学) 南昌 330022

通讯作者:

王昌晶()
参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202550901
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏