Fasta nach Mustern durchsuchen dauert zu lange

[mareaky]

Hallo,

also ich habe ich die Aufgabe eine Fasta Datei(46000kb) auf Vorkommen von verschiedenen Mustern("TATAA",usw) zu untersuchen und die Anzahl der vergleiche und die Treffer auszugeben.
Generell läuft es alles bei kleinen Dateien...aber es dauert ewig für diese Große. Wie könnte ich da effizienter machen?
Also ich hab 3 Klassen:

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;


class Sequenz{
	
	private String inhalt;
	private String header;
	private int counter;
	
	
	
	public int getCounter() {
		return counter;
	}
	public void setCounter(int counter) {
		this.counter = counter;
	}
	public Sequenz(String inhalt, String header) {
		super();
		this.inhalt = inhalt;
		this.header = header;
	}
	public Sequenz() {
		super();
	}
	public String getInhalt() {
		return inhalt;
	}
	public void setInhalt(String inhalt) {
		this.inhalt = inhalt;
	}
	public String getHeader() {
		return header;
	}
	public void setHeader(String header) {
		this.header = header;
	}
	
	public ArrayList<Integer> naiverAlg(String muster){
		
		char [] inhaltchar = new char[inhalt.length()];
		char [] musterchar = new char[muster.length()];
		
		
		inhalt.getChars(0,inhalt.length(),inhaltchar,0);
		muster.getChars(0, muster.length(), musterchar, 0);
		
		ArrayList<Integer> matches = new ArrayList<Integer>();
		
		if(muster=="")
		{
		 return null;
		}
		
		if(inhalt =="")
		{
		 return null;
		}
		
		if(inhalt.length()< muster.length())
		{
		  return null;
		}
		
		boolean full= false;
		counter = 0;
		for(int i=0; i < inhalt.length()-muster.length();i++){
			
			counter++;
			if(inhaltchar[i]== musterchar[0]){
				
				
				
				for(int j = 1; j< muster.length();j++){
					
					counter++;
					
					if(musterchar[j]== inhaltchar[i+j]){
						full=true;
					}
					else {
						   full= false;
					       break;
					 
					}
				} 
				if(full){
					matches.add(i);
				}
			}
		}
		
		
		return matches;
		
	}
	
	public ArrayList<Integer> badCharacterRule(String muster){
		
		char [] inhaltchar = new char[inhalt.length()];
		char [] musterchar = new char[muster.length()];
		
		
		inhalt.getChars(0,inhalt.length(),inhaltchar,0);
		muster.getChars(0, muster.length(), musterchar, 0);
		
		ArrayList<Integer> matches = new ArrayList<Integer>();
		
		if(muster=="")
		{
		 return null;
		}
		
		if(inhalt =="")
		{
		 return null;
		}
		
		if(inhalt.length()< muster.length())
		{
		  return null;
		}
		
		
		int i= muster.length()-1;
		boolean full= false;
		counter=0;
		while(i<inhalt.length())
		{   counter++;
			if(inhaltchar[i]== musterchar[muster.length()-1]){
				
				int k= muster.length()-2;
				for(int j= i-1;j>i-muster.length(); j--){
					
					counter++;
					
					if(inhaltchar[j]==musterchar[k]){
					 full=true;	
						
					}
					else{
						
						full=false;
						
						int verschiebung= muster.lastIndexOf(inhaltchar[j]);
						
						
						if(verschiebung==-1){
							verschiebung= muster.length();
						}
						else{
							verschiebung = muster.length()-verschiebung;
						}
						int temp=  i+ verschiebung;
						
						if(i==inhalt.length()-1){break;}
						
						if(temp >= inhalt.length()){
							
							i= inhalt.length()-1;
						}
						else{
							i=temp;
						}
						
						
						break;
					}
					
					k--;
					
					
				}
			}
			else{
				
				int verschiebung= muster.lastIndexOf(inhaltchar[i]);
				
			
				if(verschiebung==-1){
					verschiebung= muster.length();
				}
				else{
					verschiebung = muster.length()-verschiebung;
				}
				int temp=  i+ verschiebung;
				
				if(i==inhalt.length()-1){break;}
				
				if(temp >= inhalt.length()){
					
					i= inhalt.length()-1;
				}
				else{
					i=temp;
				}
			} 
			
			if(full){
				int treffer= i-(muster.length()-1);
				i = i+muster.length();
				
				matches.add(treffer);
			}
		}		
		return matches;
	}
}

die naderen 2 klassen lesen ein und testen.
Ich glaube diesen Anlegen der char[] is ineffizient. Ich hab leider keine Idee.

Danke

 

[Joose]

Ich glaube diesen Anlegen der char[] is ineffizient

Warum verwendest du nicht einfach die "toCharArray()" Methode der Klasse String, sondern kopierst es selber?

Ansonsten: Es gibt Profiler mit denen du die Performance kontrollieren kannst, dann wird dir gezeigt welche Teile deines Codes viel Zeit brauchen.

Hat nichts mit dem Thema zu tun ist aber trotzdem wichtig:
Strings werden mit ".equals" verglichen nicht mit "=="!

EDIT: Und bitte formatiere deinen Code entsprechend (passende Einrückungen, Leerzeilen in Methoden weg, ...)

EDIT2: Ansonsten fällt mir nur ein statt mit einem char[] zu arbeiten direkt mit den Strings zu arbeiten.
per ".contains" überprüfen ob das Muster im Inhalt vorkommt. Wenn nein bist du fertig, wenn ja dann den Index des 1.Vorkommen suchen und mit einem Substring (alles nach dem 1.Vorkommen) vom Inhalt das gleiche nochmal machen.
solange bis es kein vorkommen mehr gibt bzw. geben kann (länge)

 

[arilou]

[...] wenn ja dann den Index des 1.Vorkommen suchen und mit einem Substring (alles nach dem 1.Vorkommen) vom Inhalt das gleiche nochmal machen.
solange bis es kein vorkommen mehr gibt bzw. geben kann (länge)

.indexOf kann ab einer bestimmten Startposition suchen (z.B. nach dem vorigen Auftreten. Ist sicher schneller, als andauernd .substring aufzurufen.
Für deinen Algorithmus wär' schon mal ein Anfang, full=true; nur vor der Schleife 1* zu setzen, nicht in der Schleife wieder und wieder.
Was 'counter' zählt, ist mir auch schleierhaft. Kostet v.a. Rechenzeit - weglassen.

Ich vermute mal, es ist 'ne Übungsaufgabe.
Ansonsten empfehle ich dringend, .indexOf zu verwenden - afaik ist das intern hochoptimiert und berücksichtigt z.B. Selbstähnlichkeit des Suchbegriffs (ich schätze mal Knuth-Morris-Pratt).