Angella Andrea - Italian Blog

Infinita passione per lo sviluppo software !
posts - 133, comments - 216, trackbacks - 9

My Links

News

MIT OpenCourseWare: I'm invested Wikipedia Affiliate Button


Sto leggendo:

Archives

Post Categories

Siti web realizzati

Siti web tecnici

Algoritmi – Rimuovere i caratteri duplicati in una stringa


Problema:

Rimuovere tutti i caratteri duplicati da una stringa. Gli spazi devono essere preservati.

Vincoli:

Se si utilizza C++ modificare direttamente il parametro di input senza utilizzare buffer aggiuntivi.

Se si utilizza C# ritornare una nuova stringa. In quanto le stringhe sono immutabili, e’ consentito l’utilizzo del metodo ToCharArray() per attenere un buffer su cui lavorare.

Input:

Una stringa

Output:

Una stringa

Esempio:

Input: “Microsoft .Net Framework”

Output: “Microsft .Ne Famwk”

Il mio ragionamento:

Itero il buffer della stringa e costruisco all’inizio di esso la stringa risultato. Uno speciale indice mi indichera’ la posizione dell’ultimo elemento nella stringa risultato. Un nuovo carattere sara’ aggiunto solo dopo la verifica che non sia un duplicato, mentre uno spazio sara’ sempre aggiunto.

La complessita’ dell’algoritmo e’ O(N^2) dove N e’ il numero di elementi distinti presenti nella stringa.

Una soluzione piu’ efficiente consiste nell’utilizzare un vettore di booleani di appoggio per ricordarsi quali caratteri sono gia’ stati visitati. Questo evita un ciclo innestato rendendo la soluzione di complessita’ lineare.

La mia soluzione in C++:

void RemoveDuplicates(char* s)
{
    if (s == NULL) throw exception("s cannot be null");

    char c;
    int i = 0;
    int end = 0;

    while(c = s[i])
    {
        bool duplicate = false;

        if (!isspace(c))
        {
            for(int j = 0; j < i; ++j)
                if (s[j] == c)
                {
                    duplicate = true;
                    break;
                }
        }

        if (!duplicate) s[end++] = c;

        ++i;
    }

    s[end] = 0;
}


La mia soluzione in C#:

public static class StringExtension
{
    public static string RemoveDuplicates(this string s)
    {
        if (s == null) throw new ArgumentNullException("s");
        if (s.Length < 2) return s;

        char[] vc = s.ToCharArray();
        int len = s.Length;
        int end = 0;

        for (int i = 0; i < len; ++i)
        {
            char c = vc[i];
            bool duplicate = false;

            if (!char.IsWhiteSpace(c))
                for (int j = 0; j < end; j++)
                    if (c == vc[j])
                    {
                        duplicate = true;
                        break;
                    }

            if (!duplicate)
                vc[end++] = c;
        }

        return new string(vc, 0, end);
    }
}

 

Soluzione in C# piu’ efficiente

public static string RemoveDuplicates(this string s)
{
    if (s == null) throw new ArgumentNullException("s");
    if (s.Length < 2) return s;

    char[] vc = new char[s.Length];
    bool[] visited = new bool[char.MaxValue + 1];
    int end = 0;

    foreach (char c in s)
    {
        if (!visited[c] || char.IsWhiteSpace(c))
        {
            vc[end++] = c;
            visited[c] = true;
        }
    }

    return new string(vc, 0, end);                        
}

Print | posted on Saturday, September 4, 2010 3:16 PM | Filed Under [ Algoritmica ]

Feedback

Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

certo che tutti quegli if innestati non è che siano un bel vedere... ti consiglio di riguardarli un pò...
9/4/2010 3:21 PM | work
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

Se non usi strutture dati, tutti gli algoritmi diventano O(NxNxNxNx...): in altre parole, e' "algoritmi e strutture dati", non esistono gli uni senza le altre. Al limite metterei un vincolo del tipo che si possono solo usare tipi primitivi e strutture, o qualcosa di simile.

-LV
9/4/2010 4:39 PM | LudovicoVan
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

C'e' un bug nell'ultima soluzione...

E' preferibile scrivere esplicitamente:

if(!char.IsWhiteSpace(c))
if(!visited[c])
{
...
}

-LV
9/4/2010 5:16 PM | LudovicoVan
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

No, mai fault, ho riletto la specifica... :)

-LV
9/4/2010 5:18 PM | LudovicoVan
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

