# Verschlüsselungsprogramm zu langsam



## haut2000 (4. Jan 2006)

Hallo,

ich habe eine Uni-Aufgabe zu lösen in der man einen 18 MB großen Text mittels Vigener Verfahren verschlüsseln soll. Gegben sind 2 Dateien: codes.txt und der cleartext.big.txt (die 18mb datei).
Nun soll man die codes einlesen, was ich auch in der methode getCodes() mache. Die codes.txt sieht so aus:


```
.	0
,	1
 	2
!	3
?	4
a	5
A	6
b	7
B	8
c	9
C	10
d	11
D	12
e	13
E	14
f	15
F	16
g	17
G	18
h	19
H	20
i	21
I	22
j	23
J	24
k	25
K	26
l	27
L	28
m	29
M	30
n	31
N	32
o	33
O	34
p	35
P	36
q	37
Q	38
r	39
R	40
s	41
S	42
t	43
T	44
u	45
U	46
v	47
V	48
w	49
W	50
x	51
X	52
y	53
Y	54
z	55
Z	56
0	57
1	58
2	59
3	60
4	61
5	62
6	63
7	64
8	65
9	66
:	67
;	68
"	69
-	70
_	71
(	72
)	73
+	74
```

mein programm soll nun mithilfe dieser codes und dem vorgegebenen Schlüssel ("AI4 encrypts every+hing? Y3s: i7 d()3s!!") den Text verschlüsseln. Das ganze funktioniert auch einwandfrei, allerdings viiiiel zu langsam. Ich denke es liegt an meinem Vorgehen, dass ich die codes in ein array einlese und dieses array für jedes zeichen im text durchsuchen muss, um an den entsprechenden code zu kommen. 

Hier mein Programm:


```
import java.io.*;
import Prog1Tools.IOTools;
import java.text.*;
import java.util.*;

public class vigenere2 {
	
	public static char[] getCodes() throws IOException {
		
		String in = "codes.txt";
		System.out.print("Datei " +in +" wird nun eingelesen...");
		int j=0;
		char[] codes = new char[75];
		String ch;
		StringBuffer lineBuff = new StringBuffer();
		
		try {	
		
			File input = new File(in);
		
			BufferedReader r = new BufferedReader (new FileReader(in));
		
				while ( (ch = r.readLine())!= null) {
				
					lineBuff.append(ch);
					codes[j]=lineBuff.charAt(0);
					j++;
					lineBuff.setLength(0);
				
				}
			
		
		    r.close();
		    
		//for (int i=0; i < codes.length; i++) {
				
		//System.out.println("Index[" +i +"] = " +codes[i]);  //Test ob Array richtige Werte enthält
		//}
		
		}
		
		catch (IOException e) {
		System.out.println(e);
		
		};
	System.out.println(" fertig!");		
	return codes;	
	}
	
	
	
	public static int findCodes(char[] array , char target) {
	
	 
	 	
     for (int j = 0; j < array.length; j++) {
       
       	 
         if ( array[j] == target )  
         		
         		return j; // Target gefunden.
         		
         	}
         		
         
         
     return -1 ; // Target nicht gefunden.

    }
    
    
			
	
			    
	public static void main (String[] args) throws IOException {
		try {
		Date start = new Date();
		String key = new StringBuffer().append("AI4 encrypts every+hing? Y3s: i7 d()3s!!").toString();
			
		char[] codeArray = getCodes();
		
		File output = new File("output.txt");
		BufferedWriter out = new BufferedWriter (new FileWriter(output));
		
		String text = "cleartext.txt";
		String ch;
	
		
		try {	
		
			File input = new File(text);
		
			BufferedReader r = new BufferedReader (new FileReader(text));
			
				while ( (ch = r.readLine())!= null) {
				
					
					
					for (int i = 0, j = 0; i < ch.length(); i++, j++){
  							//i ist der Zähler für den Originaltext
  							//j ist der Zähler für das Schlüsselwort
  					if( j == key.length()) j = 0; 
  							//wenn Schlüsselwort durchlaufen, wieder von vorne im Schlüssel
					
						
							int var1 =	findCodes(codeArray, (char)(ch.charAt(i)));
					
							int var2 =	findCodes(codeArray, key.charAt(j));
							if (var1 != -1 && var2 != -1) {				
							int ciph = (var1 + var2) % 26;
							out.write(codeArray[ciph]);
							}
							else {
								System.out.println("Vorgang abgebrochen!");
								break;
							}
						//}
							
					}
					out.newLine();
					
						
					
			    }
			
			out.close();
			r.close();
		}
		
		catch (IOException e) {
		System.out.println(e);
		
		};
		
		Date stopp = new Date();
		long laufzeit = stopp.getTime() - start.getTime();
		System.out.println("Gesamtlaufzeit: " +laufzeit + " ms");
		
		
		
		
		}
		
		catch (IOException e) {
		System.out.println(e);
		
		};
		
	}
}
```

