Блог пользователя OSt

Java vs AntiQuickSort
Автор OSt, 15 лет назад, По-русски

По мотивам поста - завал java.util.Arrays.sort()

Я попробовал скормить данный int массив Arrays.sort() и ужаснулся - программа реально долго работает.

Но неужели всё так печально?

Оказалось - не совсем.

Далее для простоты привожу исходные коды методов, которые я использовал для проведения собственных "расследований".

Чтение в первых двух случаях шло из файла, который сгенерировал скрипт-убийца.

Последние 2 метода используют массив с рандомным заполнением. Для чистоты эксперимента, так сказать.

void solve() {

   int ar[] = new int[500000];
   for (int i = 0; i <ar.length; i++){
      ar[i] = in.nextInt();
   }
   out.println("Start sorting");
   out.flush();
   long start = System.currentTimeMillis();
   Arrays.sort(ar);
   long total = System.currentTimeMillis()-start;
   out.println("Sorted at "+total);
}

  Start sorting 
  Sorted at 123324

void solve() {
   Integer ar[] = new Integer[500000];
   for (int i = 0; i <ar.length; i++){
      ar[i] = in.nextInt();
   }
   out.println("Start sorting");
   out.flush();
   long start = System.currentTimeMillis();
   Arrays.sort(ar);
   long total = System.currentTimeMillis()-start;
   out.println("Sorted at "+total);
}
  Start sorting
  Sorted at 530


void solve() {
   Random r = new Random();
   Integer ar[] = new Integer[500000];
   for (int i = 0; i <ar.length; i++){
      ar[i] = r.nextInt();
   }
   out.println("Start sorting");
   out.flush();
   long start = System.currentTimeMillis();
   Arrays.sort(ar);
   long total = System.currentTimeMillis()-start;
   out.println("Sorted at "+total);
}
  Start sorting
  Sorted at 624

void solve() {
   Random r = new Random();
   int ar[] = new int[500000];
   for (int i = 0; i <ar.length; i++){
      ar[i] = r.nextInt();
   }
   out.println("Start sorting");
   out.flush();
   long start = System.currentTimeMillis();
   Arrays.sort(ar);
   long total = System.currentTimeMillis()-start;
   out.println("Sorted at "+total);
}
  Start sorting
  Sorted at 234

Как видно - не всё так и страшно.

Если использовать Integer[] вместо int[] - будет использоваться сортировка слиянием, не имеющая худшего случая вообще (как и лучшего).

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
Вы абсолютно правы и нигде не наврали. Хотя я бы предложил более простое решение: случайно перемешать массив.
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится -12 Проголосовать: не нравится
Вспоминается еще очень старый случай, про который я слышал еще лет 5 назад.
Про стандартную функцию бинарного поиска в Java, где было написано примерно следующее:
int lf = 0, rg = n - 1;
...цикл...{
int mid = (lf + rg) / 2;
...оператор if...
}

И при lf = 2 * 109 и rg = 2 * 109 все переполнялось, когда можно было написать 
int mid = lf + ((rg - lf) / 2) и избежать переполнения.

Говорили, что из-за этого бага у Гугла что-то падало и Гугл даже судился с Sun. 
Но это все слухи пятилетней давности.
→ Ответить