Exercism TypeScript Robot Name练习两种实现均运行超时求排查

第一种随机生成实现问题 #

• 高占比下碰撞重试开销爆炸：总可用名称共676000个（26²×10³），当已分配名称占比超过80%时，随机生成的名称碰撞概率超过80%，while循环重试次数会呈指数级上升，测试用例若覆盖全量名称分配场景，累计重试开销直接导致超时。
• 单名称生成逻辑冗余：每次生成需要两次字符随机、三次数字随机拼接，无缓存复用，单步生成效率低于预生成方案。

export class Robot {
  private _name: string = ''
  private static _releaseNames: Set<string> = new Set<string>()

  constructor() {
    this.resetName()
  }

  public get name(): string {
    return this._name
  }

  public static releaseNames(): Set<string> {
    return Robot._releaseNames
  }

  public resetName(): void {
    let name = this.generateName()
    while (Robot._releaseNames.has(name)) {
      name = this.generateName()
    }
    Robot._releaseNames.add(name)
    this._name = name
  }

  private generateName(): string {
    const letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    const digits  = '0123456789'

    let name = ''
    for (var i = 0; i < 2; i++) {
      name += letters.charAt(Math.floor(Math.random() * letters.length))
    }
    for (var i = 0; i < 3; i++) {
      name += digits.charAt(Math.floor(Math.random() * digits.length))
    }

    return name
  }
}

第二种预生成实现超时核心原因 #

预生成的思路是对的，但实现细节存在三个严重性能问题：

• 静态初始化开销过大：类加载阶段同步执行三重循环生成67.6万个字符串，再执行Fisher-Yates全数组洗牌，Exercism测试环境冷启动资源有限，这一步大概率直接触发超时阈值。
• shift()操作复杂度极高：Array.shift()是O(n)操作，需要将数组所有元素索引前移一位，累计执行67.6万次shift()的总时间复杂度达到O(n²)，哪怕初始化阶段没超时，取名称阶段也会超时。
• 未适配测试全局重置逻辑：Exercism测试用例之间会调用Robot.releaseNames()清空全局状态，你当前的releaseNames仅返回已用列表，没有重置可用池和取数位置，多轮用例执行时会直接耗尽名称抛错，也可能导致测试流程卡住。

export class Robot {
  public name: string = ''
  private static _availableNames: string[] = Robot.shuffleArray(Robot.getAvailableNames())
  private static _releaseNames: string[] = []

  constructor() {
    this.resetName()
  }

  public resetName(): void {
    let name = Robot._availableNames.shift()
    if (name === undefined) {
      throw new Error('No name available')
    }
    this.name = name
    Robot._releaseNames.push(name)
  }

  public static releaseNames(): string[] {
    return Robot._releaseNames
  }

  private static getAvailableNames(): string[] {
    let names = []

    for (let c1 = 65; c1 < 91; c1++) {
      for (let c2 = 65; c2 < 91; c2++) {
        for (let num = 0; num < 1000; num++) {
          let name = String.fromCharCode(c1) + String.fromCharCode(c2) + num.toString().padStart(3, '0')
          names.push(name)
        }
      }
    }

    return names
  }

  private static shuffleArray(array: any[]): any[] {
    for (let i = array.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [array[i], array[j]] = [array[j], array[i]];
    }
    return array;
  }
}

优化建议 #

针对第二种实现微调即可解决超时：

1. 用索引指针替代shift()取名称，将取数复杂度降到O(1)，不需要修改数组结构。
2. 完善releaseNames的全局重置逻辑，不需要重新生成数组，仅需对已有数组重新洗牌、重置指针即可，适配多轮测试用例的执行要求。
3. 可选将预生成逻辑延迟到第一次调用resetName时执行，进一步降低类初始化开销。

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