Блог

Реализация базового алгоритма с использованием last array в качестве pivot в Java, нормально ли, что для сортировки массива случайных чисел из 100 000 000 элементов требуется 5 часов?

Мои системные характеристики: Mac OS X Lion 10.7.2 (2011) Intel Core i5 2,3 ГГц 8 ГБ оперативной памяти

Update2: Итак, я думаю, что я делаю что-то не так в своих других методах, поскольку Narendra смог запустить быструю сортировку. Вот полный код, который я пытаюсь запустить.

 import java.util.Random;

public class QuickSort {
public static int comparisons = 0;

public static void main(String[] args) {
    int size = 100000000;
    int[] smallSampleArray = createArrayOfSize(size);

    System.out.println("Starting QS1...");
    long startTime = System.currentTimeMillis();
    quickSort(smallSampleArray,0,size-1);
    System.out.println(  "Finished QS1 in "   (System.currentTimeMillis() - startTime)  " seconds");
    System.out.println("Number of comparisons for QS1: "   comparisons);

}

public static int[] createArrayOfSize(int arraySize) {
    int[] anArray = new int[arraySize];
    Random random = new Random();

    for(int x=0; x < anArray.length; x   ) {
        anArray[x] = random.nextInt(1000)   1;;
    }
    return anArray;
}


public static void quickSort( int anArray[], int position, int pivot) {

    if( position < pivot ) {
        int q = partition(anArray, position, pivot);

        quickSort(anArray, position, q-1);
        quickSort(anArray, q 1, pivot);

    }

}

public static int partition(int anArray[], int position, int pivot ) {
    int x = anArray[pivot];
    int i = position - 1; 

    for(int j = position; j < (pivot-1); j   ) {
        comparisons  ;
        if(anArray[j] <= x) {
             i = i   1;
             int temp =  anArray[i];
             anArray[i] = anArray[j];
             anArray[j] = temp;
        }

    }
    int temp = anArray[i 1];
    anArray[i 1] = anArray[pivot];
    anArray[pivot] = temp;



        return i 1;
    }

}
  

Я переместил старый, теперь неактуальный ответ в конец.

Редактировать x2

Ага! Я думаю, что нашел причину вашей ужасной производительности. Вы сказали нам, что используете рандомизированные данные. Это правда. Но чего вы нам не сказали, так это того, что вы использовали такой небольшой диапазон возможных случайных значений.

Для меня ваш код очень эффективен, если вы измените эту строку:

 anArray[x] = random.nextInt(1000)   1;
  

к этому:

 anArray[x] = random.nextInt();    
  

Это противоречит ожиданиям, верно? Должно быть дешевле сортировать меньший диапазон значений, поскольку должно быть меньше обменов, которые нам нужно сделать, верно? Итак, почему это происходит?Это происходит потому, что у вас так много элементов с одинаковым значением (в среднем 100 тысяч). Так почему же это приводит к такой ужасной производительности? Ну, скажем, в каждой точке вы выбрали идеальное значение pivot: ровно на полпути. Вот как это будет выглядеть:

 1000 - Pivot: 500
 - 500  - Pivot: 750
   - 750  - Pivot: 875
   - 750- - Pivot: 625
 - 500- - Pivot: 250
  

И так далее. Однако (и это критическая часть) вы в конечном итоге перейдете к операции разделения, где каждое отдельное значение равно значению раздела. Другими словами, будет большой (100 тысяч больших) блок чисел с тем же значением, который вы попытаетесь рекурсивно отсортировать. И как это произойдет? Он будет повторяться 100 тысяч раз, удаляя только одно сводное значение на каждом уровне. Другими словами, он разделит все налево или все направо.

Расширяя приведенную выше разбивку, это будет выглядеть примерно так (я использовал 8 — степень 2 — для простоты и прошу прощения за плохое графическое представление)

 Depth Min  Max  Pvt NumElements

