Testklasse wie schnell Boyermoore ist stuerzt ab

[the_menace]

Hallo,
ich schreibe gerade eine testklasse,
wie schnell der algorithmus bei zufaelligen eingaben ist
aber er stuerzt mir immer wieder ab, und ich habe im moment keinen plan warum
er gibt mir immer ne nullpointer exception zurueck.
ich baue zufaellige teststrings, die als texte und muster, mittels algorithmus
ueberprueft werden, und die eingaben und ausgaben werden in einem array des typs structure gespeichert,und dann ausgegeben.
ich weiss, es ist nicht gerade sauber, aber ich steh hier gerade etwas unter zeitdruck
einzeln scheinen die funktionen aber auch reibungslos zu laufen

import java.util.*;

public class advbm {
	public static void PrintTable(int[] feld) {
		int i = feld.length;
		for(int z=0;z<i;z++) {
			if(feld[z] != 5)
				System.out.println(z+":"+feld[z]);
		}
		System.out.println("Ende Tabelle");
	}
	private static int[] InitNext(char[] p) {
		int m = p.length;
		int[] next = new int[m];
		int i=0;
		int j=-1;
		next[0]=-1;
		do {
			if((j<0) || (p[i] == p[j])) {
				i++;
				j++;
				next[i]=j;
			} else {
				j=next[j];
			}
		} while (i<m-1);
		return next;
	}

	private static int[] InitSkip(char[] p) {
		final int characters = 65536;
		int m = p.length; // character array laengen mit length ohne ()
		int[] skip = new int[characters];
		for(int i=0;i<characters;i++)
			skip[i]=m;
		for(int i=0; i<m;i++)
			skip[p[i]]=m-i-1;
		return skip;
	}
	private static int max(int E, int Z) {
		if(E <= Z) {
			return Z;
		} else {
			return E;
		}
	} 
	public static int bmsearch(char [] t, char[] p) {
		int n = t.length;
		int m= p.length;
		int i = m-1;
		int j = m-1;
		int[] skip = InitSkip(p);
		int[] next = InitNext(p);
		PrintTable(skip);
		PrintTable(next);
		do {
			if(t[i]==p[j]) {
				i--;
				j--;
			} else {
				i += max(skip[t[i]],next[j]);
				j=m-1;
			}
		} while ((j>=0) && (i<n));
		if(j<0)
			return i+1;
		else
			return n;
	}
	public static char[] createrandomchars(int length) {
		char[] randomstring= new char[length];
		Random r = new Random();
		String str;
		for(int i=0;i<length;i++)
			randomstring[i]=(char)(65+Math.abs(r.nextInt()) %89);

		return randomstring;
	}
	public class structure {
		private char[] text;
		private char[] muster;
		private long dauer;
		public int stelle;
		public char[] gettext() {	
			return text;
		}
		public char[] getmuster() {
			return muster;
		}
		public long getlen() {
			return dauer;
		}
		public void settext(int len,char[] _text) {
			for(int i=0;i<len;i++)
				text[i]=_text[i];
		}
		public void setmuster(int len,char[] _muster) {
			for(int i=0;i<len;i++)
				muster[i]=_muster[i];
		}
		public void setlen(long laen) {
			dauer=laen;
		}
	}	
	public static void printergebnis(structure[] tries,int anz) {
		for(int i=0;i<anz;i++) {
			System.out.println("Versuch " +i+ ":");
			System.out.println("Text: " + (tries[i].gettext()).toString());
			System.out.println("Muster: "+(tries[i].getmuster()).toString());
			System.out.println("Gefunden an Stelle "+tries[i].stelle);
			System.out.println("dauerte Sekunden:" +(tries[i].getlen()/1000) );
		}
	}	

	public static void main(String[] args) {
		//Beginn der Testklasse	
		int versuche=11;
		structure[] viele = new structure[versuche];
		// mache texte
		int textlen=23;
		int mustlen=5;
		long tm1,tm2;
		for(int i=0;i<versuche;i++) {
			viele[i].settext(textlen,createrandomchars(textlen));
			viele[i].setmuster(mustlen,createrandomchars(mustlen));
		}
		for(int i=0;i<versuche;i++) {
			tm1 = System.currentTimeMillis();
			viele[i].stelle=bmsearch(viele[i].gettext(),viele[i].getmuster());
			tm2 = System.currentTimeMillis();
			viele[i].setlen(tm2-tm1);
		}
		printergebnis(viele,versuche);

	}
}

[CengizS]

Wenn du Arrays erzeugst dann mache dir klar, dass

Object[] objArray = new Object[5];

dir keine 5 Objekte vom Typ Object liefert sondern lediglich Platz für die Referenzen reserviert. Möchtest du echte Objekte haben dann musst du für jedes einzelne ein eigenes new-Konstrukt erzeugen - also:

Object[] objArray = new Object[5];
for (int i=0; i<5; ++i)
    objArray[i] = new Object();

