Eficiência da programação puramente funcional

397

Alguém sabe qual é a pior desaceleração assintótica possível que pode acontecer durante a programação puramente funcional em oposição a imperativamente (isto é, permitindo efeitos colaterais)?

Esclarecimento do comentário de itowlson : existe algum problema para o qual o algoritmo não destrutivo mais conhecido seja assintoticamente pior que o algoritmo destrutivo mais conhecido e, em caso afirmativo, quanto?

algorithm functional-programming performance Optar
fonte
6
O mesmo que quando programa imperativamente, seja o que for.
R. Martinho Fernandes
3
@ jldupont: Para retornar o resultado de uma computação, é claro. Existem muitos programas gratuitos para efeitos colaterais. Eles simplesmente não podem fazer outra coisa senão calcular suas entradas. Mas isso ainda é útil.
jalf
24
Eu posso fazer isso tão ruim quanto você quiser, escrevendo mal meu código funcional! * sorri * Eu acho que o que você está perguntando é "existe algum problema em que o algoritmo não destrutivo mais conhecido seja assintoticamente pior que o algoritmo destrutivo mais conhecido e, em caso afirmativo, por quanto?" ... está certo ?
itowlson
2
você poderia dar um exemplo do tipo de desaceleração em que está interessado? sua pergunta é um pouco vaga.
Peter Recore
5
Um usuário excluiu sua resposta, mas afirmou que a versão funcional do problema das 8 rainhas demorou mais de um minuto para n = 13. Ele admitiu que não estava "muito bem escrito", então decidi escrever minha própria versão do 8 rainhas em F #: pastebin.com/ffa8d4c4 . Escusado será dizer que meu programa puramente funcional calcula n = 20 em pouco mais de um segundo.
Julieta

Respostas:

531

De acordo com Pippenger [1996] , ao comparar um sistema Lisp que é puramente funcional (e tem uma semântica estrita de avaliação, não preguiçosa) com um que pode alterar dados, um algoritmo escrito para o impuro Lisp executado em O ( n ) pode ser traduzido a um algoritmo no Lisp puro que é executado no tempo O ( n log n ) (baseado no trabalho de Ben-Amram e Galil [1992] sobre simulação de memória de acesso aleatório usando apenas ponteiros). Pippenger também estabelece que existem algoritmos para o melhor que você pode fazer; existem problemas que são O ( n ) no sistema impuro que são Ω ( n log n ) no sistema puro.

Existem algumas ressalvas a serem feitas sobre este artigo. O mais significativo é que ele não trata de linguagens funcionais preguiçosas, como Haskell. Bird, Jones e De Moor [1997] demonstram que o problema construído por Pippenger pode ser resolvido em uma linguagem funcional preguiçosa em O ( n ) tempo, mas eles não estabelecem (e até onde eu sei, ninguém o tem) se ou não nenhuma linguagem funcional preguiçosa pode resolver todos os problemas no mesmo tempo de execução assintótico que uma linguagem com mutação.

O problema criado por Pippenger requer Ω ( n log n ) é especificamente construído para alcançar esse resultado e não é necessariamente representativo de problemas práticos do mundo real. Existem algumas restrições no problema que são um pouco inesperadas, mas necessárias para que a prova funcione; em particular, o problema requer que os resultados sejam computados on-line, sem poder acessar a entrada futura, e que a entrada consiste em uma sequência de átomos a partir de um conjunto ilimitado de átomos possíveis, em vez de um conjunto de tamanho fixo. E o artigo apenas estabelece resultados (limite inferior) para um algoritmo impuro de tempo de execução linear; para problemas que exigem um tempo de execução maior, é possível que o O extra (log n), o fator observado no problema linear pode ser "absorvido" no processo de operações extras necessárias para algoritmos com maiores tempos de execução. Esses esclarecimentos e questões em aberto são explorados brevemente por Ben-Amram [1996] .

Na prática, muitos algoritmos podem ser implementados em uma linguagem funcional pura com a mesma eficiência que em uma linguagem com estruturas de dados mutáveis. Para uma boa referência sobre técnicas a serem usadas para implementar estruturas de dados puramente funcionais com eficiência, consulte "Estruturas de Dados Puramente Funcionais" de Chris Okasaki [Okasaki 1998] (que é uma versão expandida de sua tese [Okasaki 1996] ).

