2017-02-23 121 views
0

Ниже приведен код для целочисленного Radix Sort, который использует измененную сортировку Bucket для сортировки массива. В сортировке ведра используется массив списков, где количество списков совпадает с базовым (8-восьмеричное, 10-значное, 16-шестнадцатеричное).Создание настраиваемого списка для Radix Sort

Цифра «i», полученная с помощью операции radix, вводится в список «i» массива списка. На самом деле это не цифра, а индекс в массиве ввода, который помещается в список. Для этого требуется сканирование входного массива, следовательно, время будет равно O (n). После этого индексы получают список по списку, то есть все индексы в предыдущем списке сначала обрабатываются, прежде чем переходить к следующему списку, это массив списка, а затем временный результат помещается в temp_array.

Наконец, замена указателей массивов позволяет избежать необходимости скопировать temp_array на input_array. Когда уменьшается радиус, массив списков повторно инициализируется в новых ячейках памяти. Этот способ позволяет избежать необходимости метода list.remove (index), временная сложность которого равна O (n) из-за смещения элементов. Будут ли удалены старые ячейки памяти с помощью JVM во время выполнения или они, в конце концов, приведут к переполнению памяти?

Удаление из списка по индексу 0 и последнему индексу (= N), (list.remove (0), list.remove (N)) Какой из этих подходов быстрее?

Это хорошая идея (будет работать быстрее), чтобы создать индивидуальный список (для хранения ведер) с помощью двух методов удаления (remove1(), remove2()), где один из них удаляет элемент с самого начала (требуется для возрастания) списка в O (1) времени, а другое в конце (требуется для нисходящего порядка) в то же время O (1) (без необходимости смещения элементов, а также поддержки произвольного доступа arrayList)? (Я думаю, что не может быть и того и другого.)

Если да, то каковы были бы необходимые строки кода и импортированные классы?

В случае отсутствия какого-либо другого метода для улучшения скорости алгоритма?

Меняет ли основание базу, изменяя производительность, т. Е. Зависит от производительности на базе? В случае «да», какова оптимальная база?

Любые идеи о том, как преобразовать его в многопоточную версию? Я думаю, что это невозможно.

import java.util.List ; 
import java.util.ArrayList ; 

public class Radix_Sort 
{ 
    // input_array[] -> the array to be sorted 
    // temp_array[] -> the array to hold the temporary result, must be equal to or larger than input_array in size 
    // radix -> is the number of digits in maxiumum value in array : floor of log(MaxValue) 
    // length -> length of input_array[] 
    // base -> Base of the number system used 

    public static int[] ASC(int input_array[], int temp_array[], int radix, int length, int base) 
    { 
     int div = 1 ; 
     int swap[] ; 
     int i, s_indx, Y, j ; 
     while(radix > 0) 
     { 
      List<List<Integer>> buckets = new ArrayList<List<Integer>>(base) ; 
      i = 0 ; 
      while(i < base) 
      { 
       buckets.add(new ArrayList<Integer>()) ; 
       i++ ; 
      } 
      i = 0 ; 
      while(i < length) 
      { 
       buckets.get((input_array[i]/div) % base).add(i) ; 
       i++ ; 
      } 
      s_indx = 0 ; 
      i = 0 ; 
      while(i < base) 
      { 
       Y = buckets.get(i).size() ; 
       j = 0 ; 
       while(j < Y) 
       { 
        temp_array[s_indx++] = input_array[buckets.get(i).get(j)] ; 
        j++ ; 
       } 
       i++ ; 
      } 
      swap = input_array ; 
      input_array = temp_array ; 
      temp_array = swap ; 
      div = div * base ; 
      radix--; 
     } 
     return input_array ; 
    } 

    public static int[] DSC(int input_array[], int temp_array[], int radix, int length, int base) 
    { 
     int div = 1 ; 
     int swap[] ; 
     int i, s_indx, Y ; 
     while(radix > 0) 
     { 
      List<List<Integer>> buckets = new ArrayList<List<Integer>>(base) ; 
      i = 0 ; 
      while(i < base) 
      { 
       buckets.add(new ArrayList<Integer>()) ; 
       i++ ; 
      } 
      i = 0 ; 
      while(i < length) 
      { 
       buckets.get((input_array[i]/div) % base).add(i) ; 
       i++ ; 
      } 
      s_indx = length - 1 ; 
      i = 0 ; 
      while(i < base) 
      { 
       Y = buckets.get(i).size() ; 
       while(Y > 0) 
       { 
        Y-- ; 
        temp_array[s_indx--] = input_array[buckets.get(i).get(Y)] ; 
       } 
       i++ ; 
      } 
      swap = input_array ; 
      input_array = temp_array ; 
      temp_array = swap ; 
      div = div * base ; 
      radix--; 
     } 
     return input_array ; 
    } 
}// end of class 
+0

Добавьте ярлык ** 'java' **, чтобы увеличить количество зрителей !!! –

+0

@ J.Piquard, спасибо большое – ytoamn

ответ

0

любой другой способ, чтобы улучшить скорость работы алгоритма?

Вместо использования списков списков код может выделять матрицу и заполнять ее счетчиками вхождений каждой «цифры» для каждого элемента исходного массива за один проход исходного массива. Затем счетчики могут быть преобразованы в начальные (или конечные) индексы для границ ведра для каждой «цифры». Это позволяет использовать только один массив тем же размера, что и исходный массив, чтобы содержать «ведра» на каждом проходе сортировки счисления. Метод, который вы используете для обмена ссылками (на C или C++ это будут указатели подкачки) между temp и оригиналом во время сортировки radix, является оптимальным.

Пример C++, код базового 256 поразрядной сортировки:

Radix Sort Base 16 (Hexadecimals)

является производительность зависит от базы? В случае «да», какова оптимальная база?

Оптимальное основание зависит от размера каждого элемента и количества элементов, подлежащих сортировке. Ответ в этой теме объясняет идеальный случай, а реальный случай из-за проблем кэша:

Why is the running time of radix-sort minimized when the base of the digits is equal to the number of numbers to be sorted?

Любые идеи о том, как преобразовать его в многопоточной версии

Самый простой путь состоит в том, чтобы разбить массив на k подмассивов (предполагая k эффективных ядер), сортировать k под-массивов параллельно (используя любой метод сортировки, включая сортировку по методу radix), а затем объединить k отсортированных подматриц.