0

我正在分析算法的计算复杂度，我有两个 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=1 和 label_size=1000 增加了内部 label_size，我预计运行时间应该增加 1000 倍，而实际上不同运行的运行时间只增加 40-100 倍。为什么会这样？

4

1 回答 1

1

当 label = 1 时，外部循环的大部分时间都用于“在这里做某事”并设置内部循环，因为只在循环中运行一次“也在这里做某事”只是工作的一小部分。假设“在这里做某事”并设置内部循环需要 100 个单位的时间，而“在这里也做一些事情”只需要 10 个单位的时间。程序的总运行时间为 110 * sample_size。现在将标签增加到 1000。100 + 10 * 1000 = 10100。因此总运行时间为 10100 * sample_size。10100 / 110 = 91.8。因为“在这里做点什么”花了一些时间，所以大大减少了增加标签的影响。您必须考虑“在这里做某事”与“也在这里做某事”的比例，

于 2012-05-05T11:34:39.083 回答