Pesquisa Binária em VB  XML
Índice dos Fóruns » Outras Linguagens
Autor Mensagem
marco_andre
Debugger

Membro desde: 04/01/2008 23:28:53
Mensagens: 50
Localização: Recife, PE - Brasil
Offline

Boa tarde, estou desenvolvendo uma aplicação para um Pocket PC utilizando o software Basic4ppc .
Tenho um banco de dados em txt (que é importado de outro sistema) e necessito utilizar uma busca binária para recuperar algumas informações dentro dele de forma mais rápida.
Primeira dúvida: É possível utilizar busca binária em um arquivo?
Segunda: Se for possível, como eu posso fazer isso? Como eu conto as linhas até o final do arquivo?

Alguém pode me dar uma ajuda com isso?
vlw

--
Att,

Marco André Machado
luxu
GUJ Ranger
[Avatar]

Membro desde: 28/10/2008 18:23:12
Mensagens: 881
Localização: Presidente Prudente/SP
Offline

que eu saiba naum é possível naum, pq busca binária depende dos dados estarem ordenados o q naum é o caso de arquivo...



zicadopv.wordpress.com
[WWW]
marco_andre
Debugger

Membro desde: 04/01/2008 23:28:53
Mensagens: 50
Localização: Recife, PE - Brasil
Offline

Meus dados estão ordenados sim. Meus arquivo tem um estrutura simplificada assim: codigo_item; descricao_item.
Com isso eu consigo ter um ordenação correta pelo codigo do item.

--
Att,

Marco André Machado
entanglement
GUJ Hacker

Membro desde: 26/09/2009 09:18:56
Mensagens: 5750
Offline

Se as linhas de seu arquivo tiverem todas o mesmo tamanho, não é preciso indexá-lo (ou seja, determinar em que posição começa ou termina cada linha). Senão, é preciso fazer uma indexação para você poder determinar rapidamente como ir para uma determinada linha.
marco_andre
Debugger

Membro desde: 04/01/2008 23:28:53
Mensagens: 50
Localização: Recife, PE - Brasil
Offline

Nem todos os códigos tem o mesmo tamanho, alguns tem 6 dígitos, outros mais. As descrições tem tamanhos variáveis tb.
O que separa um campo do outro é um ; (ponto-e-vírgula). Como essa indexação poderia ser feita?

--
Att,

Marco André Machado
entanglement
GUJ Hacker

Membro desde: 26/09/2009 09:18:56
Mensagens: 5750
Offline

Bom, não sei se ajuda muito. Como seu arquivo pode exceder a quantidade de memória RAM disponível, espero que o número de linhas, vezes 4, não exceda a quantidade de memória disponível. Se isso realmente for verdade, você pode até criar um array de inteiros que contenha as posições iniciais de cada linha. A idéia é que você leia esse arquivo por inteiro mas uma vez só, mas em vez de carregar a linha inteira em memória, anote só a posição (offset) dela. Como o arquivo está ordenado por código, você poderia fazer uma espécie de busca binária onde, para pegar a linha N para poder fazer a comparação, você pegaria esse array contendo os offsets para poder achar a linha N para poder lê-la e efetuar a comparação.

marco_andre
Debugger

Membro desde: 04/01/2008 23:28:53
Mensagens: 50
Localização: Recife, PE - Brasil
Offline

entanglement wrote:Bom, não sei se ajuda muito. Como seu arquivo pode exceder a quantidade de memória RAM disponível, espero que o número de linhas, vezes 4, não exceda a quantidade de memória disponível. Se isso realmente for verdade, você pode até criar um array de inteiros que contenha as posições iniciais de cada linha. A idéia é que você leia esse arquivo por inteiro mas uma vez só, mas em vez de carregar a linha inteira em memória, anote só a posição (offset) dela. Como o arquivo está ordenado por código, você poderia fazer uma espécie de busca binária onde, para pegar a linha N para poder fazer a comparação, você pegaria esse array contendo os offsets para poder achar a linha N para poder lê-la e efetuar a comparação.



Obrigado entanglement pela ajuda.
Vou verificar se isso funciona.
wilds87
JavaBaby
[Avatar]

Membro desde: 07/07/2008 08:55:33
Mensagens: 99
Localização: POA
Offline

Para fazer uma busca binária, você deve ter uma estrutura de arvore binária.
Quando você carregar os "objetos" do texto, monte-os numa arvore, só assim você terá melhor performance numa busca.

Atenciosamente,
William Gubiani da Silva.

PPL : COD MW2, DOTA

[Email] [MSN]
Mikhas
Virtual Machine Man
[Avatar]

Membro desde: 17/06/2008 11:10:50
Mensagens: 677
Localização: São Paulo
Offline

Acho que você poderia carregar as linhas de seu arquivo em uma estrutura de dados (uma classe), colocalos em uma lista ou array e implementar o algoritmo de busca binaria.

Refractor 1.6 - Easy reflection framework
Agora muito mais rapido!
Raze - The fastest CSS selector engine




[Email] [MSN]
entanglement
GUJ Hacker

Membro desde: 26/09/2009 09:18:56
Mensagens: 5750
Offline

Mikhas wrote:Acho que você poderia carregar as linhas de seu arquivo em uma estrutura de dados (uma classe), colocalos em uma lista ou array e implementar o algoritmo de busca binaria.


Se o arquivo for pequeno até dá. Se for um pouco grande já dá problemas, já que há pouca memória RAM para trabalhar. Um exemplo é quando o arquivo está em um Micro-SD - pode ter até quase 2GB - mas tipicamente a memória RAM é bem menos que isso.
marco_andre
Debugger

Membro desde: 04/01/2008 23:28:53
Mensagens: 50
Localização: Recife, PE - Brasil
Offline

entanglement wrote:Se as linhas de seu arquivo tiverem todas o mesmo tamanho, não é preciso indexá-lo (ou seja, determinar em que posição começa ou termina cada linha). Senão, é preciso fazer uma indexação para você poder determinar rapidamente como ir para uma determinada linha.


Como essa indexação poderia ser feita?
Seria um mapeamento dos códigos dos produtos na memória do dispositivo?
 
Índice dos Fóruns » Outras Linguagens
Ir para:   
Powered by JForum 2.1.8 © JForum Team