技术面试复盘：高频算法题的前端实现思路（防抖、节流、深拷贝等）

type DebounceOptions = { leading?: boolean; trailing?: boolean; maxWait?: number }
export function debounce<T extends (...args: any[]) => any>(fn: T, wait = 100, options: DebounceOptions = {}) {
  let timer: any = null
  let lastArgs: any[] | null = null
  let lastThis: any
  let lastCallTime = 0
  let lastInvokeTime = 0
  const leading = options.leading === true
  const trailing = options.trailing !== false
  const maxWait = typeof options.maxWait === 'number' ? options.maxWait : 0
  function invoke(time: number) {
    const args = lastArgs
    const context = lastThis
    lastArgs = null
    lastThis = null
    lastInvokeTime = time
    return fn.apply(context, args as any)
  }
  function startTimer(pending: () => void, ms: number) {
    timer = setTimeout(pending, ms)
  }
  function remainingWait(time: number) {
    const sinceLastCall = time - lastCallTime
    const sinceLastInvoke = time - lastInvokeTime
    const waitTime = wait - sinceLastCall
    return maxWait ? Math.min(waitTime, maxWait - sinceLastInvoke) : waitTime
  }
  function shouldInvoke(time: number) {
    const sinceLastCall = time - lastCallTime
    const sinceLastInvoke = time - lastInvokeTime
    return lastCallTime === 0 || sinceLastCall >= wait || sinceLastCall < 0 || (maxWait && sinceLastInvoke >= maxWait)
  }
  function trailingInvoke(time: number) {
    if (trailing && lastArgs) return invoke(time)
    lastArgs = null
    lastThis = null
    return undefined
  }
  function debounced(this: any, ...args: any[]) {
    const time = Date.now()
    const isInvoking = shouldInvoke(time)
    lastArgs = args
    lastThis = this
    lastCallTime = time
    if (!timer) {
      if (leading) invoke(time)
      startTimer(timerExpired, remainingWait(time))
    } else if (maxWait) {
      startTimer(timerExpired, remainingWait(time))
    }
  }
  function timerExpired() {
    const time = Date.now()
    if (shouldInvoke(time)) {
      timer = null
      trailingInvoke(time)
    } else {
      startTimer(timerExpired, remainingWait(time))
    }
  }
  ;(debounced as any).cancel = () => {
    if (timer) clearTimeout(timer)
    timer = null
    lastArgs = null
    lastThis = null
    lastCallTime = 0
    lastInvokeTime = 0
  }
  ;(debounced as any).flush = () => {
    if (timer) {
      clearTimeout(timer)
      timer = null
      return trailingInvoke(Date.now())
    }
  }
  return debounced as T & { cancel: () => void; flush: () => any }
}

type ThrottleOptions = { leading?: boolean; trailing?: boolean }
export function throttle<T extends (...args: any[]) => any>(fn: T, wait = 100, options: ThrottleOptions = {}) {
  let timer: any = null
  let lastArgs: any[] | null = null
  let lastThis: any
  let lastInvoke = 0
  const leading = options.leading !== false
  const trailing = options.trailing !== false
  function invoke(time: number) {
    lastInvoke = time
    const res = fn.apply(lastThis, lastArgs as any)
    lastArgs = null
    lastThis = null
    return res
  }
  function trailingInvoke() {
    if (trailing && lastArgs) invoke(Date.now())
  }
  function throttled(this: any, ...args: any[]) {
    const time = Date.now()
    if (!lastInvoke && !leading) lastInvoke = time
    const remaining = wait - (time - lastInvoke)
    lastArgs = args
    lastThis = this
    if (remaining <= 0 || remaining > wait) {
      if (timer) {
        clearTimeout(timer)
        timer = null
      }
      invoke(time)
    } else if (!timer && trailing) {
      timer = setTimeout(() => {
        timer = null
        trailingInvoke()
      }, remaining)
    }
  }
  ;(throttled as any).cancel = () => {
    if (timer) clearTimeout(timer)
    timer = null
    lastArgs = null
    lastThis = null
    lastInvoke = 0
  }
  return throttled as T & { cancel: () => void }
}

