Qual é o significado da regra 90/10 da otimização de programas?

67

De acordo com a Wikipedia, a regra 90/10 da otimização de programas afirma que “90% do tempo de execução de um programa é gasto na execução de 10% do código” (veja o segundo parágrafo aqui ).

Eu realmente não entendo isso. O que exatamente isso significa? Como é que 90% do tempo de execução pode ser gasto executando apenas 10% do código? E os outros 90% do código então? Como eles podem ser executados em apenas 10% do tempo?

    
por Rakshith Ravi 25.10.2016 / 10:09
fonte

9 respostas

184

Existem dois princípios básicos em jogo aqui:

  • Algum código é executado com muito mais freqüência do que outro código. Por exemplo, algum código de tratamento de erros pode nunca ser usado. Algum código será executado somente quando você iniciar seu programa. Outro código será executado repetidamente enquanto seu programa é executado.
  • Algum código leva muito mais tempo para ser executado do que outro código. Por exemplo, uma única linha que executa uma consulta em um banco de dados ou extrai um arquivo da Internet provavelmente levará mais tempo de milhões de operações matemáticas.

A regra 90/10 não é literalmente verdadeira. Varia de acordo com o programa (e eu duvido que exista alguma base para os números específicos 90 e 10; alguém provavelmente os tirou do nada). Mas o ponto é, se você precisa que seu programa seja executado mais rapidamente, provavelmente apenas um pequeno número de linhas é significativo para que isso aconteça. Identificar as partes lentas do seu software geralmente é a maior parte da otimização.

Esse é um insight importante, e isso significa que decisões que parecem contra-intuitivas para um novo desenvolvedor podem estar corretas. Por exemplo:

  • Existe um monte de código que não vale a pena fazer "melhor" , mesmo que esteja fazendo as coisas de maneira simplista e simplista. Você poderia escrever um algoritmo de busca mais eficiente para o aplicativo XYZ? Sim, mas, na verdade, uma comparação simples de cada valor leva uma quantidade de tempo trivial, apesar de existirem milhares de valores. Então não vale a pena. Pode ser difícil para os novos desenvolvedores evitar a otimização desnecessária, pois em seu programa de graduação gastaram muito tempo escrevendo o algoritmo "correto" (ou seja, mais eficiente). Mas no mundo real, o algoritmo correto é qualquer um que funcione e seja executado com rapidez suficiente.
  • Alterações que tornam seu código muito mais longo e complexo ainda podem ser um ganho de desempenho. Por exemplo, no aplicativo FOO pode valer a pena adicionar centenas de linhas de nova lógica, apenas para evitar uma única chamada de banco de dados.
por 25.10.2016 / 10:31
fonte
21

Esta não é uma lei da natureza, mas uma regra de ouro nascida por larga experiência. Também é conhecida como regra 80/20 e é apenas uma aproximação aproximada.

Loops, branches e outro controle de fluxo.

Em cada lugar que tiver um if, você terá uma ramificação que é obtida com mais frequência do que a outra ramificação. Assim, mais tempo de execução é gasto executando essa parte do programa, e não a outra parte.

Cada lugar que tem um loop que é executado mais de uma vez, você tem código que é executado mais do que o código circundante. Assim, mais tempo é gasto lá.

Como exemplo, considere:

def DoSomeWork():
    for i in range(1000000):
        DoWork(i)
    except WorkExeption:
        print("Oh No!")

Aqui, o print("Oh No!") será executado apenas no máximo uma vez e, muitas vezes, nunca, enquanto o DoWork(i) ocorrerá cerca de um milhão de vezes.

    
por 25.10.2016 / 10:33
fonte
16

Loops.

Estou tentado a parar por aí! : -)

Considere este programa

1. do_something

2. loop 10 times
3.    do_another_thing

4.    loop 5 times
5.        do_more_stuff

A linha 1 é executada uma vez enquanto a linha 3 é executada 10 vezes. Olhando para cada linha, por sua vez

1 1   0.8%
2 10  8.3%
3 10  8.3%
4 50 41.3%
5 50 41.3%

