游戏中排行榜的实现RankMap

排行榜这个东西

相信各位大神们玩过各种牛批的游戏,游戏里或多或少都有排行榜的存在,击杀排行、得分排行、充值排行(嘿嘿)!我来给你们演示一下你们最熟悉的东西:

排名        姓名           充值数量

1             张三          10000000

2            李四            9000000

3        王麻子            8000000

不难看出,这3个土豪当中,张三最土豪,我们喜欢他。在排行榜众多细节中,我们来列举一二。其一,我们需要知道第N名是哪个土豪,以便做好跪舔的准备,其二,我们可能会做分页或者获取一个范围内的土豪,以做好跪舔的准备,其三,我们可能通过土豪的ID来查询他是第几名,以便做好跪舔的准备,其四,土豪们真是太有钱了,你追我赶,非要拼个你死我活,看到底谁更豪,我们需要快速更新排名,更好的做好跪舔的准备。

游戏中,特别是即时类游戏,为了速度,会尽量在内存中操作数据,所以我们这里讨论的结构是适用于内存中快速操作的结构。如果你说数据库可以做排名或排序,是的,可以,但是即时性和速度不符合上面的要求。

先从排序说起

想必大家在学习编程的时候,最开始都会接触到排序算法,比如冒泡排序、快速排序、归并排序、堆排序这些,但是注意,这些排序的算法都是建立在一个完整的数据上,我们这里讨论的是边插入删除数据,边变更新排名。虽然边插入删除边更新的需求让人很恼火,因为即时性非常高,但是正因为如此,我们可以规避上面的一些排序算法,因为我们数据是即时更改即时算的,我们只需要在插入数据的时候,去找到他最合适的位置即可。

我一说树,你不要害怕,我只是提一下这个东西,这里讲的排行榜是用不到他的,大家放心。所谓的树,就是字面意思,有一个根,根分出来很多的叶子,叶子就是数据的载体,给你们画个图看看

根只有一个,其他都是叶子,叶子下面可以有无数的叶子,依次无限类推,有点像一个分岔的链表结构。比如说文件系统,他就是个典型的树结构,而且他的叶子可以有很多,每个叶子就是一个文件或文件夹,叶子有子叶子,他就是文件夹,反之他就是文件。有些叶子可以埋得很深,但是你得从根目录开始找,D盘/学习资料/Java学习资料/Java8资料/不可描述的资料。一般情况下,我们要那么多叶子没得什么卵用,对于研究他的特征,我们可以来探讨二叉树。所谓二叉树就是只有两根叉叉的树。

只有两根叉叉就好说了,每个叶子的子叶子最多两个,也就是说每个叶子都有二向性,从一个叶子出发,要么走左下的一个,要么走右下的一个。对于只考虑左右来说,我们的选择和所要考虑的情况就小很多。比如我们现在要存储一堆数字到这个树里面,按照如下规则,新进来的数字对比根节点,如果根节点为空就直接放置,如果比根节点小,就去找根左边的叶子,如果比根节点大就找右边的叶子,对于下一个叶子,按照上述方法对比一次,依次类推,直到找到一个空的节点来放置就算完成。我们这里演示下下面数字[2,5,1,6,4]是如何放进一个二叉树里面的。

很容易学会如图所示的插入方法,其实通过我们对比大小的方法来插入,对于这个二叉树来说,他就已经是有序的了。如果我们要查找一个数字的位置,只需要再使用我们插入的方法来走一遍就行了。

这里有个问题,这种树的结构虽然能快速的找到我想要的元素,但是有两个东西我们没法快速确认,第一、索引,他到底是第几名,除了我们重新去查找一次,别无他法。第二、树也没有一种映射关系,比如我想通过某个土豪的ID来查找他第几名,我们只有遍历整个树来确认,不尽人意啊。

数组

数组如果你不明白,我觉得你 可以先回去补下基础了,数组内存地址连续,只需要储存他最初的地址,通过地址的偏移,我们就能很快的定位到他的第N个元素在哪,所以说,数组按编号来索引的速度是非常快的。

数组不像树那样,我们可以通过一层一层的对比,去确定是左或者右,递归下去我们总能找到想要的结果。数组是线性结构,很耿直的一条线贯穿,树的方法并不实用,但是思想我们是可以借鉴的,就是对比取左右的方法。

二分查找

如果在数组中你查找数据是一格一格来看的话,那简直就是太可爱了。我们可以找个大概,先从中间开始找,比中间小就去找左边,比中间大就去找右边,左边或右边的查找再重复这样的方式,不用遍历所有元素,我们就能很大概的把数据找出来了,是不是跟上面树的方法很相似。但是你要知道,这种查找方法是建立在有序的基础上,如果是没有序列的一组数据,你二分的意义何在?好在我们是一边对比元素一边插入数据,这样一来,每一次的操作都会保证整个数组是有序的。你要问了,数组是固定长度的呀,不适合这种操作。是的,所以我们需要一个变长的数组,ArrayList不是现成的吗。

哈希表

所谓哈希表就是说一个值(Key),我能通过这个值快速查找到另一个值(Value),一个很通俗的例子:字典,字典太典型了,你通过查找拼音或英文首字母,就能快速定位到他在哪一页。在Java里我们使用HashMap来做字典(具体HashMap的实现方法或哈希表怎么通过Key来确定Value的可以去补下课)。

RankMap