export function deepClone<T>(input: T, cache = new WeakMap()): T {
  if (typeof input !== 'object' || input === null) return input
  if (cache.has(input as any)) return cache.get(input as any)
  if (input instanceof Date) return new Date(input.getTime()) as any
  if (input instanceof RegExp) return new RegExp(input.source, input.flags) as any
  if (input instanceof Map) {
    const m = new Map()
    cache.set(input as any, m as any)
    for (const [k, v] of input as any as Map<any, any>) m.set(deepClone(k, cache), deepClone(v, cache))
    return m as any
  }
  if (input instanceof Set) {
    const s = new Set()
    cache.set(input as any, s as any)
    for (const v of input as any as Set<any>) s.add(deepClone(v, cache))
    return s as any
  }
  if (ArrayBuffer.isView(input)) {
    const Ctor: any = (input as any).constructor
    return new Ctor((input as any))
  }
  const isArray = Array.isArray(input)
  const proto = Object.getPrototypeOf(input as any)
  const result: any = isArray ? [] : Object.create(proto)
  cache.set(input as any, result)
  for (const key of Reflect.ownKeys(input as any)) {
    const desc = Object.getOwnPropertyDescriptor(input as any, key)!
    if (desc.get || desc.set) Object.defineProperty(result, key, desc)
    else result[key as any] = deepClone((input as any)[key as any], cache)
  }
  return result
}

export function deepEqual(a: any, b: any, seen = new WeakMap()): boolean {
  if (Object.is(a, b)) return true
  if (typeof a !== typeof b) return false
  if (typeof a !== 'object' || a === null || b === null) return false
  if (seen.get(a) === b) return true
  seen.set(a, b)
  if (a instanceof Date && b instanceof Date) return a.getTime() === b.getTime()
  if (a instanceof RegExp && b instanceof RegExp) return a.source === b.source && a.flags === b.flags
  if (a instanceof Map && b instanceof Map) {
    if (a.size !== b.size) return false
    for (const [k, v] of a) if (!b.has(k) || !deepEqual(v, b.get(k), seen)) return false
    return true
  }
  if (a instanceof Set && b instanceof Set) {
    if (a.size !== b.size) return false
    for (const v of a) if (![...b].some(x => deepEqual(v, x, seen))) return false
    return true
  }
  const keysA = Reflect.ownKeys(a)
  const keysB = Reflect.ownKeys(b)
  if (keysA.length !== keysB.length) return false
  for (const k of keysA) {
    const da = Object.getOwnPropertyDescriptor(a, k)
    const db = Object.getOwnPropertyDescriptor(b, k)
    if (!!da?.get !== !!db?.get || !!da?.set !== !!db?.set) return false
    if (da && !da.get && !da.set) if (!deepEqual((a as any)[k as any], (b as any)[k as any], seen)) return false
  }
  return true
}

export function createScheduler(limit = 5) {
  let active = 0
  const queue: Array<{ task: () => Promise<any>; resolve: (v: any) => void; reject: (e: any) => void }> = []
  function run() {
    while (active < limit && queue.length) {
      const item = queue.shift()!
      active++
      Promise.resolve().then(item.task).then(v => { active--; item.resolve(v); run() }).catch(e => { active--; item.reject(e); run() })
    }
  }
  return function add(task: () => Promise<any>) {
    return new Promise((resolve, reject) => { queue.push({ task, resolve, reject }); run() })
  }
}

export function curry(fn: Function, arity = fn.length) {
  function curried(this: any, ...args: any[]) {
    if (args.length >= arity) return fn.apply(this, args)
    return (...rest: any[]) => curried.apply(this, args.concat(rest))
  }
  return curried
}
export const compose = (...fns: Function[]) => (x: any) => fns.reduceRight((v, f) => f(v), x)

