Quão inteligentes são os utilitários unix?

Utilitários Unix como sort, find, grep, diff e outros são muito úteis para executar tarefas rápidas, às vezes sem escrever nenhum código.

Eu queria saber quais algoritmos eles usam internamente e como decidir de forma inteligente um algoritmo específico para uma tarefa específica? Por exemplo, se a classificação obtiver um grande arquivo de entrada, ela utilizará algoritmos diferentes para tamanhos de dados diferentes?

O grep alterna inteligentemente os algoritmos ao pesquisar diferentes conjuntos de dados?

O Unix é apenas um padrão, especifica o que as implementações devem fazer, mas não como elas devem fazer.

Portanto, as implementações do grep / sort / find provavelmente usarão abordagens diferentes em sistemas diferentes (e mesmo um sistema, como o Linux, existem implementações simultâneas).

Para Linux, você sempre pode procurar no código fonte.

Você pode estar interessado nesta postagem da lista de discussão pelo autor original do GNU grep, que explica algumas das otimizações do GNU grep. Outra exploração agradável por ridiculous_fish (autor de Hex Fiend)

O padrão UNIX não especifica detalhes de implementação para as ferramentas padrão do sistema, exceto casos realmente raros. Você pode encontrar a versão mais recente da Single Unix Specification aqui (aviso: é necessário registro).

Com isso em mente, todo UNIX (System V e descendentes diretos como BSD, Solaris, Mac OS X, etc.) ou sistema operacional baseado em UNIX (descendentes distantes ou semelhantes: Linux, Minix) possui suas próprias implementações dos utilitários descritos em a especificação UNIX. Por exemplo. dê uma olhada no FreeBSD e Linux / GNU Coreutils . Cuidado que algumas ferramentas são projetos inteiros separados por si mesmos, como GNU diff ou GNU grep . Outro fato também é que algumas implementações dessas ferramentas podem ser incluídas em outros sistemas como UNIX como padrão, em seguida, para os quais eles foram escritos inicialmente, por exemplo, alguns gnu coreutils no freebsd ou no GCC.

Bônus: Para entender a árvore genealógica do UNIX, dê uma olhada neste gráfico .

Eu queria saber quais algoritmos eles usam internamente e como decidir de forma inteligente um algoritmo específico para uma tarefa específica? Por exemplo, se a classificação obtiver um grande arquivo de entrada, ela utilizará algoritmos diferentes para tamanhos de dados diferentes?

Essa é uma pergunta interessante (+1 para isso). Não tenho idéia de qual é a resposta, mas se eu fosse você, examinaria o código fonte dos utilitários típicos do GNU para ter uma idéia de seus algoritmos.

O grep alterna inteligentemente os algoritmos ao pesquisar diferentes conjuntos de dados?

Acho que não. Não me cite, já que não posso lhe contar com 100% de certeza, mas acho que não. A filosofia das coisas do UNIX é que uma coisa faz uma coisa e apenas uma coisa. É por isso que temos várias versões do grep ( grep, egrep, fgrep).

Além disso, a idéia é fazer uma coisa e apenas uma coisa em tempo de execução. Comportamentos e algoritmos diferentes podem ser configurados como argumentos de linha de comando, para que o mesmo programa possa agir de maneira um pouco diferente (e possivelmente um pouco mais otimizada) entre as execuções. Bons exemplos são o comando wce diff.

No entanto, a adaptação comportamental é baseada na configuração (via argumentos da linha cmd); eles não alteram / adaptam o comportamento em tempo de execução. Geralmente, é uma complexidade desnecessária para o tipo de artefato que as ferramentas do UNIX pretendem ser.

Essa complexidade é mais apropriada para ferramentas IMO mais complexas e menos genéricas.

O grep alterna inteligentemente os algoritmos ao pesquisar diferentes conjuntos de dados?

Acho que não, mas ele muda para o algoritmo não rápido "RE" quando recebe o sinalizador -f (ou invocado como fgrep).