如何快速写出一个排位榜
发表于2017-03-10
导语
在游戏中,除了按数值的排行榜,另一个比较常见的就是排位榜了:和对方竞赛,如果赢了,交换排名;如果输了,保持排名不变。最近因为全民农场有一个拼车的任务,突发奇想就想写一个排位榜的实现,下面就来给大家分享下我是如何快速写出一个排位榜的。
一、目的
在游戏中,除了按数值的排行榜,另一个比较常见的就是排位榜了:和对方竞赛,如果赢了,交换排名;如果输了,保持排名不变。最近因为全民农场有一个拼车的任务,突发奇想就想写一个排位榜的实现,下面就来给大家分享下我是如何快速写出一个排位榜的。
二、原理
排位榜应该有如下功能
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 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
|
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
|
以上就是通过代码快速实现一个排位榜的教程,希望可以帮到大家。