大规模玩家场景下传球模拟算法的优化需求问询

问题背景 #

我正在解决一个公园传球问题，原问题出自brainly平台。当前实现的解决方案逻辑正确，但在处理大规模数据时存在严重性能瓶颈：当player规模达到10^9量级、seconds=9999999时，求解耗时约1分20秒，急需优化。

原解决方案代码 #

seconds = 6
player = random.sample(range(1, 11), 10)
next_receiver = player[0]
for i in range(1, seconds): 
   next_receiver = player[next_receiver-1]
   # next_receiver at the end of the loop is the player who will have the ball

优化提示 #

• 解决内存存储问题：当player规模达到10^9时，无法将整个数组存入内存。必须替换数组存储方式——如果player是伪随机生成的排列，实现一个get_next(k)函数直接计算第k个玩家的传球目标，而非存储全部数据。
• 循环检测减少遍历次数：传球过程本质是在排列的环结构上移动，每个玩家最终会进入循环。用Floyd判圈算法找到循环的长度cycle_len，计算remaining = seconds % cycle_len，只需遍历remaining次即可得到结果，时间复杂度从O(seconds)骤降为O(cycle_len)。
• 倍增法快速跳跃：预处理每个位置在2^0、2^1、2^2…步后的目标位置，将seconds拆分为二进制，通过组合预计算的跳跃步长直接得到最终位置。该方法预处理和查询时间均为O(log seconds)，适配超大seconds场景。

内容的提问来源于stack exchange，提问作者Hardik Rathod