EN中文
开发者社区 > 程序

如何快速写出一个排位榜

发表于2017-03-10
评论3 3.3k浏览

导语 
　　在游戏中，除了按数值的排行榜，另一个比较常见的就是排位榜了：和对方竞赛，如果赢了，交换排名；如果输了，保持排名不变。最近因为全民农场有一个拼车的任务，突发奇想就想写一个排位榜的实现，下面就来给大家分享下我是如何快速写出一个排位榜的。

一、目的
　　在游戏中，除了按数值的排行榜，另一个比较常见的就是排位榜了：和对方竞赛，如果赢了，交换排名；如果输了，保持排名不变。最近因为全民农场有一个拼车的任务，突发奇想就想写一个排位榜的实现，下面就来给大家分享下我是如何快速写出一个排位榜的。

二、原理
　　排位榜应该有如下功能
　　1、交换排名
　　2、添加排名
　　3、通过排名查询到玩家信息
　　4、通过玩家帐号查到排名

　　鉴于此，我们采用boost::multi_index_container库，采用random_access索引类型做为排名索引，采用ordered_unique做为帐号索引。实现了上述功能，排名的持久化通过boost::interprocess和CKV实现：整个排位榜放到内存映射文件里，排位的前N名存到CKV里，通过版本号决定是不是需要从CKV里加载数据。

三、性能
　　在现网有4个榜，每个榜5W人(做为一个活动，每个区玩的人大概这么多)，CPU没有压力。
　　分析下数据结构的时间复杂度：我们知道ordered_unique采用红黑树实现，因此添加排名是O(log(N))的，交换排名是O(1)的(交换数据就可以了)，这个索引开销不会大，random_access_index也可以交换元素(当然在代码里没这么做，不过没有关系)，所以效率应该不是问题。

附录

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#pragma once
 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
 
namespace bmi = boost::multi_index;
namespace bi = boost::interprocess;
 
typedef boost::array<char, 40=""> lpod_open_id_t;
 
class swap_ranker
{
public:
    enum ecode
    {
        e_success = 0,
        e_unknown = -1,
        e_reach_max_num = -2,
        e_duplicate_open_id = -3,
        e_open_id_not_found = -4,
    };
 
    typedef bi::basic_managed_mapped_file<char, bi::rbtree_best_fit"">, bi::iset_index> managed_mapped_file_t;
 
    typedef bi::allocator<char, managed_mapped_file_t::segment_manager="">      char_allocator_t;
    typedef bi::basic_string<char, std::char_traits<char="">, char_allocator_t> char_string_t;
 
    struct node_info
    {
        node_info(const lpod_open_id_t& open_id, char_allocator_t alloc):open_id(open_id), data(alloc){}
        lpod_open_id_t open_id;
        char_string_t data;
    };
 
    typedef bi::node_allocator""> node_info_allocator_t;
 
    struct tag_open_id{};
 
    struct tag_index{};
 
    typedef bmi::multi_index_container<
        node_info,
        bmi::indexed_by<
            bmi::ordered_unique"" &node_info::open_id=""> >,
            bmi::random_access
        >,
        node_info_allocator_t
    > node_info_db_t;
 
 
    typedef node_info_db_t::index::type open_id_index_t;
 
    typedef node_info_db_t::index::type index_index_t;
 
    int init(const std::string& fn, size_t fsize, size_t max_num);
 
    int append(const lpod_open_id_t& open_id, const char* data, int data_len);
 
    int update(const lpod_open_id_t& open_id, const char* data, int data_len);
 
    int swap(const lpod_open_id_t& open_id_a,
        const char* data_a, int data_a_len,
        const lpod_open_id_t& open_id_b,
        const char* data_b, int data_b_len);
 
    inline size_t size() const {return m_db->size();}
 
    const node_info* find_node_info_by_index(int idx) const;
 
    int find_index_by_open_id(const lpod_open_id_t& open_id) const;
 
    uint32_t get_version() const;
 
    void set_version(uint32_t version);
 
private:
    boost::shared_ptr m_file;
    node_info_db_t* m_db;
    size_t m_max_num;
    uint32_t* m_version;
};char,>char,>char,>char,>string>


?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include "swap_ranker.h"
 
