Newsgroup: it.comp.os.win.xp
Titolo: [OT] Spiegate a zipman cosa è un'organizzazione hash visto che è convinto che occorra fare una ricerca per trovare un dato


STRONZATE MEGAGALATTICHE in quanto l'organizzazione hash è fatta
apposta per fare un seek diretto alla posizione della chiave da trovare
e non c'è alcuna ricerca da fare, in quanto la chiave viene
trasformata in un indirizzo attraverso la funzione hash e con 1 solo
accesso si fa il seek a
quell'indirizzo.
Sei proprio un imbecille.
Saluti da P4

 Saluti da P4
http://www.zimuel.it/conferenze/tabellehash.pdf
c' è scritto in italiano: "Vedremo che in media il tempo di ricerca di
un elemento
in una tabella hash è O(1)."
Saluti da P4

 Saluti da P4
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 
http://www.zimuel.it/conferenze/tabellehash.pdf
Che proprio sotto il titolo scrive
"Risoluzione delle collisioni: concatenazione,
indirizzamento aperto"
Hai idea di cosa significhi?
C:\>iao Angelo


 a meno di collisioni.
infatti nei discorsi fatti ho parlato di caso ideale, ma il problema di
fondo è che zipmann ignorava clamorosamente cosa era una
organizzazione hash ed era convinto che occorresse fare una ricerca
binaria invece il vantaggio dell'organizzazione hash è accedere
direttamente alla chiave (ovviamente salvo collisioni e in tal caso gli
accessi aumentano da 1 ad qualcosa di più).
Saluti da P4

> di un elemento in una tabella hash è O(1)."
Vedi che quando dico che sei un COGLIONE non mi sbaglio?
Tu non hai letto (come se ci fossero dubbi in proposito) il documento
che hai linkato, che afferma ESATTAMENTE le stesse cose che ho affermato
io.
O(1) è la complessità dell'algoritmo ideale, ovvero quello in cui ogni
possibile valore viene identificato da una chiave nell'array. A pag. 8
chiarisce i motivi per cui tale metodo non è applicabile, ovvero il
fatto che lo spazio dei valori U è spoporzionatamente maggiore dello
spazio delle chiavi K, per cui vi sarebbe uno spreco di chiavi immenso
(che si tradurrebbe in perdita di spazio in RAM) se si utilizzasse una
tabella siffatta.
La soluzione al problema viene descritta da pag.9 a pag.11, mentre a
pag. 12 riporta giustamente che la complessità della ricerca
nell'applicazione del metodo delle tabelle hash è, nel caso peggiore,
O(n) [io qui avevo comunque menzionato il caso reale in cui la
complessità è O(log n), sempre assumendo che la funzione di hash abbia
una distribuzione uniforme].
A pag.13 spiega (come avevo detto precedentemente) che il calcolo
dell'hash può essere assimilato a O(1) (per cui non inficia sul
rendimento dell'algoritmo di ricerca); da pag.14 in avanti seguono vari
teoremi e dimostrazioni matematiche sull'uso delle funzioni hash.
Quindi LEGGI E CREPA te li puoi ficcare nel didietro, dato che sei tu il
primo ignorante che non sa leggere, nemmeno in italiano.
------------------------------------------------------------------------
-- 
Flavio Visentin
Membro del CICAP
Comitato Italiano per il Controllo delle Affermazioni di P4

 dell'algoritmo da te descritto.
E' inutile che replichi perchè hai già dimostrato che non vali un
cazzo!!!!
Ti ho già spiegato come funziona la cosa te lo rispiego per l'ultima
volta:
- vuoi memorizzare dei dati in una tabella o su un archivio su disco
- i dati sono delle chiavi (con eventualmente associati altri valori)
- attraverso una funzione hash trasformi la chiave in un indirizzo e
vai a memorizzare la chiave in quella locazione delle tabella o in quel
record del disco
- in tal modo quando vorrai ricercare un dato in quella enorme tabella
o archivio è sufficiente trasformare la chiave da ricercare in un
indirizzo e poi con 1 unico accesso accedere a quell'indirizzo dove si
trova la chiave (cioè ricerca è inesistente!!!)
In assenza di organizzazione hash invece dovresti utilizzare la ricerca
binaria da te citata ma che ha una complessità O(log2n) cioè
mediamente dovresti fare log2n tentativi di accesso fino a trovare la
chiave che volevi (fra l'altro nel caso peggiore hai O(n) cioè
dovresti leggere tutte le chiavi!!!), mentre nel caso di organizzazione
hash il tempo medio inteso come numero di accessi in memoria ram o
disco è O(1) + 2 o 3 accessi per risolvere le collisioni ma comunque
il tempo medio è un numero indipendente da n.
L'organizzazione hash si usa anche per grandissimi archivi, ma
ovviamente non devi usare funzioni hash banali e la tabella sarà
limitata e avrai un maggior numero di collisioni, ma comunque anche se
le collisioni nel caso schifoso ti portano a fare qualche altra
manciata di accessi hai che la complessità è molto più piccola di
log2n della ricerca binaria.
Saluti da P4


