一种针对GPU加速多步长前缀树的更新序列维护方法

摘要

本发明涉及一种针对GPU加速多步长前缀树的更新序列维护方法，该方法包括以下步骤：创建第一数组和第二数组，以及设置第一变量；所述第一数组第i号单元初始化为i，所述第二数组则全置为0；所述第一变量，用来记录目前更新操作的次数，并且会初始化为0；当CPU收到一个针对GAMT第x号单元执行更新的操作，CPU则调整所述第一数组上的位置。本发明可以针对GAMT更新序列排序问题，将其排序时间复杂度降低到最差情况下O(n/8)，并且往第一数组中插入新元素的时间复杂度为O(1)。