Ich brauche ca 13 Sekunden um die Datei zu verschlüsseln... leider wird in der Aufgabe verlangt, es in max. 5 sec zu tun.  also denke ich, dass da noch einiges an optimierungspotenzial vorhanden ist.

Vielen Dank schon einmal


----------



## dotlens (4. Jan 2006)

lineBuff.append(ch);
               codes[j]=lineBuff.charAt(0);
               j++;
               lineBuff.setLength(0); 

wieso in einen Buffer den du immer wieder auf null setzt? kannst direkt den char zuweisen. deine variablen namen sind unübersichtlich. ein string darf nich ch heissen!!

schau dir deine schleifen an, wo wir am meisten zeit verbraucht, was wird doppelt gemacht


----------



## haut2000 (4. Jan 2006)

Ok, ich habe die variablen mal umbenannt (war wirklich ungeschickt gewählt). 
Ich lese die codes.txt ja nur einmal ein. den linebuffer setze ich immer auf null, da ich ja immer wieder nur das erste zeichen der neuen zeile abspeichern will. Ich könnte den linebuffer auch weglasen, da hast du recht. Alledings ist mein Performance Problem von der findCodes() Methode abhängig. Diese wird immer für jedes Zeichen im Text aufgerufen. Ich kenne nur keine bessere Lösung dieses Problems. 

mein neuer Quellcode:


```
import java.io.*;
import Prog1Tools.IOTools;
import java.text.*;
import java.util.*;

public class vigenere2 {
	
	public static char[] getCodes() throws IOException {
		
		String in = "codes.txt";
		System.out.print("Datei " +in +" wird nun eingelesen...");
		int j=0;
		char[] codes = new char[75];
		String zeile;
		StringBuffer lineBuff = new StringBuffer();
		
		try {	
		
			File input = new File(in);
		
			BufferedReader r = new BufferedReader (new FileReader(in));
		
				while ( (zeile = r.readLine())!= null) {
				
					lineBuff.append(zeile);
					codes[j]=lineBuff.charAt(0);
					j++;
					lineBuff.setLength(0);
				
				}
			
		
		    r.close();
		    
		//for (int i=0; i < codes.length; i++) {
				
		//System.out.println("Index[" +i +"] = " +codes[i]);  //Test ob Array richtige Werte enthält
		//}
		
		}
		
		catch (IOException e) {
		System.out.println(e);
		
		};
	System.out.println(" fertig!");		
	return codes;	
	}
	
	
	
	public static int findCodes(char[] array , char target) {
	
	 
	 	
     for (int j = 0; j < array.length; j++) {
       
       	 
         if ( array[j] == target )  
         		
         		return j; // Target gefunden.
         		
         	}
         		
         
         
     return -1 ; // Target nicht gefunden.

    }
    
    
			
	
			    
	public static void main (String[] args) throws IOException {
		try {
		Date start = new Date();
		String key = new StringBuffer().append("AI4 encrypts every+hing? Y3s: i7 d()3s!!").toString();
			
		char[] codeArray = getCodes();
		
		File output = new File("output.txt");
		BufferedWriter out = new BufferedWriter (new FileWriter(output));
		
		String text = "cleartext.big.txt";
		String textzeile;
	
		
		try {	
		
			File input = new File(text);
		
			BufferedReader r = new BufferedReader (new FileReader(text));
			
				while ( (textzeile = r.readLine())!= null) {
				
					
					
					for (int i = 0, j = 0; i < textzeile.length(); i++, j++){
  							//i ist der Zähler für den Originaltext
  							//j ist der Zähler für das Schlüsselwort
  					if( j == key.length()) j = 0; 
  							//wenn Schlüsselwort durchlaufen, wieder von vorne im Schlüssel
					
						
							int var1 =	findCodes(codeArray, (char)(textzeile.charAt(i)));
					
							int var2 =	findCodes(codeArray, key.charAt(j));
							if (var1 != -1 && var2 != -1) {				
							int ciph = (var1 + var2) % 26;
							out.write(codeArray[ciph]);
							}
							else {
								System.out.println("Vorgang abgebrochen!");
								break;
							}
						//}
							
					}
					out.newLine();
					
						
					
			    }
			
			out.close();
			r.close();
		}
		
		catch (IOException e) {
		System.out.println(e);
		
		};
		
		Date stopp = new Date();
		long laufzeit = stopp.getTime() - start.getTime();
		System.out.println("Gesamtlaufzeit: " +laufzeit + " ms");
		
		
		
		
		}
		
		catch (IOException e) {
		System.out.println(e);
		
		};
		
	}
}
```


