obter programaticamente Big-O eficiência do código

https://stackoverflow.com/questions/480775

20-08-2019
|

Pergunta

Gostaria de saber se há alguma maneira automática de determinação (pelo menos aproximadamente) o Big-O complexidade de tempo de uma determinada função?

Se I representada graficamente uma função O (n) versus um O (n lg n) função Eu penso que seria capaz de determinar qual é visualmente que; Eu estou pensando que deve haver alguma solução heurística que permite que isso seja feito automaticamente.

Todas as idéias?

Editar:. Estou feliz de encontrar uma solução semi-automatizada, apenas querendo saber se há alguma maneira de evitar fazer uma análise totalmente manual

Solução

Parece que o que você está pedindo é uma extensão do Deter problema. Eu não acredito que tal coisa a é possível, mesmo em teoria.

Apenas respondendo à pergunta "Será que esta linha de código nunca correr?" seria muito difícil, se não impossível de fazer no caso geral.

Editado para adicionar: Embora o processo geral é intratável, ver aqui para uma solução parcial: http: / /research.microsoft.com/apps/pubs/default.aspx?id=104919

Além disso, alguns afirmaram que fazer a análise com a mão é a única opção, mas eu não acredito que é realmente a maneira correta de olhar para ele. Um problema intratável ainda é intratável, mesmo quando um ser humano é adicionada ao sistema / máquina. Após mais reflexão, acho que uma solução de 99% pode ser factível, e pode até trabalhar tão bem ou melhor do que um ser humano.

Outras dicas

Você pode executar o algoritmo sobre vários conjuntos de dados de tamanho, e você pode então usar ajuste de curvas para chegar a uma aproximação. (Basta olhar para a curva você cria provavelmente será suficiente na maioria dos casos, mas qualquer pacote estatístico tem ajuste de curva).

Note que alguns algoritmos exibem uma forma com pequenos conjuntos de dados, mas o outro com grande ... ea definição de grandes continua a ser um pouco nebulosos. Isto significa que um algoritmo com uma curva de desempenho bom poderia ter sobrecarga mundo muito real de que (para pequenos conjuntos de dados) não funciona tão bem como o teoricamente melhor algoritmo.

Quanto inspeção de código técnicas, elas não existem. Mas instrumentar seu código para ser executado em vários comprimentos e produzir um arquivo simples (RunSize RunLength seria suficiente) deve ser fácil. Geração de dados de teste adequadas poderia ser mais complexo (alguns algoritmos funcionam melhor / pior com dados parcialmente ordenados, para que gostaria de gerar dados que representados seu caso de uso normal, ).

Por causa dos problemas com a definição de "o que é grande" e o fato de que o desempenho é dependente dos dados, acho que a análise estática, muitas vezes é enganosa. Ao otimizar o desempenho e selecionando entre dois algoritmos, o mundo real "borracha bate a estrada" teste é a única última árbitro I confiança.

A resposta curta é que é impossível porque as constantes importa .

Por exemplo, eu poderia escrever uma função que é executado em O((n^3/k) + n^2). Isto simplifica a O (n ^ 3), pois como n se aproxima do infinito, o termo n^3 irá dominar a função, independentemente da constante k.

No entanto, se k é muito grande no exemplo função acima, a função será exibida para ser executado em quase exatamente n^2 até algum ponto de cruzamento, em que o termo n^3 vai começar a dominar. Porque o k constante será desconhecido para qualquer ferramenta de análise, será impossível saber quão grande um conjunto de dados para testar a função alvo com. Se k pode ser arbitrariamente grande, você não pode dados de teste ofício para determinar o oh grande-tempo de execução.

Estou curioso para saber por que é que você quer ser capaz de fazer isso. Na minha experiência, quando alguém diz: "Eu quero conhecer a complexidade de tempo de execução deste algoritmo" eles não estão pedindo que eles acham que eles estão pedindo. O que você provavelmente está pedindo é o que é o desempenho realista de tal algoritmo para dados prováveis. Calculando o Big-O de uma função é de utilidade razoável, mas há muitos aspectos que podem mudar o "desempenho de tempo de execução real" de um algoritmo em uso real que nada bate instrumentação e testes.

