c++ 游戲 積分 排名 怎么弄

zwjzwj19891228

內(nèi)容大概是這樣的： 競技場系統(tǒng)，里面的每個(gè)玩家(player_id)  打贏一盤都會有積分(player_score)，  我要知道  某個(gè)玩家 對應(yīng)排了多少名，假設(shè)積分不重復(fù)

我的想法是這樣的   類里面  有兩個(gè)map，一個(gè)是以player_id 為索引，一個(gè)是 以player_score 為索引
                                  map<   player_id,        player_score>   m1
                                  map<   player_score,   player_id>   m2

當(dāng)插入一個(gè)玩家的時(shí)候，插入到 兩個(gè)map中

當(dāng)要查詢某個(gè)  player_id對應(yīng)的 排名時(shí) 1.   通過第一個(gè)map 查詢到  這個(gè)玩家  多少分，
                                                  2.   通過第二個(gè)map查詢到   這個(gè)玩家 對應(yīng)的 迭代器，再通過  這個(gè) 迭代器 和 第二個(gè)的開始迭代器 之間的距離 來查到 他 多少名
                                                                                                                        stl有一個(gè)自帶的算法   std::distance( iter , m2.begin() )
這個(gè) 雖然看上去 還行，不過 在 步驟2  中， 由于 map 的迭代器 不是 隨機(jī)迭代器，不支持相減，所以是一個(gè)線性遍歷，來查到這個(gè)是  第幾個(gè)

各位 大神，我就是  為了避免 遍歷， 才想到 用兩個(gè)map的 ，有沒有 啥 好辦法 找到 player_id 對應(yīng)的排名，

面試官 和我說了 有更好的辦法， 可就說了一個(gè)名詞，沒有具體說，我也不太記得了，雖然面試還是過了，可是 很好奇，很好奇

謝謝

linux_c_py_php

樓主的辦法不是不行, distance的消耗我認(rèn)為還真不容易搞掉, 但缺點(diǎn)就是紅黑樹要遍歷太慢了, 為了找一個(gè)后繼要跳N下才能找到. 另外, 用map存player_id->player映射也比hash慢.

可以參考redis的zset,

用skiplist存儲score->player映射, 用hash存儲player_id->player映射.

zyzbill

如果為了distance消除遍歷樹的消耗，可以用std::vector<std::pair<player, score>>， 用lower_bound/upper_bound, distance來操作。主要，你需要用std::sort給vector排序先

hellioncu

打贏一盤的積分與相比玩家的積分相比應(yīng)該小得多，可以實(shí)時(shí)維護(hù)按積分排序的數(shù)組，有變動直接在數(shù)組中找新位置，尋找次數(shù)應(yīng)該很小，名次就是在數(shù)組中的位置

yulihua49

zyzbill 發(fā)表于 2013-09-25 19:29
如果為了distance消除遍歷樹的消耗，可以用std::vector， 用lower_bound/upper_bound, distance來操作。主要 ...

排序的開銷比遍歷還大，況且數(shù)據(jù)還是動態(tài)的。

zhaohongjian000

用AVL樹，在樹的每個(gè)節(jié)點(diǎn)上維護(hù)一個(gè)額外的信息：當(dāng)前節(jié)點(diǎn)的左子樹有多少個(gè)節(jié)點(diǎn)。這個(gè)信息在每次插入、刪除、旋轉(zhuǎn)的時(shí)候都需要維護(hù)。插入新的節(jié)點(diǎn)之后，從新節(jié)點(diǎn)向上走到根節(jié)點(diǎn)就可以知道新節(jié)點(diǎn)的名次，復(fù)雜度log(n)。

紅黑樹維護(hù)這種信息是否可行就不知道了。

zhaohongjian000

更完美的答案：順序統(tǒng)計(jì)樹（order-statistitc tree），見算法導(dǎo)論14.1節(jié)。