Chinaunix

标题: 请大牛支招排名算法 [打印本页]

---

作者: VIP_fuck    时间: 2017-04-12 12:00
标题: 请大牛支招排名算法
大概意思是这样：有很多用户，用户有各种信息，还有个人积分。

希望能多这些人的积分做一个排名，除了能快速排名之外，还要快速获取指定用户的排名。

大牛指教。

---

作者: windoze    时间: 2017-04-12 13:19
http://www.boost.org/doc/libs/1_ ... ndex/doc/index.html

---

作者: VIP_fuck    时间: 2017-04-12 13:55
回复 2# windoze

多谢多谢，以前接触过这个，不过当时没细看，现在要不是大猫提醒，也没想起来。
只是临时用 multiset 做个比较傻的处理。

研究研究，多谢多谢。

---

作者: lxyscls    时间: 2017-04-12 14:24

VIP_fuck 发表于 2017-04-12 12:00
大概意思是这样：有很多用户，用户有各种信息，还有个人积分。

希望能多这些人的积分做一个排名，除了能 ...

《算法导论》

第14章数据结构的扩张
14.1动态顺序统计

扩张红黑树，在保证全部顺序的情况下，也能定位到某个元素的顺序（rank）

你也可以用redis存，它提供了sorted set，其内部实现是skip-list（《Redis设计与实现》这么讲的）

https://redis.io/commands#sorted_set

---

作者: VIP_fuck    时间: 2017-04-12 15:48
回复 4# lxyscls

多谢指教，我先试试大猫提供的办法。
然后学习一下这个红黑树扩展。

时间有限，只能先有功能再优化。

---

作者: cokeboL    时间: 2017-04-12 16:11
游戏业内比较普遍的做法是4楼说的 redis skiplist

---

作者: windoze    时间: 2017-04-12 16:24
其实每次插入删除的时候把每个用户的排名调一下就行了。
如果插入删除不多的话这么最省事。

---

作者: cokeboL    时间: 2017-04-12 17:02
还有人用堆排序的，up down fix，也ok

---

作者: action08    时间: 2017-05-02 23:29
堆排序固然独特，但是场景有限，游戏排名不对口

---

作者: lxyscls    时间: 2017-05-03 09:37
回复 8# cokeboL

minheap只能保证第一个最小呀，heap[2i+1]和heap[2(i+1)]只能保证比heap大，请问排序怎么玩呢？

---

作者: VIP_fuck    时间: 2017-05-03 10:53
排序算法本身没啥了，我就用 set 排序了，然后针对业务逻辑再做相关优化，目前感觉还行。

---

作者: sditmaner    时间: 2017-05-03 11:01
回复 4# lxyscls

---

作者: dorodaloo    时间: 2017-05-03 12:03
感觉还行。

---

作者: cokeboL    时间: 2017-05-05 14:17
回复 10# lxyscls

不是用堆做队列，是用堆排序对数组进行排序

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2