come calcolare la durata media della sonda per il successo e il fallimento - sonda lineare (Hash Tables) [chiusa]

Question

Sto facendo un incarico per la mia classe strutture di dati. ci hanno chiesto di studio per la scansione lineare con fattori di carico di 0,1, 0,2, 0,3, ...., e 0,9. La formula per la prova è:

La durata media della sonda usando la scansione lineare è di circa

Successo -> (1 + 1 / (1-L) ** 2) / 2
o
Fallimento -.> (1 + 1 (1-L)) / 2

ci viene richiesto di trovare il teorico utilizzando la formula di cui sopra, che ho fatto (basta collegare il fattore di carico nella formula), allora dobbiamo calcolare l'empirica (che non del tutto sicuro di come fare). qui è il resto dei requisiti

  

** Per ciascun fattore di carico, 10.000 interi positivi generati casualmente   tra 1 e 50000 (compreso) si   essere inserito in una tabella di   dimensione del "giusto", dove "giusto" è   rigorosamente in base al fattore di carico   si sta testando. Ripete sono ammessi.   Assicurarsi che la formula per caso   interi generati sia corretto. C'è un   classe chiamata a caso in java.util. USO   esso! Dopo una tabella di destra (in base   upon L) formato viene caricato con 10.000   int, fanno 100 ricerche di recente   interi casuali generati dalla gamma   da 1 a 50000. calcolare media   lunghezza della sonda per ciascuno dei due   formule e indicare i denominatori   utilizzato in ogni calculationSo, per esempio, ogni prova per un carico .5 avrebbe una tabella di>> dimensione   circa 20.000 (regolata per essere   Prime) e allo stesso modo ogni test per un   .9 carico avrebbe una tabella di   dimensione approssimativa 10.000 / 0,9 (di nuovo   rettificato per essere primo).

     

Il programma dovrebbe funzionare la visualizzazione del   vari fattori di carico testati, la   Sonda media per ogni ricerca (i due   denominatori usati per calcolare la   medie aggiungerà a 100), e il   risposte teoriche attraverso formulazioni   sopra. . **

Come faccio a calcolare il successo empirico?

Ecco il mio codice finora:

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

Si dovrebbe tener conto del fatto che HashTable di Java utilizza un sistema chiuso di indirizzamento (senza sondare) l'attuazione, in modo da avere secchi separati in cui molti oggetti possono essere collocati. Questo non è quello che stai cercando nella vostra benchmark. Io non sono sicuro di implementazione HashMap ma penso che utilizza l'indirizzamento aperto troppo.

Così dimenticare classi JDK .. dal momento che si desidera calcolare i valori empirici si dovrebbe scrivere la propria versione di una tabella hash che utilizza il indirizzamento aperto implementazione con scansione lineare , ma si dovrebbe prendere cura di contare la lunghezza della sonda ogni volta che si tenta di ottenere un valore dalla hashmap ..

Ad esempio si può scrivere il hashmap e quindi si prenderà cura di avere

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

     return probeLength;
   }
}

allora si può facilmente benchmark cercando quante chiavi che si desidera e il calcolo della durata media della sonda.

In caso contrario, si può solo fornire la hasmap la capacità di memorizzare la lunghezza totale della sonda e il conteggio delle viene richiesto e recuperarli dopo la corsa di riferimento per calcolare il valore medio.

Questo tipo di esercizi deve provare che le concordates valore empirico con quello teorico. Quindi prendere in considerazione anche del fatto che potrebbe essere necessario molti punti di riferimento, e poi fare la media di tutti, assicurando che la varianza non è troppo alto.