Re: [shell-script] Problemas com dados.

[Felipe Kellermann]

On Fri, 27 Feb 2004 10:21am  -0300, Marcelino Silva wrote:

> Com certeza outras linguagens poderia lhe dar uma resposta melhor, mas
> já tentou com o AWK?

Não quer dizer, eu acho.
Nem todas as "linguagens" vão responder melhor . Há muitos fatores.

> Eu o utilizo em arquivos de logs muito grandes e tenho uma boa resposta.
>

Mas são coisas diferentes, um log e uma espécie de "base de dados".
Estou conjeturando que não é um simples log pela forma que colega mostrou
como está sendo montando. Se for para pesquisar em logs, só arruma eles da
forma correta e usa o grep, *vai* ser o mais rápido, principalmente se for
buscas com informações fixas e mesmo que seja uma lista de busca.

No caso dele, um outro uso *óbvio* seria usar o join. Se não quiser usar o
join/alguma outra busca, e quiser shell, também é muito interessante. Mas
não é bom fazer uma busca simples, linear, de chaves. Há formas de fazer
buscas relativamente boas no shell, na minha opinião.

Vou usar a bash(2). Vamos ver um exemplo.
Criamos um array de 32768 elementos. Para facilitar a visualização, vamos
definir cada "campo" chave com o próprio valor da posição do elemento. Só
para tornar mais simples nós vamos usar só uma chave. Para colocar algum
valor depois, basta modificar uma linha para fazer a verificação correta.

O motivo de eu não escolher algum valor "string" e usar uma chave é muito
simples, óbvio: Não há verificação definida em Shell para isto. E é comum
encontrar tentativas pouco funcionais de fazer isto. E as chaves estão em
ordem por dois motivos. O primeiro já mencionado, para facilitar a nossa
visualização. Segundo, porque é necessário para a busca não linear:

$ for((i = 1; i <= 32768; i++)); do v[$i]=$i; done
$ echo ${#v[*]}
32768

Está ai o nosso vetor, de 32768 chaves, e já ordenadas.

$ echo $RANDOM
19741

Vamos procurar este número $n (19741) qualquer.
Até é um número bem próximo. Não vai ser tão difícil.

$ time for((i = 1; i <= 32768; i++)); do [ ${v[$i]} = $n ] &&
bash:52> echo achei && break; done
0m50.490s/user 0m0.340s/system 0m51.633s/elapsed 98.44/%CPU
achei

Eu imagino que era sobre isto que ele falava.
Mas vamos tentar procurar de outra forma:

$ cat bbin.sh
#!/bin/sh

# bbins'fk
# 1: início; 2: fim; 3: valor; v: vetor
bbins()
{
        local m=$(($1 + (($2 - $1) / 2)));
        if [ $3 = ${v[$m]} ]; then
                return 0
        elif [ $1 -eq $2 ]; then
                [ ${v[$1]} = $3 ] && return 0 || return 1
        elif [ "$3" -lt "${v[$m]}" ]; then
                bbins $1 $m $3
        else
                bbins $((m + 1)) $2 $3
        fi
}

$ . bbin.sh
$ time bbins 1 32768 $n && echo achei
0m0.160s/user 0m0.000s/system 0m0.181s/elapsed 88.61/%CPU
achei

Há uma diferença significativa, não é? Fácil de ver. Um demorou mais de 50
segundos para encontrar um valor (Que por sorte estava próximo, ainda). O
outro ficou longe de chegar perto de 1 segundo para achar a chave. E mesmo
aumentando array, não vai mudar muito no tempo de busca. Sim, é muito mais
rápido usar C (ANSI), `qsort', `bsearch', `...'. Mas nosso tópico é shell.

Logo depois que respondi ao e-mail dele, bolei este exemplo. E já iniciei
uma outra idéia que já está semi-funcional, se alguém quiser uma cópia, só
envie um mail. Consiste em um protocolo muito simples, inicialmente eu fiz
com base em sistemas 4.4BSD, formando uma estrutura de árvore de busca com
máquinas que tentam procurar as chaves. Se a máquina inicial recebe alguma
requisição e não tem possibilidade de encontrar os valores (Chave não está
dentro dos limites), ela passa para a próxima máquina que poderia ter, ou
que poderia saber de alguém que tenha, seguindo assim recursivamente. Fica
rápido, simples e legal, ;-)

-- 
Felipe Kellermann