1

みなさん、良い一日を！ここに、マージソートを使用してファイルから50,000語をソートするプログラムがあります。私はThomasCormenの「アルゴリズム入門」の擬似コードに従いましたが、手動で「デバウジング」しているときは正しいようです。ただし、プログラムを実行すると、と表示されます Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2 。はい、それは大きい（つまり、50,000）ためだと思いますが NO_OF_WORDS 、10に減らしても、同じエラーが表示されます。

import java.io.*;
import java.util.*;

public class SortingAnalysis {

    public static void merge(String[] A, int p, int q, int r) {
        int n1 = q-p+1;
        int n2 = r-q;
        String[] L = new String[n1+1];
        String[] R = new String[n2+1];
        for (int i=1; i<n1; i++) {
            L[i] = A[p+i-1];
        }
        for (int j=1; j<n2; j++) {
            R[j] = A[q+j];
        }
        L[n1+1] = "zzzzz"; //for infinity because if I use Math.floor, it will return a double
        R[n2+1] = "zzzzz";
        int i=1;
        int j=1;
        for (int k=p; k<=r; k++) {
            int comparison = L[i].compareTo(R[j]);
            if (comparison <= 0){
                A[k] = L[i];
                i++;
            }
            else {
                A[k] = R[j];
                j++;
            }

        }

    }

    public static void mergeSort (String[] A, int p, int r) {
        if (p<r) {
            int q = (p+r)/2;
            mergeSort(A, p, q);
            mergeSort(A, q+1, r);
            merge(A, p, q, r);
        }
    }

    public static void main(String[] args) {
        final int NO_OF_WORDS = 50000;
        try {
            Scanner file = new Scanner(new File(args[0]));
            String[] words = new String[NO_OF_WORDS];

            int i = 0;
            while(file.hasNext() && i < NO_OF_WORDS) {
                words[i] = file.next();
                i++;
            }
            long start = System.currentTimeMillis();

            mergeSort(words, 0, words.length-1);

            long end = System.currentTimeMillis();
            System.out.println("Sorted Words: ");
            for(int j = 0; j < words.length; j++) {
                System.out.println(words[j]);
            }   
            System.out.print("Running time: " + (end - start) + "ms");

        }
        catch(SecurityException securityException) {
            System.err.println("Error");
            System.exit(1);
        }
        catch(FileNotFoundException fileNotFoundException) {
            System.err.println("Error");
            System.exit(1);
        } 
    } 
}

String[]LとRの宣言によるものだと思います。何が問題なのか教えてください。どうもありがとうございます！


コーメンの擬似コードを編集する

MERGE(A, p, q, r )
n1 ← q − p + 1
n2 ←r − q
create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
for i ← 1 to n1
     do L[i ] ← A[p + i − 1]
for j ← 1 to n2
     do R[ j ] ← A[q + j ]
L[n1 + 1]←∞
R[n2 + 1]←∞
i ← 1
j ← 1
for k ← p to r
     do if L[i ] ≤ R[ j ]
        then A[k] ← L[i ]
             i ←i + 1
        else A[k] ← R[ j ]
             j ← j + 1
4

2 に答える 2

1

あなたのmerge()方法には大きな問題があります：

String[] L = new String[n1+1];
String[] R = new String[n2+1];

うまく遊べない

L[n1+1] = "zzzzz"; //for infinity because if I use Math.floor, it will return a double
R[n2+1] = "zzzzz";

配列はJavaでは0ベースであるため、およびArrayIndexOutOfBoundsExceptionの値に関係なく、ここに表示されます。n1n2

于 2012-07-10T14:07:14.523 に答える
1

あなたの擬似コードが何であるかはわかりませんが、あなたの実装は間違っているようです。ウィキペディアのマージソートを見てきましたが、まったく異なります。

したがって、ここでは完全に機能するアルゴリズムについては説明しません。indexOutOfBoundsの問題を解決するための解決策を提供しますが、それでも実装にさらに取り組む必要があります。

Javaでそれを行うとき：

String[] L = new String[5];

文字列を含むことができる文字列の配列を宣言し5ます。

これらの文字列へのアクセスは次のように行われます：L[anIndex]。

最初の要素はインデックスにあります0。

したがって、サイズの配列がある場合5 、最後の要素はインデックスにあります4（0から開始するため）。

あなたのコードではこれを行います：

String[] L = new String[n1+1];
String[] R = new String[n2+1];

それから ：

L[n1+1] = "zzzzz";
R[n2+1] = "zzzzz";

したがって、ここでは常に、存在しないインデックスの文字列にアクセスしようとします。各配列の最後の要素はそれぞれn1とですn2（配列のサイズはとであるためn1+1）n2+1。

この説明で、Javaで配列がどのように機能するかをよりよく理解していただければ幸いです。まだ機能していないため、実装を改善する必要があります。よくわからない場合は、使用する擬似コードを教えてください。

編集 ：

修正しました。

これが動作するアルゴリズムです。Javaの「based-0配列」に合うようにいくつかのインデックスを変更する必要がありました。見てみましょう：

import java.io.*;
import java.util.*;

public class SortingAnalysis {

    public static void merge(String[] A, int p, int q, int r) {
        int n1 = q-p+1;
        int n2 = r-q;
        if(A[p]==null || A[q]==null)return;
        String[] L = new String[n1+1];
        String[] R = new String[n2+1];
        for (int i=0; i<n1; i++) {
            L[i] = A[p+i];
        }
        for (int j=0; j<n2; j++) {
            R[j] = A[q+j +1];
        }
        L[n1] = "zzzzz"; //for infinity because if I use Math.floor, it will return a double
        R[n2] = "zzzzz";
        int i=0;
        int j=0;
        for (int k=p; k<=r; k++) {
            int comparison = L[i].compareTo(R[j]);
            if (comparison <= 0){
                A[k] = L[i];
                i++;
            }
            else {
                A[k] = R[j];
                j++;
            }

        }

    }

    public static void mergeSort (String[] A, int p, int r) {
        if (p<r) {
            int q = (p+r)/2;
            mergeSort(A, p, q);
            mergeSort(A, q+1, r);
            merge(A, p, q, r);
        }
    }

    public static void main(String[] args) {
        final int NO_OF_WORDS = 50000;
        try {
            Scanner file = new Scanner("bla blya blay byla ybla");
            ArrayList<String> words = new ArrayList<String>();

            while(file.hasNext() && words.size() < NO_OF_WORDS) {
                words.add(file.next());
            }
            String [] wordsArray = new String[words.size()];
            words.toArray(wordsArray);
            long start = System.currentTimeMillis();

            mergeSort(wordsArray, 0, wordsArray.length-1);

            long end = System.currentTimeMillis();
            System.out.println("Sorted Words: ");
            for(int j = 0; j < wordsArray.length; j++) {
                System.out.println(wordsArray[j]);
            }   
            System.out.print("Running time: " + (end - start) + "ms");

        }
        catch(SecurityException securityException) {
            System.err.println("Error");
            System.exit(1);
        }

    }
}

Mainを変更したことに注意してください。テキストに含まれる単語が元の配列サイズより少ない場合は、null値を回避するためにarrayListを使用します。ソリューションでは、50000語を入力しないと、配列でnullが発生し、マージアルゴリズムでnullPointerExceptionが発生します。

于 2012-07-10T14:56:43.387 に答える