[Cascavel-pm] algorítmo de busca e ordenação

[Luis Campos de Carvalho]

Alceu R. de Freitas Jr. wrote:
> Olá monges,
> Alguém saberia me dizer quão eficiente é fazer uma
> busca por um item dentro de um hash? 

   Aproximadamente O(1), ou constante.
   No máximo, dependendo do seu algorítmo de calculo do hash index, 
alguma coisa perto de O((1/n)(Ln(n))), muito pequeno. Ah! Este algorítmo 
é do livro do D. Knuth.

 > Por exemplo,
> tenho um hash com nomes de alunos com chaves, e suas
> notas da última prova como valor.

   Certo...

> Como o Perl faz a ordenação/busca por esses valores?

   Os valores são indexados "diretamente".
   O Perl calcula internamente o hash index correspondente a cada chave 
e retorna o valor apontado por este index para você, e tudo acontece 
como se o hash table fosse um array:

   $value = $hash{$index};

   Para obter todos os valores, você pode usar o operador "keys":

   foreach $value( keys %hash ){
     # do something...
   }

   Para ordenar os valores de acordo com um criterio qualquer, 
implementado na sub &by_order, diga

   @ordered_keys = sort \&by_order, keys %hash;

   Ou, se você quiser os valores ordenados pela chave, pode fazer

   @notas = map { $hash{$_} } sort \&by_order, keys %hash;

> Em que situações é possível utilizar algorítmos mais
> performáticos?

   É muito complicado ter performance maior do que um hash table neste 
tipo de aplicação. Acredito que uma forma de fazer isto possa ser 
implementar seu próprio algorítmo de hash table, usando uma função de 
hash especializada (para ter ganhos ínfimos, IMHO).

> "Todo mundo precisa crer em algo. Creio que vou tomar outra cerveja."
> Grouxo Marx

   Hey! Eu me lembro disso!
   Foi do primeiro encontro dos São Paulo Perl Mongers... :-)
   A gente bem que poderia repetir a dose...

   Eu estou quase acreditando que o pessoal da lista não curte um pub...

   Putamplexos!
-- 
=======================================================
   Luis Campos de Carvalho is BsC in Computer Science,
   Certified Oracle DBA, UNIX and Linux lover, Perl
   Fanatic and Leader of the Sao Paulo Perl Mongers
   http://br.geocities.com/monsieur_champs/
=======================================================