Внедрение Quicksort кажется слишком медленным с большими данными

Я написал программу для сравнения различных алгоритмов сортировки с размером массива 10, 1000, 100 000, 1 000 000 и 10 000 000. Я, конечно же, ожидаю, что Insertion выиграет 10 и объединит кучу и быстро выполнит на верхних уровнях.

Однако, ниже - время, которое я получаю. (Обратите внимание, что быстрый сортировка растет намного быстрее, чем куча и слияние, хотя они все \ $ \ theta (n \ log n) \ $.)

Вещи, которые я рассмотрел:

  • Каждый алгоритм использует одно и то же семя для инициализации каждого массива, поэтому числа одинаковы.
  • Я использую только алгоритм и ничего лишнего.
  • Мой профессор утверждает код и не знает, что не так, но, возможно, мы оба что-то упускаем.
  • Я перенес программу с флеш-накопителя на рабочий стол, чтобы проверить возможные проблемы с передачей данных.
  • Алгоритм (за исключением теста 2) работает только ночью, и ничего больше не происходит.
 Key: Hours:Minutes:Seconds:Milliseconds:Microseconds

Тест 3

 n        Insertion        Merge            Heap             Quick            
10       0:0:0:0:3        0:0:0:0:28       0:0:0:0:35       0:0:0:0:43       
1000     0:0:0:11:470     0:0:0:2:358      0:0:0:7:787      0:0:0:3:596      
100000   0:0:1:911:865    0:0:0:51:506     0:0:0:24:257     0:0:0:55:519     
1000000  0:3:59:769:105   0:0:0:351:129    0:0:0:238:878    0:0:0:916:885    
10000000 8:11:44:552:820  0:0:3:521:108    0:0:3:560:178    0:1:13:709:830

Тест 2

 n              Insertion      Merge          Heap           Quick          
10             0:0:0:0:5      0:0:0:0:49     0:0:0:0:37     0:0:0:0:50     
1000           0:0:0:15:473   0:0:0:2:893    0:0:0:8:402    0:0:0:5:230    
100000         0:0:2:518:566  0:0:0:57:845   0:0:0:32:917   0:0:0:71:243   
1000000        0:5:38:538:795 0:0:0:460:796  0:0:0:312:66   0:0:1:398:508  
10000000       11:48:6:630:6390:0:3:690:329  0:0:3:518:281  0:1:18:180:11

Тест 1

          n    Insertion        Merge         Heap        Quick
       10       2676ns      19626ns      26316ns      33454ns
     1000   11504040ns    2298935ns    6835250ns    3741456ns
   100000 1849274815ns   47654052ns   23620952ns   52819295ns
  1000000     0:3:58ns      0:0:0ns      0:0:0ns      0:0:0ns
 10000000    8:10:25ns      0:0:3ns      0:0:3ns     0:1:15ns

Вот моя быстрая сортировка (35 строк):

 public static long quick(int[] list) {
    long startTime = System.nanoTime();

    quickSort(list, 0, list.length - 1);

    long endTime = System.nanoTime();
    return endTime - startTime;
}

public static void quickSort(int[] A, int p, int r) {
    if(p < r) {
        int q = randomizedPartition(A, p, r);
        quickSort(A, p, q-1);
        quickSort(A, q+1, r);
    }
}

public static int randomizedPartition(int[] A, int p, int r) {
    Random random = new Random();
    int i = random.nextInt((r-p)+1)+p;
    swap(A,r,i);
    return partition(A,p,r);
}

public static int partition(int[] A, int p, int r) {
    int x = A[r];
    int i = p-1;
     for(int j = p; j < r; j++) {
        if(A[j] <= x) {
            i++;
            swap(A, i, j);
        }
    }
    swap(A, i+1, r);
    return i+1;
}

И если нужно (267 строк), вот мой весь код:

 import java.util.Random;
import java.util.concurrent.TimeUnit;
import java.io.*;

