Introdução

Os estrangulamentos de desempenho em sistemas de agendamento podem significar a diferença entre uma experiência de usuário responsiva e usuários abandonando sua plataforma devido à frustração. No Cal.com, recentemente descobrimos e otimizamos vários algoritmos críticos O(n²) que estavam causando lentidão à medida que nossa base de usuários e volumes de dados aumentavam.

Neste artigo, compartilharei quatro otimizações reais de algoritmos do código do Cal.com. Você aprenderá como detectamos a complexidade O(n²), quais estratégias de otimização funcionaram melhor e como implementamos verificações automatizadas para prevenir regressões futuras.

O problema: Como um código inocente se torna O(n²)

À medida que as plataformas de agendamento crescem, é surpreendentemente fácil para loops aninhados parecerem inocentes, mas se tornarem assassinos silenciosos de desempenho. Considere este exemplo real do nosso código:

// O(n²): Every available slot is checked against every busy period
availableTimeSlots.map(slot => {
  return busy.some(busyTime => checkOverlap(slot, busyTime));
});

Para 100 intervalos e 50 períodos ocupados, isso são 5.000 verificações de sobreposição. Em escalas maiores—500 intervalos e 200 períodos ocupados—isso explode para 100.000 operações. Isso representa um aumento de vinte vezes na carga computacional para apenas um aumento de cinco vezes nos dados.

Estudo de caso 1: Otimização de verificação de conflito de intervalo

O problema original

A função checkForConflicts usava iteração aninhada para verificar se intervalos de reserva conflitavam com períodos ocupados. Isso rapidamente se tornou um problema de desempenho com grandes cronogramas.

Implementação original: Loops aninhados O(n²)

function checkForConflicts({ busy, time, eventLength }) {
  return busy.some(busyTime => {
    const slotStart = time.valueOf();
    const slotEnd = slotStart + eventLength * 60 * 1000;
    const busyStart = dayjs.utc(busyTime.start).valueOf();
    const busyEnd = dayjs.utc(busyTime.end).valueOf();
    return !(busyEnd <= slotStart || busyStart >= slotEnd);
  });
}

availableTimeSlots = availableTimeSlots
  .map((slot) => {
    if (
      !checkForConflicts({
        time: slot.time,
        busy: busySlotsFromReservedSlots,
        ...availabilityCheckProps,
      })
    ) {
      return slot;
    }
    return undefined;
  })

Implementação otimizada: O(n log n) com ordenação e término antecipado

function checkForConflicts({ sortedBusyTimes, time, eventLength }) {
  const slotStart = time.valueOf();
  const slotEnd = slotStart + eventLength * 60 * 1000;

  for (const busyTime of sortedBusyTimes) {
    if (busyTime.start >= slotEnd) {
      break;
    }
    if (busyTime.end <= slotStart) {
      continue;
    }
    return true;
  }
  return false;
}

O que mudou:
Ordenamos os tempos ocupados pelos seus horários de início, permitindo pular períodos não sobrepostos e sair antecipadamente quando não há conflitos possíveis. O resultado foi uma queda dramática no número de comparações desnecessárias.

Impacto:
A complexidade caiu de O(intervalos disponíveis × períodos ocupados) para O(n log n), e a maioria das verificações foi completamente ignorada em casos típicos.

Estudo de caso 2: Interseção de intervalo de datas usando a técnica de dois ponteiros

O problema original

A função intersect anteriormente usava loops aninhados para encontrar sobreposições na disponibilidade de vários usuários.

Implementação original: Mapeamento aninhado O(n²)

commonAvailability.forEach(commonRange => {
  userRanges.forEach(userRange => {
    const intersection = getIntersection(commonRange, userRange);
    if (intersection !== null) {
      intersectedRanges.push(intersection);
    }
  });
});

Implementação otimizada: O(n log n) com travessia de dois ponteiros

const sortedRanges = ranges.map(userRanges =>
  userRanges
    .map(r => ({
      ...r,
      startValue: r.start.valueOf(),
      endValue: r.end.valueOf()
    }))
    .sort((a, b) => a.startValue - b.startValue)
);

let commonIndex = 0;
let userIndex = 0;

while (commonIndex < commonAvailability.length && userIndex < userRanges.length) {
  const commonRange = commonAvailability[commonIndex];
  const userRange = userRanges[userIndex];

  const intersectStartValue = Math.max(commonRange.startValue, userRange.startValue);
  const intersectEndValue = Math.min(commonRange.endValue, userRange.endValue);

  if (intersectStartValue < intersectEndValue) {
    intersectedRanges.push(createIntersection(commonRange, userRange));
  }

  if (commonRange.endValue <= userRange.endValue) {
    commonIndex++;
  } else {
    userIndex++;
  }
}

O que mudou:
Ao ordenar e usar dois ponteiros para percorrer os intervalos, eliminamos a necessidade de iteração aninhada. Isso reduziu a complexidade de quadrática para quase linear na maioria das entradas práticas.

Estudo de caso 3: Árvore de intervalos para filtragem de intervalos redundantes

O problema original

