wie die durchschnittliche Sondenlänge für Erfolg und Misserfolg Compute - Linear-Sonde (Hash Tables) [geschlossen]

Question

Ich mache einen Auftrag für meine Datenstrukturen Klasse. wir wurden lineare Sondierung mit Belastungsfaktoren von 0,1, 0,2 bis zu Studie gefragt, 0,3, ...., und 0,9. Die Formel für die Prüfung ist:

Die durchschnittliche Sondenlänge mittels linearer Sondierung ist in etwa

Erfolg -> (1 + 1 / (1-L) ** 2) / 2 oder in Failure -.> (1 + 1 (1-L)) / 2

wir sind verpflichtet, die theoretischen mit der Formel zu finden, über den habe ich (gerade den Ladefaktor in der Formel-Stecker), dann müssen wir die empirische (was ich nicht ganz sicher, wie das zu tun) berechnen. hier ist der Rest der Anforderungen

  

** Für jeden Lastfaktor, 10.000 zufällig erzeugte positive Ints   zwischen 1 und 50000 (einschließlich) Willen   in eine Tabelle der eingefügt werden   „Richtige“ Größe, wo „rechts“ ist   auf den Belastungsfaktor streng basierend   Sie testen. Wiederholt sind erlaubt.   Achten Sie darauf, dass Ihre Formel für zufällig   erzeugt Ints ist richtig. Da ist ein   Klasse namens Random in java.util. VERWENDEN   es! Nach einer Tabelle von der rechten Seite (basierend   auf L) Größe wird mit 10.000 beladen   Ints, tun 100 Durchsuchungen von neu   erzeugte Zufallsganzzahlen aus dem Bereich   von 1 bis 50000. berechne die durchschnittliche   Sondenlänge für jede der beiden   Formeln und zeigen die Nenner   in jedem calculationSo zum Beispiel verwendet, wobei jeder Test für eine 0,5 Last würde eine Tabelle von>> Größe   etwa 20.000 (eingestellt sein   Prime) und in ähnlicher Weise jeden Test für ein   0,9 Last würde eine Tabelle   ungefähre Größe 10.000 / 0,9 (wieder   angepasst Primzahl ist).

     

sollte das Programm laufen die Anzeigen   verschiedene Belastungsfaktoren getestet, die   durchschnittliche Sonde für jede Suche (die beide   Nenner verwendeten berechnen   mittelt werden zu 100) hinzufügen und die   theoretische Antworten unter Verwendung der Formel   über. . **

Wie berechne ich den empirischen Erfolg?

Hier ist mein Code so weit:

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

Sie sollten berücksichtigen, dass Java HashTable verwendet eine Adressierung geschlossen (kein Sondieren) Implementierung, so dass Sie getrennte Eimer haben, in dem viele Elemente platziert werden können. Dies ist nicht das, was Sie in Ihrer Benchmarks suchen. Ich bin nicht sicher über HashMap Umsetzung, aber ich denke, es nutzt offen zu adressieren.

So etwa JDK-Klassen vergessen .. da Sie Erfahrungswerte berechnen wollen, sollten Sie Ihre eigene Version eines Hash-Tabelle schreiben, die verwendet die offene Adressierung Implementierung mit lineare Sondieren aber Sie sollen zum Zählen der Sondenlänge kümmern, wenn Sie versuchen, einen Wert aus der hashmap zu bekommen ..

Zum Beispiel können Sie Ihre hashmap schreiben und dann kümmern mit

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

     return probeLength;
   }
}

Dann können Sie einfach Benchmark es durch die Suche, wie viele Tasten, die Sie wollen, und die durchschnittliche Sondenlänge berechnet werden.

Ansonsten können Sie einfach die hasmap bieten die Möglichkeit, die gesamte Sondenlänge zu speichern und die Anzahl der wird angefordert und abgerufen werden sie nach dem Benchmark-Durchlauf Mittelwert zu berechnen.

Diese Art von Übungen unter Beweis stellen müssen, dass die empirischen Wert concordates mit der theoretischen. So berücksichtigt auch die Tatsache, dass Sie viel Benchmarks benötigen, und führen Sie dann den Mittelwert von allen, sicherzustellen, dass die Varianz ist nicht zu hoch.