Cómo calcular la duración media de la sonda para el éxito y el fracaso - sonda lineal (Tablas Hash) [cerrada]
-
23-09-2019 - |
Pregunta
Estoy haciendo un trabajo para mi clase de estructuras de datos. nos pidieron a estudio sondeo lineal con factores de carga de 0,1, 0,2, 0,3, ...., y 0.9. La fórmula para la prueba es:
La duración media de la sonda usando el sondeo lineal es aproximadamente
Éxito -> (1 + 1 / (1-L) ** 2) / 2
o
El no -.> (1 + 1 (1-L)) / 2
estamos obligados a encontrar el teórico utilizando la fórmula anterior que hice (sólo tiene que enchufar el factor de carga en la fórmula), entonces tenemos que calcular el empírica (que no lo bastante seguro de cómo hacerlo). aquí está el resto de los requisitos
** Para cada factor de carga, 10.000 enteros positivos generados aleatoriamente entre 1 y 50000 (inclusive) voluntad ser insertado en una mesa de la tamaño "correcto", en el "derecho" es estrictamente basado en el factor de ocupación que está probando. se permiten repeticiones. Asegúrese de que su fórmula de azar ints generados es correcta. Hay un clase llamada aleatoria en java.util. UTILIZAR ¡eso! Después de una tabla de la derecha (basada sobre L) tamaño se carga con 10 000 enteros, hacen 100 búsquedas de nuevo enteros aleatorios generados a partir de la gama de 1 a 50000. calcular el promedio longitud de la sonda para cada uno de los dos fórmulas e indicar los denominadores utilizado en cada calculationSo, por ejemplo, cada prueba para una carga de 0,5 tendría una tabla de>> Tamaño aproximadamente 20.000 (ajustado para ser primo) y del mismo modo cada prueba para una 0.9 carga tendría una tabla de tamaño aproximado 10000 / 0.9 (de nuevo ajustado a ser primer).
El programa debe funcionar mostrando el diversos factores de carga probados, la sonda promedio para cada búsqueda (los dos denominadores utilizados para calcular la promedios se sumará a 100), y el respuestas teóricas utilizando la fórmula encima. . **
¿Cómo se calcula el éxito empírico?
aquí es mi código hasta ahora:
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)
{
}
}
Solución
Se debe tener en cuenta que HashTable
de Java utiliza un sistema cerrado de direccionamiento (Sin sonda) la aplicación, por lo que tiene cubos separados en los que muchos artículos se pueden colocar. Esto no es lo que busca en sus puntos de referencia. No estoy seguro acerca de la aplicación HashMap
pero creo que utiliza direccionamiento abierto también.
Así que olvídate de las clases de JDK .. ya que desea calcular los valores empíricos debe escribir su propia versión de una tabla hash que utiliza el direccionamiento abierto aplicación con sondeo lineal , pero se debe tener cuidado de contar la longitud de la sonda cada vez que se intenta obtener un valor del mapa hash ..
Por ejemplo, usted puede escribir su HashMap y luego cuidar de tener
class YourHashMap
{
int empiricalGet(K key)
{
// search for the key but store the probe length of this get operation
return probeLength;
}
}
A continuación, usted puede fácilmente mediante la búsqueda de referencia que el número de teclas que desea y el cálculo de la duración media de la sonda.
De lo contrario, puede simplemente proporcionar a la hasmap la capacidad de almacenar la longitud total de la sonda y el recuento de obtiene solicitado y recuperarlos después de la ejecución de referencia para el cálculo de valor medio.
Este tipo de ejercicios debe probar que los concordatos valor empírico con la teórica. Así que tener también en cuenta el hecho de que es posible que tenga muchos puntos de referencia, y luego hacer la media de todos ellos, asegurando que la varianza no es demasiado alto.