Andrea Sodomaco - divagazioni ICT
010101010111001101100101001000000111010001101000011001010010000001110011011011110111010101110010011000110110010100101100001000000100110001110101011010110110010100100001
Il problema è di semplice formulazione... semplicissima... è già stato formulato nel titolo. Non è certo un rompicapo e ogni developer dovrebbe essere in grado di scrivere in pochissimo tempo una funzione che implementi l'algoritmo.
Siamo certi che tutti i programmatori sappiano farlo? Ho sottoposto recentemente questo problema ad alcuni sviluppatori (alcuni senior) e nessuno è giunto rapidamente ad una soluzione efficiente.
In rete non sono riuscito a trovare un algoritmo che risolva questo semplice problema o per meglio dire ne ho trovati svariati che però si basano sul costruire delle stringhe "trimmate" in cui gli spazi sono stati rimossi (un esempio in questa pagina oppure in quest'altra).
Se come specifica del problema da risolvere vi dessero solo il titolo di questa pagina: “comparare due stringhe ignorando eventuali spazi ripetuti”, sareste soddisfatti?
È chiaro che
"a•bcd•••ef" = "a•••bcd••ef"
ma rimangono da chiarire almeno i seguenti aspetti:
Definiamo space characters i caratteri spazio, tabulatore, carriage return e newline.
Definiamo la funzione equalsSpacesLenient(String,String) come la funzione che ritorna true se e solo se le stringhe sono uguali considerando tutte le sequenze di uno o più space characters come un unico spazio. Non c'è nessun particolare accorgimento per gli space characters a inizio o fine stringa.
Alcuni esempi:
"a•b" = "a••••b" "a•b" ≠ "ab" "••abc" = "→••abc" "••abc" ≠ "abc" "ab•cd•••→•ef" = "ab•↵•••cd•ef" "ab•cd•••→•ef" ≠ "abcd•ef"
Prova ad implementare una soluzione nel tuo linguaggio preferito. Dopo aver visto la soluzione dire che è semplice non vale!!!
La soluzione immediata al problema in Java è la seguente:
s1.replaceAll("\\s+"," ").equals(s2.replaceAll("\\s+"," "))
Tutto quello che sono riuscito a trovare in rete è più o meno collegato a questa soluzione che ha il vantaggio di non richiedere sviluppi (ho fatto la ricerca con riferimento a Java, negli altri linguaggi ho dato solo un'occhiata).
Il problema di questa soluzione sono le prestazioni. Ad ogni confronto verrà parsata la regular expression, costruita un'altra stringa e modificata. Solo a questo punto verranno confrontate le due stringhe. Per i vecchi buoni principi dell'informatica mi sembra abominevole manipolare delle stringhe creandone una nuova versione solo per fare un confronto.
Altre soluzioni trovate in rete si basano sull'uso di librerie e dunque richiedono di includere nel progetto una libreria che potrebbe essere piuttosto voluminosa, che andrà aggiornata e mantenuta e che richiederà l’acquisizione di un certo know-how per usarla. Riguardo a questa soluzione la mia opinione personale è che non si installa una libreria per evitare di scrivere 10-20 righe di codice. E comunque le librerie qualcuno deve scriverle!
Per capire meglio la soluzione che propongo nella prossima sezione, vediamo come si potrebbe implementare il normale confronto fra due stringhe se i linguaggi di programmazione non fossero così "lungimiranti" da farci trovare questa funzione già pronta.
Il confronto fra due stringhe viene implementato confrontando a due a due i caratteri di ciascuna di esse. Al primo carattere che differisce il processo si interrompe e le stringhe risultano diverse. Se le stringhe sono effettivamente uguali il processo continua per tutti i caratteri delle stringhe che devono dunque anche avere la stessa lunghezza.
Interessante questa trattazione in C.
Qui di seguito propongo un’implementazione poco ortodossa che prevede un test sulla lunghezza delle stringhe ad ogni interazione. Da notare che l'approccio è pensato per Java e si adatta a linguaggi che hanno una rappresentazione interna delle stringhe con lunghezza specificata (non ad esempio al C con le stringhe null terminated).
// A not so orthodox way to redo equals in Java
public static boolean strEquals(String s1, String s2) {
// It should handle the case where s1 or s2 is null
int idx=0;
for (;;) {
if (s1.charAt(idx)!=s2.charAt(idx)) {
return false; // At the first differing character, finished: the strings are different
}
}
idx++;
if (idx>=s1.length()) { // s1 has no more characters
if (idx>=s2.length()) {
return true; // s2 also has no more characters and the strings are equal
}
else {
return false; // s2 has more characters and therefore the strings are different
}
}
else { // s1 has more characters to compare
if (idx>=s2.length()) {
return false; // s2 has no more characters and therefore the strings are different
}
// s1 and s2 both have more characters to compare: continue
}
}
}
Avete già provato ad implementarlo? Se non l’avete fatto provateci prima di sbirciare la soluzione...
Partiamo dal codice qui sopra che reinventa l’equals classico per sviluppare la funzione equalsSpacesLenient.
Rispetto all’algoritmo sopra riportato, l’equalsSpacesLenient ha bisogno di due indici in quanto una stringa in un certo punto può avere uno spazio solo e l'altra due, per poi continuare con caratteri uguali. Ecco una possibile implementazione:
public static boolean equalsSpacesLenient(String s1,String s2) {
// It should handle the case where s1 or s2 is null
int idx1=0;
int idx2=0;
for (;;) {
if (isSpace(s1.charAt(idx1)) && isSpace(s2.charAt(idx2))) {
// skip any additional spaces in both strings
do {
idx1++;
} while (idx1<s1.length() && isSpace(s1.charAt(idx1)));
do {
idx2++;
} while (idx2<s2.length() && isSpace(s2.charAt(idx2)));
}
else if (s1.charAt(idx1)==s2.charAt(idx2)) {
// The current character matches: move to the next
idx1++;
idx2++;
}
else {
// There are two different characters: the strings are different: exit.
return false;
}
if (idx1>=s1.length()) { // s1 has no more characters
if (idx2<=s2.length()) {
return true; // s2 also has no more characters and the strings are equal
}
else {
return false; // s2 has more characters and therefore the strings are different
}
}
else { // s1 has more characters to compare
if (idx2<=s2.length()) {
return false; // s2 has no more characters and therefore the strings are different
}
// s1 and s2 have more characters to compare: continue
}
}
}
private static boolean isSpace(int c) {
// I can decide here how to consider 'space' in various ways
return Character.isSpaceChar(c);
// return c==' ';
// return c==' ' || c=='\t' || c=='\n' || c=='\r';
}O meglio perché
s1.replaceAll("\\s+"," ").equals(s2.replaceAll("\\s+"," "))
non va bene?
Il confronto fra stringhe è un processo piuttosto efficiente che nel peggiore dei casi (stringhe uguali) richiede tanti confronti quanto sono lunghe le stringhe. Se consideriamo stringhe casuali, statisticamente nella maggior parte dei casi differiranno già dal primo carattere e dunque il confronto terminerà immediatamente.
Supponiamo di voler confrontare due stringhe di un centinaio di caratteri. Il replaceAll verrà comunque eseguito prima del confronto per entrambe le stringhe e richiederà centinaia di operazioni. Questo anche quando le due stringhe differiscono già nel primo carattere.
Da qualche test1 su stringhe di un centinaio di caratteri il confronto con la funzione equalsSpacesLenient è qualche migliaio di volte più veloce2: parliamo dunque di un miglioramento di tre ordini di grandezza.
note a piè di pagina