Por exemplo, os seguintes algoritmos têm exatamente o mesmo Big-O (maluco pseudocódigo):

exemplo a:

huge_two_dimensional_array foo for i = 0, i < foo[i].length, i++ for j = 0; j < foo[j].length, j++ do_something_with foo[i][j]

exemplo b:

huge_two_dimensional_array foo for j = 0, j < foo[j].length, j++ for i = 0; i < foo[i].length, i++ do_something_with foo[i][j]

Mais uma vez, exatamente o mesmo big-O ... mas um deles usa ordinalidade linha e um deles usa ordinalidade coluna. Acontece que, devido à localidade de referência e de coerência de cache que você pode ter dois completamente diferentes tempos de execução reais, especialmente dependendo do tamanho real do foo matriz. Este nem sequer começar a tocar as características de desempenho real de como se comporta algoritmo se parte, é de um pedaço de software que tem alguma concorrência construído em.

Não ser negativo nelly mas big-O é uma ferramenta com um âmbito restrito. É de grande utilidade se você está bem dentro análise algorítmica ou se você está tentando provar algo sobre um algoritmo, mas se você está fazendo desenvolvimento de software comercial a prova está no pudim, e você está indo querer ter números de desempenho real para tomar decisões inteligentes.

Felicidades!

Estou surpreso ao ver tantas tentativas de afirmar que se pode "medir" a complexidade por um cronômetro. Várias pessoas deram a resposta certa, mas acho que ainda há espaço para conduzir o repouso do ponto essencial.

Algoritmo complexidade não é uma questão "programação"; é uma questão "ciência da computação". Respondendo a pergunta requer analisar o código a partir da perspectiva de um matemático, de modo que o cálculo da complexidade Big-O é praticamente uma forma de prova matemática. Ela exige uma forte compreensão do computador operações fundamentais, álgebra, talvez cálculo (limites), e da lógica. Nenhuma quantidade de "ensaios" pode ser substituído por esse processo.

O Deter problema se aplica, portanto, a complexidade de um algoritmo é fundamentalmente undecidable por uma máquina.

Os limites de ferramentas automatizadas aplica , por isso pode ser possível escrever um programa para ajudar, mas ele só seria capaz de ajudar tanto quanto uma calculadora ajuda com sua lição de casa física, ou tanto quanto um navegador refatoração ajuda com a reorganização de uma base de código.

Para qualquer um pensando seriamente em escrever essa ferramenta um, eu sugiro o seguinte exercício. Escolha um algoritmo razoavelmente simples, como o seu tipo favorito, como seu algoritmo assunto. Obter uma referência sólida (livro, tutorial baseado na web) para levá-lo através do processo de cálculo da complexidade algoritmo e, finalmente, o "Big-O". Documentar seus passos e resultados à medida que avança o processo com o seu algoritmo assunto. Execute as etapas e documentar o seu progresso para vários cenários, tais como o melhor caso, pior caso e do caso médio. Assim que estiver pronto, rever a documentação e se perguntar o que seria necessário para escrever um programa (ferramenta) para fazer isso por você. Isso pode ser feito? Qual seria, na verdade, ser automatizado, e quanto ainda estaria manual?

Os melhores cumprimentos.

Esta poderia trabalhar para algoritmos simples, mas que sobre O (n ^ 2 lg n), ou O (n lg ^ 2 n)?

Você poderia se deixe enganar visualmente muito facilmente.

E se a sua realmente uma má algoritmo, talvez ele não iria voltar, mesmo em n = 10.

A prova de que este é indecidível:

Suponha que nós tivemos algum algoritmo HALTS_IN_FN (programa, função) que determinou se um programa interrompido em O (f (n)) para todo n, para alguma função f.

Seja P o seguinte programa:

if(HALTS_IN_FN(P,f(n))) { while(1); } halt;

