Ir para conteúdo

Arquivado

Este tópico foi arquivado e está fechado para novas respostas.

mattknob

Algoritmo de busca inteligente

Recommended Posts

Boa tarde galera, tenho um problema complicado (pelo menos pra mim) portanto vou tentar deixar o mais claro possível:

Tenho uma tabela onde estão armazenadas várias palavras ordenadas alfabeticamente e a única forma de buscá-las é através de sua posição nesta tabela (seu index). Por exemplo, buscando pela posição 15, me retorna a palavra BANANA.

Somente para ilustrar:

2d6l2cw.jpg

Através desta, e somente desta tabela preciso desenvolver um algoritmo que busque a posição de determinada palavra. Por exemplo, o usuário informará a palavra AZEITE e o algoritmo terá que retornar 3.

Até aí tudo bem, poderia ser resolvido com um simples laço de repetição, buscando todas as posições da tabela até encontrar a palavra. Maaaas, preciso que o número de buscas realizado nessa tabela (que é gigantesca) seja o menor possível. Ou seja, varrer a tabela em busca da posição da palavra está fora de cogitação.

Como não é possível realizar a busca na tabela por palavra, somente por posição, preciso de um algoritmo que busque de forma inteligente os dados dessa tabela.

 

Alguma ideia?

Compartilhar este post


Link para o post
Compartilhar em outros sites

1. Tente ordernar a tabela em ordem alfabética sem alterar o index e crie um indece crescente,

2. Conte o valor de itens que existe,

3. pegue o valor do meio e veja se a palavra é maior ou menor que a que vc está procurando

4. Se for maior, descarte a primeira metade e se for menor descarte a segunda

5. Retorne ao processo 2. até achar a palavra

 

Se sua lista tiver 1000 itens, e o que estiver procurando estiver no 28 e dps de alterar a ordem ele for para o novo 83

Vc olha o 1, dps o 1000, 500, 250, 125, 62, 91, 76, 83

 

neste forma em 9 buscas ele achou o que deveria, mas se não me engano para esse caso de 1000 seria no maximo 25 buscas,

Sem duvidas melhor do que rodar a lista inteira :)

 

Não sei se minha explicação ajudou, e se o que vc tem é possível realizar :)

 

espero ter ajudado :)

Compartilhar este post


Link para o post
Compartilhar em outros sites

1. Tente ordernar a tabela em ordem alfabética sem alterar o index e crie um indece crescente,

2. Conte o valor de itens que existe,

3. pegue o valor do meio e veja se a palavra é maior ou menor que a que você está procurando

4. Se for maior, descarte a primeira metade e se for menor descarte a segunda

5. Retorne ao processo 2. até achar a palavra

 

Se sua lista tiver 1000 itens, e o que estiver procurando estiver no 28 e dps de alterar a ordem ele for para o novo 83

você olha o 1, dps o 1000, 500, 250, 125, 62, 91, 76, 83

 

neste forma em 9 buscas ele achou o que deveria, mas se não me engano para esse caso de 1000 seria no maximo 25 buscas,

Sem duvidas melhor do que rodar a lista inteira :)

 

Não sei se minha explicação ajudou, e se o que você tem é possível realizar :)

 

espero ter ajudado :)

 

Primeiramente obrigado pela disponibilidade.

 

Segundamente, a ideia é boa porém eu esqueci de comentar que não tenho como fazer a contagem de elementos dessa tabela. Pra falar a verdade coloquei em forma de tabela apenas para simplificar um pouco, na verdade é um WebService, portanto não tenho como fazer a contagem, até porque é possível que o "dicionário" aumente ou diminua, portanto o algoritmo não pode levar em consideração o número de elementos.

 

É complicado, mas com certeza há uma solução :yes:

Compartilhar este post


Link para o post
Compartilhar em outros sites

Olá, você poderia fazer criando uma matriz de 26 linhas, cada linha representando uma letra do alfabeto em ordem crescente, e as colunas receberão os produtos com a mesma letra inicial. Exemplo: se eu quero adicionar abacate e abóbora na lista eu adiciono um na primeira linha( que representa a letra A ) e primeira coluna, e o outro adiciona na primeira linha( pois começa com A também ) e segunda coluna. Tipo Assim:

 

