Ricerca in archivio

[posta10100]

Ciao a tutti!!
Ho questo problemino che mi sta, è proprio il caso di dirlo, facendo perdere un sacco di tempo!!!
Ho un archivio composto da alcuni milioni di elementi.
Devo scrivere un metodo che, dato un elemento, mi dica se l'elemento è presente nell'archivio e dove.

La soluzione più semplice è quella di scorrere l'archivio in cerca dell'elemento e, nel caso lo si trovi, restituire il suo indice.
I problemi sono 2: la ricerca viene ripetuta molte migliaia di volte e molto spesso l'elemento non è presente e deve quindi essere aggiunto.

Purtroppo questa soluzione è da buttare perché è veramente troppo lenta!!!

Qualcuno ha una idea di come poter cercare in maniera furba il valore nell'archivio, sono disposto anche a modificare la struttura dell'archivio pur di venirne fuori....

Grazie dell'aiuto!!!

Luca.

[ginfizz]

Ciao,
che linguaggio di programmazione e che tipo di archivio ?

[posta10100]

Il linguaggio è il c++, ma non importa, mi basta un'idea su cui lavorare...

Nell'archivio sono presenti dei "unsigned long long" da 64 bit.

Hai qualcosa per le mani?

[ginfizz]

Purtroppo sul C++ avevo fatto qualcosina 10 anni fa, ma anche allora un problema simile mi avrebbe messo in difficolta'. Ora non mi ricordo piu' niente.
Ora preferisco linguaggi di piu' alto livello.
Ad ogni modo presumo che "unsigned long long" siano numeri da 8 bytes. Se e' cosi' mi viene il dubbio che il rallentamento sia dovuto al fatto che l'elemento da cercare venga immesso in forma decimale, e cercato in questo formato, facendo la conversione binario ->decimale su ogni elemento. Se la mia supposizione e' giusta potresti invece cercarlo nell'archivio in modo bruto, convertendo il dato decimale in binario e facendo un confronto byte per byte.
Se gia' fai cosi' un altro trucco potrebbe essere quello di ordinare gli elementi in ordine crescente. La ricerca potrebbe essere effettuata con salti da 10 mila-100 mila elementi alla volta. Appena viene trovato un elemento maggiore del valore da cercare si torna indietro elemento per elemento, fino a trovare l'elemento corrispondente o uno minore rispetto al valore cercato.
Altro non saprei. Ci ho provato

[posta10100]

Innanzitutto grazie dell'interessamento!!!

Avevo pensato anche io al confronto byte per byte ma mi sa che il codice macchina faccia già un confronto simile (ho visto come lavora un compilatore per PIC e questo pensa faccia lo stesso...).

Anche a ordinare l'archivio avevo pensato, in un archivio ordinato si può fare una ricerca dicotomica (si dice così ) e analizzare solo piccole parti di database... il mio problema è che ogni volta che aggiungo un elemento devo riordinare l'archivio... anche se forse usando lo stesso trucco della ricerca non è così lento... ma deve essere fatto comunque un sacco di volte...

In realtà la posizione all'interno dell'archivio mi serve per capire chi è arrivato prima e chi dopo, se riordino l'archivio mi devo portare dietro anche questa informazione, raddoppiando la dimensione del database!!!

Sembra non esserci via d'uscita... tempo o memoria... e dovendo girare su winzozz la memoria è importante.
Non so se lo sai ma la bestiaccia non accetta array più grandi di poco meno di 64MB... altrimenti, senza dire niente a nessuno da un simpatico errore (che ovviamente non visualizza) e chiude il programma!

Se ti viene qualche altra idea...

Grazie!!

Luca.

[ginfizz]

Innanzitutto grazie dell'interessamento!!!

Di niente, cosi' forse mi tolgo un po' di ruggine che si e' accumulata su queste cose ...

Avevo pensato anche io al confronto byte per byte ma mi sa che il codice macchina faccia già un confronto simile (ho visto come lavora un compilatore per PIC e questo pensa faccia lo stesso...).