STRONZATE MEGAGALATTICHE in quanto l'organizzazione hash č fatta
apposta per fare un seek diretto alla posizione della chiave da trovare
e non c'č alcuna ricerca da fare, in quanto la chiave viene
trasformata in un indirizzo e con 1 solo accesso si fa il seek a
quell'indirizzo.


 fermo alla dicotomica.
Tu ignori che l'organizzazione hash NON è un semplice archivio
ordinato dove le chiavi sono messe a caso, ma sono preventivamente
memorizzate all'indirizzo generato dalla funzione hash!! Ancora una
volta dimostri la tua COMPLETA IGNORANZA e STUPIDITA'.
Saluti da P4

 log2n della ricerca binaria.
Aridaje. Dimmi quanti accessi debbo fare per accedere a questo benedetto
dato. Non è così difficile.


 FAMMI VEDERE IL CODICE DI QUESTA FUNZIONE!!!!
Per tua informazione le tabelle hash sono implementate in tutti i
moderni linguaggi di programmazione (vedi java, c#, ecc.). Provale tu
stesso se non credi che esistano!
Saluti da P4


Forse non hai capito. Io so perfettamente che esistono le
implementazioni di hash table, ma io voglio che TU mi mostri un
centinaio di righe di codice che fanno quello che tu dici, ovvero la
funzione di hash che, data in input una stringa arbitraria (chiave di un
array associativo) mi restituisca in output l'indice dell'array
corrispondente (unico caso in cui un hash table è O(1)).
Sai, la mia ignoranza non mi permette di trovare autonomamente una
soluzione al problema, quindi richiedo a te, sommo guru della
programmazione, di illuminarmi (magari dandoti fuoco :-)


 accessi.
FALSISSIMO.
Log2n è il valore medio. Il caso peggiore è O(n)
Vedo che non sai nemmeno come funziona la ricerca dicotomica, ora te la
spiego:
- hai un archivio ordinato e vuoi ricercare una chiave
- dividi l'archivio a metà
- se la chiava sta nella prima metà la ricerchi la (sai che sta la
perchè è ordinato), se sta nella secondo metà la ricerchi nella
seconda e scarti l'altra metà
- continui a dividere la parte fino a che non trovi la chiave
- nel caso sfortunatissimo devi dividere fino a che ti ritrovi con 2
soli elementi ovvero hai acceduto in totale a tutti gli n elementi.
Saluti da P4

mi correggo ho detto una cazzata è log2n visto che scarti gli elementi.

 chiave in un indirizzo e accedere direttamente senza fare ricerche.
Pezzo di P4-fake, quando impari a quotare in modo decente ??

 mi correggo ho detto una cazzata č log2n visto che scarti gli elementi.
Azz... finalmente te ne sei reso conto :-)
meglio tardi che mai :-)


 meglio tardi che mai :-)
guarda che ho solo sbagliato il calcolo della ricerca binaria ma non
cade nulla su quanto ho detto dell'organizzazione hash che ho ragione
io e tu insistevi che occorreva fare la ricerca binaria non capendo
nulla dell'organizzazione hash.
L'organizzazione hash è O(1), mentre la ricerca binaria è O(log2n) e
con l'organizzazione hash non si fanno ricerche delle altrimenti cade
l'utilità della organizzazione hash
Saluti da P4

 meglio tardi che mai :-)
Ha solo sbagliato un calcolo sulla ricerca binaria tirata in ballo da te, 
che non ha nulla a che vedere con l'organizzazione hash di cui tu ignoravi 
totalmente il funzionamento. 

 Hai idea di cosa significhi?
﻿In una tabella hash in cui le collisioni sono risolte per
concatenazione, nell’ipotesi di uniformità semplice della funzione
hash, una ricerca con successo richiede in media tempo Θ(1+α)
Per cui Θ(1+c(α/2))=Θ(1+α) con 0<= c <1.
• Da questa analisi se ne deduce che se il numero di posizioni
nella tabella hash è almeno proporzionale al numero di elementi
nella tabella, ossia n=O(m), si ha α=n/m=O(m)/m=O(1). Quindi
la ricerca richiede in media tempo costante.
http://www.zimuel.it/conferenze/tabellehash.pdf
Saluti da P4

 volta dimostri la tua COMPLETA IGNORANZA e STUPIDITA'.
Miiii ... detto da un vero intenditore (di stupidita' ! ) come te , e' un
vero complimento , niente niente ti stessi innamorando di ZiPMan ??