public class algComp {
public static void main(String[] args) {
    driver(10); // Sort array of length 10
    driver(1_000); // Sort array of length 1000
    driver(100_000);

    /* WARNING: Running program with the below values takes a lot of time!! */
    driver(1_000_000);
    //driver(10_000_000);
    /* You are now leaving the danger zone. */

    System.out.println("-----------------------------------------------");
    content = String.format(content + "\nKey: Hours:Minutes:Seconds:Milliseconds:Microseconds");
    printToFile(); // Prints data to times.txt
}

public static void driver(int n) {

    // Insertion sort
    int[] list = data(n);
    if(n == 10) {
        System.out.format("%10s","Unsorted: ");
        printList(list);
    }
    long iTime = insertion(list);
    if(n == 10) {
        System.out.format("%10s","iSorted: ");
        printList(list);
    }

    // Merge sort
    list = data(n);
    long mTime = mergeSort(list);
    if(n == 10) {
        System.out.format("%10s","mSorted: ");
        printList(list);
    }

    // Heap sort
    list=data(n);
    long hTime = heap(list);
    if(n == 10) {
        System.out.format("%10s","hSorted: ");
        printList(list);
    }

    // Quick sort
    list=data(n);
    long qTime = quick(list);
    if(n == 10) {
        System.out.format("%10s","qSorted: ");
        printList(list);
    }

    if(n == 10) { // This will only print once
        // Print prettifying stuff
        System.out.println("Data is being written to times.txt...");
        content = String.format(content + "%-9s%-17s%-17s%-17s%-17s\n",
            "n","Insertion","Merge","Heap","Quick");
    }

    content = String.format(content + "%-9d%-17s%-17s%-17s%-17s%-1s",n,displayTime(iTime),
    displayTime(mTime),displayTime(hTime),displayTime(qTime),"\n");
}

public static long insertion(int[] A) {
    long startTime = System.nanoTime();
    int i, j, key;
    for(j = 1; j < A.length; j++) {
        key = A[j];
        // If previous is greater than selected (key) swap
        for(i = j - 1; (i >= 0) && (A[i] > key); i--) {
            A[i+1] = A[i];
        }
        A[i+1] = key;
    }
    long endTime = System.nanoTime();
    return endTime - startTime;
}

public static long mergeSort(int[] A) {
    long startTime = System.nanoTime();

    if(A.length > 1) {
        // First Half
        int[] firstHalf = new int[A.length/2];
        System.arraycopy(A, 0, firstHalf, 0, A.length/2);
        mergeSort(firstHalf);

        // Second Half
        int secondHalfLength = A.length - A.length/2;
        int[] secondHalf = new int[secondHalfLength];
        System.arraycopy(A, A.length/2, secondHalf, 0, secondHalfLength);
        mergeSort(secondHalf);

        // Merge two arrays
        merge(firstHalf,secondHalf,A);
    }

    long endTime = System.nanoTime();
    return endTime - startTime;
}

public static void merge(int[] A1, int[] A2, int[] temp) {
    int current1 = 0; // Current index in list 1
    int current2 = 0; // Current index in list 2
    int current3 = 0; // Current index in temp

    // Compares elemets in A1 and A2 and sorts them
    while(current1 < A1.length && current2 < A2.length) {
        if(A1[current1] < A2[current2])
            temp[current3++] = A1[current1++];
        else
            temp[current3++] = A2[current2++];
    }

    // Merge two arrays into temp
    while(current1 < A1.length)
        temp[current3++] = A1[current1++];

    while(current2 < A2.length)
        temp[current3++] = A2[current2++];
}

public static long heap(int[] A) {
    long startTime = System.nanoTime();
    int temp;

    int heapSize = A.length-1;
    buildMaxHeap(A);
    for(int i = A.length-1; i >= 1; i--) {
        swap(A,0,i); // Root is now biggest element, swap to end of array
        heapSize--; // Reduce heapSize to ignore sorted elements
        maxHeapify(A,0,heapSize);
    }


    long endTime = System.nanoTime();
    return endTime - startTime;
}

public static void buildMaxHeap(int[] A) {
    int heapSize = A.length-1;
    // Bottom up, check parents children, sort and move up tree
    for(int i = (heapSize/2); i >= 0; i--)
        maxHeapify(A,i,heapSize);
}

public static void maxHeapify(int[] A, int i, int heapSize) {
    int temp,largest;
    int l = left(i); // 2i
    int r = right(i); // 2i + 1

    if(l <= heapSize && A[l] > A[i]) // Check left child (which is largest?)
        largest = l;
    else largest = i;
    if(r <= heapSize && A[r] > A[largest]) // Check right child
        largest = r;
    if(largest != i) { // If parent is biggest do nothing, else make parent largest
        swap(A,i,largest);
        maxHeapify(A,largest,heapSize);
    }
}

public static int left(int i) {
    return 2*i;
}

public static int right(int i) {
    return 2*i+1;
}

public static long quick(int[] list) {
    long startTime = System.nanoTime();

    quickSort(list, 0, list.length - 1);

    long endTime = System.nanoTime();
    return endTime - startTime;
}

public static void quickSort(int[] A, int p, int r) {
    if(p < r) {
        int q = randomizedPartition(A, p, r);
        quickSort(A, p, q-1);
        quickSort(A, q+1, r);
    }
}

public static int randomizedPartition(int[] A, int p, int r) {
    Random random = new Random();
    int i = random.nextInt((r-p)+1)+p;
    swap(A,r,i);
    return partition(A,p,r);
}

public static int partition(int[] A, int p, int r) {
    int x = A[r];
    int i = p-1;
    for(int j = p; j < r; j++) {
        if(A[j] <= x) {
            i++;
            swap(A, i, j);
        }
    }
    swap(A, i+1, r);
    return i+1;
}

public static void swap(int[] list, int i, int j) {
    int temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

public static String displayTime(long n) {
    long hours = TimeUnit.NANOSECONDS.toHours(n);
    long minutes = TimeUnit.NANOSECONDS.toMinutes(n) - (TimeUnit.NANOSECONDS.toHours(n)*60);
    long seconds = TimeUnit.NANOSECONDS.toSeconds(n) - (TimeUnit.NANOSECONDS.toMinutes(n) *60);
    long milliseconds = TimeUnit.NANOSECONDS.toMillis(n) - (TimeUnit.NANOSECONDS.toSeconds(n)*1000);
    long microseconds = TimeUnit.NANOSECONDS.toMicros(n) - (TimeUnit.NANOSECONDS.toMillis(n)*1000);
    String displayThis = (hours + ":" + minutes + ":" + seconds + ":" + milliseconds + ":" + microseconds);
    return displayThis;
}

public static int[] data(int n) {
    Random random = new Random(seed); // Random seed stays same for all sorts
    int[] list = new int[n];

    for(int i = 0; i < list.length; i++) {
        list[i] = random.nextInt(1000);
    }

    return list;
}

public static void printList(int[] list) {
    for(int i = 0; i < list.length; i++) {
            System.out.format("%5d",list[i]);
    }
    System.out.println();
}

public static void printToFile() {
    // Print to file
    try {
        File file = new File("times.txt");
        if(!file.exists())
            file.createNewFile();
        FileWriter fw = new FileWriter(file.getAbsoluteFile());
        BufferedWriter bw = new BufferedWriter(fw);
        bw.write(content);
        bw.close();
        System.out.println("Done.");
    } catch (IOException e) {
        e.printStackTrace();
    }
}

// Global variables
public static String content = ""; // Used to print data to text file times.txt
public static int seed = (int)(Math.random()*10_000); // Seed for generating lists
}

Как вы думаете? Разумеется, быстрый сорт должен работать около 3 секунд на 10 милях, а не на минуту. Что я делаю неправильно?

35 голосов | спросил Ethan 21 +04002014-10-21T05:46:57+04:00312014bEurope/MoscowTue, 21 Oct 2014 05:46:57 +0400 2014, 05:46:57

2 ответа


25

@mjolka смог определить проблему с корнем до того, как я был ;-) В дополнение к тому, что он указал, есть две проблемы.

