Utilitários Unix como sort, find, grep, diff et são muito úteis para realizar 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 arquivo de entrada enorme, usará algoritmos diferentes para tamanhos de dados diferentes?
O grep alterna inteligentemente algoritmos ao pesquisar diferentes conjuntos de dados?
O Unix é apenas um padrão, ele especifica o que as implementações devem fazer, mas não como elas devem ser feitas.
Portanto, implementações do grep / sort / find provavelmente usarão diferentes abordagens em diferentes sistemas (e até mesmo um sistema, como o Linux, existem implementações simultâneas).Para o Linux, você pode sempre olhar para o código-fonte.
Você pode estar interessado nesta postagem da lista de discussão do GNU original grep author 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 em casos realmente raros. Você pode encontrar a última vesion da Especificação Unix Única aqui (aviso: registro obrigatório).
Com isso em mente, todo UNIX (Sistema V e descendentes diretos como BSD, Solaris, Mac OS X, etc.) ou Sistema Operacional baseado em UNIX (descendente distante ou similares: Linux, Minix) tem suas próprias implementações do utilitários descritos na especificação do UNIX. Por exemplo. Dê uma olhada no FreeBSD's e Linux/GNU Coreutils . Esteja ciente de que algumas ferramentas são separadas por todo o projeto por si só, como GNU diff ou GNU grep . Também outro fato é que algumas implementações dessas ferramentas podem encontrar seu caminho para outros sistemas semelhantes ao UNIX como padrão, então aquelas para as quais foram inicialmente escritas, por exemplo. alguns gnu coreutils no freebsd ou no GCC.
Bônus: Para dar uma olhada na árvore genealógica do UNIX, dê uma olhada em este gráfico .
I wanted to know what algorithms do they internally use and how do intelligently decide a specific algorithm for a specific task? For example if sort gets a huge input file, will it use different algorithms for different data sizes?
Essa é uma pergunta interessante (+1 para isso). Eu não tenho idéia do que a resposta é, mas se eu fosse você, eu olharia o código-fonte dos utilitários GNU típicos para ter uma idéia de seus algoritmos.
Does grep intelligently switch algorithms while searching different data sets?
Eu não penso assim. Não me cite desde que eu não posso realmente dizer com 100% de certeza, mas eu realmente não penso assim. A filosofia das coisas do UNIX é que uma coisa faz uma coisa e uma coisa só. É por isso que temos várias versões do grep ( grep , egrep , fgrep ).
Além disso, a ideia é 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 forma ligeiramente diferente (e possivelmente um pouco mais otimizado) entre as execuções. Bons exemplos são o comando wc e diff .
No entanto, a adaptação comportamental é baseada em configuração (via argumentos de linha cmd); eles não mudam / adaptam o comportamento em tempo de execução. Normalmente, é uma complexidade desnecessária para o tipo de artefatos que as ferramentas UNIX pretendem ser.
Essa complexidade é mais apropriada para ferramentas mais complexas e menos genéricas, IMO.
Does grep intelligently switch algorithms while searching different data sets?
Eu não penso assim, mas ele muda para o algoritmo não-RE "rápido" quando recebe o sinalizador -f (ou invocado como fgrep).
Tags coreutils grep text-processing sort