1794569_546743468790927_8041342187981477
Pra achar o produto desejado basta pegar a primeira letra do produto digitado e percorrer a linha da lista que representa essa letra.
A lógica que eu consegui achar foi essa, deixo a codificação com você, pois só aprende praticando :). Espero ter ajudado, mesmo :D

Compartilhar este post


Link para o post
Compartilhar em outros sites

 

Olá, você poderia fazer criando uma matriz de 26 linhas, cada linha representando uma letra do alfabeto em ordem crescente, e as colunas receberão os produtos com a mesma letra inicial. Exemplo: se eu quero adicionar abacate e abóbora na lista eu adiciono um na primeira linha( que representa a letra A ) e primeira coluna, e o outro adiciona na primeira linha( pois começa com A também ) e segunda coluna. Tipo Assim:

 

1794569_546743468790927_8041342187981477
Pra achar o produto desejado basta pegar a primeira letra do produto digitado e percorrer a linha da lista que representa essa letra.
A lógica que eu consegui achar foi essa, deixo a codificação com você, pois só aprende praticando :). Espero ter ajudado, mesmo :D

 

 

Obrigado pela resposta colega.

 

Entendi sua ideia, porém para saber a posição inicial de cada letra terei fazer exatamente o que eu não posso: percorrer toda a tabela. :pinch:

Compartilhar este post


Link para o post
Compartilhar em outros sites

Como você não pode contar toda a tabela? Se for um XML você pode contar a quantidade de elementos

 

Coloquei no problema como tabela apenas para facilitar o entendimento, na verdade é um WebService onde cada consulta é uma requisição ao mesmo.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Sim, então. Quando o webservice retornar para você o resultado, ele vai sr ou em XML ou em array, ai você pode contar os elementos.

 

Não, ele retorna apenas a palavra da posição.

 

Eu mando o número da posição pelo WebService e ele me retorna a palavra. Não tem um método que retorna todo o dicionário entende?

Compartilhar este post


Link para o post
Compartilhar em outros sites

Mas existe algum meio de saber todas as palavras? Caso contrário não temos como realizar uma busca

 

Somente fazendo a requisição por posição uma a uma até não retornar mais nada, porém a intenção é evitar isso. Andei pesquisando bastante sobre isso nos últimos dias e sei que é complicado mas há uma forma, talvez envolvendo muito mais a matemática do que a programação em si.

Compartilhar este post


Link para o post
Compartilhar em outros sites

Então Matt, o problema é que se você não consegue saber a lista de palavras, você não consegue saber a posição, você tem que ter uma lista de todas as palavras disponíveis, a não ser que a lista siga uma lógica forte

Compartilhar este post


Link para o post
Compartilhar em outros sites

Então Matt, o problema é que se você não consegue saber a lista de palavras, você não consegue saber a posição, você tem que ter uma lista de todas as palavras disponíveis, a não ser que a lista siga uma lógica forte

 

A lista segue a ordem alfabética.

 

Uma alternativa que encontrei é verificar as palavra letra por letra. Por exemplo, se eu quiser buscar a palavra MACACO, faço uma primeira requisição no webservice e verifico a primeira letra. A primeira palavra é ABACATE, portanto não vou procurar as próximas posições. A próxima requisição a ser feita é a 101. Verifico a primeira letra novamente, se for antes de M eu continuo avançando, se for depois eu retrocedo a metade (50). Achando alguma palvra com a letra M parto para a segunda letra e assim sucessivamente.

 

Ficou uma gambiarra digna de troféu e não é nem de longe a melhor solução, mas enquanto continuo buscando alguma "fórmula mágica" estou fazendo desse jeito.

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Essa, na verdade, é a única aproximação que eu consigo pensar para uma lista oculta deste jeito. Uma das ideias é você fazer milestones, ou seja, você define variáveis manualmente no código marcando o "Ponto de inicio" de cada letra, por exemplo, a letra G começa no indice 56. Então quando você for fazer uma pesquisa que comece com G você já sabe que ele vai estar acima do 56 e abaixo do indice da próxima letra.

 

Isso evita você ter que fazer várias requisições para o seu serviço