Во-первых, очень плохая форма создания новых случайных экземпляров для каждого раздела. Случайные экземпляры внутренне синхронизируются на некоторых логических структурах и вызывают много накладных расходов при их создании. Вместо этого у вас должен быть другой механизм разделения.

Кроме того, ваше имя ужасно:

  • имя вашего класса начинается с нижнего регистра
  • ваши переменные имеют длину 1 букву, а некоторые - в верхнем регистре (A, p, q, r code>, ...).

Итак, я провел несколько тестов с вашим кодом, кроме того, что я изменил генератор данных на:

public static int[] data(int n) {
    Random random = new Random(seed); // Random seed stays same for all sorts
    int[] list = new int[n];

    for(int i = 0; i < list.length; i++) {
        list[i] = random.nextInt(list.length * 10);
    }

    return list;
}

Когда я запустил код yur с этим, я получил результаты:

n        Insertion        Merge            Heap             Quick            
10       0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:0:34   
1000     0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:2:480  
100000   0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:21:987 
1000000  0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:139:194
10000000 0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:1:468:183

В результате вы не попадаете в проблему с дублирующимися данными, и сортировка выполняется быстро.

Затем я удалил new Random() из произвольного раздела и просто использовал среднее значение, и результаты:

n        Insertion        Merge            Heap             Quick        
10       0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:0:17   
1000     0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:0:708  
100000   0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:18:462 
1000000  0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:103:790
10000000 0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:1:182:385

