Java 用线程对单词数组进行排序

Question

我有一个 txt 文件，其中包含我需要能够按字母顺序排序的名称。然后，我的程序获取该数组，将其拆分为在终端中作为参数传递的线程数量，并为每个线程提供一 block 数组进行排序，然后将所有线程存储在一个数组中。现在，我需要一些帮助是: 我现在想要在线程完成后立即获取线程(即，如果两个线程先于其他线程完成，则它们开始合并，然后等待更多线程)。把它想象成辫子。我知道如何编写合并的排序代码，但我希望你能帮助我的是:如何管理线程？我知道 wait() 和 notification() 的作用，但我似乎无法将我的 ead 包装在我到底需要做什么才能使它们合并到一个数组中。我应该:

1. 在线程类中创建一个合并数组的方法？
2. 为每个已完成的其他线程创建一个新线程，将两个排序后的单词数组作为参数传递，然后让该线程进行排序？
3. 还有一些我没想到的事情。

我希望这足够清楚，并且问题的质量足够好。

Answer 1

我认为你应该使用Merge Sort算法及其实现基于 ForkJoinPool (当然，如果您使用的是 Java 7)。

该算法非常适合，因为作业可以拆分为独立的任务，可以由不同的线程处理。现在，ForkJoinPool 为您提供了易于使用的池，您可以在其中提交排序任务。

实现应该像这样完成:

• 每个任务都会对给定的一段数组/列表进行排序；
• 如果数组很小(小的确切含义可以通过常量配置) - 则使用标准 .sort() 方法进行排序，否则将拆分为两半，并将这些半提交到池中进行排序；
• 然后任务等待两个子任务完成并将两个已排序的数组/列表合并为一个，然后返回；

这是该算法的示例实现。请注意，这远非最佳，因为它消耗了大量的额外内存。我这样实现它是为了演示方法。使用 -Xmx1024m 运行它。

public class ForkJoinSort {

    private static final int LIST_SIZE = 10000;

    private static final int SORT_THRESHOLD = 10; //the minimal length of the list to use standard java sort rather than mergesort

    private static ForkJoinPool forkJoinPool = new ForkJoinPool();

    public static class MergeSortTask extends RecursiveTask<List<Integer>> {

        private final List<Integer> victim;

        public MergeSortTask(List<Integer> victim) {
            this.victim = victim;
        }

        @Override
        protected List<Integer> compute() {
            if (victim.size() < SORT_THRESHOLD) {
                Collections.sort(victim);
                return victim;
            }

            //sorting left and right parts of the list separately in separate threads
            MergeSortTask leftTask = new MergeSortTask(victim.subList(0, victim.size() / 2));
            MergeSortTask rightTask = new MergeSortTask(victim.subList(victim.size() / 2, victim.size()));
            forkJoinPool.submit(leftTask);
            forkJoinPool.submit(rightTask);

            //do merge
            return merge(leftTask.join(), rightTask.join());
        }

        public List<Integer> merge(List<Integer> left, List<Integer> right) {
            List<Integer> result = new ArrayList<Integer>(left.size() + right.size());

            Iterator<Integer> leftIterator = left.iterator();
            Iterator<Integer> rightIterator = right.iterator();

            Integer fromLeft = null;
            Integer fromRight = null;

            while (leftIterator.hasNext() || rightIterator.hasNext()) {
                //if current value taken from the iterator is null - take new one if possible, otherwise do nothing
                fromLeft = fromLeft == null ? leftIterator.hasNext() ? leftIterator.next() : null : fromLeft;
                fromRight = fromRight == null ? rightIterator.hasNext() ? rightIterator.next() : null : fromRight;

                if (fromLeft != null && (fromRight == null || fromLeft <= fromRight)) {
                    result.add(fromLeft);
                    fromLeft = null; //this is done to indicate that value from left iterator already passed to result list
                } else if (fromRight != null && (fromLeft == null || fromRight <= fromLeft)) {
                    result.add(fromRight);
                    fromRight = null;
                }
            }

            return result;
        }
    }

    public static void main(String[] args) throws Exception {
        SecureRandom random = new SecureRandom();

        //generate array of random numbers
        List<Integer> victim = new ArrayList<Integer>(LIST_SIZE);
        for (int i = 0; i < LIST_SIZE; ++i) {
            victim.add(random.nextInt());
        }

        //do some benchmarking as long as we're here
        long timeMark = System.currentTimeMillis();
        MergeSortTask task = new MergeSortTask(victim);
        forkJoinPool.submit(task);
        List<Integer> probablySorted = task.get();
        timeMark = System.currentTimeMillis() - timeMark;

        //asserting that array is sorted
        for (int i = 0; i < probablySorted.size() - 1; ++i) {
            if (probablySorted.get(i) > probablySorted.get(i + 1)) {
                throw new IllegalStateException("Sorting failed :(");
            }
        }

        System.out.println("Sorting " + LIST_SIZE + " random numbers using merge sort algorithm in " + Runtime.getRuntime().availableProcessors() + " threads took " + timeMark + " ms.");
    }
}

我试图使代码易于阅读。如果我在某个地方失败了，请随时询问。