Fazendo a coisa certa.
August 28th, 2005
Vendo o site da ITA Software e achei algumas informações interessantes. Por exemplo:
…
“There are 25,000,000 practical flight combinations for a round-trip between Boston and Los Angeles with one-day travel windows. Computing the price for any one of those ways is at least NP-hard. The availability data is changing at 100 Hz. Find the cheapest solution in 10 seconds or less…”
Imagino como deve ser para processar as informações para o número de pessoas que necessitam de informações. Mas lendo um pouco mais….
…
“Our programmers write robust, efficient code using whatever language is best suited to the task, be it LISP, C++, Java, Python, Perl or XSLT. If you have computer science training, a love of hacking, and are willing to endure the messy complexity inherent in a real-world domain such as travel, apply today!”
…
Não podia ser diferente. Qualquer um com um pouco mais de conhecimento sabe que não existe A linguagem ideal para tudo. Se você precisa do máximo, terá que utilizar diversas ferramentas. De nada vai adiantar se os programadores não forem habilidosos (nem precisava ter escrito, né?).
A empresa também não precisa perder um monte de tempo entrevistando qualquer um. Basta criar uma página com os requisitos necessários. Fora instrução e outros detalhes, o pedido de um pequeno teste já ajuda a efetuar uma seleção prévia. Se não conseguiu resolver, nem chama para a entrevista. Procurar por uma resposta pronta e copiar? Acho que nem pensar. :-)
Atualmente existem seis problemas que podem ser resolvidos, utilizando-se qualquer linguagem. Por exemplo:
Write a program to find the largest possible rectangle of letters such that every row forms a word (reading left to right) and every column forms a word (reading top to bottom). Words should appear in this dictionary: WORD.LST (1.66MB). Heuristic solutions that may not always produce a provably optimal rectangle will be accepted: seek a reasonable tradeoff of efficiency and optimality.
Mesmo sem ver o dicionário já parece complicado? Ok, um que seja de resolução mais fácil:
Write a program to compute the sum of all the integers between 1 and 1011 that are both divisible by seven and, when the decimal digits are reversed, are still divisible by seven. Solutions to this problem will be judged on performance or algorithmic sophistication.
Enquanto isso, outras coisas acontecem por aqui. :-)
Entry Filed under: Geral
6 Comments
1. TaQ | August 28th, 2005 at 11:17 am
Rapaz, ontem eu fiz uma palestra de Ruby no SlackwareShow (foi a última, atrasou, muita gente já tinha saído, mas foi legal! :-) e entre as palestras troquei muita idéia com o pessoal que estava por lá.
Achei legal que todo mundo que falei, apesar de serem defensores de X linguagem e Y metodologia de desenvolvimento, concorda com essa premissa que não tem A a solução global para todas as situações, e sim a melhor para cada situação. :-)
2. nemesis | August 28th, 2005 at 1:45 pm
ITA Software, hein? andou dando uma espiada no site do Paul Graham? ;)
É, ouvi dizer também que seus sistemas são ( ou eram ) escritos primariamente em Common Lisp, e quando precisavam realmente de performance, usavam C++ como um programador C++ usa assembly. :)
êta probleminhas cascudos… demandam um bocado de habilidade lógica e algoritmica. escolher essa ou aquela linguagem é irrelevante: elas não ajudam a pensar o algoritmo certo, apenas a implementá-lo da forma mais conveniente.
embora, digam alguns, as linguagens também moldam sua forma de pensar. e não estou falando especificamente de linguagens de programação…
3. Guaracy Monteiro | August 31st, 2005 at 2:04 am
> Achei legal que todo mundo que falei, apesar de serem defensores de X
> linguagem e Y metodologia de desenvolvimento, concorda com essa
> premissa que não tem A a solução global para todas as situações, e
> sim a melhor para cada situação. :-)
Ontem estava vendo uma apresentação sobre uma linguagem e apareceram 5 slides contendo: “Use the Right Tool for the JOB”. Cada um com seus detalhes como expressividade da linguagem, tipos de estruturas de dados disponíveis, compilado/interpretado/bytecode, etc.
4. Guaracy Monteiro | August 31st, 2005 at 2:05 am
Quase. Era sobre Lisp mas foi em:
http://www.cs.helsinki.fi/u/jesnellm/blog/archive/2005-08-27b.html
> êta probleminhas cascudos… demandam um bocado de habilidade lógica
> e algoritmica. escolher essa ou aquela linguagem é irrelevante: elas
> não ajudam a pensar o algoritmo certo, apenas a implementá-lo da
> forma mais conveniente.
>
>
>
> embora, digam alguns, as linguagens também moldam sua forma de
> pensar. e não estou falando especificamente de linguagens de
> programação…
Apesar de não conhecer muitas linguagens, até concordo com ‘os alguns’. Até quando a gente pega um texto em inglês existem alguns detalhes que facilitam quando a gente lê em ingês e entende em vez de traduzir para o Português. Certamente se pegarmos algo como Japonês, deve ser diferente.
Por isso acho interessante o programador conhecer outras linguagens. Muitas vezes a forma de resolver o problema em uma pode facilitar em outra. Algo que me chamou a atenção é a maneira para calcular números de Fibonacci. A maioria das linguagens apresenta um algoritmo recursivo e só. Meio paradoxal, mas apenas em linguagens funcionais (até pode ter em outras) mostram que é a pior forma. Um algoritmo não recursivo, mesmo em uma linguagem interpretada,pode dar um banho em um algoritmo recursico compilado em C (para números grandes).
5. nemesis | September 1st, 2005 at 12:54 pm
“Meio paradoxal, mas apenas em linguagens funcionais (até pode ter em outras) mostram que é a pior forma. Um algoritmo não recursivo, mesmo em uma linguagem interpretada,pode dar um banho em um algoritmo recursico compilado em C (para números grandes).”
Bem, não temos como fugir à realidade: recursão eventualmente vai causar algum estouro de pilha, pois memória será sempre um recurso limitado, diferente de uma hipotética, abstrata e infinita fita em uma máquina de turing idealizada.
Isso seria uma grande infelicidade para linguagens funcionais, em que não existem construções sintáticas específicas para loop: elas são apenas funções ( ou macros maquiando funções ) como outra qualquer e ocupam espaço na pilha quando chamadas.
Então, o que o pessoal que implementa linguagens funcionais fez foi padronizar uma técnica que permitiria aos programadores exprimir idéias com uma aparente sintaxe recursiva, mas que na verdade implementa um algoritmo imperativo implicitamente. Dessa forma, une-se a conveniência de uma sintaxe natural e recursiva para algoritmos recursivos, com a eficiência de uma implementação imperativa.
Essa técnica se chama tail-recursion e é uma padronização sobre como transformar funções recursivas que se atenham a um determinado padrão para chamadas de função em um goto/jump implícito.
O padrão é muito simples e diz o seguinte: se a chamada à uma função for a última expressão avaliada, essa função está em um contexto de tail ( cauda ).
Portanto, funções tail-recursive são aquelas que chamam a si próprias em um contexto de tail.
Por exemplo, a seguinte função fatoria NÃO É tail-recursive:
(define (fact n)
(if (= 0 n)
1
(* n (fact (- n 1)))))
Pq não? Observe que a última expressão é (* n (fact (- n 1))), ou seja, uma multiplicação, não a chamada à própria função. Essa função, se chamada para números muito grandes, vai causar um gasto imenso de memória, até da eventual exaustão da pilha.
Por outro lado:
(define (tail-fact n)
(define (fact num acc)
(if (= num 0)
acc
(fact (- num 1) (* acc num))))
(fact n 1))
Vai funcionar com um mínimo de memória, para qualquer número imaginável. Obviamente, não recomendo números muito acima de 500000, pois pode vir a demorar um bom tempo para a computação chegar ao fim. Mas vai chegar ao fim.
Observe que a expressão do algoritmo parece natural e recursiva, mas na verdade é imperativa: ela retorna o resultado que foi acumulado ( acc ) conforme a função é “recursivamente chamada/aplicada”. Obviamente, pelo fato dela se usar da convenção de tail-recursion, o que o interpretador scheme faz não é uma chamada exatamente, mas sim um simples goto ao começo dela.
Seja OCaml, Haskell ou Scheme: todas as implementações são requeridas de suportarem tail-recursion para linguagens funcionais, senão, não daria para serem funcionais sem imporem severos limites práticos para não causarem estouros de pilha…
6. Guaracy Monteiro | September 2nd, 2005 at 10:05 pm
> Bem, não temos como fugir à realidade: recursão eventualmente vai
> causar algum estouro de pilha, pois memória será sempre um recurso
> limitado, diferente de uma hipotética, abstrata e infinita fita em
> uma máquina de turing idealizada.
O problema das séries/números de fibonacci não estaria diretamente
relacionado com estouro de pilha e sim com a extrema ineficiência do
algoritmo mesmo. Ele efetua uma duplicidade muito grande de cálculos.
Procurei uma coisa e achei outra. Mas já é possível ter uma idéia em:
http://cubbi.org/serious/fibonacci/algorithms.html