Für dein Beispiel heisst dies: Das Array von structure ist nicht definiert (null) ergo gibt es eine NullPointerException in Zeile 124. Übrigens ist es nicht schöner Stil alle Methoden als static zu definieren. Das gibt auch schon mal Probleme bei einer Umsetzung (wie oben).

[the_menace]

ich habs halt als static deklariert, weil er gemeckert hat.
ich habs jetzt so gelöst, dass die setter-chararray methoden
klassenvariable= _methodenparameter machen. sollte doch der logik
nach funktionieren, er bringt mir aber immer noch ne exception..
ich habe ehrlich gesagt, nicht so ganz kapiert, warum
ich nicht in der settext methode nicht schreiben kann
char[] text= new char[len];
warum ist damit nicht wirklich platz in der klassenvariable gemacht worden?

[Jockelx]

the_menace schrieb:

...nicht so ganz kapiert, warum
ich nicht in der settext methode nicht schreiben kann
char[] text= new char[len];
warum ist damit nicht wirklich platz in der klassenvariable gemacht worden?

Das wurde ja nicht behauptet. Mit

structure[] viele = new structure[versuche];

werden nur keine Klasseninstanzen erzeugt.
Unterschiede zwischen Objekt-Arrays und primitiven Datentypen!

Jockel

[the_menace]

jetzt bin ich total verwirrt
wenn ich jetzt denn wirklich versuche
einzeln platz zu reservieren mit viele[i]=new structure();
kommt der fehler "non-static variable this cannot be referenced from a static context viele[i] = new structure();"
das bild das ich von der java'anischen speicherverwaltung hatte, ist mittlerweile
komplett zusammengebrochen :|

[Jockelx]

Du musst das dringend aufräumen!

Warum ist structure eine lokale Klasse, wenn advbm die niemals
brauch?

Mach mal für den Anfang 3 Klassen in 3 Dateien:
1. advbm
2. structure
3. Test, wo nur die main-Fkt drin ist.

Dann wird's klappen, bzw. weiss man dann eher woran es liegt.

Jockel

[CengizS]

CengizS schrieb:

Übrigens ist es nicht schöner Stil alle Methoden als static zu definieren. Das gibt auch schon mal Probleme bei einer Umsetzung (wie oben).

Wie hier schon angesprochen ...

[Jockelx]

CengizS schrieb:

CengizS schrieb:

Übrigens ist es nicht schöner Stil alle Methoden als static zu definieren. Das gibt auch schon mal Probleme bei einer Umsetzung (wie oben).

Wie hier schon angesprochen ...

Sehe ich zumindest bei der advbm Klasse anders.
Diese Funktionen stellen Dienste bereit, die unabhängig von einer
Instanz arbeiten.
Bei so Sachen wie max(a,b) würde ich statische Methoden jedenfalls vorziehen.

Jockel

[CengizS]

Sicher, ich sagte ja auch dass man nicht alle Methoden static machen soll.

[the_menace]

Ich habe jetzt alles in eigene klassen gepackt
Die ehemals structure klasse ist in speicher.java
und heisst auch so:
und ich habe in den setterfunktionen nochmal platz für die sachen allokiert
aber trotzdem gibts ne nullpointerexception. Ich schätze mal, dass hängt wieder damit zusammen, oder?
dreiste frage, was wäre denn richtig und vor allem *warum*?
weil wenn ich in den forschleifen der setter methoden zusätzlich noch
text[i]=new char(); definiere, meckert der compiler von wegen incompatible types.
ein bisschen im trüben und in google rumstochern hat nicht wirklich was erbracht.

public class speicher {
	private char[] text;
	private char[] muster;
	private int stelle;
	private long dauer;
	public char[] gettext() {
		return text;
	}
	public char[] getmuster() {
		return muster;
	}
	public int getstelle() {
		return stelle;
	}
	public long getdauer() {
		return dauer;
	}
	public void settext(char[] _text) {
		text = new char[_text.length];
		for(int i=0;i<_text.length;i++)
			text[i]=_text[i];
	}
	public void setmuster(char[] _muster) {
		muster = new char[_muster.length];
		for(int i=0;i<_muster.length;i++)
			muster[i]=_muster[i];
	} 
	public void setstelle(int _stelle) {
		stelle=_stelle;
	}
	public void setdauer(long _dauer) {
		dauer=_dauer;
	}
}

[CengizS]

Das Problem liegt nicht in der Klasse structure (jetzt speicher) sondern in der Art und Weise wie du ein Array von solchen Objekten erzeugst.

Du musst zuerst ein Array erzeugen
Jedes Array-Element muss für sich selbst neu erzeugt werden wie in meinem Beispiel zu Anfang.

[the_menace(ausgeloggt)]

so, dank euch geht das jetzt
jetzt hab ich aber noch ein problem, ich generiere randommässig ein paar strings
wobei die zeichen intmässig alle zwischen (also davor halt die (char) konvertierung) 66 und 88 liegen. trotzdem kommen da nicht druckbare zeichen und <enter> hervor. hat jemand ne ahnung, woran das liegen könnte?