Qualquer pessoa que precise implementar algoritmos em estruturas de dados puramente funcionais deve ler Okasaki. Você sempre pode obter, na pior das hipóteses, uma desaceleração de O (log n ) por operação simulando memória mutável com uma árvore binária equilibrada, mas em muitos casos você pode se sair consideravelmente melhor do que isso, e Okasaki descreve muitas técnicas úteis, de técnicas amortizadas a reais. os que executam o amortizado trabalham incrementalmente. Estruturas de dados puramente funcionais podem ser um pouco difíceis de trabalhar e analisar, mas oferecem muitos benefícios, como transparência referencial, que são úteis na otimização do compilador, na computação paralela e distribuída e na implementação de recursos como controle de versão, desfazer e reversão.

Observe também que tudo isso discute apenas os tempos de execução assintóticos. Muitas técnicas para implementar estruturas de dados puramente funcionais fornecem uma certa quantidade de desaceleração constante dos fatores, devido à contabilidade extra necessária para que eles funcionem e aos detalhes de implementação do idioma em questão. Os benefícios de estruturas de dados puramente funcionais podem compensar essas lentidões constantes dos fatores; portanto, você geralmente precisará fazer trocas com base no problema em questão.

Referências

Brian Campbell
fonte
50
Pippinger é a autoridade indiscutível nesta questão. Mas devemos enfatizar que seus resultados são teóricos , não práticos. Quando se trata de tornar as estruturas de dados funcionais práticas e eficientes, você não pode fazer melhor que o Okasaki.
Norman Ramsey
6
itowlson: Devo admitir que não li o suficiente de Pippenger para responder à sua pergunta; foi publicado em uma revista revisada por pares, citada por Okasaki, e li o suficiente para determinar que suas alegações são relevantes para essa questão, mas não o suficiente para entender a prova. A resposta imediata que recebo das consequências do mundo real é que é trivial converter um algoritmo O ( n ) impuro em um O ( n log n ) puro, simplesmente simulando memória modificável usando uma árvore binária equilibrada. Existem problemas que não podem fazer melhor que isso; Não sei se são puramente teóricas.
Brian Campbell
3
O resultado de Pippenger faz duas suposições importantes que limitam seu escopo: considera cálculos "on-line" ou "reativos" (não o modelo usual de um cálculo de mapeamento de entradas finitas para uma única saída) e cálculos "simbólicos" em que entradas são seqüências de átomos, que podem ser testados apenas quanto à igualdade (ou seja, a interpretação da entrada é extremamente primitiva).
Chris Conway
2
Resposta muito boa; Gostaria de acrescentar que, para linguagens puramente funcionais, não existe um modelo universalmente aceito para a complexidade da computação, enquanto no mundo impuro a máquina de RAM com custo unitário é relativamente padrão (o que torna a comparação das coisas mais difícil). Observe também que o limite superior de uma diferença Lg (N) em puro / impuro pode ser intuitivamente explicado com muita facilidade observando uma implementação de matrizes em uma linguagem pura (custa lg (n) por operação (e você obtém histórico)) .
User51568 23/05
4
Ponto importante: Traduzir meticulosamente uma especificação puramente funcional em uma implementação puramente funcional eficiente e mais complicada é de pouco benefício se você for eventualmente - automaticamente ou manualmente - convertê-la em código impuro ainda mais eficiente. A impureza não é tão importante se você pode mantê-la em uma gaiola, por exemplo, trancando-a em uma função externa sem efeitos colaterais.
Robin Green
44

De fato, existem vários algoritmos e estruturas de dados para os quais nenhuma solução puramente funcional assintoticamente eficiente (aquela implementável no cálculo lambda puro) é conhecida, mesmo com preguiça.

  • A união-encontrar acima mencionada
  • Tabelas de hash
  • Matrizes
  • Alguns algoritmos gráficos
  • ...

Entretanto, assumimos que em linguagens "imperativas" o acesso à memória é O (1), enquanto na teoria isso não pode ser tão assintoticamente (ou seja, para tamanhos de problemas ilimitados) e o acesso à memória em um grande conjunto de dados é sempre O (log n) , que pode ser emulado em uma linguagem funcional.

Além disso, devemos lembrar que, na verdade, todas as linguagens funcionais modernas fornecem dados mutáveis, e Haskell ainda os fornece sem sacrificar a pureza (a mônada ST).

