Visitante!
Faça seu Login ou Registre-se!

Galeria de Jogos

[Ruby] Algoritmo #2 - Busca 5 Respostas | 1823 Visualizações

0 Membros e 1 Visitante estão vendo este tópico.

Raizen

  • *
  • Mensagens: 2476 Ouro: 1838

    Vencedor CRM Awards - Melhor Scripter Vencedores das edições do Concurso Projeto Rickas!

    • Ver perfil
    • E-mail
[Ruby] Algoritmo #2 - Busca
Online: 28 Fev 2014, 15:02
Índice das aulas básicas
Índice das aulas avançadas
Índice das aulas de algoritmos
Algoritmo de Busca
Conhecimento necessário : médio
Introdução

Olá jovens, bem-vindo a minha seção de aulas sobre algoritmos, esta é a segunda aula sobre algoritmos comuns e muito utilizados. Nessa aula relativamente curta, falaremos dos algoritmos de busca.


Busca Linear



A busca linear é o tipo de busca mais lógico possível, basta verificar cada valor na array ou na hash e ver se aquele valor bate com o valor inserido.
Abaixo o código em Ruby.
Código: [Selecionar]
class Array
  def linear_search(value)
    for n in 0...self.size
      return true if self[n] == value
    end
    return false
  end
end
ou seja eu usando o código abaixo
Código: [Selecionar]
p [1, 3, 5, 6, 7].linear_search(7) # retorna true
p [1, 3, 5, 6, 7].linear_search(8) # retorna false

A busca linear verifica cada um dos elementos e retorna no momento que encontra o elemento, logo
complexidade do pior caso (n)
complexidade do melhor caso (1)
e caso médio (>n/2) (visto que há chances de não estar no vetor)

Considerando isso será que há modos de reduzir o número de verificações? Pois bem, digo que sim, mas com algumas restrições, vamos abaixo para algumas buscas famosas.

Busca Binária

A busca binária é uma das buscas mais famosas, porém ela necessita que a array esteja ordenada. Devo lembrar que o sort tem uma complexidade muito maior que a busca, logo rearranjar a array para usar a busca binária não é o ideal. O ideal para essa busca, é quando ela é utilizada em uma array que já foi criada ordenada, logo optimizando esse método.
Abaixo a lógica da busca binária ,
uma busca para o número 3 por exemplo.

Ele divide no meio a array e verifica se o valor está a esquerda ou a direita, e faz isso consecutivamente até um dos valores ser o valor procurado. A busca binária não é eficiente para arrays pequenas, mas com arrays grandes ou valores fora da array ela é muito mais eficiente que a busca linear, abaixo o código em Ruby.
Código: [Selecionar]
class Array
  def binary_search(value)
    new_array = self
    while new_array.size > 1
      mid = new_array[new_array.size/2]
      mid < value ? new_array.shift(new_array.size/2) : new_array.pop(new_array.size/2)
      return true if new_array.max == value || new_array.min == value
    end
    return false
  end
end
Basicamente eu retiro os elementos indesejaveis da array para buscar no mesmo, feito isso posso buscar um elemento na complexidade.
no pior caso (log n)
no melhor caso (1)


Busca de Texto

Na busca de textos, muda um pouco a complexidade, é necessário verificar o texto todo para ver se certa palavra está contida no texto geral, segue abaixo o código de busca de texto baseado no método Rabin-Karp

Código: [Selecionar]
class String
  def rabin_search(str)
      for j in 0...(self.size - str.size + 1)
        return true if str == self[j..(j+str.size - 1)]
      end
   return false
  end
end
Um exemplo de uso
Código: [Selecionar]
p 'aqui eh um cara maneiro'.rabin_search('neiro') # retorna true
p 'aqui eh um cara maneiro'.rabin_search('neio') # retorna false

A complexidade máxima dessa busca é de (n-m) para o Ruby que tem a função de strings e não necessita verificar char por char.

Finalizando

Finalizando:
Ai está a segunda aula de algoritmos, espero que estejam gostando, a ideia é começar a usar a lógica para achar soluções para problemas cotidianos da programação. Em breve mais aulas  :)
« Última modificação: 16 Dez 2015, 10:30 por Raizen »

Molotov Dias

  • *
  • Mensagens: 308 Ouro: 16
  • Kick out the JAMMS
    • Unity
    • Facebook
    • Twitter
    • Ver perfil
  • BreaklanceSpiked MailNightWisherNightWalker
Re: Algoritmo #2 - Busca
Resposta 1 Online: 01 Mar 2014, 13:24
Caraca... Seus tutoriais estão ficando bem profissionais, mano. Eu tenho estudado algoritmos na escola e são coisas assim que a gente vai fazendo. Acho bem interessante passar esses tutoriais para o Maker. E você não teria um exemplo de aplicação? Seria interessante, para situar os alunos.

Btw, você pretende dar aulas de Lista, Bubble Sort e coisas assim? xD

Safety and Peace.
ALGUÉM FALOU EM JAIMES DESING?!

// -> cHEAT .exeKUTIVE OFF-ice ~~//


Raizen

  • *
  • Mensagens: 2476 Ouro: 1838

    Vencedor CRM Awards - Melhor Scripter Vencedores das edições do Concurso Projeto Rickas!

    • Ver perfil
    • E-mail
Re:  Algoritmo #2 - Busca
Resposta 2 Online: 01 Mar 2014, 15:36
Caraca... Seus tutoriais estão ficando bem profissionais, mano. Eu tenho estudado algoritmos na escola e são coisas assim que a gente vai fazendo. Acho bem interessante passar esses tutoriais para o Maker. E você não teria um exemplo de aplicação? Seria interessante, para situar os alunos.

