Como você chama isso quando altera o tempo de execução do Big O de uma função [fechado]

19

Digamos que eu tenho uma função que classifica um banco de dados no O(n^2)tempo. Quero refatorá-lo para que ele funcione a O(n log(n))tempo e, ao fazer isso, mudarei a maneira fundamental como a operação é executada, mantendo os valores de retorno e as entradas equivalentes.

Como chamo essa atividade de refatoração?

"Acelerar-se-ifying" não parece muito certo, pois você pode fazer um algoritmo ir mais rápido sem alterar a grande velocidade O na qual foi executado.

"Simplificar" também não parece certo.

Como chamo essa atividade?

Atualizar

A melhor resposta que encontrei é reduzir a complexidade do tempo assintótico.

Code Whisperer
fonte
Espera-se que os algoritmos sejam mais rápidos na maioria dos casos de uso após a modificação? Para observar, às vezes é bom mudar para uma classe de complexidade com melhor escala, mesmo com um desempenho médio esperado, apenas para obter um comportamento de desempenho mais consistente.
Nat
22
Esta não é a refatoração
theonlygusti
6
A rigor, a função que corre no O(log(n))tempo também corre no O(n^2)tempo. O significado de O(n^2)é "não cresce mais rápido que o quadrático". Você provavelmente quis dizer Theta (log (n)), que significa "cresce tão rápido quanto log(n)". en.wikipedia.org/wiki/…
Džuris
4
<pedantic> você não alterou o grande tempo de execução de uma função. uma função é um relacionamento entre um domínio e um codomain e existe independentemente de suas tentativas humanas insignificantes de implementação. em vez disso, você encontrou um algoritmo com melhor desempenho que implementa a função </pedantic> <human> bom trabalho </human>
emory
5
@theonlygusti: Depende. Se a função anteriormente fez uma garantia / complexidades, não é refatoração. Se não garantiu nada, é refatoração. Se foi explícito sobre não dar garantias, é especialmente uma refatoração.
Phresnel

Respostas:

44

Geralmente é chamado de "otimização de desempenho" , mas eu não chamaria de "refatoração", pois esse termo geralmente se refere a alterações no código que não alteram seu comportamento visível . E uma mudança no Big-O é definitivamente algo que eu chamaria de mudança visível.

ao fazer isso, vou mudar a maneira fundamental como a operação é executada

Nesse caso, sua otimização é uma reescrita dessa função. Nem toda otimização, mesmo que mude "Big-O", seja necessariamente uma reescrita, às vezes apenas pequenas alterações são necessárias para obter essa melhoria, mas mesmo assim, reluto em usar o termo "refatoração" para isso, porque tende a dar uma impressão errada sobre a natureza da mudança.

Edição: Eu chequei a lista de refatoração de Fowler e, dentre essas ~ 100 refatorações nomeadas, a última é chamada "Algoritmo Substituto" . Portanto, se tomarmos isso como referência canônica, há uma pequena área cinza onde uma otimização da forma descrita pode ser chamada de um tipo especial de refatoração (mas o IMHO não é o típico). Observe também que o objetivo de Fowler com todas as refatorações era sempre melhorar o design, com foco na capacidade de manutenção e evolução do código existente sem reescrevê-lo e claramente não na otimização do desempenho.

Doc Brown
fonte
10
verdade? Eu acho que a refatoração está correta, a menos que os requisitos mudem. Então .. Não, se a função for chamada BubbleSort, mas sim, se for apenas Sort
Ewan
3
@Ewan Sim, legalmente uma refatoração pode ser uma otimização de desempenho, mas a primeira é muito geral e não captura adequadamente o impacto das alterações.
Deduplicator
1
Eu estava em uma apresentação inicial do cara que inventou e cunhou a refatoração (Fowler?) E toda a idéia estava conectada à programação automática e a melhorias verificáveis ​​e comprováveis ​​no código que não tinham efeito na entrada versus na saída.
Sentinel
1
@Steve. Acordado. Eu estava apenas acrescentando ao consenso que melhorias no Big O representam melhorias algorítmicas, não melhorias na forma como esses algoritmos são representados ou mantidos. Em outras palavras, a atividade é uma reescrita
Sentinel
1
@ Steve: sim, eu sabia disso, pensei em adicionar uma nota à minha resposta. Minha edição foi apenas uma observação para deixar claro que há uma pequena área cinza.
Doc Brown
13

Eu não acho que exista um termo padrão, um comumente usado para otimizar, embora melhore , ou acelerar também seria correto, esclarecendo que você está falando sobre alterações de código e não sobre alterações de hardware.

ichantz
fonte
7

Como outros já disseram, "otimizar" é o termo geral para melhorar o desempenho de um algoritmo. No entanto, otimizar muitas vezes significa melhorar fatores constantes. Se eu quisesse, de maneira concisa, mas clara, reduzir a complexidade assintótica (tempo), diria que "melhorei o desempenho assintótico". Às vezes, as pessoas descrevem isso como "melhorando a escala", mas isso é especialmente ambíguo hoje em dia.

