como calcular o comprimento médio da sonda para sucesso e falha - Sonda linear (tabelas hash) [fechado]

Question

Estou fazendo uma tarefa para minha aula de Estruturas de Dados.fomos solicitados a estudar sondagens lineares com fatores de carga de 0,1, 0,2, 0,3, .... e 0,9.A fórmula para teste é:

O comprimento médio da sonda usando sondagem linear é aproximadamente

Sucesso -> (1 + 1/(1-L)**2)/2
ou
Falha--> (1+1(1-L))/2.

somos obrigados a encontrar o teórico usando a fórmula acima que eu fiz (basta inserir o fator de carga na fórmula), então temos que calcular o empírico (o que não tenho certeza de como fazer).aqui está o resto dos requisitos

** Para cada fator de carga, 10.000 ints positivos gerados aleatoriamente entre 1 e 50000 (inclusive) ser inserida numa tabela do tamanho "direito", onde "direito" é com base restritamente no factor da carga Estás a testar.Repetições são permitidas.Certifique-se de que a sua fórmula para aleatoriamente o ints gerado está correcto.Há uma uma classe chamada Aleatório em java.util.UTILIZAR isto!Depois de uma tabela da direita (baseada em cima de L) o tamanho é carregado com 10,000 ints, fazer 100 pesquisas de recentemente ints aleatórios gerados a partir do intervalo de 1 a 50000.Calcular a média comprimento da sonda para cada um dos dois fórmulas e indicar os denominadores utilizado em cada calculationAssim, por exemplo, cada teste para uma carga de .5 teria uma tabela de > > size aproximadamente 20 000 (ajustado para ser prime) e, da mesma forma, cada teste para um .9 carga teria uma tabela de tamanho aproximado 10,000/.9 (novamente ajustado para ser prime).

O programa deve ser executado exibindo os vários fatores de carga testados, a sonda média para cada pesquisa (os dois denominadores usados ​​para calcular as médias adicionarão a 100) e as respostas teóricas usando a fórmula acima..**

como calculo o sucesso empírico?

Aqui esta o meu codigo ate agora:

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)
{

}

}

Answer 1

Você deve levar em conta que o Java HashTable usa uma implementação de endereçamento fechado (sem sondagem), portanto você tem compartimentos separados nos quais muitos itens podem ser colocados.Não é isso que você procura em seus benchmarks.não tenho certeza sobre HashMap implementação, mas acho que também usa endereçamento aberto.

Então esqueça as aulas de JDK.como você deseja calcular valores empíricos, você deve escrever sua própria versão de uma tabela hash que use o endereçamento aberto implementação com sondagem linear mas você deve ter o cuidado de contar o comprimento da sonda sempre que tentar obter um valor do hashmap.

Por exemplo, você pode escrever seu hashmap e depois cuidar de ter

class YourHashMap
{
   int empiricalGet(K key)
   {
     // search for the key but store the probe length of this get operation

     return probeLength;
   }
}

Em seguida, você pode compará-lo facilmente pesquisando quantas chaves deseja e calculando o comprimento médio da sonda.

Caso contrário, você pode simplesmente fornecer ao hasmap a capacidade de armazenar o comprimento total da sonda e a contagem de solicitações solicitadas e recuperá-las após a execução do benchmark para calcular o valor médio.

Este tipo de exercícios deve provar que o valor empírico concorda com o teórico.Portanto, leve também em consideração o fato de que você pode precisar de muitos benchmarks e depois faça a média de todos eles, garantindo que a variância não seja muito alta.