export function timeout<T>(p: Promise<T>, ms = 2000) {
  return Promise.race([p, new Promise<T>((_, rej) => setTimeout(() => rej(new Error('timeout')), ms))])
}
export async function retry<T>(fn: () => Promise<T>, times = 3, delay = 200, factor = 2) {
  let d = delay
  for (let i = 0; i < times; i++) {
    try { return await fn() } catch { if (i === times - 1) throw new Error('retry failed'); await new Promise(r => setTimeout(r, d)); d *= factor }
  }
}
export function allSettled<T>(arr: Iterable<T | Promise<T>>) {
  return Promise.all(Array.from(arr, p => Promise.resolve(p).then(v => ({ status: 'fulfilled', value: v })).catch(e => ({ status: 'rejected', reason: e }))))
}

export class Emitter {
  private store = new Map<string, Set<Function>>()
  on(event: string, handler: Function) { if (!this.store.has(event)) this.store.set(event, new Set()); this.store.get(event)!.add(handler); return () => this.off(event, handler) }
  once(event: string, handler: Function) { const wrap = (...args: any[]) => { this.off(event, wrap); handler(...args) }; return this.on(event, wrap) }
  off(event: string, handler: Function) { const set = this.store.get(event); if (set) set.delete(handler) }
  emit(event: string, ...args: any[]) { const set = this.store.get(event); if (!set) return; for (const h of set) h(...args) }
}

const onInput = debounce((v: string) => doSearch(v), 300, { trailing: true })
const onScroll = throttle(() => checkPosition(), 200)
const cloned = deepClone({ a: new Map([[1, { x: 1 }]]) })
const equal = deepEqual(new Set([1,2]), new Set([2,1]))
const add = createScheduler(4)
add(() => fetch('/a'))
const req = retry(() => fetch('/api').then(r => r.json()), 3, 200)
const bus = new Emitter()
bus.on('ready', () => {})

import { expect } from 'vitest'
expect(typeof debounce(() => 1, 100)).toBe('function')
expect(deepEqual({a:1}, {a:1})).toBe(true)
expect(deepEqual(new Date(1), new Date(1))).toBe(true)
const s = createScheduler(2)
const order: number[] = []
await Promise.all([
  s(async () => { order.push(1) }),
  s(async () => { order.push(2) }),
  s(async () => { order.push(3) })
])
expect(order[0]).toBe(1)

export function debounceThrottle<T extends (...args:any[])=>any>(fn:T, debounceMs=300, throttleMs=100){
  const d = debounce(fn, debounceMs)
  const t = throttle(fn, throttleMs)
  return (...args:any[])=>{ d(...args); t(...args) }
}

export async function fetchWithTimeout(input: RequestInfo, init: RequestInit & { timeout?: number } = {}){
  const ctrl = new AbortController()
  const id = setTimeout(()=>ctrl.abort(), init.timeout ?? 2000)
  try { const res = await fetch(input, { ...init, signal: ctrl.signal }); return res }
  finally { clearTimeout(id) }
}

type Task = { run: () => Promise<any>; priority: number }
export function createPriorityScheduler(limit=4){
  let active=0
  const q: Task[]=[]
  function schedule(){ q.sort((a,b)=>b.priority-a.priority); while(active<limit && q.length){ const t=q.shift()!; active++; t.run().then(()=>{active--; schedule()}).catch(()=>{active--; schedule()}) } }
  return (run:()=>Promise<any>, priority=0)=>{ q.push({run,priority}); schedule(); return new Promise<void>(r=>{ r() }) }
}

export function rafThrottle<T extends (...args:any[])=>any>(fn:T){
  let locked=false
  return (...args:any[])=>{
    if(locked) return
    locked=true
    requestAnimationFrame(()=>{ locked=false; fn(...args) })
  }
}

