这是一个创建于 3890 天前的主题，其中的信息可能已经有所发展或是发生改变。
每个用户进入游戏后，系统随机推荐几个他以前从未挑战过的用户。一旦他挑战过了，就不再出现在这个推荐列表当中。
该如何设计这个程序能让查询高效一些呢，用户有很多，把用户表和挑战记录表连表查询效率肯定低。这种情况下如何设计合理的程序呢？
该如何设计这个程序能让查询高效一些呢，用户有很多，把用户表和挑战记录表连表查询效率肯定低。这种情况下如何设计合理的程序呢？
 |
1
Mutoo 2014-05-03 00:05:05 +08:00  3
可以考虑使用布隆过滤器。这样不需要存储大量的冗余信息，只要一个二进制串就可以了。
|
 |
2
xatest 2014-05-03 00:42:15 +08:00 1
为了简化问题，我假定2个前提，不知道你的实际需求是否容许。
1. 挑战记录是有限个的，例如1024个。如果挑战记录超出了这个上限，那么很早很早以前挑战过的用户，还是有可能推荐给他。 2. 挑战记录的上限不多，至少不像用户表那么大。 挑战记录在插入时排序。查找一个用户是否挑战过，只要二分查找就行了，效率是O(Log(N))。比如N是1024，那最多10次比较就能判断。 |
 |
3
alexapollo 2014-05-03 01:04:31 +08:00 1
在用户远大于1024时
随机推荐用户，如果以挑战过继续随机推荐 |
 |
4
akfish 2014-05-03 11:33:46 +08:00 2
如果用户数量固定，然后又不需要对对手做一定条件的限制的话，用不重复的伪随机数生成器，你只需要存储随机数种子就行了。
随机数就是对手的唯一id，每次next。 等于是用户一来，他挑战对手的顺序就已经决定了，不过对于用户而言，依然是随机的。 如果用户数量要变化，或者要做参数过滤，分几坨就行了（比如按注册时间一坨，按等级一坨等等），然后每坨内用同样的方式index。 |
|
5
akfish 2014-05-03 11:36:32 +08:00
哦，不知道你的重复挑战是怎么定义的。
如果A打过B，然后B打A也算重复的话，可以在B打A的时候取A的随机数种子，然后生成一遍看B自己的ID出现过没。 |
 |
6
kurtis 2014-05-03 12:06:33 +08:00 1
我的建议是，如果空间开销允许，可以拿空间换时间，
例如：假设仍旧是最近1024个为上限，为每个用户开一个不超过1024长的可变数组（插入时要排序）， 挑战过或者被挑战过都记录在内。 下次随机生成时只要跳过该数组内出现的用户即可。基本上生成随机用户是线性复杂度或者常数复杂度（用户数固定的话）。 |
|
7
kurtis 2014-05-03 12:14:13 +08:00
顺便问一下，如何达到线性复杂度，需要说明吗？
|
|
9
akfish 2014-05-03 15:52:58 +08:00
@jjdd 不谢，那没问题如上。伪随机数生成器是deterministic的，seed定了，每次序列都一样，最坏线性时间，每个用户多两个int字段，每次数据库读一次写一次。这样时间、存储、IO需要都不高。
|
 |
10
Sherlockhlt 2014-05-03 19:11:08 +08:00
@akfish
这方法靠谱，赞一个！ |
|
11
Sherlockhlt 2014-05-03 19:14:02 +08:00
@akfish
不过用户数目是一直在增加的，用随机数似乎就无包括后面增加的一些用户了，比如用户人数是 1000 的时候随机到1999，那么就余数得到999，然后以后就再也无法和1999挑战了。 |
|
12
akfish 2014-05-03 19:31:46 +08:00
@Sherlockhlt 可以按一定规律把用户列表分出几个固定长度N的bucket，每个bucket一个ID K，用不重复的[1, N]区间的定长N伪随机数序列。
存随机数的seed，当前用到的bucket ID，上一次打过的user ID。 打完一个bucket的用户，再K++撸下一个的。 这样可以解决用户数的增加的问题。 对于未满的bucket，简单的做法是，ID越界检测，不存在的跳过就行了。缺点是bucket未满时被跳过的ID，用户就打不到了。 当然可以bucket满了才能被随机到(在未满bucket里的用户依然能打别人)，如果是按注册时间来分的话，等于顺便实现了新手保护规则。 |
|
13
kurtis 2014-05-05 11:17:27 +08:00 1
平心而论， 很少看到认真讨论些东西的帖子，不少帖子是：买这个好吗，这种语言好吗，没有gf怎么办之类的
|
Select Language