Btw, você pretende dar aulas de Lista, Bubble Sort e coisas assim? xD

Safety and Peace.
Já tem a do Sort xD
http://centrorpg.com/aulas-para-rgss/algoritmo-1-otrs-gt-sort/
é mais complexo que search, mas acabei fazendo antes kk :P.

é vou colocar no finalizando, acho que será interessante mostrar aonde no rpg maker é usado isso x)

Vlws :D

Pretty-Belle

  • *
  • Mensagens: 169 Ouro: 634

    Melhor pontuação no Evento X'mas Factory

  • "Can't find a door, make your own!"
    • DeviantArt
    • Ver perfil
  • Elmo de Natal
Re: Algoritmo #2 - Busca
Resposta 3 Online: 09 Mar 2014, 18:56
Parabéns pelos tutoriais, Raizen! Até agora tô acompanhando todos :3
Só tenho uma dúvida, em relação ao primeiro código ali... vi o termo "self.size". Já vi esse "self" milhares de vezes, até já usei ele (para edições simples, como mudar tamanho de janela e tals), mas usei meio às cegas mesmo, e entendo muito pouco. Você vai fazer um tutorial detalhando métodos como esse (sei nem se isso é um método xD)? Tipo... quando podemos usá-lo, e quando não faz sentido usar?

E alguma uma sugestão em relação a todos os tutoriais... eu os achei bem explicadinhos e tals, mas acho que tá faltando uma contextualização. Tô achando meio teórico demais, sabe? Como a gente poderia usar todas essas informações na hora de fazer um script? Em que tipo de scripts as arrays, hashes, laços aparecem mais?

Bem, é isso x3 Gbye!
Já perceberam que em vez de as pessoas usarem esse espaço para uma assinatura de fato, elas colocam alguma coisa aleatória (imagem, frase filosófica, divulgação), e colocam no corpo das mensagens o que deveria ser a assinatura?

katumblo

  • *
  • Mensagens: 577 Ouro: 205
  • Aposentado esperando o Uthred pagar minha aposent.
    • Ver perfil
    • E-mail
  • BreaklanceBladerEscudo CRMKnight Crest
Re: Algoritmo #2 - Busca
Resposta 4 Online: 09 Mar 2014, 19:38
eu falei tanta merda ( a merda começa quando falei que self era um objeto ) que decidi voltar aqui e apagar esta resposta, então algum moderador por favor apague essa mensagem ._.
« Última modificação: 09 Mar 2014, 19:56 por katumblo »
Tudo vai dar certo (y(8.

Raizen

  • *
  • Mensagens: 2476 Ouro: 1838

    Vencedor CRM Awards - Melhor Scripter Vencedores das edições do Concurso Projeto Rickas!

    • Ver perfil
    • E-mail
Re:  Algoritmo #2 - Busca
Resposta 5 Online: 09 Mar 2014, 22:10
Parabéns pelos tutoriais, Raizen! Até agora tô acompanhando todos :3
Só tenho uma dúvida, em relação ao primeiro código ali... vi o termo "self.size". Já vi esse "self" milhares de vezes, até já usei ele (para edições simples, como mudar tamanho de janela e tals), mas usei meio às cegas mesmo, e entendo muito pouco. Você vai fazer um tutorial detalhando métodos como esse (sei nem se isso é um método xD)? Tipo... quando podemos usá-lo, e quando não faz sentido usar?

E alguma uma sugestão em relação a todos os tutoriais... eu os achei bem explicadinhos e tals, mas acho que tá faltando uma contextualização. Tô achando meio teórico demais, sabe? Como a gente poderia usar todas essas informações na hora de fazer um script? Em que tipo de scripts as arrays, hashes, laços aparecem mais?

Bem, é isso x3 Gbye!
Ah sim eu deveria colocar uns exemplos maneiros, apesar que tem uns no meio da aula xD.
o self é só a representação dele mesmo, por exemplo eu fiz uma instância dele que é isso daqui.
a = Array.new
No caso, tudo dentro da classe Array que tem self, sempre que eu estiver mexendo com o a, será o próprio a :P.

Explicando melhor.
a = [1, 2, 3, 4] # Aqui eu já inicio a como uma array e dei o tal valor [1, 2, 3, 4] para ele.
Se na classe Array, em algum lugar self, esse self será exatamente o [1, 2, 3, 4]
Então o self.size por exemplo é exatamente a mesma coisa que [1, 2, 3, 4].size

Por isso não precisa de uma aula especifica, pois tudo que funcionar com o objeto original funciona com o self, por isso você consegue usar self.size, self.x e coisas afins :D.



As aulas de algoritmos são dado em cursos de computação e talz, mas a ideia não é bem saber como fazer, e sim pegar a lógica dele xD, assim ajudando a fazer outras coisas. Não é necessário saber como a busca é feita no caso, mas saber como ela é feita, da uma ideia MUITO boa de como sair de algumas situações que você fique presa por exemplo.
As arrays e talz, são usadas em... quase tudo que necessita de muita informação, ou seja, você tem tanta info que criar 100 variáveis fica muito fora de mão, ai você usa a Hash se for para mais organização, ou a array se for para usar coisas como ordenação e talz. :)

@katumblo: relaxa, se precisar perguntar algo por mais idiota que ache que seja e tiver a ver com o assunto, fique a vontade.

 

Versão Mobile