首页 > 代码库 > 我的游戏服务器类库 -- 配置表及其搜索算法
我的游戏服务器类库 -- 配置表及其搜索算法
配置表
想必所有的游戏服务器都要用到配置表,配置表可能来自于文件(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); }
我的游戏服务器类库 -- 配置表及其搜索算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。