[ALGORITMO] Nuovo algoritmo di ricerca

[Mauri94]

Salve a tutti. Tutto ciò che presenterò è solo un idea partorita pochi secondi fa e su cui non ho lavorato per niente. Sono uno studente di informatica agli inizi, quindi ho conoscenze davvero scarse sull'argomento. Non prendetemi per stupido se tutto ciò che presenterò è banale, d'altronde è solo una idea che non avrei problemi a vedere smentita immediatamente. Dunque, ciò che vorrei presentare è un nuovo algoritmo di ricerca. Dunque, come funziona sostanzialmente?

- Condizioni:

1) E' necessario un VETTORE , o una LISTA, che non abbia una dimensione costante, ma variabile ;

2) Il contenuto del vettore sia formato da numeri interi ;

- Esposizione:

Dati in input una serie di numeri interi, questi vengono memorizzati all'interno di un vettore a dimensione variabile. La particolarità sarà far corrispondere il numero inserito all'indice del vettore. Ad esempio:

Input: 3 - 5 - 1
Indice 0 del vettore -> Vuoto
Indice 1 del vettore -> 1
Indice 2 del vettore -> Vuoto
Indice 3 del vettore -> 3
Indice 4 del vettore -> vuoto
Indice 5 del vettore -> 5

Quindi potremmo scrivere:

Vett [N] <- Intero
App <- Intero
Scrivi "Inserisci un numero intero"
Leggi App;
Vett [App] = App;

In questo modo, per effettuare la ricerca all'interno del vettore potremmo semplicemente fare:

// Vettore già riempito con il criterio precedente
X <- Intero 
Scrivi "Inserisci l'elemento da cercare" 
Leggi X;
Se (X=Vett[X])
    Scrivi "L'elemento è stato trovato."

Il concetto di base è questo, ma ci sarebbe tanto da dire. Ora essendo ignorante in materia, in termini di tempo 'posso immaginare' sia più veloce di una ricerca qualunque, anche se non ne ho la certezza.

- Difetti:

1) Enorme spreco di locazioni di memoria che non potrebbero essere riempite ;

2) Non è possibile inserire due volte lo stesso elemento ;

3) Limite per la tipologia di elementi che posso ricercare .

- Pregi:

1) Probabile riduzione di tempo di ricerca ;

Senza aggiungere altro, anche se i difetti non sono banali, a voi la parola.

[infinitejustice]

La tua idea è nota come Hashing e qualcuno ci ha pensato qualche anno fa

[Mauri94]

Ah ti ringrazio per avermelo fatto notare, avrei voluto cercare ma non sapevo quale parola chiave inserire su google. Ora allora mi faccio un giro sull'argomento =)

[oregon]

Non ho capito bene ... se inserisco il valore 1233208388 devo *comunque* creare tutti gli elementi precedenti ?

Ma che idea è ? Che avevi fumato ?

[Mauri94]

Si esatto. L'unico pregio sarebbe il tempo di ricerca, cioè basterebbe solo una ricerca.

[infinitejustice]

Quello che devi fare è creare una funzione che traduca una chiave in un indirizzo unico all'interno della tua struttura dati. Il problema è che ipoteticamente due chiavi diverse dovrebbero avere un indirizzo (posizione) diversa. Nella realtá questo non accade. Si parla di collisioni. Esiston diverse tecniche per gestire queste collisioni (linear probing, double hashing, cuckoo hashing, ...).

Visto che ti han rubato l'idea dell'hashing, potresti cocnentrarti su una nuova tecnica di gestione delle collisioni, per quanto le attuali siano gia particolarmente efficienti.