上面讲了一大堆,差不多把我们最开始说的需求都罗列了一遍,现在整理一下让他组装成一个RankMap。RankMap需要哪些操作,不外乎放入比较对象,获取第几名是哪个土豪,做分页查询,通过映射来获取土豪是第几名。我们定义如下接口

public interface RankMap<K, V extends RankMap.RankObj<K>> {
    interface RankObj<K> {
        K key();

        int compareKey(K other);
    }

    interface LongRankObj extends RankObj<Long> {

        @Override
        default int compareKey(Long other) {
            return Long.compare(other, key());
        }
    }

    /**
     * 获取值
     *
     * @param key
     * @return
     */
    @Nullable
    V get(@NotNull final K key);

    /**
     * 替换或放入新的值
     *
     * @param value
     * @return
     */
    void replaceOrPut(@NotNull V value);

    /**
     * 是否包含Key
     *
     * @param key
     * @return
     */
    boolean containsKey(@NotNull final K key);

    /**
     * 删除值
     *
     * @param key
     * @return
     */
    V remove(@NotNull final K key);

    /**
     * 更新值
     *
     * @param key
     * @param consumer
     */
    void update(@NotNull final K key, @NotNull final Proc1<V> consumer);

    /**
     * 如果不存在则放入
     *
     * @param value
     */
    void putIfAbsent(@NotNull final V value);

    /**
     * 新增或更新
     *
     * @param key
     * @param consumer
     * @param instance
     */
    void updateOrPut(@NotNull final K key, @NotNull final Proc1<V> consumer, @NotNull final Func<V> instance);

    /**
     * 集合大小
     *
     * @return
     */
    int size();

    /**
     * 找到此Key在排行榜的名次
     *
     * @param key
     * @return
     */
    int getIndex(@NotNull final K key);

    /**
     * 获取一个范围的数据
     *
     * @param start 开始索引(包含边界)
     * @param end   结束索引(包含边界)
     * @return
     */
    @NotNull
    List<V> getRange(int start, int end);

    /**
     * 获取所有
     *
     * @return
     */
    @NotNull
    List<V> getAll();

    /**
     * 获取指定位置的元数
     *
     * @param index
     * @return
     */
    V getAt(int index);

    /**
     * 清空
     */
    void clear();

}

RankObj是作为比较的对象,他来确定对比哪些数值。

private final List<V> list;
private final Map<K, V> map;
private final Comparator<V> comparator;
private final int capacity;

要实现这些接口我们需要一个ArrayList和HashMap来存储数据,以及数据的比较器和排行榜的最大容量(缓存结构,要控制容量大小,不然服务器要炸)

实现一下二分查找,这里因为我们有插入数据和查找数据两种需求,所以二分查找的功能是找到最近似的位置或精确位置,近似的位置我们用来做插入操作,精确的位置用来确定数据的排名(代码改编自Java源代码)

private int binarySearch(V v, boolean similar) {
    int low = 0;
    int high = size() - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        V midVal = list.get(mid);
        int cmp = this.comparator.compare(midVal, v);
        if (cmp == 0) {
            cmp = midVal.compareKey(v.key());
        }
        if (cmp < 0) low = mid + 1;
        else if (cmp > 0) high = mid - 1;
        else return mid;
    }
    if (similar) {
        return low;
    }
    throw new IllegalStateException("can not find pos,maybe change the value without this map???");
}

由于我们每次对比数据来源于插入操作,如果外部持有了某个元素的引用而修改了会用于比较的值,这种情况会导致排名错误,所以我们封装的方法中,必须要做检测,并且在插入的时候要移除依次老的对象,让他重新确定位置,防止错误的发生。

   @Override
    public void update(K key, Proc1<V> consumer) {
        V old = map.get(key);
        Conditions.notNull(old != null, "key(%s) pufIfAbsent first!", key);
        // 在更新前先找到老值的位置
        listRemove(old);
        consumer.run(old);
        int newIndex = binarySearch(old, true);
        list.add(newIndex, old);
    }

    @Override
    public void putIfAbsent(V value) {
        Conditions.notNull(value, "value");
        if (map.containsKey(value.key())) {
            return;
        }
//        Conditions.args(!map.containsKey(value.key()), "key duplicated:%s", value.key());
        int binarySearch = 0;
        if (size() > 0) {
            binarySearch = binarySearch(value, true);
        }
        map.put(value.key(), value);
        list.add(binarySearch, value);
        while (capacity > 0 && map.size() > this.capacity) {
            V pollLast = list.remove(map.size() - 1);
            map.remove(pollLast.key());
        }
    }

    @Override
    public void updateOrPut(K key, Proc1<V> consumer, Func<V> instance) {
        if (!containsKey(key)) {
            V newInstance = instance.run();
            consumer.run(newInstance);
            putIfAbsent(newInstance);
        } else {
            update(key, consumer);
        }
    }

    private void listRemove(V old) {
        int i = binarySearch(old, false);
        V remove = list.remove(i);
        Conditions.args(
                old == remove, "remove obj not equals,comparator or key comparator must be error!");
    }

虽然说每次插入数据会导致数组的其他元素发生偏移,但是经过测试,量级在十万级别及以下的时候,并不会造成明显的性能问题,对于即时排行榜来说够用了。我不相信各位大佬的游戏中即时排行榜会要求存储这么多元素,显然是需求没提好…好了,详细内容去看Limitart源码,这里就不拓展了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注