A mágica do LIS (Longest Increasing Subsequence) - Como o framework “descobre” o que pode reaproveitar

Imagine que você tem uma lista de elementos na tela, por exemplo, uma lista de amigos, produtos ou tarefas.

Você muda a ordem desses itens, e... o navegador atualiza tudo em milissegundos.
Mas já se perguntou como o framework sabe o que realmente mudou?

💡 É aí que entra o algoritmo de diffing, e dentro dele, uma joia da computação chamada LIS (Longest Increasing Subsequence).

O contexto: o que o framework precisa resolver

Toda vez que o estado muda, o React/Vue precisa:

1. Gerar uma nova versão da sua interface (Virtual DOM).

2. Comparar com a versão anterior.

3. Descobrir o que mudou.

4. Atualizar somente o necessário no DOM real.

Mas quando há listas (como <ul><li>...</li></ul>), o problema fica difícil.

Exemplo simples

Antes:

<ul>
  <li>Amanda</li>
  <li>Lucas</li>
  <li>João</li>
</ul>

Depois:

<ul>
  <li>Lucas</li>
  <li>Amanda</li>
  <li>João</li>
</ul>

👀 Só trocamos “Amanda” e “Lucas”, certo?

Mas sem uma análise inteligente, o framework pode pensar:

“Tudo mudou! Vou destruir e recriar toda a lista!”

Isso desperdiça recursos e deixa o app lento.

O desafio técnico

Comparar duas árvores completas (o DOM antigo e o novo) pode ser uma operação de complexidade O(n³), ou seja, absurdamente lenta.

Mas frameworks modernos não fazem isso. Eles usam heurísticas (regras práticas que funcionam bem na maioria dos casos). Uma dessas heurísticas é baseada na LIS.

O que é a LIS (Longest Increasing Subsequence)

A LIS (Maior Subsequência Crescente) é um conceito clássico em algoritmos.

👉 Dado um conjunto de números, ela encontra a maior sequência que já está em ordem.

Por exemplo:

Array: [3, 1, 2, 5, 4]
LIS:   [1, 2, 4]  (tamanho 3)

Esses números já estão na ordem crescente, não precisam ser movidos!!

💡 Em termos do Virtual DOM:

A LIS mostra quais elementos da lista ainda estão na posição correta e podem ser reaproveitados.

Aplicando isso ao Virtual DOM

Quando o React/Vue compara listas, ele faz algo assim:

Situação inicial

Antes:  [A, B, C, D]
Depois: [B, C, A, D]

O framework cria um mapa de posições antigas:

Elemento	Posição antiga
B	1
C	2
A	0
D	3

Agora temos a sequência: [1, 2, 0, 3]

E a LIS é [1, 2, 3] → que representa [B, C, D].

💡 Interpretação:

Esses três elementos ainda estão na ordem correta. Só o A precisa ser movido.

Visualizando o passo a passo

Imagine que o DOM é uma estante:

ANTES:
1️⃣ A
2️⃣ B
3️⃣ C
4️⃣ D

Queremos reorganizar pra:

DEPOIS:
1️⃣ B
2️⃣ C
3️⃣ A
4️⃣ D

🔹 O algoritmo comum (sem LIS) tiraria todos os livros e recolocaria um por um.
🔹 O algoritmo com LIS pensa:

“B, C e D já estão certos, só preciso mover o A pra frente.”

✨ Resultado: 1 movimento, em vez de 4.

O impacto prático: desempenho real

O uso da LIS reduz a complexidade de reordenação de:

• 🐌 O(n²) (comparando tudo com tudo)

• ⚡ para O(n log n) (graças à LIS)

Isso faz uma diferença brutal em listas grandes como grids de produtos, chats, dashboards em tempo real, etc.

💬 Sem LIS, reordenar 1000 itens pode travar.
💪 Com LIS, roda em milissegundos.

Códigosimplificado

O núcleo do algoritmo (simplificado):

function diff(oldList, newList) {
  // Mapeia posição antiga de cada elemento
  const oldPos = new Map()
  oldList.forEach((item, i) => oldPos.set(item, i))

  // Transforma a nova lista em índices antigos
  const newOrder = newList.map(item => oldPos.get(item))

  // Calcula a LIS
  const lis = findLIS(newOrder)

  // Move apenas quem não está na LIS
  for (let i = 0; i < newList.length; i++) {
    if (!lis.includes(newOrder[i])) {
      moveNode(newList[i])
    }
  }
}

A função findLIS() é o cérebro, e ela é um clássico em ciência da computação (base de vários algoritmos em sorting, compressão e rendering).

Como o LIS é calculado

O algoritmo da LIS usa uma técnica chamada Binary Search (busca binária) pra montar a subsequência crescente o mais rápido possível.

Ele percorre o array uma vez, guardando os “candidatos” a subsequência e trocando conforme encontra números menores.

Essa técnica dá a ele uma complexidade de O(n log n), o mesmo desempenho de um algoritmo de ordenação eficiente.

Como testar e ver isso na prática

Quer ver a LIS trabalhando no seu próprio código?

Passo 1: crie um componente React simples

function Lista() {
  const [lista, setLista] = useState(['A', 'B', 'C', 'D'])

  function embaralhar() {
    setLista([...lista].sort(() => Math.random() - 0.5))
  }

  return (
    <>
      <button onClick={embaralhar}>Embaralhar</button>
      <ul>
        {lista.map((item, i) => (
          <li key={i}>{item}</li>
        ))}
      </ul>
    </>
  )
}

Agora reordene várias vezes e observe no DevTools → Elements:

• Cada <li> é destruído e recriado 😬

Passo 2: troque a key

<li key={item}>{item}</li>

Agora reordene de novo.
Note que os <li> são reaproveitados, só mudam de posição.
Tudo fica instantâneo e o DOM quase não muda. ⚡

💡 Isso é a LIS e o diffing trabalhando juntos!

Casos reais onde a LIS brilha

🏷️ Catálogo de produtos (e-commerce)

Quando o usuário filtra ou reordena produtos, a LIS garante que só os produtos realmente removidos/alterados sejam atualizados.

💬 Chat em tempo real

Mensagens novas aparecem sem “piscar” as antigas, porque os nós antigos são reaproveitados com base nas keys.

📈 Dashboards de dados

Gráficos e tabelas dinâmicas são atualizados em tempo real sem re-renderizar toda a estrutura.

Comparação visual: sem LIS vs com LIS

Situação	O que o framework faz	Custo	Resultado
Sem LIS	Recria todos os elementos	🐌 Lento (O(n²))	Pisca, perde estado
Com LIS	Move só os elementos fora da sequência	⚡ Rápido (O(n log n))	Suave, estável

Em resumo

Conceito	Explicação simples
Virtual DOM	Representação em memória da interface
Diffing	Comparar versões antiga e nova
Key	Identidade única de cada nó
LIS	Descobre o que já está “no lugar certo”
Patch	Aplica as mudanças no DOM real
Resultado final	Atualização mínima e ultra rápida ⚡

Conclusão

O algoritmo de diffing com LIS é o que permite que frameworks como React e Vue sejam tão rápidos e eficientes, mesmo com milhares de elementos sendo atualizados por segundo.

É uma mistura perfeita de:

• 🧠 teoria de algoritmos clássicos,

• ⚙️ engenharia de performance,

• 💡 e design de software elegante.

Sem ele, a web moderna simplesmente travaria.