Fasta nach Mustern durchsuchen dauert zu lange

M

mareaky

Mitglied
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:
Java:
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
 
J

Joose

Top Contributor
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)
 
Zuletzt bearbeitet:
A

arilou

Bekanntes Mitglied
[...] 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).
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
W Pdf verwerfen, weil Checkbox nach Unterschrift geaendert wurde Allgemeine Java-Themen 5
G File not found - nach dem Kompilieren Allgemeine Java-Themen 6
S Swing Speichern nach Button-Klick Allgemeine Java-Themen 5
Meeresgott Effizientester Weg um nach der Value einer verschachtelten Map aufzulösen Allgemeine Java-Themen 5
M Java 8 nach Java 6 konvertieren Allgemeine Java-Themen 7
N Neustarten des Codes nach der Fehlermeldung Allgemeine Java-Themen 17
L Nach dem Login // Java Desktop Software Allgemeine Java-Themen 7
N Programm nach Abschluss neustarten lassen Allgemeine Java-Themen 6
F Java Code ausführen direkt nach Anmelden in Windows Allgemeine Java-Themen 2
J Jasper Reports - Compilerproblem nach Umstellung von Groovy auf Java Allgemeine Java-Themen 7
looparda Liste filtern nach Prädikaten verschiedener Typen Allgemeine Java-Themen 3
S Apache POI Filtern nach bestimmten Kriterium Allgemeine Java-Themen 1
L Korrektur nach der Berechnung vornehmen, aber wie? Allgemeine Java-Themen 11
C Config nach bestimmten Wertdurchsuchen. Allgemeine Java-Themen 2
B Suche nach einem Testprogramm für meine BA Allgemeine Java-Themen 0
B Maven Keycloak library wirft exceptions nach maven package Allgemeine Java-Themen 1
D BufferedReader bricht nach 1248 Iterationen ab Allgemeine Java-Themen 14
K Eclipse Java findet MySQL Driver nach export nicht mehr Allgemeine Java-Themen 2
H IDEA IntelliJ Java Mail funktioniert nach Export nicht mehr! Allgemeine Java-Themen 1
F Zurnung nach Buchstaben und deren Prüfung Allgemeine Java-Themen 9
M Dateien nach kopieren vergleichen Allgemeine Java-Themen 9
M Sortieren nach Stellenangaben Allgemeine Java-Themen 7
L Erste Schritte Liste von Datums filter nach Monate Allgemeine Java-Themen 4
GreenTeaYT Elemente eines 2Dim LinkedList von links nach rechts ausgeben? Allgemeine Java-Themen 0
J Ausgabe von Links nach Rechts ausgeben? Allgemeine Java-Themen 2
K JAR Datei Corrupt nach Kopieren Allgemeine Java-Themen 4
The Pi 2D-Grafik Tic Tac Toe nach Gewinn rot Allgemeine Java-Themen 1
G Programm, das nach abgearbeiteter main Methode weiterläuft Allgemeine Java-Themen 72
C PDFBox: Nach RegEx ganze Zeile Allgemeine Java-Themen 4
R javax.comm --> Programm funktioniert nach Export nicht mehr Allgemeine Java-Themen 0
L Suche nach CalDav Server API Allgemeine Java-Themen 0
K Java ruft Methoden nicht der Reihe nach auf Allgemeine Java-Themen 14
T Textarea nach nur 1 wort durchsuchen Allgemeine Java-Themen 3
D Methoden Buttons erscheinen doppelt nach Wiederholung in Schleife Allgemeine Java-Themen 1
I nach Image Load in ListView, kann Ordner nicht mehr gelöscht werden Allgemeine Java-Themen 1
K Auf einer Website nach einem String suchen Allgemeine Java-Themen 5
C Eclipse OutOfMemory nach dem exportieren Allgemeine Java-Themen 4
D Erste Schritte Array von einer forschleife nach ausserhalb trasferieren Allgemeine Java-Themen 3
VfL_Freak Große und seltsame Probleme nach Java-Update auf V1.8.0_91 Allgemeine Java-Themen 3
heyluigi Random Integer Array Ausgabe nach Größe sortieren Allgemeine Java-Themen 6
D Java Datei nach Eclipse Export funktioniert nicht Allgemeine Java-Themen 0
B Bild aus Jar kann nach Export nicht mehr gefunden werden Allgemeine Java-Themen 13
B Umgebungsvariable Anpassen der Umgebungsvariablen nach Java-Update ? Allgemeine Java-Themen 14
H jid3lib nach schreiben keine Tags im Folder angezeigt Allgemeine Java-Themen 1
F Methoden Arraylist weiterverwenden nach methoden Aufruf Allgemeine Java-Themen 2
KilledByCheese Dezimal nach Hexadezimal rechner wirft seltsame exception Allgemeine Java-Themen 4
J Programm meldet "Keine Rückmeldung" nach Verbindung zum Server Allgemeine Java-Themen 4
E Java wird beendet nach paar Sekunden Allgemeine Java-Themen 14
H Best Practice setHeader in jsp nach RequestDispatcher.include Allgemeine Java-Themen 0
L Nach Button drücken den Text festspeichern Allgemeine Java-Themen 9
M .jar nach Datei prüfen Allgemeine Java-Themen 2
F String nach Schlüsselwörtern durchsuchen und ganze Zeile ausgeben Allgemeine Java-Themen 4
HarleyDavidson Input/Output Heruntergeladene Datei direkt nach dem Download öffnen ohne zu speichern Allgemeine Java-Themen 1
J Swing Cursor.WAIT funktioniert nicht nach JFileChooser Allgemeine Java-Themen 1
VfL_Freak JDK installieren Problem mit Erstellungspfad nach Wechsel von Java7 auf Java8 Allgemeine Java-Themen 1
B Eclipse Nach Export einer .jar Fehler: Hauptklasse konnte nicht gefunden oder geladen werden Allgemeine Java-Themen 5
thet1983 nach teilen eines Dateinamens suchen Allgemeine Java-Themen 6
F JLabel nach 5 Sekunden wieder leeren Allgemeine Java-Themen 7
J Bilder halb in falscher Farbe nach kopieren aus Web Allgemeine Java-Themen 3
Thallius Neuen Prozess starten, der auch nach Beedingung des Starter-Prozesses weiterläuft? Allgemeine Java-Themen 5
T Nach Java Update: Jar Datein öffnen sich nicht mehr mit doppelklick Allgemeine Java-Themen 3
S Start des zweiten Threads erst nach Beenden des ersten Threads Allgemeine Java-Themen 13
A Funktionen aufrufen nach Schema x Allgemeine Java-Themen 2
G JavaFX Problem nach Update auf Java 8 Allgemeine Java-Themen 0
AssELAss String jeweils nach x Zeichen Zeilenumbruch Allgemeine Java-Themen 1
F E-Mail aus JAVA senden nach Umstellung auf Netbean 7.4 mit Java 7U45 nicht mehr möglich Allgemeine Java-Themen 4
J Ausgabe nach Excel Allgemeine Java-Themen 1
K PCM_UNSIGNED nach PCM_SIGNED Allgemeine Java-Themen 0
D Object nach Vererbung mit Class Object überprüfen Allgemeine Java-Themen 4
AssELAss Zeilenumbruch immer nach bestimmtem Zeichen Allgemeine Java-Themen 1
L Strings nach sortiertem String zurück ordnen Allgemeine Java-Themen 0
A Java - Suche nach Datensatz mit DateChooser Allgemeine Java-Themen 0
L Strings nach gleichem Muster ordnen Allgemeine Java-Themen 4
F Nach Export wird PDF Datei nicht mehr gefunden Allgemeine Java-Themen 0
K Sortieren nach Vorgabe Allgemeine Java-Themen 6
G nervendes Problem mit unterschieden zwischen Javax64 und x86 | je nach Programmbedarf beides nötig Allgemeine Java-Themen 2
L nach form submit textfeld an java übergeben? Allgemeine Java-Themen 2
L iText PDF Form-Felder werden nach Bearbeitung mit iText nicht mehr richtig erkannt. Allgemeine Java-Themen 2
C Objekt Datenverlust nach Methodenaufruf Allgemeine Java-Themen 9
P Datentypen String-Daten zu Byte-Zahlen konvertieren - Komme nicht weiter nach vielem versuchen :-/ Allgemeine Java-Themen 7
H WAV abspielen nach Button-Klick Allgemeine Java-Themen 4
F.S.WhiTeY JDK installieren Linux: Nach Update link auf Java zerschossen Allgemeine Java-Themen 4
A Excel nach bestimmten Inhalt durchsuchen Allgemeine Java-Themen 8
B Button-Registrierung beim ActionListener erst NACH Tastendruck Allgemeine Java-Themen 2
S arraylist nach n. Eintrag numerisch Sortiren Allgemeine Java-Themen 5
Iron Monkey Mit Regex nach Beträge suchen Allgemeine Java-Themen 4
P Ordnerstruktur nach .js-Files durchsuchen Allgemeine Java-Themen 2
S leeres Package nach neuinstallation des Pc Allgemeine Java-Themen 6
eskimo328 Textfile nach Stromausfall leer Allgemeine Java-Themen 5
H Scanner: Ausgabe erst nach Abbruch Allgemeine Java-Themen 8
H LinkedList<LinkedList<String>> nach ArrayList<ArrayList<String>> ? Allgemeine Java-Themen 9
C Swing Focus nach Beendigung eines Modal-JDialogs Allgemeine Java-Themen 5
J .txt erstellen, nach name der vorhergehenden txt Allgemeine Java-Themen 7
C Umlautdarstellung nach Jar-Erstellung Allgemeine Java-Themen 4
P Files - nach der reihe String reinschreiben Allgemeine Java-Themen 2
S HTML-Quelltext nach bestimmter Stelle durchsuchen Allgemeine Java-Themen 2
M Process wird gestoppt und nach beenden der Anwendung fortgeführt Allgemeine Java-Themen 4
T JFreeChart Diagramm speichern - Problem mit ImageIO nach Projektexport Allgemeine Java-Themen 3
G Map nach key sortieren Allgemeine Java-Themen 14
L Unterscheidung nach männlichen, weiblichen Personen Allgemeine Java-Themen 6

Ähnliche Java Themen

Anzeige

Neue Themen


Oben