Наиболее удобной парадигмой многопоточности для сортировки слиянием является парадигма fork-join. Это предоставляется в Java 8 и новее. Следующий код демонстрирует сортировку слиянием с использованием fork-join.
import java.util.*;
import java.util.concurrent.*;
public class MergeSort<N extends Comparable<N>> extends RecursiveTask<List<N>> {
private List<N> elements;
public MergeSort(List<N> elements) {
this.elements = new ArrayList<>(elements);
}
@Override
protected List<N> compute() {
if(this.elements.size() <= 1)
return this.elements;
else {
final int pivot = this.elements.size() / 2;
MergeSort<N> leftTask = new MergeSort<N>(this.elements.subList(0, pivot));
MergeSort<N> rightTask = new MergeSort<N>(this.elements.subList(pivot, this.elements.size()));
leftTask.fork();
rightTask.fork();
List<N> left = leftTask.join();
List<N> right = rightTask.join();
return merge(left, right);
}
}
private List<N> merge(List<N> left, List<N> right) {
List<N> sorted = new ArrayList<>();
while(!left.isEmpty() || !right.isEmpty()) {
if(left.isEmpty())
sorted.add(right.remove(0));
else if(right.isEmpty())
sorted.add(left.remove(0));
else {
if( left.get(0).compareTo(right.get(0)) < 0 )
sorted.add(left.remove(0));
else
sorted.add(right.remove(0));
}
}
return sorted;
}
public static void main(String[] args) {
ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
List<Integer> result = forkJoinPool.invoke(new MergeSort<Integer>(Arrays.asList(7,2,9,10,1)));
System.out.println("result: " + result);
}
}
Следующий вариант кода, который гораздо менее прямолинеен, устраняет чрезмерное копирование ArrayList. Первоначальный несортированный список создается только один раз, и вызовы подсписка не должны выполнять какое-либо копирование. Раньше мы копировали список массивов при каждом ответвлении алгоритма. Кроме того, теперь при объединении списков вместо создания нового списка и копирования в него значений каждый раз мы повторно используем левый список и вставляем в него наши значения. Избегая дополнительного шага копирования, мы улучшаем производительность. Здесь мы используем LinkedList, потому что вставки довольно дешевы по сравнению с ArrayList. Мы также исключаем вызов remove, который также может быть дорогостоящим для ArrayList.
import java.util.*;
import java.util.concurrent.*;
public class MergeSort<N extends Comparable<N>> extends RecursiveTask<List<N>> {
private List<N> elements;
public MergeSort(List<N> elements) {
this.elements = elements;
}
@Override
protected List<N> compute() {
if(this.elements.size() <= 1)
return new LinkedList<>(this.elements);
else {
final int pivot = this.elements.size() / 2;
MergeSort<N> leftTask = new MergeSort<N>(this.elements.subList(0, pivot));
MergeSort<N> rightTask = new MergeSort<N>(this.elements.subList(pivot, this.elements.size()));
leftTask.fork();
rightTask.fork();
List<N> left = leftTask.join();
List<N> right = rightTask.join();
return merge(left, right);
}
}
private List<N> merge(List<N> left, List<N> right) {
int leftIndex = 0;
int rightIndex = 0;
while(leftIndex < left.size() || rightIndex < right.size()) {
if(leftIndex >= left.size())
left.add(leftIndex++, right.get(rightIndex++));
else if(rightIndex >= right.size())
return left;
else {
if( left.get(leftIndex).compareTo(right.get(rightIndex)) < 0 )
leftIndex++;
else
left.add(leftIndex++, right.get(rightIndex++));
}
}
return left;
}
public static void main(String[] args) {
ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
List<Integer> result = forkJoinPool.invoke(new MergeSort<Integer>(Arrays.asList(7,2,9,-7,777777,10,1)));
System.out.println("result: " + result);
}
}
Мы также можем улучшить код еще на один шаг, используя итераторы вместо прямого вызова get при выполнении слияния. Причина этого в том, что попадание в LinkedList по индексу имеет низкую временную производительность (линейную), поэтому с помощью итератора мы устраняем замедление, вызванное внутренней итерацией связанного списка при каждом получении. Вызов next на итераторе - это постоянное время, в отличие от линейного времени для получения вызова. Следующий код изменен для использования вместо него итераторов.
import java.util.*;
import java.util.concurrent.*;
public class MergeSort<N extends Comparable<N>> extends RecursiveTask<List<N>> {
private List<N> elements;
public MergeSort(List<N> elements) {
this.elements = elements;
}
@Override
protected List<N> compute() {
if(this.elements.size() <= 1)
return new LinkedList<>(this.elements);
else {
final int pivot = this.elements.size() / 2;
MergeSort<N> leftTask = new MergeSort<N>(this.elements.subList(0, pivot));
MergeSort<N> rightTask = new MergeSort<N>(this.elements.subList(pivot, this.elements.size()));
leftTask.fork();
rightTask.fork();
List<N> left = leftTask.join();
List<N> right = rightTask.join();
return merge(left, right);
}
}
private List<N> merge(List<N> left, List<N> right) {
ListIterator<N> leftIter = left.listIterator();
ListIterator<N> rightIter = right.listIterator();
while(leftIter.hasNext() || rightIter.hasNext()) {
if(!leftIter.hasNext()) {
leftIter.add(rightIter.next());
rightIter.remove();
}
else if(!rightIter.hasNext())
return left;
else {
N rightElement = rightIter.next();
if( leftIter.next().compareTo(rightElement) < 0 )
rightIter.previous();
else {
leftIter.previous();
leftIter.add(rightElement);
}
}
}
return left;
}
public static void main(String[] args) {
ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
List<Integer> result = forkJoinPool.invoke(new MergeSort<Integer>(Arrays.asList(7,2,9,-7,777777,10,1)));
System.out.println("result: " + result);
}
}
Наконец, самые сложные версии кода, эта итерация использует полностью локальную операцию. Создается только начальный ArrayList, и никакие дополнительные коллекции никогда не создаются. Таким образом, логику особенно сложно соблюдать (поэтому я оставил ее напоследок). Но он должен быть максимально приближен к идеальной реализации.
import java.util.*;
import java.util.concurrent.*;
public class MergeSort<N extends Comparable<N>> extends RecursiveTask<List<N>> {
private List<N> elements;
public MergeSort(List<N> elements) {
this.elements = elements;
}
@Override
protected List<N> compute() {
if(this.elements.size() <= 1)
return this.elements;
else {
final int pivot = this.elements.size() / 2;
MergeSort<N> leftTask = new MergeSort<N>(this.elements.subList(0, pivot));
MergeSort<N> rightTask = new MergeSort<N>(this.elements.subList(pivot, this.elements.size()));
leftTask.fork();
rightTask.fork();
List<N> left = leftTask.join();
List<N> right = rightTask.join();
merge(left, right);
return this.elements;
}
}
private void merge(List<N> left, List<N> right) {
int leftIndex = 0;
int rightIndex = 0;
while(leftIndex < left.size() ) {
if(rightIndex == 0) {
if( left.get(leftIndex).compareTo(right.get(rightIndex)) > 0 ) {
swap(left, leftIndex++, right, rightIndex++);
} else {
leftIndex++;
}
} else {
if(rightIndex >= right.size()) {
if(right.get(0).compareTo(left.get(left.size() - 1)) < 0 )
merge(left, right);
else
return;
}
else if( right.get(0).compareTo(right.get(rightIndex)) < 0 ) {
swap(left, leftIndex++, right, 0);
} else {
swap(left, leftIndex++, right, rightIndex++);
}
}
}
if(rightIndex < right.size() && rightIndex != 0)
merge(right.subList(0, rightIndex), right.subList(rightIndex, right.size()));
}
private void swap(List<N> left, int leftIndex, List<N> right, int rightIndex) {
//N leftElement = left.get(leftIndex);
left.set(leftIndex, right.set(rightIndex, left.get(leftIndex)));
}
public static void main(String[] args) {
ForkJoinPool forkJoinPool = ForkJoinPool.commonPool();
List<Integer> result = forkJoinPool.invoke(new MergeSort<Integer>(new ArrayList<>(Arrays.asList(5,9,8,7,6,1,2,3,4))));
System.out.println("result: " + result);
}
}
person
Jeffrey Phillips Freeman
schedule
26.04.2018
