Нужна помощь в понимании этого 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 в параметрах вызываемой быстрой сортировки).Это основной способ избежать слишком большого количества параллельных потоков.

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

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

создает анонимный внутренний класс (который расширяет Thread), который затем запускается.

Answer 2

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

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

3. Это уже сделано (см. Пункт 1).

Answer 3

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

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

Многопоточная быстрая сортировка или слияние

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

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

Это считается "правильным" реализация параллели быстрая сортировка? Я спрашиваю, потому что это не использовать реализует Runnable или расширяет Автор ...

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

Runtime.getRuntime().availableProcessors()

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

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

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

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

Answer 4

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

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

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