jkff
fonte
3
Se o conjunto de dados se encaixar na memória física, o acesso é O (1), pois é possível encontrar um limite superior absoluto na quantidade de tempo para ler qualquer item. Se o conjunto de dados não estiver, você está falando sobre E / S e esse será o fator dominante de longe, no entanto, o programa está escrito.
Donal Fellows
Bem, é claro que estou falando de operações O (log n) de acesso à memória externa. Bs No entanto, em qualquer caso, eu estava falando: memória externa também pode ser O (1) -addressable ...
JKFF
2
Eu acho que uma das maiores coisas que a programação imperativa ganha em comparação com a programação funcional é a capacidade de manter referências a muitos aspectos distintos de um estado e gerar um novo estado de modo que todas essas referências aponte para os aspectos correspondentes do novo estado. O uso da programação funcional exigiria que as operações de desreferenciação direta fossem substituídas pelas operações de pesquisa para encontrar o aspecto apropriado de uma versão específica do estado geral atual.
supercat
Mesmo o modelo de ponteiro (acesso à memória O (log n), falando de maneira simples) não é fisicamente realista em escalas extremamente grandes. A velocidade da luz limita a rapidez com que diferentes equipamentos de computação podem se comunicar, enquanto atualmente acredita-se que a quantidade máxima de informações que podem ser mantidas em uma determinada região seja limitada por sua área de superfície.
Dfeuer
36

Este artigo alega que as implementações puramente funcionais conhecidas do algoritmo de localização e união têm pior complexidade assintótica do que a que eles publicam, que possui uma interface puramente funcional, mas usa dados mutáveis ​​internamente.

O fato de outras respostas afirmarem que nunca pode haver diferença e que, por exemplo, a única "desvantagem" do código puramente funcional é que ele pode ser paralelizado fornece uma idéia da informação / objetividade da comunidade de programação funcional sobre esses assuntos. .

EDITAR:

Os comentários abaixo apontam que uma discussão tendenciosa dos prós e contras da programação funcional pura pode não vir da "comunidade de programação funcional". Bom ponto. Talvez os advogados que vejo sejam apenas, para citar um comentário, "analfabetos".

Por exemplo, acho que este post do blog foi escrito por alguém que pode ser considerado representante da comunidade de programação funcional e, como é uma lista de "pontos para avaliação preguiçosa", seria um bom lugar para mencionar qualquer desvantagem que programação preguiçosa e puramente funcional pode ter. Um bom lugar teria sido o seguinte (tecnicamente verdadeiro, mas tendencioso a ponto de não ser engraçado):

Se uma função estrita tem complexidade O (f (n)) em uma linguagem estrita, também possui complexidade O (f (n)) em uma linguagem lenta. Por que se preocupar? :)

Pascal Cuoq
fonte
4

Com um limite superior fixo no uso da memória, não deve haver diferença.

Esboço de prova: Dado um limite superior fixo no uso da memória, deve-se conseguir escrever uma máquina virtual que execute um conjunto de instruções imperativas com a mesma complexidade assintótica como se você estivesse realmente executando nessa máquina. Isso ocorre porque você pode gerenciar a memória mutável como uma estrutura de dados persistente, fornecendo leitura e gravação de O (log (n)), mas com um limite superior fixo no uso da memória, você pode ter uma quantidade fixa de memória, fazendo com que decaimento para O (1). Portanto, a implementação funcional pode ser a versão imperativa em execução na implementação funcional da VM e, portanto, ambas devem ter a mesma complexidade assintótica.

Brian
fonte
6
Um limite superior fixo no uso da memória não é como as pessoas analisam esse tipo de coisa; você assume uma memória arbitrariamente grande, mas finita. Ao implementar um algoritmo, estou interessado em saber como ele será dimensionado da entrada mais simples até qualquer tamanho de entrada arbitrário. Se você coloca um limite superior fixo no uso da memória, por que não coloca um limite superior fixo em quanto tempo permitirá que a computação leve e diz que tudo é O (1)?
Brian Campbell
Brian Campbell: Isso é verdade. Só estou sugerindo que, se você quisesse, poderia ignorar a diferença no fator constante em muitos casos na prática. Ainda é preciso estar atento à diferença ao comprometer a memória e o tempo para garantir que o uso de m vezes mais memória diminua o tempo de execução em pelo menos um fator de log (m).
Brian