كيفية حساب متوسط ​​طول المسبار للنجاح والفشل - المسبار الخطي (جداول التجزئة) [مغلق]

Question

أقوم بمهمة لصف هياكل البيانات الخاص بي.لقد طُلب منا دراسة الفحص الخطي باستخدام عوامل الحمولة .1، .2، .3، ....، و.9.صيغة الاختبار هي:

يبلغ متوسط ​​طول المسبار باستخدام المسبار الخطي تقريبًا

نجاح--> ( 1 + 1/(1-L)**2)/2
أو
الفشل--> (1+1(1-L))/2.

مطلوب منا العثور على النظرية باستخدام الصيغة التي قمت بها أعلاه (فقط قم بتوصيل عامل التحميل في الصيغة)، ثم يتعين علينا حساب القيمة التجريبية (وهو ما لست متأكدًا تمامًا من كيفية القيام به).وهنا بقية المتطلبات

** لكل عامل تحميل ، سيتم إدراج 10000 ints إيجابية تم إنشاؤها بشكل عشوائي بين 1 و 50000 (شامل) في جدول من "الحجم الأيمن" ، حيث يعتمد "يمين" بشكل صارم على عامل التحميل الذي تختبره.التكرارات مسموحة.تأكد من أن صيغة ints التي تم إنشاؤها عشوائيًا صحيحة.هناك فئة تسمى عشوائي في java.util.استخدمه!بعد تحميل جدول من الحجم الأيمن (استنادًا إلى L) بـ 10000 ints ، قم بـ 100 عملية بحث عن ints العشوائية التي تم إنشاؤها حديثًا من 1 إلى 50000.حساب متوسط ​​طول المسبار لكل من الصيغتين والإشارة إلى القواسم المستخدمة في كل عملية حسابية ، على سبيل المثال ، سيكون لكل اختبار لحمل .5 جدول من>> حوالي 20،000 بالنسبة إلى A .9 ، سيكون هناك جدول بحجم 10،000/.9 تقريبي (تم ضبطه مرة أخرى ليكون أولي).

يجب أن يقوم البرنامج بتشغيل عرض عوامل التحميل المختلفة التي تم اختبارها ، ومتوسط ​​التحقيق لكل بحث (سيضيف المقامان المستخدمان لحساب المتوسطات إلى 100) ، والإجابات النظرية باستخدام الصيغة أعلاه..**

كيف يمكنني حساب النجاح التجريبي؟

هنا هو رمز بلادي حتى الآن:

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

يجب أن تأخذ في الاعتبار أن Java HashTable يستخدم تنفيذ معالجة مغلقة (بدون فحص)، بحيث يكون لديك مجموعات منفصلة يمكن وضع العديد من العناصر فيها.ليس هذا ما تبحث عنه في معاييرك.لست متأكدا من ذلك HashMap التنفيذ لكنني أعتقد أنه يستخدم العنونة المفتوحة أيضًا.

لذا انسَ دروس JDK ..نظرًا لأنك تريد حساب القيم التجريبية، فيجب عليك كتابة نسختك الخاصة من جدول التجزئة الذي يستخدم معالجة مفتوحة التنفيذ مع التحقيق الخطي لكن يجب أن تهتم بحساب طول المسبار كلما حاولت الحصول على قيمة من الهاشماب..

على سبيل المثال، يمكنك كتابة الهاشماب الخاص بك ثم الاهتمام بامتلاكه

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

     return probeLength;
   }
}

ومن ثم يمكنك قياسه بسهولة من خلال البحث عن عدد المفاتيح التي تريدها وحساب متوسط ​​طول المسبار.

بخلاف ذلك، يمكنك فقط تزويد hasmap بالقدرة على تخزين إجمالي طول المسبار وعدد الطلبات المطلوبة واستردادها بعد التشغيل المعياري لحساب القيمة المتوسطة.

وهذا النوع من التمارين يجب أن يثبت أن القيمة التجريبية تتوافق مع القيمة النظرية.لذا، خذ في الاعتبار أيضًا حقيقة أنك قد تحتاج إلى العديد من المعايير، ثم قم بحساب متوسطها جميعًا، مع التأكد من أن التباين ليس مرتفعًا جدًا.