面试时遇到一个问题 某一接口t秒内只能访问n次 注意是严格限制 即任意t秒内都不能超过n次 我给出的思路是记录最近n次访问的时间 空间复杂度是n 但面试官说不需要记录n次 可以优化 我也想到了如图的算法 但是这样并不能严格限制 求大佬指点
楼主说：不知道是不是面试官加班太多累糊涂了
深圳游戏员工说：m
深圳游戏员工说：可以按秒为单位
ivd员工说：创立定时监控结构，初次调用加入定时器，此后依次累加 累加的变量放监控结构，注意写保护和内存cache步，timer 结构到点抽出，这样不需记时间，对定时结构访问做互斥，对次数读取做读写保护
前深圳万翼科技有限公司员工说：Redis记录第一次时间然后设置过期时间，没次访问用原子增，可以解决吧
楼主说：定时器的开销更大吧
ivd员工说：觉得 面试官主要想考两个 原子操作 读写保护
ivd员工说：定时器只是为了清空调用次数 让该接口可重新被调
ivd员工说：你只需要在第一次调用把监控放入timer，到点后就清，抽出，没人调用的时候不需要管
楼主说：面试官没想那么多 就想问数据结构
ivd员工说：我是参照c c++的实现，感觉这里面的坑就是 会被并发访问的对象的更改 保护
网易游戏员工说：令牌桶
程序猿.泰山弟子说：这个没涉及到并发吧
ivd员工说：可能会，除非单线程被锁在一个cpu上
京东员工说：令牌桶啊兄弟
程序猿.武当弟子说：令牌桶不满足条件
百度员工说：这个可以用限流算法里的滑动窗口，窗口大小是t
程序猿.秃笔翁说：维护一个下次可访问的时间戳和空闲数量就行了
程序猿.丁春秋说：m
楼主说：限制某一用户的操作
血腥的资本家说：这个比较难得，得多重窗口滑动
曲非烟说：典型的 RateLimiter
昆仑弟子说：真假不重要，重要的是你想的这里有吗？
程序猿.萧让说：令桶
楼主说：令牌桶是限制全局的访问量 这里说的是指定用户的
程序猿.纪灵说：针对单个用户或者ip的令牌桶呗
楼主说：如果用户有几百万 要弄几百万个令牌桶？ 集群中数据怎么共享
美团点评员工说：限制某一用户的操作更简单了吧，redis原子操作计数器啊。。
美团点评员工说：m
楼主说：注意审题 只做计数器的话不能满足t秒内限制n次
程序猿.解宝说：滑动窗口