----------



## Bleiglanz (4. Jan 2006)

a) nimm eine Hashtable oder eine Map statt des Code-Arrays, das ist wesentlich schneller als jedesmal durchzulaufen

b) noch besser eine Vorausberechnung (lohnt sich wohl bei 18MB Klartext): 

blase dein ganzes array auf die grösse von 2^16 auf - durch Wiederholung wie es sich bei Vignere gehört - und schreib einfach 

return neuesarray[target]

um deinen index j zurückzubekommen

b wäre wohl am besten: selbst wenn im schnitt das ding bei der hälfte ist, musst du ja immer 2 mal durch gehen und hast

18 000 000 * 35 * 2

operationen allein für das nachschlagen

ach ja: spar dir das mit dem zeilenweise lesen, wozu ist das gut?, verschlüssle lieber die \n gleich mit (nimm readChar..)


----------



## Bleiglanz (4. Jan 2006)

ach ja, das nachschlagen für den key kannst du auch im voraus berechnen, der key hängt ja nicht vom Plaintext ab


```
int var1 =  findCodesImVorausArray[textzeile.charAt(i)]
int var2 =  findKeyCodesImVorausArray[j]
```


----------



## SlaterB (4. Jan 2006)

das derzeitige Array unterstützt die schnelle Zurückrechnung, 
vom Code führt es direkt zum zugehörigen Char,

das kann aber auch leicht in die andere Richtung bauen, einfach ein Array für alle Chars und darin
an der richtigen Stelle die zugehörigen Code-Werte,

wenn man dann noch für den key das ganze im vorausberechnet sinkt die Zeit ungefähr auf 1/3:


```
import java.io.*;
import java.text.*;
import java.util.*;

public class vigenere3 {

	static int anz = 150;
	static int[] clearToCode = new int[anz];
	static char[] codeToClear = new char[anz];

	static int[] key;

	public static void getCodes() throws IOException {

		String in = "codes.txt";
		System.out.println("Datei " + in + " wird nun eingelesen...");
		int j = 0;
		String zeile;

		for (int i = 0; i < anz; i++) {
			clearToCode[i] = -1;
			codeToClear[i] = (char) -1;
		}

		try {
			File input = new File(in);
			BufferedReader r = new BufferedReader(new FileReader(in));

			while ((zeile = r.readLine()) != null) {
				clearToCode[zeile.charAt(0)] = (char) j;
				codeToClear[j] = zeile.charAt(0);
				j++;
			}
			r.close();
		} catch (IOException e) {
			System.out.println(e);

		};
		System.out.println("Codes lesen fertig!");
	}

	public static void main(String[] args) throws IOException {
		try {
			getCodes();
			codiere();
		} catch (IOException e) {
			System.out.println(e);

		};
	}

	public static void codiere() throws IOException {

		long start = System.currentTimeMillis();

		String keyString = "AI4 encrypts every+hing? Y3s: i7 d()3s!!";

		key = new int[keyString.length()];
		for (int i = 0; i < key.length; i++) {
			key[i] = clearToCode[keyString.charAt(i)];
		}

		File output = new File("output.txt");
		BufferedWriter out = new BufferedWriter(new FileWriter(output));

		String text = "cleartext.big.txt";
		String textzeile;

		File input = new File(text);
		BufferedReader r = new BufferedReader(new FileReader(text));


		while ((textzeile = r.readLine()) != null) {

			for (int i = 0, j = 0; i < textzeile.length(); i++, j++) {
				//i ist der Zähler für den Originaltext
				//j ist der Zähler für das Schlüsselwort
				if (j == key.length) {
					j = 0;
				}
				//wenn Schlüsselwort durchlaufen, wieder von vorne im Schlüssel

				int var = clearToCode[textzeile.charAt(i)];

				if (var != -1) {
					var = (var + key[j]) % 26;
					out.write(codeToClear[var]);
				} else {
					System.out.println(
						"unbekanntes Zeichen in Quelldatei, Vorgang abgebrochen!");
					return;
				}
			}
			out.newLine();
		}
		out.close();
		r.close();

		long laufzeit = System.currentTimeMillis() - start;
		System.out.println("Gesamtlaufzeit: " + laufzeit + " ms");

	}
}
```


