почему среднее время 3 алгоритмов отрицательное?

Я должен использовать массивы размером от 10000 до 50000 с размером шага 10000, давать одинаковые входные данные всем трем алгоритмам и для каждого входа повторять выполнение 100 раз, измерять выполнение в наносекундах (используя System.nanoTime()), и сообщить среднее время в миллисекундах. это то, что я сделал ниже, но некоторые средние значения отрицательны, я не знаю, почему?

import java.util.Arrays;

public class Sort{

   public static void main(String[]args){

      double[] arr5 = new double[50000];

      for(int i=0;i<arr5.length;i++)
         arr5[i] = Math.random();

      selectionSort(arr5,10000);
      bubbleSort(arr5,10000);
      quickSort(arr5,10000);

      selectionSort(arr5,20000);
      bubbleSort(arr5,20000);
      quickSort(arr5,20000);

      selectionSort(arr5,30000);
      bubbleSort(arr5,30000);
      quickSort(arr5,30000);

      selectionSort(arr5,40000);
      bubbleSort(arr5,40000);
      quickSort(arr5,40000);

      selectionSort(arr5,50000);
      bubbleSort(arr5,50000);
      quickSort(arr5,50000);
   }

   public static void selectionSort(double [] A,int n){
      int sum = 0;
      System.out.println("Algorithm 1");
      for(int s=0;s<100;s++){
         long arr[] = new long[100];

         long startTime = System.nanoTime();

         for(int i=0;i<n-1;i++){
            int min = i;
            for(int j=i+1;j<n;j++){
               if(A[j] < A[min])
                  min=j;}
            double tmp = A[i];
            A[i] = A[min];
            A[min]=tmp;}

         long endTime = System.nanoTime();

         arr[s] = endTime - startTime;
      //System.out.println(arr[s]);
         sum+=arr[s];
      }
      System.out.println("Average:" + ((sum/100)*Math.pow(10,-6)));

   }

   public static void bubbleSort(double A [],int n){
      int sum = 0;
      System.out.println("\nAlgorithm 2");
      for(int s=0;s<100;s++){
         long[] arr = new long[100];

         long startTime = System.nanoTime();

         for(int i=0;i<n-1;i++){
            for(int j=0;j<n-1-i;j++){
               if(A[j]<A[j+1]){
                  double tmp = A[j];
                  A[j] = A[j+1];
                  A[j+1] = tmp;}}}

         long endTime = System.nanoTime();

         arr[s] = endTime - startTime;
      //System.out.println(arr[s]);
         sum+=arr[s];
      }
      System.out.println("Average:" + ((sum/100)*Math.pow(10,-6)));

   }

//algorithm 3
   public static void quickSort(double A [],int n){
      int sum = 0;
      System.out.println("\nAlgorithm 3");
      long[] arr = new long[100];

      for(int i=0;i<100;i++){
         long startTime = System.nanoTime();

         Arrays.sort(A,0,n-1);

         long endTime = System.nanoTime();

         arr[i] = endTime - startTime;
      //System.out.println(arr[i]);
         sum+=arr[i];
      }
      System.out.println("Average:" + ((sum/100)*Math.pow(10,-6)));

   }

}

java analysis algorithm time-complexity performanceanalytics
person user7150641    schedule 13.10.2017    source источник
comment
Другая проблема заключается в том, что вы создаете массив: long arr[] = new long[100]; внутри цикла for...   -  person Nir Alfasi    schedule 13.10.2017

Ответы (1)


arrow_upward
5
arrow_downward

Переменная sum, используемая для ваших вычислений, имеет тип int. Когда вы увеличиваете sum, он переполняется из-за того, что endTime - startTime является довольно большим значением. Когда происходит переполнение sum, его значение возвращается к минимальному значению (отрицательному) и снова продолжает увеличиваться.

Исправить: изменить тип sum на long.

Другой комментарий

Ваши массивы с именем arr кажутся избыточными, поскольку они не используются в расчетах и ​​сбрасываются при каждом цикле.

Например, в вашем методе bubbleSort(). Вы объявляете и инициализируете массив long[] arr = new long[100]; внутри цикла for: for(int s=0;s<100;s++).

Теперь единственная цель этого массива arr в настоящее время состоит в том, чтобы сохранить результат endTime - startTime по индексу s, который затем используется для увеличения sum (sum+=arr[s];).

Если это его единственная цель, почему бы просто не сделать sum += endTime - startTime и полностью удалить массив?

Если вы на самом деле собирались отслеживать все результаты в этом массиве, то вам следует переместить long[] arr = new long[100]; за пределы цикла for for(int s=0;s<100;s++), так как в настоящее время он повторно объявляется и инициализируется при каждой итерации.

Чтобы продемонстрировать, рассмотрим этот небольшой пример, который повторяет то, что вы делаете в bubbleSort() и других методах:

for (int i = 0; i < 5; i++) {
    int[] arr = new int[5];
    arr[i] = (i + 1);
    System.out.println(Arrays.toString(arr));
}

Результат:

[1, 0, 0, 0, 0]
[0, 2, 0, 0, 0]
[0, 0, 3, 0, 0]
[0, 0, 0, 4, 0]
[0, 0, 0, 0, 5]

Если массив объявлен до цикла, то поведение будет иметь больше смысла:

int[] arr = new int[5];
for (int i = 0; i < 5; i++) {
    arr[i] = (i + 1);
    System.out.println(Arrays.toString(arr));
}

В этом случае вывод:

[1, 0, 0, 0, 0]
[1, 2, 0, 0, 0]
[1, 2, 3, 0, 0]
[1, 2, 3, 4, 0]
[1, 2, 3, 4, 5]

Выведите содержимое вашего массива arr на консоль в цикле for, и вы поймете, что я имею в виду.

person d.j.brown    schedule 13.10.2017
comment
Да, я только что понял ошибку int, но я не понимаю, что вы подразумеваете под сбросом каждого цикла, что вы предлагаете мне делать? - person user7150641; 13.10.2017
comment
@ user7150641, пожалуйста, прочитайте весь ответ, он предложил использовать long - person Nir Alfasi; 13.10.2017