Implementazione del codice Kamasutra
Questo è l'esercizio 3.1.31. dal libro Computer Science An Interdisciplinary Approach di Sedgewick & Wayne:
Scrivere un filtro KamasutraCipher che prenda due stringhe come argomento della riga di comando (le stringhe di chiavi), quindi legga le stringhe (separate da spazi) dallo standard input, le sostituisca con ciascuna lettera come specificato dalle stringhe di chiavi e stampi il risultato sullo standard output. Questa operazione è alla base di uno dei primi sistemi crittografici conosciuti. La condizione sulle stringhe di chiavi è che debbano essere di uguale lunghezza e che qualsiasi lettera nello standard input debba apparire esattamente in una di esse. Ad esempio, se le due chiavi sono THEQUICKBROWN e FXJMPSVLAZYDG, allora creiamo la tabella
IL MARRONE RAPIDO
FXJMPSVLAZYDG
che ci dice che dovremmo sostituire F per T, T per F, H per X, X per H e così via quando si filtra lo standard input in standard output. Il messaggio viene codificato sostituendo ogni lettera con la sua coppia. Ad esempio, il messaggio MEET AT ELEVEN è codificato come QJJF BF JKJCJG. La persona che riceve il messaggio può utilizzare gli stessi tasti per recuperare il messaggio.
Ecco il mio programma:
public class KamasutraCipher
{
public static void encrypt(String s, String t)
{
int m = s.length();
int n = t.length();
if (m != n)
{
throw new RuntimeException("The key lengths must be equal");
}
while (!StdIn.isEmpty())
{
String word = StdIn.readString();
int wordLength = word.length();
for (int i = 0; i < wordLength; i++)
{
for (int j = 0; j < m; j++)
{
if (String.valueOf(word.charAt(i)).equals(String.valueOf(s.charAt(j))))
{
String temp = word;
word = temp.substring(0,i) + String.valueOf(t.charAt(j)) + temp.substring(i+1);
}
else if (String.valueOf(word.charAt(i)).equals(String.valueOf(t.charAt(j))))
{
String temp = word;
word = temp.substring(0,i) + String.valueOf(s.charAt(j)) + temp.substring(i+1);
}
}
}
System.out.print(word + " ");
}
}
public static void main(String[] args)
{
encrypt(args[0], args[1]);
}
}
StdIn è una semplice API scritta dagli autori del libro. Ho controllato il mio programma e funziona.
C'è un modo per migliorare il mio programma?
Grazie per l'attenzione.
Risposte
L'implementazione sembra buona, ho solo alcuni suggerimenti.
Principio di responsabilità unica
Il metodo encryptsembra avere molte responsabilità:
- Legge l'input dell'utente
- Crittografa l'input
- Invia il risultato alla console
Una definizione di SRP è "Una classe dovrebbe avere solo una ragione per cambiare". Ma ci sono molte ragioni per KamasutraCiphercambiare:
- L'input può provenire da
System.in, file, database, ecc. - La libreria
StdIncambia. - L'output deve andare su un file, ecc.
- L'output deve essere formattato correttamente per l'utente
- eccetera..
L'unica responsabilità di KamasutraCipherdovrebbe essere crittografare (o decrittografare) una stringa e restituire il risultato.
L'interfaccia può essere rifattorizzato da questo:
public class KamasutraCipher {
public static void encrypt(String s, String t)
}
A:
public class KamasutraCipher {
public KamasutraCipher(String key1, String key2)
public String encrypt(String s)
}
Ora l'unico motivo per KamasutraCiphercambiare è per le ottimizzazioni o se l'algoritmo del Kamasutra cambia, ma quest'ultimo non accadrà presto.
Tutta la logica per la richiesta dell'ingresso e la produzione dell'uscita viene spinta nel main.
Le stringhe sono immutabili
In Java le stringhe sono oggetti immutabili e qualsiasi modifica a una stringa crea una nuova stringa. Pertanto questa parte:
String temp = word;
word = temp.substring(0,i) + String.valueOf(t.charAt(j)) + temp.substring(i+1);
Può essere modificato in:
word = word.substring(0,i) + t.charAt(j) + word.substring(i+1);
Ottimizzazione
La complessità del metodo encryptè O(m*n)dove mè la lunghezza della stringa di input ed nè la lunghezza della chiave. (ignorando i metodi di Stringe il ciclo while).
Un modo più efficiente sarebbe utilizzare una mappa per memorizzare le chiavi di stringa. Ad esempio, date le chiavi di stringa ABC e FGH , la mappa conterrebbe:
- A -> F
- B -> G
- C -> H
- F -> A
- G -> B
- H -> C
Il metodo encryptdiventa quindi una semplice ricerca sulla mappa, riducendo la complessità a O(m):
public String encrypt(String s) {
StringBuilder sb = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
sb.append(keyMap.get(c));
}
return sb.toString();
}
SpringBuilderci consente di risparmiare un po' di memoria creando la stringa di risultato in modo più efficiente. keyMapviene creato nel costruttore perché le chiavi non cambiano dopo l'inizializzazione.
Convalida dell'ingresso
qualsiasi lettera in standard input deve apparire esattamente in una di esse (tasti)
Come accennato da altri, questo è un requisito che deve essere gestito, possibilmente nel metodo encrypt.
Per le eccezioni puoi usare IllegalArgumentExceptioninvece di RuntimeException.
Codice rifattorizzato
public class KamasutraCipher {
private final Map<Character,Character> keyMap;
public KamasutraCipher(String key1, String key2) {
if (key1.length() != key2.length()) {
throw new IllegalArgumentException("The key lengths must be equal");
}
keyMap = new HashMap<>();
for (int i = 0; i < key1.length(); i++) {
keyMap.put(key1.charAt(i), key2.charAt(i));
keyMap.put(key2.charAt(i), key1.charAt(i));
}
}
public String encrypt(String s) {
StringBuilder sb = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
if(!keyMap.containsKey(c)) {
throw new IllegalArgumentException(String.format("'%c' is not in the keys", c));
}
sb.append(keyMap.get(c));
}
return sb.toString();
}
public static void main(String[] args) {
KamasutraCipher cipher = new KamasutraCipher(args[0], args[1]);
while (!StdIn.isEmpty()) {
String input = StdIn.readString();
System.out.println(cipher.encrypt(input));
}
}
}
Marc ha coperto gran parte del terreno, ma vorrei sottolineare un paio di cose che non ha menzionato esplicitamente e aggiungere alcuni ulteriori commenti.
- "crittografia vuota statica pubblica (String s, String t)". Nota come Marc ha sostituito i nomi opachi "s" e "t" con nomi più significativi. In generale i nomi brevi non sono nostri amici. L'uso di "s" da parte di Marc come nome di un argomento nel suo metodo encrypt() è, IMHO, OK in questo contesto poiché il metodo è così breve, ma in generale preferisce nomi più lunghi più espressivi.
- "String.valueOf(word.charAt(i)).equals(String.valueOf(s.charAt(j)))" String.charAt(int) restituisce un valore char , che in realtà è un numero intero (abbastanza) piccolo. Non è necessario racchiudere due caratteri in Strings e utilizzare String.equals() per confrontarli. Puoi semplicemente dire "word.charAt(i) == s.charAt(j)".
- Né la tua soluzione né quella di Marc controllano effettivamente che le due stringhe di chiavi non condividano caratteri né contengano duplicati.
- La specifica del problema suggerisce che se la parola da crittografare contiene un carattere non nelle stringhe di chiavi, si tratta di un errore. Né la tua soluzione né quella di Marc la trattano come tale.
In alternativa alla soluzione di Marc, delineerò una strategia di ricerca alternativa al posto di Marc's Map. (Non lo codificherò - sarebbe un esercizio più utile per te farlo.)
Se crei un array di caratteri di dimensione Character.MAX_VALUE, puoi popolarlo con caratteri sostitutivi e accedervi semplicemente usando i caratteri di input come indice. Le voci non assegnate nell'array (per i caratteri non forniti nelle stringhe di chiavi) verranno inizializzate sul carattere nullo ( come da specifica della lingua ).
[Nota: ho ignorato le unità di codice surrogato presumendo che l'input degli OP non li coinvolgerà ...]