Duas linhas representam 83% do tempo de execução (supondo que todas as linhas demorem aproximadamente o mesmo tempo para serem executadas. Portanto, 40% do programa leva > 80%.

Com exemplos maiores do mundo real, isso aumenta, então apenas uma pequena quantidade de linhas é responsável por grande parte do tempo de execução.

A regra 90/10 (ou como às vezes é colocada 80/20) é uma "regra prática" - apenas aproximadamente verdadeira.

Veja também Princípio de Pareto

    
por 25.10.2016 / 10:57
fonte
5

Como você perguntou sobre o tempo de execução apenas, este exemplo pode ser útil:

int main() {
    sleep(90); // approximately 10% of the program.
    // other 90% of the program:
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    sleep(1);
    return 0;
}

Se para ser um pouco mais sério, significa que no código real você quase sempre chama uma função pesada em um loop (em vez de sleep(90); ), enquanto o restante 10% do tempo você executa um single-pass cálculos.

Outro exemplo é o tratamento de erros em algum serviço de alta disponibilidade. Qualquer serviço altamente disponível é projetado para funcionar em um tempo infinito em condições normais. Ele opera normalmente 99% do tempo, mas ocasionalmente, em caso de erro, ele executa algum tratamento e recuperação de erros, o que pode ser ainda mais logicamente complexo que o próprio serviço.

    
por 25.10.2016 / 10:25
fonte
3

O raciocínio de 90/10 significa que uma pequena parte de seu código será repetida ou usada mais que outras. Isso costuma ser usado para sugerir que você deve concentrar 90% do seu esforço de desenvolvimento / otimização nesse 10% de seu código.

Pense em um processador de texto normal, como Microsoft Word ou OpenOffice :

  • A caixa de diálogo de preferências não é muito usada;
  • As sub-rotinas que desenham os caracteres são usadas o tempo todo.

Esse ditado também é usado em ciências da administração ... Esta é uma lição para a vida em si ... Significado: concentre a maior parte de seus esforços onde você obtém mais resultados.

    
por 25.10.2016 / 16:10
fonte
2

Imagine um programa como este:

print "H"
print "e"
print "l"
print "l"
print "o"
for i=0 to 1,000,000
    print "How long now?"
next
print "B"
print "y"
print "e"

Observe como há 11 linhas aqui, onde 3 das 11 são o loop for, em quanto tempo é gasto com esse pequeno código? Um pouco enquanto as outras 8 linhas estão imprimindo apenas um único caractere. Assim, tenha em atenção que, embora alguns códigos possam ser curtos, isso não lhe diz com que frequência é executado e quanto tempo demora.

    
por 25.10.2016 / 10:30
fonte
0

Além do looping, como mencionado por outras ótimas respostas, há também os princípios do DRY a serem considerados. Bem escrito, o código Orientado a Objetos possui muitas partes reutilizáveis. Essas partes que são reutilizadas, por definição, são usadas pelo menos duas vezes mais do que algo que é executado apenas uma vez. Se você tem muito código OO, você pode estar reutilizando algumas classes e métodos várias vezes, e alguns outros códigos de código apenas uma vez.

Como mencionado em outras respostas, provavelmente é melhor gastar esforço para tornar o código que é usado com mais frequência melhor do que melhorar o código que é usado apenas uma única vez.

    
por 25.10.2016 / 18:11
fonte
0

Isso não é uma regra, é apenas um cara que editou a Wikipedia com alguns números tirados do nada e chamou isso de regra. Compare com o Princípio de Pareto, que é mais firmemente estabelecido em outros contextos. Eu gostaria de ver que pesquisa foi feita (se houver) sobre a precisão dessa "regra".

Mas, basicamente, a resposta à sua pergunta é que algum código é executado com muito mais frequência do que outro código. Loops são muitas vezes a razão para isso. Outras razões são chamadas demoradas, por ex. para recursos externos, como serviços da Web ou mídia de armazenamento.

    
por 26.10.2016 / 20:59
fonte
0

É uma reinterpretação do "princípio de Pareto", que afirma que "para muitos eventos, cerca de 80% dos efeitos provêm de 20% das causas", também conhecida como regra 80/20. Essa regra é aplicada principalmente à economia, por isso faz sentido que ela seja proposta para programação.

É apenas um padrão que foi observado durante um longo período de tempo.

Aqui está um vídeo muito bom sobre padrões como esse, e também explica o Princípio de Pareto.

link

    
por 29.10.2016 / 06:52
fonte