自组织搜索程序

Question

作业问题要求使用以下数组的每个数字调用"find"和"find2".但是,我被困住了,因为我不知道代码在做什么.从文本中可以看出,该程序"测试100个元素的算法,其中'局部'集合包含20%的元素和30%的参考文献."

{9,0,0,6,3,9,2,4,5,9,0,0,6,3,9,2,4,5,9,0,0,6,3,9,2,4,5} //A given set repeated 3 times

我被告知的是:

1. 我应该改变当前的for-loop体
2. 我必须打印出搜索到的数组(搜索到的数字移动到更早的位置).

我要求的是对以下内容的解释.然后我可以继续实际操作代码.

1. find2到底在做什么？
2. 在调用find和find2的for循环中发生了什么？
3. 如何获得4286和3903(如输出中所示)的计数？(这可能最终在之前的一个问题中得到回答)

码:

private static int x[]=new int[100];
public static void main(String[] args){
    Random r=new Random(17);

    //Making the array//
    for(int i=0;i<x.length;i++)x[i]=x.length-i;
    System.out.println(Arrays.toString(x));

    r.setSeed(17);
    // straight search
    for(int i=0;i<x.length*1;i++){
        float p=r.nextFloat();
        int j=(int)(p*79);
        if(p<0.3)find(j%20+1);
        else find(j+21);
    }
    System.out.println(n+" "+count);
    //identical but self-organizing
    r.setSeed(17);count=0;n=0;
    for(int i=0;i<x.length*1;i++){
        float p=r.nextFloat();
        int j=(int)(p*79);
        if(p<0.3)find2(j%20+1);
        else find2(j+21);
    }
    System.out.println(Arrays.toString(x));
    System.out.println(n+" "+count);
}

//Find
private static int find(int target){
    for(int i=0;i<x.length;i++)
        if(x[i]==target){
            count+=i;n++;
            return i;
        }
    return -1;
}
static int count=0,n=0;
static final int NEAR=100/10;

//Find2
private static int find2(int target){
    for (int i=0;i<x.length;i++)
        if(x[i]==target){
            count+=i; n++;
            if(i>NEAR){     //swap to NEAR
                x[i]=x[NEAR];
                x[NEAR]=target;
            } else if(i!=0){    //swap with predecessor
                x[i]=x[i-1];
                x[i-1]=target;
            }
            return i;
        }
    return -1;
}

输出:

[100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
100 4286
[99, 100, 97, 96, 98, 92, 93, 91, 94, 95, 5, 84, 56, 46, 86, 52, 83, 87, 49, 82, 3, 78, 45, 53, 44, 75, 74, 6, 2, 71, 85, 69, 18, 7, 19, 68, 64, 81, 62, 12, 88, 16, 4, 57, 90, 61, 55, 70, 63, 51, 50, 73, 48, 47, 1, 89, 79, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 65, 80, 17, 58, 15, 14, 13, 72, 11, 10, 9, 8, 67, 66, 54, 59, 77, 60, 76]
100 3903

非常感谢任何帮助.另外,如果我问这个问题的方式有问题,请告诉我,因为这是我的第一个问题.

编辑:我尝试了以下修改,输出已更改.但是,如果不了解代码正在做什么,我并不完全知道潜在的影响.

private static int y[]={9,0,0,6,3,9,2,4,5,9,0,0,6,3,9,2,4,5,9,0,0,6,3,9,2,4,5}; //placed right under x[]
for(int j=0;j<y.length;j++)find(y[j]); //for the 'straight search' for-loop body
for(int j=0;j<y.length;j++)find2(y[j]); //for the 'self-organizing' for-loop body

Answer 1

1. find2到底在做什么？
自组织算法试图以一种方式组织自己,使得更频繁搜索的项目更靠近前方.这样,当搜索阵列时,可以在后续搜索中更快地找到目标.例如,如果您在i = 99处搜索并找到1,则将其移动到NEAR(10)将导致第二次检索速度提高10倍.然而,就我所见,创建一个排序数组以显示它的想法有点愚蠢.如果您已经有一个已排序的数组,比如说例子中的1 - 100,那么您可以检查目标并拆分数组,或者直接将其作为x [100-target]给出,它确实会给你目标.如果是我,我会把这些元素随机化,哦.

2.在调用find和find2的for循环中发生了什么？
这些只是生成*伪*随机数作为目标.它们是伪的,因此每次结果都是相同的,因为"随机"数字不是那么随机.它们也仅限于数据集,因为nextFloat()将返回介于0.0和1.0之间的数字 - p*79只给出79的百分比,然后基于p然后计算目标,它将介于1和100之间

.如何获得4286和3903的计数？
这些是试图向您展示您已经完成了所尝试的内容的计数,即更快地查找数据.基本上计数是累加器.每次在i处找到目标时,都会将i添加到计数中.如果在i = 1,2和3处找到三个元素,则count将为6.较大的元素显示找到的目标的所有索引的总和,而不允许它自行组织.较小的一个表明,由于新组织,您可以改进搜索.如果没有获得任何表现,那么数字将是相同的.

您可以将目标存储在另一个数组中,并查看某些目标的调用频率,以便将您所看到的内容与输出相关联,乍一看它只是看起来是随机的.