comment calculer la longueur moyenne de la sonde de succès et d'échec - sonde linéaire (des tables de hachage) [fermée]
-
23-09-2019 - |
Question
Je fais une mission pour ma classe Structures de données. on nous a demandé d'étudier linéaire de sondage avec des facteurs de charge de 0,1, 0,2, 0,3, .... et .9. La formule pour le test est:
La longueur moyenne de la sonde à l'aide de palpage linéaire est à peu près
Réussite -> (1 + 1 / (1-L) ** 2) / 2
ou
Le non -> (1 + 1 (1-L)) / 2
.
nous devons trouver la théorie en utilisant la formule ci-dessus que je ne (fiche que le facteur de charge dans la formule), alors nous devons calculer l'empirique (que je pas tout à fait sûr de savoir comment faire). voici le reste des exigences
** Pour chaque facteur de charge, 10.000 ints positifs générés au hasard entre 1 et 50000 (inclus) seront être insérée dans une table de la taille « droit », où « droit » est strictement en fonction du facteur de charge vous testez. Répète sont autorisés. Assurez-vous que votre formule au hasard ints généré est correct. Il y a un classe appelée aléatoire dans java.util. UTILISATION il! Après une table du droit (base taille à L) est chargé avec 10 000 ints, faire 100 recherches de nouvelles ints générés au hasard dans la gamme de 1 à 50000. Calculer la moyenne longueur de la sonde pour chacun des deux formules et indiquent les dénominateurs utilisé dans chaque calculationSo, par exemple, chaque test pour une charge 0,5 aurait une table de>> Taille environ 20 000 (ajusté pour être premier) et de même chaque test pour .9 charge aurait une table de taille approximative 10 000 / 0,9 (encore une fois ajusté pour être premier).
Le programme doit exécuter l'affichage de la divers facteurs de charge testés, le Sonde moyenne pour chaque recherche (les deux dénominateurs utilisés pour calculer la moyennes seront à 100), et réponses théoriques à l'aide de la formule au dessus de. . **
Comment calculer le succès empirique?
voici mon code jusqu'à présent:
import java.util.Random;
/**
*
* @author Johnny
*/
class DataItem
{
private int iData;
public DataItem(int it)
{iData = it;}
public int getKey()
{
return iData;
}
}
class HashTable
{
private DataItem[] hashArray;
private int arraySize;
public HashTable(int size)
{
arraySize = size;
hashArray = new DataItem[arraySize];
}
public void displayTable()
{
int sp=0;
System.out.print("Table: ");
for(int j=0; j<arraySize; j++)
{
if(sp>50){System.out.println("");sp=0;}
if(hashArray[j] != null){
System.out.print(hashArray[j].getKey() + " ");sp++;}
else
{System.out.print("** "); sp++;}
}
System.out.println("");
}
public int hashFunc(int key)
{
return key %arraySize;
}
public void insert(DataItem item)
{
int key = item.getKey();
int hashVal = hashFunc(key);
while(hashArray[hashVal] != null &&
hashArray[hashVal].getKey() != -1)
{
++hashVal;
hashVal %= arraySize;
}
hashArray[hashVal]=item;
}
public int hashFunc1(int key)
{
return key % arraySize;
}
public int hashFunc2(int key)
{
// non-zero, less than array size, different from hF1
// array size must be relatively prime to 5, 4, 3, and 2
return 5 - key % 5;
}
public DataItem find(int key) // find item with key
// (assumes table not full)
{
int hashVal = hashFunc1(key); // hash the key
int stepSize = hashFunc2(key); // get step size
while(hashArray[hashVal] != null) // until empty cell,
{ // is correct hashVal?
if(hashArray[hashVal].getKey() == key)
return hashArray[hashVal]; // yes, return item
hashVal += stepSize; // add the step
hashVal %= arraySize; // for wraparound
}
return null; // can’t find item
}
}
public class n00645805 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
double b=1;
double L;
double[] tf = new double[9];
double[] ts = new double[9];
double d=0.1;
DataItem aDataItem;
int aKey;
HashTable h1Table = new HashTable(100003); //L=.1
HashTable h2Table = new HashTable(50051); //L=.2
HashTable h3Table = new HashTable(33343); //L=.3
HashTable h4Table = new HashTable(25013); //L=.4
HashTable h5Table = new HashTable(20011); //L=.5
HashTable h6Table = new HashTable(16673); //L=.6
HashTable h7Table = new HashTable(14243); //L=.7
HashTable h8Table = new HashTable(12503); //L=.8
HashTable h9Table = new HashTable(11113); //L=.9
fillht(h1Table);
fillht(h2Table);
fillht(h3Table);
fillht(h4Table);
fillht(h5Table);
fillht(h6Table);
fillht(h7Table);
fillht(h8Table);
fillht(h9Table);
pm(h1Table);
pm(h2Table);
pm(h3Table);
pm(h4Table);
pm(h5Table);
pm(h6Table);
pm(h7Table);
pm(h8Table);
pm(h9Table);
for (int j=1;j<10;j++)
{
//System.out.println(j);
L=Math.round((b-d)*100.0)/100.0;
System.out.println(L);
System.out.println("ts "+(1+(1/(1-L)))/2);
System.out.println("tf "+(1+(1/((1-L)*(1-L))))/2);
tf[j-1]=(1+(1/(1-L)))/2;
ts[j-1]=(1+(1/((1-L)*(1-L))))/2;
d=d+.1;
}
display(ts,tf);
}
public static void fillht(HashTable a)
{
Random r = new Random();
for(int j=0; j<10000; j++)
{
int aKey;
DataItem y;
aKey =1+Math.round(r.nextInt(50000));
y = new DataItem(aKey);
a.insert(y);
}
}
public static void pm(HashTable a)
{
DataItem X;
int numsuc=0;
int numfail=0;
int aKey;
Random r = new Random();
for(int j=0; j<100;j++)
{
aKey =1+Math.round(r.nextInt(50000));
X = a.find(aKey);
if(X != null)
{
//System.out.println("Found " + aKey);
numsuc++;
}
else
{
//System.out.println("Could not find " + aKey);
numfail++;
}
}
System.out.println("# of succ is "+ numsuc+" # of failures is "+ numfail);
}
public static void display(double[] s, double[] f)
{
}
}
La solution
Vous devez prendre en compte que la HashTable
Java utilise un adressage fermé (pas de sondage) la mise en œuvre, de sorte que vous avez des seaux séparés dans lesquels peuvent être placés de nombreux articles. Ce n'est pas ce que vous cherchez dans vos repères. Je ne suis pas sûr de la mise en œuvre de HashMap
mais je pense qu'il utilise l'adressage ouvert aussi.
Alors oubliez les classes .. JDK puisque vous voulez calculer les valeurs empiriques que vous devez écrire votre propre version d'une table de hachage qui utilise le adressage ouvert mise en œuvre avec linéaire sondage mais vous devez prendre soin de compter la longueur de la sonde chaque fois que vous essayez d'obtenir une valeur de la table de hachage ..
Par exemple, vous pouvez écrire votre hashmap puis prendre soin d'avoir
class YourHashMap
{
int empiricalGet(K key)
{
// search for the key but store the probe length of this get operation
return probeLength;
}
}
Ensuite, vous pouvez comparer facilement en recherchant le nombre de touches que vous voulez et le calcul de la longueur de la sonde moyenne.
Sinon, vous pouvez simplement fournir la hasmap la capacité de stockage de la longueur totale de la sonde et le nombre de demande et obtient les récupérer après la course de référence pour calculer la valeur moyenne.
Ce genre d'exercices doit prouver que la valeur empirique concordats avec le théorique. Alors, prenez également en compte le fait que vous pouvez avoir besoin de nombreux points de repère, puis faire la moyenne de tous, assurant que la variance est pas trop élevé.