int swap_ranker::init(const std::string& fn, size_t fsize, size_t max_num)
{
    m_file.reset(new managed_mapped_file_t(bi::open_or_create, fn.c_str(), fsize));
 
    node_info_allocator_t alloc(m_file->get_segment_manager());
    m_db = m_file->find_or_construct("node_info_db")(alloc);
 
    m_max_num = max_num;
 
    m_db->get().reserve(m_max_num);
 
    m_version = m_file->find_or_construct("version")(0);
 
    return e_success;
}
 
int swap_ranker::append(const lpod_open_id_t& open_id, const char* data, int data_len)
{
    if (m_db->size() >= m_max_num)
    {
        // full
        return e_reach_max_num;
    }
 
    char_allocator_t alloc(m_file->get_segment_manager());
    node_info info(open_id, alloc);
    info.open_id = open_id;
    if (data != NULL && data_len > 0)
    {
        info.data.assign(data, data_len);
    }
    if (!m_db->insert(info).second)
    {
        return e_duplicate_open_id;
    }
 
    return e_success;
}
 
struct node_info_modifier
{
    node_info_modifier(const lpod_open_id_t& open_id, const char* data, int data_len):open_id(open_id), data(data), data_len(data_len){}
    bool operator()(swap_ranker::node_info& info)
    {
        info.open_id = open_id;
        info.data.assign(data, data_len);
        return true;
    }
    lpod_open_id_t open_id;
    const char* data;
    int data_len;
};
 
 
 
int swap_ranker::update(const lpod_open_id_t& open_id, const char* data, int data_len)
{
    open_id_index_t& index = m_db->get();
    open_id_index_t::iterator it = index.find(open_id);
    if (it == index.end())
    {
        return append(open_id, data, data_len);
    }
      
    index.modify(it, node_info_modifier(open_id, data, data_len));
    return e_success;
}
 
extern void print_rank(const swap_ranker& ranker);
 
int swap_ranker::swap(const lpod_open_id_t& open_id_a,
        const char* data_a, int data_a_len,
        const lpod_open_id_t& open_id_b,
        const char* data_b, int data_b_len)
{
    if (open_id_a == open_id_b)
    {
        return e_success;
    }
 
    open_id_index_t& index = m_db->get();
    index_index_t& iindex = m_db->get();
 
    append(open_id_a, data_a, data_a_len);
    append(open_id_b, data_b, data_b_len);
 
    index_index_t::iterator ita = m_db->project"">(index.find(open_id_a));
    index_index_t::iterator itb = m_db->project"">(index.find(open_id_b));
 
    if (ita != iindex.end())
    {
        if (itb != iindex.end())
        {
            index_index_t::iterator ita_next = ita + 1;
            index_index_t::iterator itb_next = itb + 1;
            iindex.relocate(ita_next, itb);
            iindex.relocate(itb_next, ita);
        }
        else
        {
            iindex.modify(ita, node_info_modifier(open_id_b, data_b, data_b_len));
        }
    }
    else
    {
        if (itb != iindex.end())
        {
            iindex.modify(itb, node_info_modifier(open_id_a, data_a, data_a_len));
        }
        else
        {
            // all not on board, nothing todo.
        }
    }
     
    return e_success;
}
 
const swap_ranker::node_info* swap_ranker::find_node_info_by_index(int idx) const
{
    if ((size_t)idx >= size())
    {
        return NULL;
    }
    index_index_t& index = m_db->get();
    return &index[idx];
}
 
int swap_ranker::find_index_by_open_id(const lpod_open_id_t& open_id) const
{
    open_id_index_t& index = m_db->get();
    index_index_t& iindex = m_db->get();
    index_index_t::const_iterator it = m_db->project"">(index.find(open_id));
    if (it != iindex.end())
    {
        return it - iindex.begin();
    }
    else
    {
        return -1;
    }
}
 
 
uint32_t swap_ranker::get_version() const
{
    return *m_version;
}
 
void swap_ranker::set_version(uint32_t version)
{
    *m_version = version;
}

以上就是通过代码快速实现一个排位榜的教程，希望可以帮到大家。

如社区发表内容存在侵权行为，您可以点击这里查看侵权投诉指引

标签：

游戏开发Boost游戏视觉排行榜ArrayCPU