A função filterRedundantDateRanges verificava cada intervalo em relação a outro para ver se um continha o outro. Para grandes cronogramas, isso se tornava dolorosamente lento.

Implementação original: Verificação de contenção O(n²)

return dateRanges.filter((range, index) => {
  return !dateRanges.some((otherRange, otherIndex) => {
    if (index === otherIndex) return false;
    return isCompletelyContained(range, otherRange);
  });
});

Implementação otimizada: O(n log n) com uma árvore de intervalos

export function filterRedundantDateRanges(dateRanges) {
  const sortedRanges = [...dateRanges].sort((a, b) => a.start.valueOf() - b.start.valueOf());
  const intervalNodes = createIntervalNodes(
    sortedRanges,
    (range) => range.start.valueOf(),
    (range) => range.end.valueOf()
  );
  const intervalTree = new IntervalTree(intervalNodes);
  const searchAlgorithm = new ContainmentSearchAlgorithm(intervalTree);

  return sortedRanges.filter((range, index) => {
    const containingIntervals = searchAlgorithm.findContainingIntervals(
      range.start.valueOf(),
      range.end.valueOf(),
      index
    );
    return containingIntervals.length === 0;
  });
}

O que mudou:
Em vez de comparação por força bruta, usamos uma estrutura de árvore de intervalos para permitir consultas rápidas de contenção O(log n). Esta é uma abordagem clássica na geometria computacional que funciona maravilhosamente para aplicativos de agendamento.

Resultados de desempenho: Antes e depois

Nossos benchmarks mostraram melhorias significativas:

• Verificação de conflito de intervalo: Reduzido de O(n²) para O(n log n), tornando 100 intervalos e 50 períodos ocupados cerca de dez vezes mais rápidos.

• Interseção de intervalo de datas: Caiu de O(n²) para O(n log n), permitindo que centenas de intervalos de datas fossem processados em milissegundos.

• Filtragem de intervalos redundantes: Reduzido de O(n²) para O(n log n), com até cinquenta vezes mais velocidade para milhares de intervalos de datas.

• Interseção de intervalo geral: Através de muitos padrões, vimos melhorias de vinte e cinco vezes ou mais.

Técnicas fáceis para detectar algoritmos O(n²)

Reconhecer padrões problemáticos

Fique atento a:

• Iterações aninhadas de arrays, especialmente .map, .forEach, .filter dentro de outra.

• Métodos de array como .some, .find ou .filter em loops ou callbacks de array.

• Filtros encadeados ou mapeamento aninhado em listas grandes.

Teste de escalabilidade explicitamente

Escreva testes de desempenho que executem sua função em dados de tamanho crescente e registre tempos de execução. Se o tempo crescer quadraticamente com o tamanho dos dados, você tem um problema O(n²).

Automatize a análise estática

Adicione regras de lint ou análise estática que:

• Sinalizem funções com loops aninhados ou métodos de arrays aninhados.

• Identifiquem recursão sem memoização.

• Detectem funções com múltiplas chamadas aninhadas de .some, .find ou .filter.

Estratégias comprovadas para substituir código O(n²)

• Use busca binária para consultas em arrays ordenados.

• Use técnicas de dois ponteiros para mesclar ou intersectar sequências ordenadas.

• Use estruturas de dados baseadas em árvore para consultas de intervalos ou dados hierárquicos.

Automatizando verificações de desempenho

Adicione benchmarks de desempenho ao seu pipeline de IC que executem algoritmos críticos em dados realistas. Compare tempos de execução em todas as solicitações de pull e bloqueie mesclagens que causem regressão. Adicione regras de lint personalizadas para evitar que padrões óbvios O(n²) cheguem à produção. Implemente monitoramento em tempo de execução para caminhos críticos para detectar novas regressões antes que os usuários percebam.

Principais lições

• A prevenção é sempre melhor que a cura. Verificações automatizadas capturarão algoritmos O(n²) antes que eles causem problemas.

• Sempre faça perfis antes de otimizar. Use testes para encontrar gargalos reais.

• Escolha as estruturas de dados certas para suas necessidades. Arrays ordenados, abordagens de dois ponteiros e árvores são inestimáveis.

• Teste com dados realistas e em grande escala. Testes pequenos podem esconder grandes problemas.

• Monitore em produção. Alertas automatizados podem capturar regressões cedo.

Conclusão

As otimizações que fizemos no Cal.com mostram que ganhos significativos de desempenho são possíveis aplicando-se técnicas algorítmicas comprovadas. Combine revisão de código, estruturas de dados inteligentes e monitoramento automatizado para manter seu aplicativo rápido à medida que cresce.

O desempenho deve ser incorporado em todas as etapas do desenvolvimento, desde revisões de código que sinalizam padrões suspeitos até pipelines de IC que executam testes de escalabilidade e monitoramento de tempo de execução que detectam regressões.

O algoritmo rápido de hoje pode facilmente se tornar o estrangulamento de amanhã à medida que seus dados crescem. Mantenha-se vigilante, teste em escala e esteja sempre pronto para otimizar.