Aviso : Reduzir a complexidade do tempo assintótico não é necessariamente o mesmo que otimizar em um contexto prático . Muitas vezes, algoritmos assintoticamente não ótimos são usados ​​porque, no intervalo de entradas, o programa é realmente exposto a algoritmos menos ótimos, com melhor desempenho.

Derek Elkins deixou o SE
fonte
5

Depende do contexto.

"Corrigindo um erro de desempenho quadrático em tempo de execução" é normalmente o que eu vejo. No entanto, se isso merece correção (uma alteração de código) depende do contexto.

Lembre-se de que os bancos de dados fornecem muitas ferramentas para melhorar a complexidade do tempo. Por exemplo, para obter os N principais resultados de um banco de dados, basta dizer. Ao converter kludge ineficiente em chamada otimizada integrada, a explicação parece supérflua.

O motivo pelo qual considero que um algoritmo com tempo de execução quadrático merece uma revisão de código (discussão) não é tanto porque é lento (lento é relativo; quadrático é rápido quando comparado com exponencial), mas porque a intuição humana (como seus clientes ou colegas programadores) são naturalmente desconfortáveis ​​com uma funcionalidade de software que se afasta muito do tempo de execução linear, devido à mistura de expectativas da vida cotidiana.

Muitas reclamações de clientes sobre desempenho de software se enquadram nessas duas categorias:

  • Todo o sistema (software e hardware) foi especificado com base no uso estimado. Na semana passada, tudo corre bem, uma certa funcionalidade levou menos de 5 segundos. Nesta semana, após a instalação de uma atualização, a mesma funcionalidade leva mais de 1 minuto.

    • Esta é uma comparação com um desempenho previamente comparado. O cliente mantém o desempenho futuro em uma escala absoluta de escala humana (de segundos a minutos).
  • Enviei 100 trabalhos para o sistema. Por que está demorando 400 vezes o tempo de processamento, em comparação com o tempo necessário para um único trabalho?

    • O cliente espera que o tempo de processamento seja linear. De fato, o cliente não pode entender ou aceitar a existência de tarefas mais lentas que lineares.

Por esse motivo, um cliente considerará o tempo de execução um erro se ambos forem verdadeiros:

  • Mais lento que linear
  • Perceptível (isto é, está dentro do intervalo de tempo humano (mais que segundos ou minutos), considerando os tamanhos de tarefas típicos)

Argumentos legítimos que explicam que um algoritmo de tempo de execução quadrático não representa um problema (isto é, não merece uma alteração de código):

  • O tamanho da tarefa geralmente tratada por essa função de tempo de execução quadrático é um pouco limitado
  • Dada a faixa de tamanho típico, o tempo de execução real (absoluto) ainda é pequeno o suficiente para ser descartado
  • Se um usuário realmente tentar enviar uma tarefa que seja grande o suficiente para ser perceptível, ele receberá uma mensagem avisando sobre o longo tempo de execução
  • Os usuários do sistema são todos especialistas, portanto, eles sabem o que estão fazendo. Por exemplo, os usuários de uma API devem ter lido as letras pequenas na documentação da API.

Muitos algoritmos úteis para o desenvolvimento típico de aplicativos são, de fato, mais lentos que lineares (principalmente O (N log N), como na classificação), portanto, softwares em larga escala tentarão solucionar isso, classificando apenas a parte relevante do dados ou use técnicas de filtragem de histograma (estatística) que obtêm efeito semelhante.

Isso se aplica aos clientes de software, mas se você considerar que os usuários de uma biblioteca de software ou função de API também são "clientes", a resposta ainda será aplicada.

rwong
fonte
2

Se o algoritmo original foi implementado corretamente (ou se algum erro for irrelevante), "altere o algoritmo" ou "substitua o algoritmo" , pois essas alterações significam que você está fazendo exatamente isso; substituindo um algoritmo com complexidade de tempo diferente pelo usado anteriormente.

Se a complexidade do tempo anterior foi devido a um erro na implementação (por exemplo, digamos que você estava redefinindo acidentalmente o ponto inicial de um loop interno em uma sequência para que o que deveria ter sido O (n) se tornasse O (n 2 )), então "corrigindo um erro de custo quadrático " ou similar.

Há uma sobreposição, nesse caso, o efeito no código é o mesmo se você souber desde o início que o trabalho poderia ser feito em O (n) tempo e O (n 2 ) era um erro, ou se você o implementou deliberadamente em O (n 2 ) e depois percebeu que ainda funcionaria corretamente sem redefinir o ponto de partida e, portanto, substituiu um algoritmo de O (n) por um de O (n 2 ).

Jon Hanna
fonte
1

Otimização de velocidade por ordem / magnitude. Embora essa linguagem seja matematicamente incorreta, ela transmite melhor a ideia de que a Ordem está sendo alterada.

Melhorou a escalabilidade. ouvi também.

Joop Eggen
fonte