PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Stapelspeicher durchsortieren



Barny
28.06.2012, 15:33
Hiho!
Ich habe vor kurzem einen Wordlistgenerator geschrieben und bin auf das Problem gestoßen, dass doch viele Wörter doppelt oder dreifach in der Liste vorhanden sind, was ja nicht unbedingt sein muss.
Zur Lösung des Problems habe ich etwas gecodet, was mir diese Liste einmal komplett durchsortiert, und da wir in Informatik vor kurzem den Stapelspeicher oder auch Kellerspeicher durchgenommen haben, wollte ich diesen direkt einmal sinnvoll einsetzen.
Hat auch gut geklappt, nur jetzt erhalte ich einen Fehler der eher mit meinem Array zusammenhängt ( ArrayIndexOutOfBoundsException ), welchen ich mir aber nicht erklären kann oder einfach nur blind bin.^^
Vielleicht sieht ja einer von euch den Fehler und kann mir ein wenig auf die Sprünge helfen.^^
Hier ist der Quellcode:

import java.io.BufferedReader;
import java.io.FileReader;


public class main {


public static void main(String[] args) throws InterruptedException{

int i=0,j=0;

String[]array= new String[5001];

verweiskeller v = new verweiskeller();


try {

BufferedReader in = new BufferedReader(new FileReader("/home/Barny/Desktop/wordlist.txt"));
String zeile = null;

//Einlesen der Wörter
while ((zeile = in.readLine()) != null) {
v.push(zeile);
System.out.println("Wort "+(i+1)+" gelesen!");
i++;
}
System.out.println("Alle Wörter wurden eingelesen und sind bereit zum Sortieren...");
Thread.sleep(2000);
System.out.println("Beginne Sortieren...");
Thread.sleep(1500);

//Sortieren
do{
int k=0;
int duplikat=0;

while((k<=array.length-1)) {
if(v.top().equals(array[k])){
duplikat++;
}
k++;
}

if(duplikat>0) {
v.pop();
duplikat=0;
} else {
array[k]= (String) v.top();
k=0;
v.pop();
}

}while(!v.empty());


}catch(Exception e) {
System.err.println("Ein Fehler ist aufgetreten");
}

}

}

Zum Verständnis meiner Kellerspeichers:
Ich arbeite mir dem "First in last out"-Prinzip.
pop() = Oberstes Element löschen
top() = Oberstes Element abrufen
push() = Element hinzufügen
empty() = boolsche Abfrage ob noch was auf dem Stack liegt

Ich bedanke mich schonmal im Vorraus für die Hilfe und ich hoffe mein Fehler ist nicht ganz so daneben. Ist heute echt warm und kann mich kaum konzentrieren, würde das aber trotzdem heute gerne fertig kriegen. :D

mfg

Barny

blackberry
28.06.2012, 19:40
Ich hoffe dir ist aber bewusst, dass es in Java für solche Aufgaben spezialisierte Datentypen wie Mengen (Set) gibt?

Für gewöhnlich ist Laufzeit bei kleinen Programmen ja wohl keine Frage, aber wenn es hier um Wortlisten geht und du da wirklich viele davon hast, die du sortieren willst, dann wird das das mit Sicherheit doch einen bemerkbaren Laufzeitverlust geben.

Wieso also nicht mit Sets? Kurz, schnell, elegant:

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.HashSet;

public class main
{
public static void main(String[] args) throws InterruptedException
{
HashSet<String> M = new HashSet<String>();
try
{
BufferedReader in = new BufferedReader(new FileReader("wordlist.txt"));
String zeile = null;
while ((zeile = in.readLine()) != null)
{
M.add(zeile);
}
for(String s : M)
{
System.out.println(s);
}
}
catch(Exception e)
{
System.err.println("Ein Fehler ist aufgetreten");
}
}
}

Beispiel:

● ● ● cat wordlist.txt
das
ist
ein
Test
wobei
das
"das"
doppelt
vorkommt
● ● ● javac main.java; java main
das
Test
wobei
ein
vorkommt
"das"
ist
doppelt

Barny
28.06.2012, 19:53
Danke für die Antwort, und wenn ich ehrlich bin war mir das bis jetzt nicht bewusst, aber man lernt ja nie aus.^^
Das es evtl. zu Laufzeitverlusten kommen kann bei größeren Wortlisten war mir aber bewusst, und ich denke, dass deine Lösung optimal ist. :)

mfg

Barny

//Edit:
Habe es jetzt so umgesetzt und funktioniert 1a. ;)