----------



## haut2000 (4. Jan 2006)

hallo, ich habe leider nicht ganz verstanden was du mit Aufblasen meinst. Was soll ich da ins Array legen? kann ich mit array[char] das feld aufrufen? muss der index kein int wert sein oder wandelt java den char direkt als int um? wenn das ginge, dann könnte ich ja das array mit den char-int werten als index verwenden und man bräuchte gar nicht mehr suchen. zb wenn "B" als int wert in java 123 hätte (nur ein beispiel) dann könnte ich ja in das array[123] den codewert für "B" abspeichern.
Hast du das so gemeint? Für den Key ein Array zu erstellen macht natürlich dann genauso sinn.


----------



## haut2000 (4. Jan 2006)

hey slaterB, danke für die optimierung. jetzt brauch ich ja nur noch 1/4 der zeit. ich wusste nicht, dass mann ein array mit char-index aufrufen kann. hab zu selten programmiert in meinem leben 



Viiielen Dank für Eure Hilfe!!!  :toll:


----------



## Bleiglanz (5. Jan 2006)

das Ding ist trotzdem hässlich

BufferedReader#public int read(char[] cbuf,int off,int len)

mit einem festem Buffer char[] dessen Länge genau die keylänge ist wäre IMHO klarer und schneller als das gewürge mit readLine

irgendwie ist es auch falsch, bei jeder neuen Zeile im key wieder von vorne anzufangen? wenn im Plaintext jede Zeile nur 5 Zeichen hat, dann würden auch nur die ersten 5 Zeichen des keys verwendet -> der soll doch "fortlaufend" sein


```
if (var != -1) {
               var = (var + key[j]) % 26;
               out.write(codeToClear[var]);
```
das %26 versteh ich auch nicht: in var stehen die Zahlen 0...25, d.h. jedes Zeichen der Eingabe wird in nur 26 verschiedene Ausgabezeichen kodiert: wie soll man das jemals dekodieren?

Vignere ist doch ganz anders?


----------



## haut2000 (5. Jan 2006)

ja, du hast recht,  der schlüssel soll fortlaufend sein. aber meiner meinung nach macht das programm es ja richtig: er liest so lange neue zeilen ein, bis das streamende erreicht ist. jede zeile wird einzeln codiert und der schlüssel geht doch erst dann wieder auf 0 wenn sein ende erreicht ist. oder hab ich da was falsch verstanden???

zu %26 : oh mann, die aufgabenstellung war in englisch und ich hab sie nur überflogen. da war ein beispiel des original vigenere und da warens nur 26 zeichen.. dummerweise hab ich da nicht gelesen, dass wir unseren algorithmus anpassen sollen  sehr dumm! es sollte natürlich %75 heißen. sonst könnte man es tatsächlich nimmer decodieren

was meinst du mit dem festen buffer char[]????


----------



## haut2000 (5. Jan 2006)

funktioniert nun alles einwandfrei


----------



## Guest (10. Jan 2007)

haut2000 hat gesagt.:
			
		

> Hallo,
> 
> ich habe eine Uni-Aufgabe zu lösen in der man einen 18 MB großen Text mittels Vigener Verfahren verschlüsseln soll. Gegben sind 2 Dateien: codes.txt und der cleartext.big.txt (die 18mb datei).
> Nun soll man die codes einlesen, was ich auch in der methode getCodes() mache. Die codes.txt sieht so aus:
> ...


----------



## Loki (11. Jan 2007)

Keine Ahnung ob das hilft:


107 (char) entfernen

int var1,var2,ciph außerhalb der Schleife deklarieren

wenn du codeArray als Klassenattribut benutzt und die Zugriffe findeCode ohne codeArray stattfinden sondern stattdessen direkt drauf zugreifst ist der Code auf jeden Fall schneller, leider weniger OOP Style, da weniger Overhead beim Prozedurenaufruf

findCodes( ch.charAt(i) );  also so aufrufen


----------

