2

マージソートを使用してマルチスレッドを実装しようとしています。配列を半分にカットした時点で新しいスレッドを作成しています。
配列は、[配列のサイズ] 対 [新しいスレッドを作成する回数] に応じて並べ替えられます。 6 を作成すると、ソートされずに返されます。私が考えたのは、スレッドが同期されていなかったということですが、私は threadName.join() を使用しました

ここにいくつかのコードがあります：merge.java

import java.util.Random;

public class merge implements Runnable {
    int[] list;
    int length;
    int countdown;

    public merge(int size, int[] newList, int numberOfThreadReps, int firstMerge) {
        length = size;
        countdown = numberOfThreadReps;
        list = newList;
        if (firstMerge == 1)
            threadMerge(0, length - 1);
    }

    public void run() {
        threadMerge(0, length - 1);
    }

    public void printList(int[] list, int size) {
        for (int i = 0; i < size; i++) {
            System.out.println(list[i]);
        }
    }

    public void regMerge(int low, int high) {
        if (low < high) {
            int middle = (low + high) / 2;
            regMerge(low, middle);
            regMerge(middle + 1, high);
            mergeJoin(low, middle, high);
        }
    }

    public void mergeJoin(int low, int middle, int high) {
        int[] helper = new int[length];

        for (int i = low; i <= high; i++) {
            helper[i] = list[i];
        }

        int i = low;
        int j = middle + 1;
        int k = low;

        while (i <= middle && j <= high) {
            if (helper[i] <= helper[j]) {
                list[k] = helper[i];
                i++;
            } else {
                list[k] = helper[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            list[k] = helper[i];
            k++;
            i++;
        }
        helper = null;
    }

    public void threadMerge(int low, int high) {
        if (countdown > 0) {
            if (low < high) {
                countdown--;
                int middle = (low + high) / 2;
                int[] first = new int[length / 2];
                int[] last = new int[length / 2 + ((length % 2 == 1) ? 1 : 0)];
                for (int i = 0; i < length / 2; i++)
                    first[i] = list[i];
                for (int i = 0; i < length / 2 + ((length % 2 == 1) ? 1 : 0); i++)
                    last[i] = list[i + length / 2];

                merge thread1 = new merge(length / 2, first, countdown, 0);// 0
                                                                            // is
                                                                            // so
                                                                            // that
                                                                            // it
                                                                            // doesn't
                                                                            // call
                                                                            // threadMerge
                                                                            // twice
                merge thread2 = new merge(length / 2
                        + ((length % 2 == 1) ? 1 : 0), last, countdown, 0);

                Thread merge1 = new Thread(thread1);
                Thread merge2 = new Thread(thread2);
                merge1.start();
                merge2.start();

                try {
                    merge1.join();
                    merge2.join();
                } catch (InterruptedException ex) {
                    System.out.println("ERROR");
                }

                for (int i = 0; i < length / 2; i++)
                    list[i] = thread1.list[i];
                for (int i = 0; i < length / 2 + ((length % 2 == 1) ? 1 : 0); i++)
                    list[i + length / 2] = thread2.list[i];

                mergeJoin(low, middle, high);
            } else {
                System.out.println("elsd)");
            }
        } else {
            regMerge(low, high);
        }
    }
}

proj4.java

import java.util.Random;

public class proj4 {
    public static void main(String[] args) {
        int size = 70000;
        int threadRepeat = 6;
        int[] list = new int[size];
        list = fillList(list, size);
        list = perm(list, size);
        merge mergy = new merge(size, list, threadRepeat, 1);
        // mergy.printList(mergy.list,mergy.length);
        for (int i = 0; i < mergy.length; i++) {
            if (mergy.list[i] != i) {
                System.out.println("error)");
            }
        }
    }

    public static int[] fillList(int[] list, int size) {
        for (int i = 0; i < size; i++)
            list[i] = i;
        return list;
    }

    public static int[] perm(int[] list, int size) {
        Random generator = new Random();
        int rand = generator.nextInt(size);
        int temp;
        for (int i = 0; i < size; i++) {
            rand = generator.nextInt(size);
            temp = list[i];
            list[i] = list[rand];
            list[rand] = temp;
        }
        return list;
    }

}

TL;DR配列のサイズと、スレッドを使用して配列を分割した回数に基づいて、マルチスレッドマージソートによって配列がソートされません...なぜですか?

4

1 に答える 1

4

わお。これはマゾヒズムの興味深い演習でした。あなたは先に進んだと確信していますが、私は後世のために考えました...

コードのバグはmergeJoin引数にありmiddleます。これは問題ありregMergeませんがthreadMerge、途中で is(low + high) / 2の代わりに渡され(length / 2) - 1ます。inthreadMerge lowは常に 0 でhighありlength - 1、first配列には(length / 2)サイズがあるためです。これは、エントリ数が奇数のリストの場合、ランダム化によっては失敗することが多いことを意味します。

また、このプログラムを非常に複雑にし、エラーを起こしやすい多くのスタイルの問題もあります。

  • list.lengthJava がより簡単で安全な便利な呼び出しを持っている場合、コードは配列のサイズを渡します。
  • length/2このコードでは、多くの場所で計算が重複しています (「参考文献」を参照)。
  • コードは、サブ配列を作成せずに配列内でソートできる必要があります。
  • クラスは大文字で始める必要があります (Mergeの代わりにmerge)
  • firstMergeブール値である必要があります
  • コードはThread変数merge1とmerge変数に名前を付けますthread1。ゴクゴク。
  • コンストラクターのmerge呼び出しthreadMerge(0,length -1)は奇妙です。newコールバックの後にそのコールを入れproj4ます。その後firstMerge、削除することができます。
  • high最大値ではなく、最大値を1つ超えるように切り替えることを検討します。for (int i = 0; i < 10; i++)以上のように考える傾向がありますi <= 9。次に、コードはtoおよびfrom toにj移動できます。より良い対称性。low< middlekmiddle< high

幸運を祈ります。

于 2011-09-20T20:46:46.830 に答える