0     0     7    4   100 000 000
1     0     3    2    50 000 000    
2     0     1    1    25 000 000
3     0     0    0    12 500 000 < at this point, you're
4     0     0    0    12 499 999 < no longer dividing and
5     0     0    0    12 499 998 < conquering effectively.
3     1     1    1    12 500 000
4     1     1    1    12 499 999
5     1     1    1    12 499 998
2     2     3    3    25 000 000
3     ...    
3     ...    
1     4     7    6    50 000 000    
2     4     5    5    25 000 000
3     ...
3     ...    
2     6     7    7    25 000 000
3     ...
3     ... 
  

Если вы хотите противостоять этому, вам нужно оптимизировать свой код, чтобы уменьшить последствия этого. Подробнее об этом (я надеюсь)…

…и продолжил. Простой способ решить вашу проблему — проверить, отсортирован ли массив уже на каждом шаге.

 public static void quickSort(int anArray[], int position, int pivot) {

    if (isSorted(anArray, position, pivot   1)) {
        return;
    }

    //...
}


private static boolean isSorted(int[] a, int start, int end) {
    for (int i = start 1; i < end; i  ) {
        if (a[i] < a[i-1]) {
            return false;
        }
    }
    return true;
}
  

Добавьте это, и вы не будете повторять без необходимости, и вы должны быть золотыми. Фактически, вы получаете лучшую производительность, чем при использовании значений, рандомизированных по всем 32 битам целого числа.

Старый ответ (только для потомков)

Ваша логика разделения выглядит для меня действительно подозрительной. Давайте извлекем и проигнорируем логику подкачки. Вот что у вас есть:

     int i = position - 1; 

    for(int j = position; j < pivot; j   ) {

        if(anArray[j] <= x) {
             i = i   1;
             swap(anArray, i, j);
        } 

    }
  

Я не понимаю, как это вообще будет работать. Например, если бы самое первое значение было меньше сводного значения, оно было бы заменено на себя?

Я думаю, вы хотите что-то вроде этого (просто грубый набросок):

 for ( int i = 0, j = pivot - 1; i < j; i   ) {

   if ( anArray[i] > pivotValue ) {
      //i now represents the earliest index that is greater than the pivotValue,
      //so find the latest index that is less than the pivotValue
      while ( anArray[j] > pivotValue ) {
         //if j reaches i then that means that *all* 
         //indexes before i/j are less than pivot and all after are greater
         //and so we should break out here
         j--;
      }

      swap(anArray, i, j);
   }
} 

//swap pivot into correct position
swap(anArray, pivot, j 1);
  

Редактировать

Думаю, теперь я понимаю исходную логику разделения (я перепутал if-блок, чтобы он просматривал элементы, превышающие pivot). Я оставлю свой ответ на случай, если он обеспечит лучшую производительность, но я сомневаюсь, что это будет иметь существенное значение.

Будучи парнем из c #, я просто вставил приведенный выше код в пустой проект c #.
Для массива из 100 000 000 целых чисел потребовалось 35 секунд.
Кажется, в коде нет ничего плохого, в вашей среде должно быть что-то еще. Разрешено ли процессу Java выделять ~ 800 МБ ОЗУ?

Что произойдет, если вы уменьшите размер массива до 10.000.000. Тогда вы приближаетесь к ~ 3 секундам?
Существует ли определенный размер массива, при котором сортировка внезапно замедляется?

Редактировать

Я почти уверен, что у вас нет случайного массива, вы, вероятно, потерпели неудачу с вашей случайной инициализацией.

Если вы создаете новый случайный объект для каждого элемента, вы обычно получаете одинаковое значение для каждого элемента, поскольку каждая Random инициализация генерирует генератор случайных чисел с текущим временем в миллисекундах. Если весь массив инициализируется в течение одной миллисекунды, все элементы получают одинаковое значение.

В c # я инициализирую так

 Random r = new Random();
var intArr = (from i in Enumerable.Range(0, 10000)
            select r.Next()).ToArray();
var sw = System.Diagnostics.Stopwatch.StartNew();
quickSort(intArr, 0, intArr.Length - 1);
sw.Stop();
  

Для сортировки требуется 2 миллисекунды.

Если я повторно инициализирую свой Random объект для каждого элемента

 var intArr = (from i in Enumerable.Range(0, 10000)
              select (new Random()).Next()).ToArray();
  

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