关于一种游戏规则的算法实现

[jjdd]

每个用户进入游戏后，系统随机推荐几个他以前从未挑战过的用户。一旦他挑战过了，就不再出现在这个推荐列表当中。

该如何设计这个程序能让查询高效一些呢，用户有很多，把用户表和挑战记录表连表查询效率肯定低。这种情况下如何设计合理的程序呢？

[Mutoo]

可以考虑使用布隆过滤器。这样不需要存储大量的冗余信息，只要一个二进制串就可以了。

[xatest]

为了简化问题，我假定2个前提，不知道你的实际需求是否容许。
1. 挑战记录是有限个的，例如1024个。如果挑战记录超出了这个上限，那么很早很早以前挑战过的用户，还是有可能推荐给他。
2. 挑战记录的上限不多，至少不像用户表那么大。
挑战记录在插入时排序。查找一个用户是否挑战过，只要二分查找就行了，效率是O(Log(N))。比如N是1024，那最多10次比较就能判断。

[alexapollo]

在用户远大于1024时
随机推荐用户，如果以挑战过继续随机推荐

[akfish]

如果用户数量固定，然后又不需要对对手做一定条件的限制的话，用不重复的伪随机数生成器，你只需要存储随机数种子就行了。
随机数就是对手的唯一id，每次next。
等于是用户一来，他挑战对手的顺序就已经决定了，不过对于用户而言，依然是随机的。

如果用户数量要变化，或者要做参数过滤，分几坨就行了（比如按注册时间一坨，按等级一坨等等），然后每坨内用同样的方式index。

[akfish]

哦，不知道你的重复挑战是怎么定义的。
如果A打过B，然后B打A也算重复的话，可以在B打A的时候取A的随机数种子，然后生成一遍看B自己的ID出现过没。

[kurtis]

我的建议是，如果空间开销允许，可以拿空间换时间，
例如：假设仍旧是最近1024个为上限，为每个用户开一个不超过1024长的可变数组（插入时要排序），
挑战过或者被挑战过都记录在内。

下次随机生成时只要跳过该数组内出现的用户即可。基本上生成随机用户是线性复杂度或者常数复杂度（用户数固定的话）。

[kurtis]

顺便问一下，如何达到线性复杂度，需要说明吗？

[jjdd]

@akfish 感谢回复。a挑战b等于b也挑战了a的

[akfish]

@jjdd 不谢，那没问题如上。伪随机数生成器是deterministic的，seed定了，每次序列都一样，最坏线性时间，每个用户多两个int字段，每次数据库读一次写一次。这样时间、存储、IO需要都不高。

[Sherlockhlt]

@akfish
这方法靠谱，赞一个！

[Sherlockhlt]

@akfish
不过用户数目是一直在增加的，用随机数似乎就无包括后面增加的一些用户了，比如用户人数是 1000 的时候随机到1999，那么就余数得到999，然后以后就再也无法和1999挑战了。

[akfish]

@Sherlockhlt 可以按一定规律把用户列表分出几个固定长度N的bucket，每个bucket一个ID K，用不重复的[1, N]区间的定长N伪随机数序列。
存随机数的seed，当前用到的bucket ID，上一次打过的user ID。
打完一个bucket的用户，再K++撸下一个的。
这样可以解决用户数的增加的问题。

对于未满的bucket，简单的做法是，ID越界检测，不存在的跳过就行了。缺点是bucket未满时被跳过的ID，用户就打不到了。
当然可以bucket满了才能被随机到(在未满bucket里的用户依然能打别人)，如果是按注册时间来分的话，等于顺便实现了新手保护规则。

[kurtis]

平心而论， 很少看到认真讨论些东西的帖子，不少帖子是：买这个好吗，这种语言好吗，没有gf怎么办之类的