Compartilhar este post


Link para o post
Compartilhar em outros sites

 

A lista segue a ordem alfabética.

 

 

se ela está em ordem alfabética é só fazer o que eu te disse, só pular o passo de organizar em ordem alfabética.

você consegue saber qual o ultimo índice desta lista?

 

Ficou uma gambiarra digna de troféu e não é nem de longe a melhor solução, mas enquanto continuo buscando alguma "fórmula mágica" estou fazendo desse jeito.

 

 

não é uma gambiarra saca só Pesquisa Binária na nossa amiga Wikipédia

 

 

se não me engano, se vc fizer

if('Matt' > 'Jackson'){

 

}

 

ele retorna verdadeiro ou falso... não precisa fazer uma por uma

Compartilhar este post


Link para o post
Compartilhar em outros sites

 

Essa, na verdade, é a única aproximação que eu consigo pensar para uma lista oculta deste jeito. Uma das ideias é você fazer milestones, ou seja, você define variáveis manualmente no código marcando o "Ponto de inicio" de cada letra, por exemplo, a letra G começa no indice 56. Então quando você for fazer uma pesquisa que comece com G você já sabe que ele vai estar acima do 56 e abaixo do indice da próxima letra.

 

Isso evita você ter que fazer várias requisições para o seu serviço

O problema é que para achar o ponto de início de cada letra vou ter que fazer inúmeras requisições...

 

se ela está em ordem alfabética é só fazer o que eu te disse, só pular o passo de organizar em ordem alfabética.

você consegue saber qual o ultimo índice desta lista?

 

 

não é uma gambiarra saca só Pesquisa Binária na nossa amiga Wikipédia

 

 

se não me engano, se você fizer

if('Matt' > 'Jackson'){

 

}

 

ele retorna verdadeiro ou falso... não precisa fazer uma por uma

Infelizmente não consigo saber o último item da lista.

 

Agora, não sabia que if('Matt' > 'Jackson') retornava um booleano, vai simplificar bastante meu código... E acho que vou acabar deixando por isso mesmo, continua com um bom número de requisições porém nem se compara a ideia inicial de pesquisar todas as posições...

Compartilhar este post


Link para o post
Compartilhar em outros sites
O problema é que para achar o ponto de início de cada letra vou ter que fazer inúmeras requisições...

 

 

Apenas inicialmente, uma vez que você tiver tudo salvo você pode usar como dicionário

Compartilhar este post


Link para o post
Compartilhar em outros sites

Tente usar arvore binaria ou Hash para organizar os itens em memoria. Caso não de pra fazer faça assim:

 

Quando chegar uma palavra, pule para o meio da lista

Depois verifique se essa palavra vai estar a esquerda ou a direita da sua lista

Independentemente da direção pule para o meio da metade e faça isso até achar sua palavra

 

Algo assim:

 

1 2 3 4 5 6 7 8 9 10 11

 

 

if (7 < 6)

// codigo aqui

else (7 > 6)

// 7 8 9 10 11 <- vai pro meio da metade

if (7 < 9)

// 7 8

if (7 < 8) < pega qualquer um dos dois e compara logo em seguida

// 7 = 7

Compartilhar este post


Link para o post
Compartilhar em outros sites

Tente usar arvore binaria ou Hash para organizar os itens em memoria. Caso não de pra fazer faça assim:

 

Quando chegar uma palavra, pule para o meio da lista

Depois verifique se essa palavra vai estar a esquerda ou a direita da sua lista

Independentemente da direção pule para o meio da metade e faça isso até achar sua palavra

 

Algo assim:

 

1 2 3 4 5 6 7 8 9 10 11

 

 

if (7 < 6)

// codigo aqui

else (7 > 6)

// 7 8 9 10 11 <- vai pro meio da metade

if (7 < 9)

// 7 8

if (7 < 8) < pega qualquer um dos dois e compara logo em seguida

// 7 = 7

Acho que essa é a solução mais próxima do ideal, muito obrigado, vou utilizá-la :)

Compartilhar este post


Link para o post
Compartilhar em outros sites

×

Informação importante

Ao usar o fórum, você concorda com nossos Termos e condições.