[Ruby] Algoritmo #2 - Busca

[Raizen]

[box class=windowbg1]

Índice das aulas básicas

• Aula 1 - Introdução
  
• Aula 2 - Objetos
  
• Aula 3 - Operações
  
• Aula 4 - Condições
  
• Aula 5 - Repetição
  
• Aula 6 - Arrays
  
• Aula 7 - Hashes
  [/box]
  [box class=windowbg1]
  Índice das aulas avançadas
• Aula 8 - Superclasses e instâncias
  [/box]
  [box class=windowbg1]
  Índice das aulas de algoritmos
• Aula 1 - Sort
  
• Aula 2 - Busca
  
• Aula 3 - Recursividade
  [/box]
  
  [box class=windowbg]
  Algoritmo de Busca
  [/box]
  
  Conhecimento necessário : médio
  [box class=windowbg]
  Introdução
  [/box]
  [box class=windowbg2]
  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.
  
  [/box]
  
  [box class=windowbg]
  Busca Linear
  [/box]
  
  [box class=windowbg2]
  
  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.
  

  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
  

  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.
  [/box]
  
  [box class=windowbg]
  Busca Binária
  [/box]
  
  [box class=windowbg2]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.
  

  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)
  
  [/box]
  
  [box class=windowbg]
  Busca de Texto
  [/box]
  
  [box class=windowbg2]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
  
  

  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
  

  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.
  [/box]
  
  [box class=windowbg]
  Finalizando
  [/box]
  
  [box class=windowbg2]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  :)
  [/box]

[Molotov Dias]

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.

[Raizen]

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]

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!

[katumblo]

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 ._.

[Raizen]

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.