0

私はアルゴリズムの計算の複雑さを分析している最中です。2つのforループがあります。

    short i=0;
    short j=0;
    short ii=0;
    short[] counts = new short[2];

    int label_size  = MapRedUtils.label_size;
    int max_index=0;                        
    int sample_size =data.getSampleSize();

    float max_ig = 0;
    float totalVar=0;
    float var=0;
    float cov_ig;

    float[] tocopy = new float[label_size];        
    float[][] sums = new float[2][];
    float[] totalSum = new float[label_size];



    byte value;
    ByteBuffer label = ByteBuffer.allocate(label_size*4); 

    for( j=0; j<2; j++ )        
        sums[j] = new float[label_size];

    for( ii=0; ii<3; ii++)// 3 ways of split the current node
    {          
          long startTime;
    long endTime;
    long totalTime;
    startTime = System.currentTimeMillis();
        counts[0]=0;
        counts[1]=0;

        System.arraycopy(tocopy,0,totalSum,0,label_size);
        System.arraycopy(tocopy,0,sums[0],0,label_size);
        System.arraycopy(tocopy,0,sums[1],0,label_size);

        for ( i = 0; i < sample_size; i++) 
        {
            OneSample instance = data.get(i);
            value = (byte) instance.getTheGenoytpe(snpid);

            label = instance.getPhenotype();                                                                          

            if( value==ii)
            {   
                counts[0]++;
                for(j=0; j< label_size; j++)
                     sums[0][j] += label.getFloat(j*4);
            }
            else
            {
                counts[1]++;                    
                for(j=0; j< label_size; j++)
                    sums[1][j] += label.getFloat(j*4);                    
            }

            for(j=0; j< label_size; j++)  
                totalSum[j] += label.getFloat(j*4);
        }                                              

          totalVar=0;
          var=0;
         for(i=0; i< label_size; i++)
         {
           totalVar += totalSum[i]*totalSum[i];          
         } 

        totalVar = totalVar/sample_size;//it is averaged by sample size

        for(j=0; j< 2; j++)
           //var += sumSquared(sums[j],  MapRedUtils.inverse_covariance , counts[j]);  
             var += sumSquared(sums[j], counts[j]);


        cov_ig = var- totalVar;

        if(cov_ig > max_ig)
        {
            max_ig=cov_ig;
            max_index=ii;
        } 
        endTime = System.currentTimeMillis();                    
        totalTime = (endTime - startTime);
        System.out.println(totalTime);

内側のlabel_sizeをlabel_size=1およびlabel_size=1000から増やします。実行時間は、1000倍になるはずですが、実際には、実行時間は、さまざまな実行で40〜100倍しか増えません。なんでこんな感じ？

4

1 に答える 1

1

label = 1 の場合、外側のループのほとんどの時間は、「ここで何かを行う」と内側のループを設定することに費やされます。これは、「ここでも何かを行う」というループを 1 回だけ実行することは、作業のごく一部にすぎないためです。「ここで何かをする」と仮定すると、内側のループの設定には 100 単位の時間がかかり、「ここでも何かをする」には 10 単位の時間しかかかりません。プログラムの合計実行時間は、110 * sample_size になります。ここで、ラベルを 1000 に増やします。100 + 10 * 1000 = 10100 です。したがって、合計実行時間は 10100 * sample_size です。10100 / 110 = 91.8。「ここで何かをする」には少し時間がかかったので、ラベルを増やすことの影響を大幅に減らしました。「ここで何かをする」と「ここでも何かをする」の比率を考える必要があります。

于 2012-05-05T11:34:39.083 に答える