export class LRU<K,V>{
  private map=new Map<K,V>()
  constructor(private cap:number){}
  get(k:K){ if(!this.map.has(k)) return undefined as any; const v=this.map.get(k)!; this.map.delete(k); this.map.set(k,v); return v }
  set(k:K,v:V){ if(this.map.has(k)) this.map.delete(k); this.map.set(k,v); if(this.map.size>this.cap){ const first=this.map.keys().next().value as K; this.map.delete(first) } }
  has(k:K){ return this.map.has(k) }
  size(){ return this.map.size }
}

type Job<T>=()=>Promise<T>
export function createAsyncPool(limit=4){
  let active=0
  const q: Array<()=>void> = []
  function drain(){ while(active<limit && q.length){ const f=q.shift()!; active++; f() } }
  return function run<T>(job: Job<T>){
    return new Promise<T>((resolve,reject)=>{
      const exec=()=>{ job().then(v=>{ active--; resolve(v); drain() }).catch(e=>{ active--; reject(e); drain() }) }
      q.push(exec); drain()
    })
  }
}
export async function withRetry<T>(fn:()=>Promise<T>, times=3, delay=200, factor=2){
  let d=delay
  for(let i=0;i<times;i++){ try{ return await fn() } catch(e){ if(i===times-1) throw e; await new Promise(r=>setTimeout(r,d)); d*=factor } }
  throw new Error('retry failed')
}
export async function withTimeout<T>(p:Promise<T>, ms=2000){ return Promise.race([p,new Promise<T>((_,rej)=>setTimeout(()=>rej(new Error('timeout')),ms))]) }

export function all<T>(arr:Array<T|Promise<T>>){ return Promise.all(arr.map(x=>Promise.resolve(x))) }
export function any<T>(arr:Array<T|Promise<T>>){
  return new Promise<T>((resolve,reject)=>{
    let remaining=arr.length
    const errors:any[]=[]
    arr.forEach(p=>Promise.resolve(p).then(resolve).catch(e=>{ errors.push(e); if(--remaining===0) reject(new AggregateError(errors)) }))
  })
}
export function race<T>(arr:Array<T|Promise<T>>){ return new Promise<T>((resolve,reject)=>{ arr.forEach(p=>Promise.resolve(p).then(resolve,reject)) }) }

export function safeClone<T>(x:T):T{ const sc=(globalThis as any).structuredClone; return typeof sc==='function' ? sc(x) : deepClone(x as any) }

const pool=createAsyncPool(4)
const search=debounce((q:string)=>pool(()=>withTimeout(fetch(`/api?q=${q}`).then(r=>r.json()),1500)),300,{trailing:true})
const onScroll=rafThrottle(()=>pool(()=>withRetry(()=>fetch('/more').then(r=>r.json()),2,200)))

import React, { useMemo, useState } from 'react'
import { debounce, rafThrottle, retry } from './utils'

export default function SearchPage() {
  const [q, setQ] = useState('')
  const debouncedSearch = useMemo(() => debounce((x: string) => fetch(`/api?q=${x}`), 300, { trailing: true }), [])
  const onScroll = useMemo(() => rafThrottle(() => retry(() => fetch('/more'), 2, 200)), [])
  return (
    <div onScroll={onScroll as any}>
      <input value={q} onChange={e => { setQ(e.target.value); debouncedSearch(e.target.value) }} />
    </div>
  )
}

import { ref, onMounted } from 'vue'
import { debounce, rafThrottle } from './utils'
export default {
  setup() {
    const q = ref('')
    const run = debounce((x: string) => fetch(`/api?q=${x}`), 300, { trailing: true })
    const onScroll = rafThrottle(() => fetch('/more'))
    onMounted(() => window.addEventListener('scroll', onScroll))
    return { q, run }
  }
}

防抖/节流    时间 O(1)    空间 O(1)
深拷贝        时间 O(n)    空间 O(n)
深比较        时间 O(n)    空间 O(n)
并发池        时间 O(k+n)  空间 O(n)