Наконец, я выполнил свой собственный сортинг, используя группировку с равными значениями, и вернул данные, чтобы ограничить их до 1000, и результаты:

n        Insertion        Merge            Heap             Quick            Monkey           
10       0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:0:16       0:0:0:0:9        
1000     0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:0:562      0:0:0:0:684      
100000   0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:16:675     0:0:0:18:119     
1000000  0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:532:437    0:0:0:65:608     
10000000 0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:48:533:774   0:0:0:694:184 

С более случайными данными сортировка обезьян замедляется, а скорость быстрого сортировки увеличивается:

n        Insertion        Merge            Heap             Quick            Monkey           
10       0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:0:16       0:0:0:0:8        
1000     0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:0:631      0:0:0:0:819      
100000   0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:16:834     0:0:0:22:353     
1000000  0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:0:103:699    0:0:0:127:421    
10000000 0:0:0:0:0        0:0:0:0:0        0:0:0:0:0        0:0:1:223:673    0:0:1:372:614 

Суть в том, что даже при хороших данных 20% вашего времени собирается создавать новые случайные экземпляры. Я использовал метод randomizePartition:

public static int randomizedPartition(int[] data, int first, int last) {
    // Random random = new Random();
    // int i = random.nextInt((last-first)+1)+first;
    swap(data,last,first + (last - first)/2);
    return partition(data,first,last);

Затем, если вас интересует сортировка обезьян:

public static long monkey(int[] list) {
    long startTime = System.nanoTime();
    monkeySort(list, 0, list.length - 1);
    return System.nanoTime() - startTime;
}

private static void monkeySort(final int[] data, final int left, final int right) {

    if (left >= right) {
        return;
    }

    // partition in this method because we need two outputs, the 'same' and the 'lft'.
    // swap values the same as the partition to the end as well.
    final int val = data[right];
    int lft = left;
    int rht = right - 1;
    int same = right;
    while (lft <= rht) {
        if (data[lft] > val) {
            swap(data, lft, rht);
            rht--;
        } else if (data[rht] == val) {
            same--;
            swap(data, rht, same);
            rht--;
        } else {
            lft++;
        }
    }

    // move all the 'same' values in to the pivot point.
    int ntop = lft - 1;
    while (same <= right) {
        swap(data, lft++, same++);
    }
    monkeySort(data, left, ntop);
    monkeySort(data, lft, right);

}

Подробнее о Random ()

Я сделал ссылку на Random, и мне стоит больше понять, что я имею в виду. Это (слегка реорганизованный) исходный код для java.util.Random :.

private static final AtomicLong seedUniquifier
    = new AtomicLong(8682522807148012L);

public Random() {
    this(seedUniquifier() ^ System.nanoTime());
}

private static long seedUniquifier() {
    // L'Ecuyer, "Tables of Linear Congruential Generators of
    // Different Sizes and Good Lattice Structure", 1999
    for (;;) {
        long current = seedUniquifier.get();
        long next = current * 181783497276652981L;
        if (seedUniquifier.compareAndSet(current, next))
            return next;
    }
}

public Random(long seed) {
    if (getClass() == Random.class)
        this.seed = new AtomicLong(initialScramble(seed));
    else {
        // subclass might have overriden setSeed
        this.seed = new AtomicLong();
        setSeed(seed);
    }
}

Обратите внимание, что существует статический AtomicLong, называемый seedUniquifier. Каждый раз, когда вы создаете новый Random, к этому AtomicLong добавляются две ссылки, что приводит к ненужному количеству эффектов памяти. Кроме того, существует потенциальное состояние гонки, которое может заставить процесс зациклиться и повторить попытку.

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

ответил rolfl 21 +04002014-10-21T08:41:15+04:00312014bEurope/MoscowTue, 21 Oct 2014 08:41:15 +0400 2014, 08:41:15
36

Эта реализация Quicksort имеет низкую производительность для массивов со многими повторяющимися элементами . Из Википедии акцент мой

  

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

     

Чтобы решить этот быстродействующий эквивалент проблемы голландского национального флага, можно использовать альтернативную процедуру разделения по линейному времени, которая разделяет значения на три группы: значения меньше, чем точка поворота, значения, равные оси вращения, и значения, превышающие стержень.

Вы можете увидеть это квадратичное поведение, запустив его на входном new int[10000], например. Фактически, вы, скорее всего, получите StackOverflowError.

Теперь в ваших тестовых данных у вас есть \ $ 10 {,} 000 {,} 000 \ $ элементы, но вы выбираете только случайные значения в диапазоне \ $ [0,1 {,} 000) \ $. Итак ... у вас много повторяющихся элементов!

Давайте запустим его как есть на моем компьютере (я не запускал сортировку вставки, поскольку она слишком медленная)

$ java AlgComp && cat times.txt
Unsorted:   323  653  751   33  350  378  913  280  243  792
 mSorted:    33  243  280  323  350  378  653  751  792  913
 hSorted:    33  243  280  323  350  378  653  751  792  913
 qSorted:    33  243  280  323  350  378  653  751  792  913
Data is being written to times.txt...
-----------------------------------------------
Done.
n        Insertion        Merge            Heap             Quick
10       0:0:0:0:0        0:0:0:0:27       0:0:0:0:35       0:0:0:0:38
1000     0:0:0:0:0        0:0:0:1:852      0:0:0:0:822      0:0:0:3:224
100000   0:0:0:0:0        0:0:0:28:421     0:0:0:20:784     0:0:0:37:872
1000000  0:0:0:0:0        0:0:0:233:576    0:0:0:202:443    0:0:0:905:65
10000000 0:0:0:0:0        0:0:2:359:261    0:0:2:752:239    0:1:20:914:310

Теперь давайте изменим эту строку в data:

list[i] = random.nextInt(1000);

к этому

list[i] = random.nextInt(1000000);

Теперь результаты соответствуют нашим ожиданиям:

$ java AlgComp && cat times.txt
Unsorted: 1662389001535502665295332468356126461089888942823562420254
 mSorted: 2356224683166238420254529533550266561264610898889428900153
 hSorted: 2356224683166238420254529533550266561264610898889428900153
 qSorted: 2356224683166238420254529533550266561264610898889428900153
Data is being written to times.txt...
-----------------------------------------------
Done.
n        Insertion        Merge            Heap             Quick
10       0:0:0:0:0        0:0:0:0:21       0:0:0:0:98       0:0:0:0:56
1000     0:0:0:0:0        0:0:0:1:997      0:0:0:1:14       0:0:0:2:41
100000   0:0:0:0:0        0:0:0:27:223     0:0:0:22:562     0:0:0:21:587
1000000  0:0:0:0:0        0:0:0:283:939    0:0:0:215:551    0:0:0:137:658
10000000 0:0:0:0:0        0:0:2:899:176    0:0:3:681:388    0:0:1:845:255

Конечно, реальное исправление заключается не в изменении data, а в изменении алгоритма разбиения.

ответил mjolka 21 +04002014-10-21T07:37:27+04:00312014bEurope/MoscowTue, 21 Oct 2014 07:37:27 +0400 2014, 07:37:27

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132