Come dice LudovicoVan, credo la parte più lenta è l'allocazione e inizializzazione di un'array di 128 KB, di cui tra l'altro usi al massimo n byte. In questo caso la complessità non sarebbe più O(n), perchè dominata da un altro termine. Inoltre, gli accesi all'array avvengono a indirizzi casuali, quindi la località del codice è scarsa.

Io avrei utilizzato un albero per memorizzare i caratteri già incontrati, ottenendo complessità temporale n*log(n) ma riducendo i requisiti di memoria e migliorando la località del codice. Questa soluzione è applicabile per un generico vettore di valori che supportano un'operazione di confronto. La tua soluzione, se anzichè una stringa ci fosse un'array di interi a 32 bit, richiederebbe l'allocazione di 16 GB di memoria.
9/4/2010 6:48 PM | Andrea
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

> Si rispetto alla mia versione quadratica questa e' notevolmente piu' leggibile anche se ci sono dei ritocchi da fare. Praticamente il "trucco" sta nel creare delle funzioni/metodi addizionali e sfruttare il meccanismo del return come un modo per evitare degli IF.

Si' ma, se posso dire la mia, e' assolutamente assurdo creare una funzione per mascherare un if. IMO, al contrario la leggibilita' e' semmai minore mentre la complessita' ovviamente aumenta: hai solo spostatyo l'if in una funzione interna, nella quale poi non hai scritto if perche' crei prima un booleano... nonsense.

E' assurdo fare campagne anti-if: occorrono professionisti competenti e consapevoli, non regole da operatori di fast-food senza capacita' pensanti.

-LV
9/5/2010 3:43 PM | LudovicoVan
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

@LudovicoVan: non volermene ma pecchi un po' di presunzione... in ogni caso sicuramente avere meno if riduce la complessità... e qui chiudo la discussione tanto con te le tue competenze puoi migliorare e testare il codice su riportato senza alcun problema.
9/5/2010 8:32 PM | work
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

Andrea:> voglio sforzarmi di pensare "diversamente", lo faccio costantemente per riuscire a capire meglio le cose

Questo e' apprezzabile: d'altra parte l'ingegneria non e'una scienza, e' piuttosto la pratica di imparare dai propri errori per poi evitare di ricommetterli. In questo senso 'e doppiamente bene guardarsi bene intorno.

Luca:> Infine una cosa interessante é che quando il problema é scomposto come nel refactoring postato, si possono testare separatamente GetWhiteSpaceAndNonDuplicatedCharacter e RemoveDuplicates.

Fai esplodere un semplice if, che in piu' e' parte integrante della logica dell'algoritmo in questione, in due funzioni separate, che offuscano solo l'algoritmo originale e in piu' ti creano un'esplosione di test che e' nell'ordine della decina, ma giusto se sei bravo. Follia, come e' folle pensare che sostituire due if in cascata con un unico if con due condizioni in and faccia *qualunque* tipo di differenza se non sulla leggibilita' e manutenibilita' immediata delle due righe di codice in questione.

work:> non volermene ma pecchi un po' di presunzione

Figurati, per un pirata mascherato sei fin troppo gentile.

Matteo:> oppure i caratteri duplicati globalmente

La seconda che hai detto... Eravamo piu' o meno giunti al fatto che si puo' fare in "quasi" O(N) usando un dictionary per N piccolo e un array quando N supera l'ordine delle migliaia (o giu' di li')...

-LV
9/6/2010 4:25 PM | LudovicoVan
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

Si', assolutamente. Considera che per me l'originale e' molto meglio: l'algoritmo si presenta nella sua interezza, per non dire che il check per il white-space almeno viene fatto fuori dal loop interno... Al limite all'originale solleverei qualche obiezione di stile, e poi noterei che senza un qualche appoggio si puo' fare ben poco di diverso dalla forza bruta (ma forse Matteo ci sapra' dire altro).

-LV
9/6/2010 4:39 PM | LudovicoVan
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

>> - é meno leggibile e piu difficile da capire

> come ho detto, penso che sia il contrario

Non per niente, l'if mascherato si tramuta in if a spasso...

-LV
9/6/2010 6:20 PM | LudovicoVan
Gravatar

# re: Algoritmi – Rimuovere i caratteri duplicati in una stringa

Infatti cambia poco o nulla quale script prendi. Questa cosa mi ricorda quando insistevi a farmi risolvere un problema di deadlock e io continuavo a ripeterti che corretto il disegno il problema non si poneva proprio. :e metriche: altro bell'argomento.

-LV
9/8/2010 5:40 AM | LudovicoVan
Comments have been closed on this topic.

Powered by:
Powered By Subtext Powered By ASP.NET