首页 > 代码库 > 我的游戏服务器类库 -- 配置表及其搜索算法

我的游戏服务器类库 -- 配置表及其搜索算法

配置表

想必所有的游戏服务器都要用到配置表,配置表可能来自于文件(Excel、XML、JSON等)或者数据库,但为了避免频繁访问磁盘文件或数据库,最终都会在服务器启动时读到内存里。配置表一般由很多行组成,每一行有一个唯一ID。在游戏逻辑中,可以根据ID来查找某项配置。由于每一个游戏服务器都要写类似的逻辑,所以我把它们抽象出来,加到了我的GitHub项目里。

配置项

没有对配置表项做更多的假设,只要求它有一个唯一ID

public interface Config {
    public int getId();
}
ConfigBase是Config接口的抽象实现,以方便子类继承:

public abstract class ConfigBase implements Config {

    private final int id;

    public ConfigBase(int id) {
        this.id = id;
    }
    
    @Override
    public int getId() {
        return id;
    }
    
}

搜索算法

有时候配置表也可能会比较大(比如几千上万行),所以按照ID快速找到一项配置就比较重要。SearchAlgorithm对配置表搜索算法进行了抽象:

public abstract class SearchAlgorithm {
    public abstract <T extends Config> T search(List<T> cfgs, int id);
}

我目前实现了3种搜索算法:按索引查找、二分查找、遍历查找。如果配置表ID是连续(递增)的,那么最快的搜索算法是按索引搜索:

public final class IndexedSearch extends SearchAlgorithm {

    @Override
    public <T extends Config> T search(List<T> cfgs, int id) {
        int firstId = cfgs.get(0).getId();
        int index = id - firstId;
        return cfgs.get(index);
    }
    
}
如果ID不连续,但是配置表比较小(比如小于8条),那么遍历整张表也许是最快的搜索算法:

public final class TraverseSearch extends SearchAlgorithm {

    @Override
    public <T extends Config> T search(List<T> cfgs, int id) {
        for (T cfg : cfgs) {
            if (cfg.getId() == id) {
                return cfg;
            }
        }
        
        throw new ConfigNotFoundException(cfgs, id);
    }
    
}
否则(配置表ID必须是递增的),使用二分法查找:

public final class BinarySearch extends SearchAlgorithm {

    @Override
    public <T extends Config> T search(List<T> cfgs, int id) {
        int index = indexedBinarySearch(cfgs, id);
        if (index >= 0) {
            return cfgs.get(index);
        } else {
            throw new ConfigNotFoundException(cfgs, id);
        }
    }
    
    // 代码是从java.util.Collections.indexedBinarySearch()里拷贝过来的,并进行了修改
    private static <T extends Config> int indexedBinarySearch(List<T> list, int id) {
        int low = 0;
        int high = list.size()-1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            T midVal = list.get(mid);
            int cmp = Integer.compare(midVal.getId(), id);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }
    
}

SearchAlgorithm的static方法selectAlgorithm()根据配置表的上述特点来选择最优的搜索算法,具体的代码就不贴了。

ConfigList

ConfigList将配置表和搜索算法封装在了一起:

public class ConfigList<T extends Config> {
    
    private final List<T> cfgs; // size > 0
    private final SearchAlgorithm searchAlgorithm;
    
    public ConfigList(List<T> cfgs) {
        if (cfgs.isEmpty()) {
            throw new IllegalArgumentException("empty list");
        }
        
        cfgs = new ArrayList<>(cfgs);
        sortCfgs(cfgs);
        checkSameId(cfgs); // ID不能重复
        
        this.cfgs = Collections.unmodifiableList(cfgs);
        searchAlgorithm = SearchAlgorithm.selectAlgorithm(this.cfgs);
    }

    ...
}
getConfigs()方法返回全部配置,getConfig(int)按ID查找配置:

    public List<T> getConfigs() {
        return cfgs;
    }
    
    public T getConfig(int id) {
        // todo check id
        return searchAlgorithm.search(cfgs, id);
    }



我的游戏服务器类库 -- 配置表及其搜索算法