Uma vez que a função eo programa são fixos, HALTS_IN_FN nesta entrada é tempo constante. Se HALTS_IN_FN retorna true, o programa é executado para sempre e, claro, não parar em O (f (n)) para qualquer f (n). Se HALTS_IN_FN retorna false, as paradas de programa em O (1) tempo.

Assim, temos um paradoxo, uma contradição, e assim que o programa é indecidível.

Eu acho que é praticamente impossível fazer isso automaticamente. Lembre-se que O (g (n)) é o pior caso limite superior e muitas funções executam melhor do que isso para um monte de conjuntos de dados. Você teria que encontrar o conjunto de dados de pior caso para cada um, a fim de compará-los. Essa é uma tarefa difícil por conta própria para muitos algoritmos.

Jeffrey L Whitledge está correto. A simples redução do problema da parada prova que este é indecidível ...

Também, se eu poderia escrever este programa, eu usá-lo para resolver P versus NP, e tem R $ 1 milhão ... B -)

Um monte de pessoas têm comentado que este é um problema inerentemente insolúvel em teoria. bastante justo, mas, além disso, mesmo resolvê-lo para qualquer, mas a maioria dos casos triviais parece ser incrivelmente difícil.

Digamos que você tenha um programa que tem um conjunto de loops aninhados, cada um com base no número de itens em uma matriz. O (n ^ 2). Mas e se o loop interno é executado somente em um conjunto muito específico de circunstâncias? Digamos, em média, ele é executado em aprox log (n) casos. De repente, o nosso "obviamente" O (n ^ 2) algoritmo é realmente O (n log n). Escrever um programa que poderia determinar se o circuito interno seria executado, e quantas vezes, é potencialmente mais difícil do que o problema original.

Lembre-se de O (N) não é Deus; altas constantes pode e vai mudar o campo de jogo. algoritmos quicksort são O (n log n), é claro, mas quando a recursão fica pequeno o suficiente, dizem até 20 itens ou menos, muitas implementações de quicksort vai mudar táticas para um algoritmo separado, pois é realmente mais rápido para fazer um tipo diferente de tipo , dizem tipo de inserção com pior O (N), mas constante muito menor.

palpites Assim, compreender os seus dados, verifique educadas e teste.

Bem, desde que você não pode provar ou não a funcionar mesmo paradas, acho que você está pedindo um pouco demais.

Caso contrário @Godeke tem.

Você também deve tomar cuidado ao executar tais benchmarks. Alguns algoritmos terá um comportamento fortemente dependente do tipo de entrada.

Tome Quicksort por exemplo. É o pior caso de O (N²), mas normalmente de O (nlogn). Para duas entradas do mesmo tamanho.

O caixeiro-viajante é (eu penso, não tenho certeza) O (n²) ( EDIT: o valor correto é 0 (n) para a força bruta algotithm ), mas a maioria dos algoritmos ficar bastante bom aproximada soluções muito mais rápido.

Isto significa que a estrutura de benchmarking tem a maior parte do tempo ser adaptado em uma base ad hoc. Imagine escrever algo genérico para os dois exemplos mencionados. Seria muito complexo, provavelmente inutilizáveis, e provavelmente vai estar dando resultados incorretos de qualquer maneira.

Eu acho que isso não é possível de uma forma totalmente automática, pois o tipo ea estrutura da entrada difere muito entre as funções.

Eu não sei qual é o seu objetivo ao fazer isso, mas tivemos um problema semelhante em um curso que eu estava de ensino. Os alunos foram obrigados a implementar algo que funciona a uma certa complexidade.

Para não passar por cima de sua solução manualmente, e ler o seu código, foi utilizado o método @Godeke sugeriu. O objetivo era encontrar alunos que utilizaram lista ligada em vez de uma árvore de busca balansed, ou estudantes que implementaram bubble sort em vez de pilha tipo (ou seja, implementações que não funcionam na complexidade exigida - mas sem realmente ler o seu código)
Surpreendentemente, os resultados não revelam os alunos que enganado. Isso pode ser porque os nossos alunos são honestos e querem aprender (ou apenas sabia que vamos verificar isso ;-)). É possível perder estudantes batota se as entradas são pequenos, ou se o próprio entrada é ordenada ou tal. Também é possível estar errado sobre os alunos que não enganam, mas têm grandes valores constantes.