beh, qualasiasi sia il linguaggio usato, il codice macchina risultante dopo la compilazione dovrebbe (con il condizionale quindi presumo) fare un confronto byte per byte, qualsiasi tipo di dato si confronti. Il problema e' che se nel sorgente usi un numero esadecimale o decimale cercando una equivalenza negli elementi dell'array con l'operatore "=" o simili, il codice macchina deve fare due operazioni: convertire il numero da cercare in binario, poi convertire l'elemento corrente in binario e poi fare il confronto byte per byte.
Se invece lo cerchi come stringa il codice macchina non deve fare nessuna conversione e quindi dovrebbe (sempre con il condizionale) essere piu' veloce.
Potresti trasformare quell' array numerico in array stringa ?
Inoltre la gestione dell'array potrebbe allungare i tempi.
Esiste in C++ un operatore che permetta la ricerca di una stringa all'interno di un'altra ?
Se la risposta e' si potresti trasformare l'array in una stringa di bytes unica da 1-2 mega (PS: da moltiplicare per otto ....) .
Qual'e' la dimensione massima delle variabili stringa ?
Supponendo che sia 64kbytes, carichi in una variabile 64 k di stringa alla volta ed effettui la ricerca della stringa con l'operatore suddetto di ricerca delle sottostringhe. Se trova la corrispondenza (dopo esserti accertato che la posizione sia un multiplo esatto di otto) e' facile risalire con un semplice calcolo alla posizione assoluta all'interno dell'archivio.

Anche a ordinare l'archivio avevo pensato, in un archivio ordinato si può fare una ricerca dicotomica (si dice così ) e analizzare solo piccole parti di database... il mio problema è che ogni volta che aggiungo un elemento devo riordinare l'archivio... anche se forse usando lo stesso trucco della ricerca non è così lento... ma deve essere fatto comunque un sacco di volte...

si certo: se l'inserimento e' molto frequente allora si allungano troppo i tempi. E poi se ti serve ricavare anche l'ordine di inserimento non e' fattibile.
Spero che qualcuno sappia darti indicazioni piu' precise e spero di non aver scritto troppe fesserie

[posta10100]

[
beh, qualasiasi sia il linguaggio usato, il codice macchina risultante dopo la compilazione dovrebbe (con il condizionale quindi presumo) fare un confronto byte per byte, qualsiasi tipo di dato si confronti. Il problema e' che se nel sorgente usi un numero esadecimale o decimale cercando una equivalenza negli elementi dell'array con l'operatore "=" o simili, il codice macchina deve fare due operazioni: convertire il numero da cercare in binario, poi convertire l'elemento corrente in binario e poi fare il confronto byte per byte.

Non ho potuto verificare, quindi faccio anche io delle supposizioni.
Io lavoro su una macchina a 64 bit, quindi teoricamente per fare un confronto tra 2 numeri a 64 bit dovrebbe bastare una semplice operazione, nel caso di macchine a 32 bit dovrebbe farlo in 2 passi, se la prima parte è diversa allora non fa la seconda.
Questo è quanto ho visto con il compilatore per i PIC (avevo bisogno di vedere come venivano eleborati i dati, col PC non ci provo nemmeno!!!) e penso funzioni così ovunque!!

Potresti trasformare quell' array numerico in array stringa ?
Inoltre la gestione dell'array potrebbe allungare i tempi.
Esiste in C++ un operatore che permetta la ricerca di una stringa all'interno di un'altra ?

Trasformarlo in una stringa sarebbe valido se winzozz non avesse il problema della dimensione dell'array...

Proverò a riordinare l'array... o meglio i suoi pezzetti visto che per colpa di win devo fare tanti piccoli array da 64MB... ora non riesco più a trovare il link alla pagina, domani al lavoro lo cerco e lo posto, è un problema noto a microsoft, problema che si sono guardati bene dal risolvere!!!

Ciao,

Luca.

[ginfizz]

Mah. Preferisco non addentrarmi in questo ginepraio, ma ci sarebbe da dire che nel PIC probabilmente programmi in un linguaggio molto simile all'Assembly, mentre il C++ va compilato, e quella semplice instruzione di uguaglianza potrebbe venire trasformata in una serie di istruzioni macchina da richiedere una miriade di cicli.

Ad ogni modo prova qui: http://www.msfn.org/board/Programming-C ... c-f66.html: e' un forum dove ci sono dei veri guru in tutti i campi. Quando ho posto quesiti impossibili su windows ho trovato risposte insperate: c'e' veramente gente in gamba.
non mi e' ancora capitato di porre quesiti di programmazione, ma se il livello e' quello fa ben sperare.
In bocca al lupo

[best89]

io ordinerei gli elementi con la procedura di ordinamento quick sort e poi farei la ricerda binaria logaritmica....sono i metodi piu veloci ke conosco...

[posta10100]

Sono riuscito, attraverso un archivio ordinato, a fare una ricerca abbastanza veloce, ora resta il problema di mettere gli elementi nell'archivio in maniera ordinata, senza dover riordinare tutto ogni volta che devo aggiungere un elemento!!!

Qualche idea?

Grazie!