Нужна помощь понимание этого Java код пожалуйста :-)

Question

Просто интересно, если кто-нибудь сможет посмотреть на этот код для реализации алгоритма быстрой сортировки и ответьте мне на несколько вопросов, пожалуйста :-)

public class Run 
{ 
    /*************************************************************************** 
    * Quicksort code from Sedgewick 7.1, 7.2. 
    **************************************************************************/ 
    public static void quicksort(double[] a) 
    { 
    //shuffle(a); // to guard against worst-case 
    quicksort(a, 0, a.length - 1, 0); 
    } 

    static void quicksort(final double[] a, final int left, final int right, final int tdepth) 
    { 
    if (right <= left) 
     return; 
    final int i = partition(a, left, right); 

    if ((tdepth < 4) && ((i - left) > 1000)) 
    { 
     final Thread t = new Thread() 
     { 
     public void run() 
     { 
      quicksort(a, left, i - 1, tdepth + 1); 
     } 
     }; 
     t.start(); 
     quicksort(a, i + 1, right, tdepth + 1); 

     try 
     { 
     t.join(); 
     } 
     catch (InterruptedException e) 
     { 
     throw new RuntimeException("Cancelled", e); 
     } 
    } else 
    { 
     quicksort(a, left, i - 1, tdepth); 
     quicksort(a, i + 1, right, tdepth); 
    } 
    } 

    // partition a[left] to a[right], assumes left < right 
    private static int partition(double[] a, int left, int right) 
    { 
    int i = left - 1; 
    int j = right; 
    while (true) 
    { 
     while (less(a[++i], a[right])) 
     // find item on left to swap 
     ; // a[right] acts as sentinel 
     while (less(a[right], a[--j])) 
     // find item on right to swap 
     if (j == left) 
      break; // don't go out-of-bounds 
     if (i >= j) 
     break; // check if pointers cross 
     exch(a, i, j); // swap two elements into place 
    } 
    exch(a, i, right); // swap with partition element 
    return i; 
    } 

    // is x < y ? 
    private static boolean less(double x, double y) 
    { 
    return (x < y); 
    } 

    // exchange a[i] and a[j] 
    private static void exch(double[] a, int i, int j) 
    { 
    double swap = a[i]; 
    a[i] = a[j]; 
    a[j] = swap; 
    } 

    // shuffle the array a[] 
    private static void shuffle(double[] a) 
    { 
    int N = a.length; 
    for (int i = 0; i < N; i++) 
    { 
     int r = i + (int) (Math.random() * (N - i)); // between i and N-1 
     exch(a, i, r); 
    } 
    } 

    // test client 
    public static void main(String[] args) 
    { 
    int N = 5000000; // Integer.parseInt(args[0]); 

    // generate N random real numbers between 0 and 1 
    long start = System.currentTimeMillis(); 
    double[] a = new double[N]; 
    for (int i = 0; i < N; i++) 
     a[i] = Math.random(); 
    long stop = System.currentTimeMillis(); 
    double elapsed = (stop - start)/1000.0; 
    System.out.println("Generating input: " + elapsed + " seconds"); 

    // sort them 
    start = System.currentTimeMillis(); 
    quicksort(a); 
    stop = System.currentTimeMillis(); 
    elapsed = (stop - start)/1000.0; 
    System.out.println("Quicksort: " + elapsed + " seconds"); 

    } 
} 

Мои вопросы:

1. Какова цель переменной tdepth?

2. Рассматривается ли это «правильная» реализация параллельной быстрой сортировки? Я спрашиваю, потому что он не использует implements Runnable или extends Thread ...

3. Если это еще не есть, возможно ли изменить этот код, чтобы использовать несколько потоков? Передавая количество потоков, которые вы хотите использовать в качестве параметра, например ...?

Большое спасибо,

Brian

Answer 1

