java - 两个for循环，里面的for循环增加1000倍，而速度只增加100倍？

Question

我正在分析算法的计算复杂度，我有两个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倍。 为什么会这样？

Answer 1

当 label = 1 时，外循环的大部分时间都花在了“do something here here”和设置内循环上，因为“do something here also”循环只运行一次，只是循环的一小部分工作。假设“在这里做某事”并设置内循环需要 100 个时间单位，而“在这里也做某事”只需要 10 个时间单位。程序的总运行时间为 110 * sample_size。现在您将标签增加到 1000。100 + 10 * 1000 = 10100。因此总运行时间为 10100 * sample_size。 10100/110 = 91.8。因为“Do something here here”花费了一些时间，它显着降低了增加标签的影响。您必须考虑“在这里做某事”与“也在这里做某事”的比率，而不仅仅是旧标签值与新标签值的比率。