Executando verificação de segurança...
3
Moyza
1 min de leitura ·

Problema com algoritmo de pesquisa

Estou trabalhando em um projeto eu estou com uma demanda de fazer uma barra de pesquisa em uma tabela, pensei em fazer com um algoritmo simples de pesquisa linear, usando For, mas depois fiquei pensando que eu poderia melhorar o desempenho dessa pesquisa utilizando de outros algoritmos como o de pesquisa binária, mas não sei se é ideal pois para executar esse algortmo eu necessitaria ordenar a lista, então teria que usar dois algoritimos nessse caso que ficaria mais lento, então não sei se é melhor utilizar a busca linear mesmo ou fazer a ordenação e usar o pesquisa binária depois. Gostaria que algum dev mais experiênte pude-se me orientar.

1
0
1
uriel

Tabela?
Tabela em banco de dados?

Se for banco de dados isso já tem neles!

Se for sei lá uma tabela simples em HTML
Não precisaria se matar pra melhorar o algoritmo!
Quase nada fara isso ser lento

1
Moyza
Autor
Autor

Entendi, mas eu vou mexer com uma grande quantidade de dados e pode acabar ficando lento, esqueci de especificar mesmo, é tabela Html.

1
uriel

Não é muito certo lidar com uma grande quantidade de dados no HTML!
Você pode usar web Worker para lidar melhor com essa quantidade de dados!

Pq JS lida na thread principal com tudo. Se tiver muita coisa vai travar!
o DOM já aguenta mais coisas! Mas se precisa manipular com JS use web Worker
que é feito pra isso!

Olha esse artigo não é diretamente o que vc precisa,
mas ele da um vislumbre das coisas!

https://dev.to/urielsouza29/o-objeto-atomics-do-js-uma-introducao-5d17

1
Moyza
Autor
Autor

Eu já tinha dado uma estudada em web Worker, mas não tinha passado pela minha cabeça nesse caso, parece ser uma ferramenta muito útil. Vou ler o artigo sim, obrigado pela sugestão.

1
clovisdanielss

Sim, é pre-requisito da busca binária que a lista em questão esteja ordenada.

Se não tiver como garantir que os elementos inseridos na lista sejam inseridos ordenados, provavelmente não vale apena ordenar e aplicar busca binária.

Mas vale a pena fazer uma análise.
Encontrar um elemento em uma lista é O(n), enquanto a busca binária é (logn), um algoritmo de ordenação é de O(nlogn) ~ O(n²), dependendo de qual você esteja usando. Se tiver propriedades muito específicas você conseguiria ordenar até com O(n) com Radix Sort, mas não acho que seja o caso. Por fim, usar qualquer desses juntamente a busca binária daria O(logn + nlogn) que é O(nlogn), ou seja, ficaria melhor usar busca simples na lista.

Claro, tô imaginando o cenário mais simples possível pq você não falou muito, se por exemplo forem realizadas várias buscas consecutivas no mesmo array, ordenar e realizar apenas buscas binárias pode melhorar a performace.

Por fim, termino incentivando você a pesquisar um pouco mais antes de perguntar. Pois qualquer pesquisa rápida responderia que busca binária exige que a entrada esteja ordenada (Se não não dá para saber para qual lado deve ir).

Outra coisa, se a pesquisa está lenta, avalie se lista é a melhor estrutura de dados para o problema em questão.

1
Moyza
Autor
Autor

Entendi, faz sentido, obrigado pela ajuda, com essas informações ficara bem mais facil para mim achar a solução, acho que talvez eu tenha alterar mesmo minha estrutura de dados, ou até mesmo ja guardar os dados já ordenados e só aplicar a pesquisa binária depois.

0
andreliberato

Se for uma tabela HTML sugiro que dê uma olhada na lib datatables. Nela já tem várias funcionalidades como paginação, campo de busca, ordenação das colunas e várias outras coisas.

Mas se você só quer uma solução básica no HTML meio que a quantidade de dados pra deixar essa busca perceptivelmente lenta tem que ser muito grande. Então, se não for o caso, pode implantar usando um laço comum mesmo. As vezes a abordagem mais direta é a melhor.