1.   Он используется для отслеживания глубины рекурсии. Это проверяется, чтобы решить, следует ли запускать параллельно. Обратите внимание, что когда функция работает параллельно, она проходит tdepth + 1 (которая становится tdepth в параметрах вызываемого quicksort). Это основной способ избежать слишком большого количества параллельных потоков.

2.   Да, это определенно использует другую тему. Код:

new Thread() 
{ 
    public void run() 
    { 
    quicksort(a, left, i - 1, tdepth + 1); 
    } 
}; 

создает anonymous inner class (который расширяет тему), который затем запускается.

Answer 2

1. Видимо, tdepth используется, чтобы избежать создания слишком большого количества потоков

2. Он использует анонимный класс, который неявно расширяет Пропустите

3. Это уже (смотри пункт 1.)

Answer 3

1. tdepth там так, что есть до за ограничение количества созданных потоков. Обратите внимание, что всякий раз, когда метод вызывает себя рекурсивно (что делается в новом потоке), tdepth увеличивается на единицу. Таким образом, только первые четыре уровня рекурсии будут создавать новые потоки, по-видимому, предотвращать перегрузку ОС со многими потоками для небольшой выгоды.

2. Этот код запускает собственные потоки в определении метода quicksort, поэтому он будет использовать параллельную обработку. Можно было бы утверждать, что это может быть связано с каким-то управлением потоками, и, например, какой-то Executor может быть лучше, но он определенно параллелен. См. Звонок new Thread() ..., а затем start(). Кстати, вызов t.join() вызовет поток current, чтобы подождать, пока закончится нить t, если вы этого не знали.

3. Этот код уже использует несколько потоков, но вы можете настроить, сколько он порождает, учитывая сравнение на tdepth; увеличение или уменьшение значения определит, сколько уровней рекурсии создает потоки. Вы можете завершить переписывание кода, чтобы использовать исполнители и потоковые пулы, или, возможно, выполнять рекурсию вместо двоичной, но я подозреваю, что в том смысле, о котором вы просили; нет, нет простой способ настроить количество потоков.

Answer 4

Я на самом деле написал (правильно) многопоточного QuickSort в Java так что, возможно, я могу немного помочь ...

Вопрос здесь для тех, кто интересуется:

Multithreaded quicksort or mergesort

Какова цель переменной tdepth?

как другие прокомментировали, он служит для определения того, создавать ли новые потоки или нет.

Является ли это считается «правильной» реализации параллельного сортировки? Я спрашиваю, потому что это не использование реализует Runnable или расширяет тему ...

Я не думаю, что это то, что собственно по нескольким причинам: во-первых, вы должны сделать его CPU зависит. Нет смысла создавать 16 потоков на процессоре с одним ядром: однопоточный QuickSort должен превосходить многопоточность на одноядерном компьютере. На 16-ядерных машинах, конечно, огонь до 16 потоков.

Runtime.getRuntime().availableProcessors() 

Тогда вторая причина, я действительно не нравится то, что он использует последнюю век низкоуровневого Java idiosyncrasish поточной деталь: Я предпочитаю держаться подальше от .join() и использовать более высокий уровень (см. раздел fork/join в другом вопросе или что-то вроде CountDownLatch'es и т. д.). Проблема с тем, что низкоуровневая, например, «поток» в Java, заключается в том, что она не имеет никакого полезного значения: это 100% -ная Java-специфика и может быть заменена более высокоуровневыми средствами потоковой передачи, концепция которых переносима на разных языках.

Тогда не комментируйте тасование в начале. Когда-либо. Я видел набор данных, где QuickSort деградирует квадратично, если вы удалите эту перетасовку. И это всего лишь O (п) перетасовать, что не замедлит ваш сорт :)

Если это не уже, возможно изменить этот код, чтобы использовать несколько потоков? Пропустив число потоков, которые вы хотите использовать в качестве параметра , например ...?

Я бы попытался написать и/или повторно использовать реализацию с использованием средств параллелизма на более высоком уровне. Посмотрите советы в вопросе, который я задал здесь некоторое время назад.