2

我将其作为一个问题发布，因为我想与你们澄清在 Java 1.7 中使用 F/J 框架的概念，因为我看到互联网上的一些示例似乎没有意义。

使用列表而不是数组的代码是有意的。

这是递归合并排序的线性/常规版本。

package org.algorithms.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;


public class MergeSortor<T> {
    private final List<T> items;
    private final Comparator<T> c;

    public MergeSortor(final List<T> original, final Comparator<T> c) {
        if (original == null) {
            this.items = Collections.emptyList();
        } else {
            this.items = original;
        }
        this.c = c;
    }

    protected List<T> compute() {
        List<T> result = null;
        int currentSize = this.items.size();
        if (currentSize <= 1) {
            result = items;
        } else{
            int midPoint = currentSize / 2;
            List<T> left =new MergeSortor<T>(items.subList(0, midPoint), c).getSortedResult();
            List<T> right =new MergeSortor<T>(items.subList(midPoint,
                    currentSize), c).getSortedResult();
            result = merge(left,right);
        }
        return result;
    }
    private List<T> merge(List<T>left,List<T>right) {

        List<T> result = new ArrayList<T>(left.size()+right.size());
        T firstLeft = null;
        T firstRight = null;
        while (left.size() > 0 || right.size() > 0) {
            if (left.size() > 0 && right.size() > 0) {
                firstLeft = left.get(0);
                firstRight = right.get(0);
                if (c.compare(firstLeft, firstRight) <= 0) {
                    result.add(firstLeft);
                    left = left.subList(1, left.size());
                } else {
                    result.add(firstRight);
                    right = right.subList(1, right.size());
                }
            } else if (left.size() > 0){
                result.add(left.get(0));
                left = left.subList(1, left.size());
            } else if (right.size() > 0){
                result.add(right.get(0));
                right = right.subList(1, right.size());
            }
        }

        return result;
    }

    public List<T> getSortedResult() {
        return this.compute();
    }

    static public class IntegerComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            int f = o1.hashCode(); // Auto-unboxing
            int s = o2.hashCode(); // Auto-unboxing
            return f < s ? -1 : (f == s ? 0 : 1); // No unboxing
        }
    }
}

这是扩展递归任务的合并排序的 F/J 版本。

package org.algorithms.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.RecursiveTask;

public class MergeTask<T> extends RecursiveTask<List<T>>{
    private final List<T> items;
    private final Comparator<T> c;


    private static final long serialVersionUID = 8193108777395886772L;

    public MergeTask(final List<T> original, final Comparator<T> c){
        if (original == null) {
            this.items = Collections.emptyList();
        } else {
            this.items = original;
        }
        this.c = c;

    }

    @Override
    protected List<T> compute() {
        List<T> result = null;
        int currentSize = this.items.size();
        if (currentSize <= 1) {
            result = items;
        } else{
            int midPoint = currentSize / 2;
            MergeTask<T> leftSortor = new MergeTask<T>(items.subList(0, midPoint), c);
            MergeTask<T> rightSortor = new MergeTask<T>(items.subList(midPoint,
                    currentSize), c);

            rightSortor.fork(); 
            leftSortor.fork();
            result = merge(leftSortor.join(),rightSortor.join());
        }
        return result;
    }
    private List<T> merge(List<T>left,List<T>right) {

        List<T> result = new ArrayList<T>(left.size()+right.size());
        T firstLeft = null;
        T firstRight = null;
        while (left.size() > 0 || right.size() > 0) {
            if (left.size() > 0 && right.size() > 0) {
                firstLeft = left.get(0);
                firstRight = right.get(0);
                if (c.compare(firstLeft, firstRight) <= 0) {
                    result.add(firstLeft);
                    left = left.subList(1, left.size());
                } else {
                    result.add(firstRight);
                    right = right.subList(1, right.size());
                }
            } else if (left.size() > 0){
                result.add(left.get(0));
                left = left.subList(1, left.size());
            } else if (right.size() > 0){
                result.add(right.get(0));
                right = right.subList(1, right.size());
            }
        }

        return result;
    }

}

这是调用它们的主程序。

package org.algorithms.sort;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;

import org.algorithms.sort.MergeSortor.IntegerComparator;

    public class SortingRunner {

        public static void main(String[] args) throws InterruptedException, ExecutionException {
            Integer[] initialOrders = new Integer[Short.MAX_VALUE*32];
            Random random = new Random();
            for (int i =0 ;i<Short.MAX_VALUE*32;i++){
                initialOrders[i]=Integer.valueOf(random.nextInt(Integer.MAX_VALUE));
            }
            MergeSortor<Integer> sortor = new MergeSortor<Integer>(
                    Arrays.asList(initialOrders), new IntegerComparator());

            ForkJoinPool pool = new ForkJoinPool();
            MergeTask<Integer> task = new MergeTask<Integer>(Arrays.asList(initialOrders), new IntegerComparator());


            long start = System.currentTimeMillis();
            sortor.getSortedResult();
            long end =  System.currentTimeMillis();
            System.out.println(end - start );


            start = System.currentTimeMillis();
            pool.invoke(task);
            end =  System.currentTimeMillis();
            System.out.println(end - start );
        }

    }

我在网上考虑的问题是，大多数示例中的分叉是将分割任务的两条腿分叉在一起，或者先分叉左边的分叉部分，然后再分叉右边。

在合并排序中使用 F/J 的情况下，我认为这应该是一个很大的禁忌。

归并排序实际上是从左到右的线性相关排序。先左分叉不会产生任何已经存在的并行进程。F/J 框架将所有你的 fork() 按提交顺序放入队列中，然后由 F/J 池的每个工作线程分别按提交顺序提取和执行。

但是，首先正确分叉将为您提供稍后应该执行的并行计算的优势（与原始/线性实现相比）提前并首先进行尾部的划分/合并。

让我知道你们的想法。并希望这将是使用 F/J 进行排序的一个很好的例子。

4

0 回答 0