Análise de complexidade de algoritmos em implementações funcionais de linguagens de programação

Aprendi hoje que a análise de algoritmos difere com base no modelo computacional. É algo em que nunca pensei ou ouvi falar.

Um exemplo dado a mim, que o ilustrou ainda mais, pelo usuário @chi foi:

Por exemplo, considere a tarefa: dado retorne . Na RAM, isso pode ser resolvido em pois o acesso ao array é de tempo constante. Usando TMs, precisamos varrer toda a entrada, para que seja $(i,x_1 ,…,x_n )$ $x_i$ $O(1)$ $O(n)$

Isso me faz pensar sobre linguagens funcionais; Pelo meu entendimento, "linguagens funcionais estão intimamente relacionadas ao cálculo lambda" (de um comentário de Yuval Filmus aqui ). Portanto, se as linguagens funcionais são baseadas no cálculo lambda, mas são executadas em máquinas baseadas em RAM, qual é a maneira correta de realizar análises de complexidade em algoritmos implementados usando estruturas e linguagens de dados puramente funcionais?

Não tive a oportunidade de ler Estruturas de dados puramente funcionais, mas examinei a página da Wikipedia sobre o assunto e parece que algumas estruturas de dados substituem as matrizes tradicionais por:

"Matrizes podem ser substituídas por mapa ou lista de acesso aleatório, que admite implementação puramente funcional, mas o tempo de acesso e atualização é logarítmico."

Nesse caso, o modelo computacional seria diferente, correto?

complexity-theory algorithm-analysis computability computation-models lambda-calculus Abdul
fonte

Definitivamente, não sou especialista neste tópico, mas acredito que ouvi dizer que 1) uma máquina do tipo lisp (com seu próprio modelo de custo) pode simular programas de RAM com um fator adicional (parece fácil de provar ) e 2) se esse fator é realmente necessário ainda é um problema em aberto. Além disso, pode-se argumentar que atribuir um custo O (1) ao acesso à matriz no modelo de RAM é muito generoso. No hardware, o acesso à memória precisa atravessar portas onde é o tamanho da memória física.

O (\log n)

$O(\log n)$

O (\log n)

$O(\log n)$

n

$n$

chi

Lembre-se também de que praticamente todas as linguagens FP do mundo real têm matrizes de alguma forma, com um tempo de acesso garantido (como nas linguagens imperativas). Isso geralmente é resolvido adicionando-os como um idioma primitivo.

O (1)

$O(1)$

chi

Um exemplo de um modelo computacional diferente seria o número de reduções beta feitas em um termo de cálculo lambda. Em FP estamos mais assim usando um modelo de carneiro vestido como um cálculo lambda, se isso faz sentido

Kurt Mueller

@KurtMueller Observe que podemos obter um termo lambda de tamanho após apenas reduções de bete. Isso torna o modelo de custo da contagem do número de beta irrealista. Um indiscutivelmente melhor seria pesar cada passo pelo tamanho dos termos em questão. No entanto, este não é o único modelo possível: a avaliação ideal dos termos lambda não aplica o beta de maneira ingênua, preferindo algumas máquinas de redução de gráficos mais sofisticadas. Nesse caso, contar os betas provavelmente não seria apropriado.

O (2^{n})

$O(2^n)$

O (n)

$O(n)$

chi

Observe que você também precisa saber se sua linguagem funcional é ansiosa ou preguiçosa / estrita ou não estrita. Recentemente, encontrei uma situação em que um algoritmo do mundo real era polinomial em Haskell (não estrito), mas a tradução ingênua para OCaml (estrito) era exponencial.

Eric Lippert

Respostas:

Depende da semântica da sua linguagem funcional. Você não pode fazer análise de algoritmo em linguagens de programação isoladamente, porque não sabe o que as declarações realmente significam. A especificação para o seu idioma precisa fornecer semântica suficientemente detalhada. Se o seu idioma especificar tudo em termos de cálculo lambda, você precisará de alguma medida de custo para reduções (eles são O (1) ou dependem do tamanho do termo que você reduz?).

Eu acho que a maioria das linguagens funcionais não faz dessa maneira e, em vez disso, fornece instruções mais úteis como "chamadas de função são O (1), acrescentadas ao cabeçalho de uma lista é O (1)", coisas assim.

adrianN
fonte

Acredito que meio que entendi sua resposta (o mal-entendido é provavelmente devido à minha falta de compreensão no cálculo lambda): Você está dizendo que basicamente precisa fazer a análise caso a caso (caso sendo linguagem), em vez de uma maneira geral, porque certas operações têm significados diferentes por idioma. Meu entendimento está correto?

Abdul

Sim. O designer da linguagem precisa dizer o que realmente significa o que você pode escrever na linguagem antes de poder analisar o tempo de execução de um algoritmo.

adriann

"Você não pode fazer análise de algoritmo em linguagens de programação isoladamente" - isso se referia a linguagens ou linguagens FP em geral? Se estava se referindo ao anterior, então como fazemos a análise de algoritmos na escola de maneira tão geral, ou seja, analisamos problemas em Java, C / C ++, Python? É porque eles são todos muito parecidos? Ou é porque as estruturas de dados subjacentes e os ADTs são todos iguais e implementados da mesma maneira também? Ou, finalmente, é porque esses cursos são simplesmente para fins educacionais e não precisam ser estritamente precisos?

Abdul

É verdade para todas as linguagens de programação. Para ser estritamente correto, você primeiro precisa consertar o modelo de uma máquina, digamos a RAM e (algumas poucas) instruções que ele suporta. Você só pode fazer análises em programas usando apenas essas instruções. Então você pode pensar em um mapeamento da sua linguagem de programação para esse modelo de máquina. Então você pode analisar os programas na linguagem de programação. Para um tratamento muito rigoroso, verifique como Knuth faz isso em The Art of Computer Programming. Muito disso pode ser simplificado devido às constantes ocultas de grande O.

adriann