externes Sortieren (MergeSort

[Nova]

Hallo,

Ich soll für die Uni MergeSort einmal rekursiv und einmal nicht-rekursiv programmieren. Ausserdem soll ich das "externe Sortieren" implementieren mit MergeSort.
Während die rekursive und nicht-rekursive Version recht übersichtlich und nur knapp 90 Zeilen lang sind ist das externe Sortieren 186 Zeilen lang... Ich denke das muss auch kürzer und einfacher gehen, weiß aber nicht wie (haben bisher noch nichts mit Dateien gemacht)

Kurz zum externen sortieren:
Die zu sortierenden Zahlen liegen in einer Datei.
Man darf die Datei nicht in ein Array einlesen und auch sonst nur von der Eingabegröße unabhängig viele Speicherzellen belegen.
Sinn soll wohl sein das man auch Dateien mit sehr vielen Zahlen sortieren kann.
=> Statt Arrays und "Hilfs-Arrays" nimmt man Dateien und "Hilfs-Dateien"



Das Programm funktioniert so wie es momentan ist, reicht wohl auch völlig für die Abgabe.
Es interessiert mich aber wie man sowas effizienter und übersichtlicher programmieren könnte.


Hier der Code:
(mir ist schon klar das man Variablen normalerweise klein schreibt, in der Vorlesung haben wir die Variablennamen der Dateien und Arrays aber groß geschrieben, daher habe ich das vorerst auch so gemacht um den Überblick zu behalten, werde ich eventuell noch ändern)

import java.io.File;
import java.util.Formatter;
import java.util.Scanner;
import javax.swing.JOptionPane;

public class Externes_sortieren{
	
	public static void main(String[]args){
		/* Vorraussetzungen: 
		 * Datei besteht aus Integerwerten getrennt durch Leerzeichen	
		 * A.txt ist die Quelldatei und befindet sich im selben Ordner */
		mergesort();
		
		System.exit(0);
	}
	
	public static void mergesort(){
		int count;                   // Anzahl Elemente in A.txt
		int laenge = 1;              // Länge der "Teildateien"
		int l = 0;                   // Position in A (fängt bei 0 an)
		File A = null;
		Scanner reader_A = null;     // Liest Datei A.txt
		File A1 = null;
		File A2 = null;
		Formatter output_A1 = null;	 // schreibt Datei A1.txt
		Formatter output_A2 = null;  // schreibt Datei A2.txt
		
		// Bestimme die Anzahl der Zahlen:
		count = bestimme_Anzahl(new File("A.txt"));	
		
		while (laenge <= count){
			for (int anz = count/laenge; anz > 0; anz -= 2){
				try {
		            A = new File("A.txt");
			        reader_A = new Scanner(A);
		   		    A1 = new File("A1.txt");
		            A2 = new File("A2.txt");
		            output_A1 = new Formatter(A1);
		            output_A2 = new Formatter(A2);
			    } catch (Exception e){
			        JOptionPane.showMessageDialog(null, "Problem in mergesort\n" + e.toString());
			        System.exit(1);
			    }
				for (int i = 0; i < l; i++){
					reader_A.nextInt(); // überspringen
				}
		    	for (int i = 1; (reader_A.hasNextInt() && i <= laenge); i++){
			    	output_A1.format("%s ",reader_A.nextInt());
		    	}
		    	for (int i = 1; (reader_A.hasNextInt() && i <= laenge); i++){
			    	output_A2.format("%s ",reader_A.nextInt());
		    	}
		    	output_A1.close();
		    	output_A2.close();
		    	reader_A.close();
		    	
		    	merge(A1,A2,A,l);
		    	
		        A1.delete();
		        A2.delete();
		    	
		    	l += 2*laenge;
		    }
		    l = 0;
			laenge *= 2; // Größe der zu sortierenden Felder verdoppeln
		}
	}
	
	public static void merge(File A1, File A2, File A, int l){
		Scanner reader_A1 = null;    // liest Datei A1.txt
		Scanner reader_A2 = null;    // liest Datei A2.txt
		File X = null;
		Scanner reader_X = null;     // liest Datei X.txt
		Formatter output_A = null;   // schreibt Datei A.txt
		
		
		try {
		    reader_A1 = new Scanner(A1);
		    reader_A2 = new Scanner(A2);
		    
		    X = new File("X.txt");
		    kopiereDatei(A,X); // A in X kopieren
		    reader_X = new Scanner(X);
		    A.delete();
		
		    output_A = new Formatter(A);
		} catch (Exception e){
			JOptionPane.showMessageDialog(null, "Problem in merge\n" + e.toString());
			System.exit(1);			
		}
		
		int count_anz = 0; // Zählt wie oft die Schleife durchlafen wurde 
		                   // (=> Anzahl der in X.txt zu überspringenden Werte) 		
		int a1 = 0, a2 = 0;
		boolean a1_used = true, a2_used = true;
		
		for (int i = 1; i <= l; i++){
			output_A.format("%s ",reader_X.nextInt());
		}
		
		while ((reader_A1.hasNextInt()) || (reader_A2.hasNextInt()) || !a1_used || !a2_used){
			count_anz++;
			if (!reader_A1.hasNextInt() && a1_used){ // falls A1 komplett "verwendet" wurde
			    if (a2_used){
			        a2 = reader_A2.nextInt();
			    }
				output_A.format("%s ",a2);
				a2_used = true;
				continue;
			}
			if (!reader_A2.hasNextInt() && a2_used){ // falls A2 komplett "verwendet" wurde
			    if (a1_used){
		            a1 = reader_A1.nextInt();
		        }
				output_A.format("%s ",a1);
				a1_used = true;
				continue;
			}
			if (a1_used){
		        a1 = reader_A1.nextInt();
		        a1_used = false;
		    }
		    if (a2_used){	
	            a2 = reader_A2.nextInt();
	            a2_used = false;
	        }
			if (a1 >= a2){
				output_A.format("%s ",a2);
				a2_used = true;
			} else {
				output_A.format("%s ",a1);
				a1_used = true;	
			}
		}
		
		for (int i = 1; i <= count_anz; i++){
			reader_X.nextInt(); // überspringen
		}
		while (reader_X.hasNextInt()){
			output_A.format("%s ",reader_X.nextInt());
		}
		
		reader_X.close();
		X.delete();
		output_A.close();
	
		reader_A1.close();
		reader_A2.close();
	}
	
	
	public static int bestimme_Anzahl(File file){
		int count = 0;
		try {
		    Scanner scanner = new Scanner(file);
		    
		    while (scanner.hasNextInt()){
		    	scanner.nextInt();
			    count++;	
		    }
		    scanner.close();
		} catch(Exception e){
			JOptionPane.showMessageDialog(null, e.toString());
			System.exit(1);
		}
		return count;
	}
	
	public static void kopiereDatei(File A, File X){
		Formatter output_X = null;
		Scanner reader_A = null;
		try {
	     	output_X = new Formatter(X);
	     	reader_A = new Scanner(A);
	    } catch (Exception e){
			JOptionPane.showMessageDialog(null, "Problem in kopiereDatei\n" + e.toString());
			System.exit(1);
	    }
	    while (reader_A.hasNextInt()){
	    	output_X.format("%s ",reader_A.nextInt());
	    }
	    output_X.close();
	    reader_A.close();
	}
}

Was mich vor allem stört:
1. kann ich die Methode "kopiereDatei(File A, File X)" nicht irgendwie umgehen indem ich die Datei A.txt in X.txt umbenenne? Mit A.rename(new File("A.txt")) hat das irgendwie nicht funktioniert...
2. kann ich die Anzahl der ahlen auch einfacher bestiommen als ich es in "bestimmeAnzahl(File file)" gemacht habe?
3. Sind Scanner zum lesen und Formatter zum schreiben von Zahlen überhaupt sinnvoll?
4. Muss ich die Files, Scanner und Formatter immer zuerst mit null initialisieren, dann im try-Block "richtig" initialisieren und kann sie dann erst benutzen?
Wenn ich diese Instanzen direkt "richtig" initialisieren will meckert er das es in einem try/catch Block stehen muss (klar, kann ja eine IO-Exception auftreten). Schreibe ich es in einen try/catch-Block meckert er das er die Variablen nicht kennt (theoretisch könnte ein Fehler auftreten wodurch nicht alle Variablen erstellt würden, kann bei mir aber nicht passieren da in dem Fall ddas Prograqmm beendet wird)
Gibts da irgendeine bessere Methode das zu realisieren?
5. Ähnliches Problem in Zeile 95. Ich muss die Variablen initialisieren, obwohl die Variablen 100%ig vor der ersten Benutzung initialisiert werden
6. Muss ich die Dateien immer wieder schließen und neu öffnen um wieder von Anfang an auslesen zu können? Oder kann ich irgendwie an den Anfang "zurückspringen" Das würde das Problem 4 schonmal stark reduzieren da diese Initialisierungen nur einmal gemacht werden müssten und es müssten auch nur einmal die Dateien geschlossen werden (unmittelbar bevor das Programm beendet wird).


Hat jemand zu einem oder mehreren Punkten eine Idee wie man das verbessern könnte?
Oder sonst einen Verbesserungsvorschlag?


mfg
Christian

 

[Nova]

Keine Verbesserungsvorschläge?


mfg
Christian

 

[Fred Ferkel]

muss das mergesort sein??
quicksort hab ich kürzlich so gemacht:

aber achtung das du das nicht zu oft laufen lässt, da geht die HDD sicher nach ner weiile in arsch...

naja das war auch halt für was ganz anders gedacht und kann als argumente strings-sequenzen bekommen wovon dann nur ein String nach int geht und zum vergleichen benutzt wird,
wenn man den überflüssigen kram rauslöscht, dann ist das vieel kürzer...

package Main;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class qSortOnDsk {
	private static String stackFile = "stack.dat";

	private static int actVal = 0;

	public static void qSort(String file, int i) {
		actVal = i;
		long nextFile = 0;
		String currentStackEntry = "";
		// "fileL0|fileR1|fileE2|fileM3|val"
		// val==0 => sort(file0)
		// val==1 => sort(file1)
		// val==2 => merge file0+file3+file1 => file2
		// else => finished
		int val = 0;
		boolean firstPop = true;
		while (firstPop || (currentStackEntry = popStack()) != null) {
			val = -2;
			if (firstPop) {
				val = 0; // fake it (or =1)
			} else {
				val = Integer.parseInt(Main.splitByChar(currentStackEntry, 4,
						'|'));
				file = Main.splitByChar(currentStackEntry, val, '|');
			}
			if (val == 0 || val == 1) {
				boolean ends = splitFile(file, Main.getFile(nextFile, 1), Main
						.getFile(nextFile + 2, 1), Main
						.getFile(nextFile + 1, 1));
				if (!firstPop)
					pushStack(Main.splitByChar(currentStackEntry, 0, '|') + "|"
							+ Main.splitByChar(currentStackEntry, 1, '|') + "|"
							+ Main.splitByChar(currentStackEntry, 2, '|') + "|"
							+ Main.splitByChar(currentStackEntry, 3, '|') + "|"
							+ (val + 1));
				if (ends)
					pushStack(Main.getFile(nextFile, 1) + "|"
							+ Main.getFile(nextFile + 1, 1) + "|" + file + "|"
							+ Main.getFile(nextFile + 2, 1) + "|2");
				else
					pushStack(Main.getFile(nextFile, 1) + "|"
							+ Main.getFile(nextFile + 1, 1) + "|" + file + "|"
							+ Main.getFile(nextFile + 2, 1) + "|0");
				nextFile += 3;
				firstPop = false;
			} else if (val == 2) {
				mergeFiles(Main.splitByChar(currentStackEntry, 0, '|'), Main
						.splitByChar(currentStackEntry, 1, '|'), Main
						.splitByChar(currentStackEntry, 3, '|'), Main
						.splitByChar(currentStackEntry, 2, '|'));
				Main.deleteFile(Main.splitByChar(currentStackEntry, 0, '|'));
				Main.deleteFile(Main.splitByChar(currentStackEntry, 1, '|'));
				Main.deleteFile(Main.splitByChar(currentStackEntry, 3, '|'));
			} else if (val == -1) {
				// should not happen! since popStack should return null or valid
				// string?
				// invalid quicksort value
				Log.epln("ERROR #1");
			}
		}
	}

	private static void mergeFiles(String fileL, String fileR, String fileM,
			String fileE) {
		Main.deleteFile(fileE);
		BufferedWriter bw = null;
		BufferedReader brL = null;
		BufferedReader brM = null;
		BufferedReader brR = null;
		try {
			bw = new BufferedWriter(new OutputStreamWriter(
					new FileOutputStream(fileE, true)));
			brL = new BufferedReader(new InputStreamReader(new FileInputStream(
					fileL)));
			brM = new BufferedReader(new InputStreamReader(new FileInputStream(
					fileM)));
			brR = new BufferedReader(new InputStreamReader(new FileInputStream(
					fileR)));
		} catch (FileNotFoundException e) {
			Log.epln("ERROR: FileNotFound @ mergeFiles");
			System.exit(1);
		}
		String tmp = null;
		try {
			while ((tmp = brL.readLine()) != null)
				bw.write(tmp + "\n");
			while ((tmp = brM.readLine()) != null)
				bw.write(tmp + "\n");
			while ((tmp = brR.readLine()) != null)
				bw.write(tmp + "\n");
			bw.close();
			brL.close();
			brM.close();
			brR.close();
		} catch (IOException e4) {
			Log.epln("ERROR: IO @ mergeFiles");
			System.exit(1);
		}
	}

	private static boolean splitFile(String fileS, String fileL, String fileM,
			String fileR) {
		boolean res = true;
		Main.deleteFile(fileL);
		Main.deleteFile(fileM);
		Main.deleteFile(fileR);
		BufferedReader br = null;
		BufferedWriter bwL = null;
		BufferedWriter bwM = null;
		BufferedWriter bwR = null;
		try {
			br = new BufferedReader(new InputStreamReader(new FileInputStream(
					fileS)));
			bwL = new BufferedWriter(new OutputStreamWriter(
					new FileOutputStream(fileL, true)));
			bwM = new BufferedWriter(new OutputStreamWriter(
					new FileOutputStream(fileM, true)));
			bwR = new BufferedWriter(new OutputStreamWriter(
					new FileOutputStream(fileR, true)));
		} catch (FileNotFoundException e) {
			Log.epln("ERROR: FileNotFound @ splitFile");
			System.exit(1);
		}
		try {
			String mid = br.readLine();
			if (mid != null) {
				long midL = Long.parseLong(Main.splitByChar(mid, actVal, '*'));
				bwM.write(mid + "\n");
				String tmp = null;
				long tmpL = 0;
				while ((tmp = br.readLine()) != null) {
					tmpL = Long.parseLong(Main.splitByChar(tmp, actVal, '*'));
					if (tmpL > midL) {
						bwR.write(tmp + "\n");
						res = false;
					} else if (tmpL < midL) {
						bwL.write(tmp + "\n");
						res = false;
					} else
						bwM.write(tmp + "\n");
				}
			}
			br.close();
			bwL.close();
			bwM.close();
			bwR.close();
		} catch (IOException e4) {
			Log.epln("ERROR: IO @ splitFile");
			System.exit(1);
		}
		return res;
	}

	private static String popStack() {
		return (stack.isEmpty()) ? null : (String) stack
				.remove(stack.size() - 1);
	}

	private static Stack stack = new Stack();

	private static void pushStack(String stackEntry) {
		stack.add(stackEntry);
	}

}

mit (hier ein paar sachen drin die du nicht benötigst)
es geht nur darum das du abhängig von einer Zahl einen stack entry bekommst

	public static String getFile(long v, int t) {
		String res = "";
		if (t == 0) // HashFiles
			res += "hf";
		if (t == 1) // stack
			res += "st";
		do {
			res += "\\" + Log.ensureWidth(v % 1000, 3);
			v /= 1000;
		} while (v != 0);
		res = appPath + res;
		res += ".dat";
		File fRes = new File(res.substring(0, res.lastIndexOf("\\")));
		fRes.mkdirs();
		if (deleteOld) {
			if (t == 0 && v > maxHF) {
				for (long i = maxHF + 1; i <= v; i++) {
					File f = new File(res);
					if (f.exists())
						f.delete();
				}
				maxHF = v;
			}
			if (t == 1 && v > maxST) {
				for (long i = maxST + 1; i <= v; i++) {
					File f = new File(res);
					if (f.exists())
						f.delete();
				}
				maxST = v;
			}
		}
		return res;
	}

und noch ne andere billig methode

	public static String splitByChar(String doublePath, int id, char c) {
		return doublePath.split("[" + c + "]")[id];
	}

und noch eine nicht unbedingt notwendige die da oben auch verwendet wird

	// appends "0" to the beginning of i until the string has a length of w 
	public static String ensureWidth(long i, int w){
		String res= String.valueOf(i);
		while(res.length()<w)
			res="0"+res;
		return res;
	}