Mas, apesar dos possíveis erros, é bem a pena, uma vez que poupa muito tempo verificando.

Como já foi dito, este é teoricamente impossível. Mas, na prática, você pode fazer um palpite sobre se a função é O ( n ) ou O ( n ^ 2), desde que você não se importa estar errado às vezes.

primeira vez que o algoritmo, executá-lo na entrada de vários n . Traçar os pontos em um log-log graph . Traçar a linha de melhor ajuste através dos pontos. Se a linha se encaixa todos os pontos bem, em seguida, os dados sugerem que o algoritmo é O ( n ^ k ), onde k é a inclinação da linha.

Eu não sou um estatístico. Você deve levar tudo isso com um grão de sal. Mas eu realmente fizeram isso no contexto de testes automatizados para regressões de desempenho. O patch aqui contém algum código JS para isso.

Eu estou usando uma biblioteca big_O ( link aqui ) que se encaixa a mudança no tempo de execução contra n variável independente para inferir a ordem de O() classe crescimento.

O pacote sugere automaticamente a melhor classe encaixe através da medição do resíduo a partir de dados recolhidos contra cada um comportamento de crescimento classe.

Verifique o código em esta resposta .

Exemplo de saída,

Measuring .columns[::-1] complexity against rapid increase in # rows -------------------------------------------------------------------------------- Big O() fits: Cubic: time = -0.017 + 0.00067*n^3 -------------------------------------------------------------------------------- Constant: time = 0.032 (res: 0.021) Linear: time = -0.051 + 0.024*n (res: 0.011) Quadratic: time = -0.026 + 0.0038*n^2 (res: 0.0077) Cubic: time = -0.017 + 0.00067*n^3 (res: 0.0052) Polynomial: time = -6.3 * x^1.5 (res: 6) Logarithmic: time = -0.026 + 0.053*log(n) (res: 0.015) Linearithmic: time = -0.024 + 0.012*n*log(n) (res: 0.0094) Exponential: time = -7 * 0.66^n (res: 3.6) --------------------------------------------------------------------------------

Se você tem um monte de recursos computacionais homogêneos, eu lhes tempo contra várias amostras e fazer a regressão linear, em seguida, basta levar o maior prazo.

É fácil obter uma indicação (por exemplo, "é a função linear? Sub-linear? Polinomial? Exponencial")

É difícil encontrar a complexidade exato.

Por exemplo, aqui está uma solução Python: você fornecer a função e uma função que cria parâmetros de tamanho N para ele. Você recebe de volta uma lista de valores (n, tempo) a trama, ou para realizar análise de regressão . It vezes uma vez para a velocidade, para obter uma realmente boa indicação de que teria de tempo que muitas vezes para minimizar a interferência de fatores ambientais (por exemplo, com o timeit módulo).

import time def measure_run_time(func, args): start = time.time() func(*args) return time.time() - start def plot_times(func, generate_args, plot_sequence): return [ (n, measure_run_time(func, generate_args(n+1))) for n in plot_sequence ]

E usá-lo para o tempo bubble sort:

def bubble_sort(l): for i in xrange(len(l)-1): for j in xrange(len(l)-1-i): if l[i+1] < l[i]: l[i],l[i+1] = l[i+1],l[i] import random def gen_args_for_sort(list_length): result = range(list_length) # list of 0..N-1 random.shuffle(result) # randomize order # should return a tuple of arguments return (result,) # timing for N = 1000, 2000, ..., 5000 times = plot_times(bubble_sort, gen_args_for_sort, xrange(1000,6000,1000)) import pprint pprint.pprint(times)

Este impresso na minha máquina:

[(1000, 0.078000068664550781), (2000, 0.34400010108947754), (3000, 0.7649998664855957), (4000, 1.3440001010894775), (5000, 2.1410000324249268)]

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow