[C] Confronto tra stringhe

[carloekekko]

perfetto grazie ora ci provo

[MItaly]

Originariamente inviato da YuYevon
Devi innanzitutto confrontare la lunghezza delle stringhe, come ti dicevo. Anzi, ora che ci faccio caso devi implementare una piccola funzione anche per fare quello visto che se ricorri alla strlen() siamo punto e a capo.

A ben vedere in realtà facendo così perdi solo tempo: per determinare la lunghezza delle stringhe devi comunque leggerle entrambe fino al terminatore NUL, per poi eventualmente rileggerle per confrontarle: a quel punto tanto vale confrontarle già alla prima lettura.
Un esempio "ermetico" di funzione strcmp:

int mystrcmp(const char * str1, const char * str2)
{
    /* Salta tutti i caratteri uguali, arrivando al massimo fino al primo NUL */
    for(;*str1 && *str2 && *str1==*str2;str1++,str2++)
        ;
    /* Confronta i caratteri a cui siamo arrivati (ossia i primi due che differiscono, 
    oppure i due NUL se le due stringhe sono identiche), effettuando la differenza tra l'uno
    e l'altro; in questa maniera se i due caratteri sono uguali la funzione restituirà 0, se
    quello di str1 è minore verrà restituito un numero negativo, se quello di str1 è maggiore
    verrà restituito un valore positivo; i cast servono per gestire correttamente i caratteri
    oltre il 127 e per evitare che accadano cose strane nell'effettuare la sottrazione */
    return (int)*((unsigned char *)str1)-(int)*((unsigned char *)str2);
}

.

[YuYevon]

Giusto per farci due chiacchiere

Se ci fai caso, il metodo dell'analisi preliminare delle dimensioni conviene se queste sono uguali: in quel caso facciamo due cicli iterativi che incrementano un semplice contatore e poi usciamo. Col metodo del "confronto diretto", invece, nel caso di dimensioni uguali andiamo in ogni caso ad incrementare due contatori e poi, nello stesso tempo, a fare un confronto (che prima non facevamo), che aumenta il costo della computazione... anche se - ovviamente - asinoticamente rimane lo stesso.

Il metodo che proponi tu conviene, invece, se le dimensioni non sono uguali, perché con la funzione che dicevo io andremmo a fare praticamente due cicli iniziali inutili...

A quel punto bisogna fare un'analisi: qual è la probabilità che le stringhe in input abbiano dimensione diversa? Se questa probabilità è "relativamente" alta, conviene il metodo che proponevo io. Se è bassa, quello che dicevi tu.

In fondo, quando anche non fosse possibile un'analisi preliminare, le due probabilità quasi si equivalgono no? Anzi forse è anche più probabile che siano diverse... boh ^^"

Vabbè, in fondo è una questione quasi "retorica"

[MItaly]

Originariamente inviato da YuYevon
Giusto per farci due chiacchiere

Se ci fai caso, il metodo dell'analisi preliminare delle dimensioni conviene se queste sono uguali: in quel caso facciamo due cicli iterativi che incrementano un semplice contatore e poi usciamo. Col metodo del "confronto diretto", invece, nel caso di dimensioni uguali andiamo in ogni caso ad incrementare due contatori e poi, nello stesso tempo, a fare un confronto (che prima non facevamo), che aumenta il costo della computazione... anche se - ovviamente - asinoticamente rimane lo stesso.

Il confronto nel tuo metodo comunque si fa almeno una volta (con NUL, ossia 0, per verificare se si è arrivati alla fine della stringa), e si leggono entrambe le stringhe fino alla fine, cosa che, nel metodo che suggerisco, non avviene (la scansione delle due stringhe termina nel momento in cui una delle due termina). Per cui nel tuo caso abbiamo un overhead fisso di scansione completa delle stringhe, seguita eventualmente da un confronto diretto tra di esse (ossia una nuova scansione completa con confronto). Nel mio caso invece la scansione è una sola e interessa solo la parte di stringhe strettamente necessaria per determinare se le stringhe sono uguali o diverse.

Vabbè, in fondo è una questione quasi "retorica"

In questo caso sicuramente, ma, dovendo implementare la strcmp in una libreria standard C la questione diventa rilevante, visto che la funzione in questione può essere usata anche in cicli da milioni di ripetizioni.

[YuYevon]

Originariamente inviato da MItaly
Il confronto nel tuo metodo comunque si fa almeno una volta (con NUL, ossia 0, per verificare se si è arrivati alla fine della stringa), e si leggono entrambe le stringhe fino alla fine, cosa che, nel metodo che suggerisco, non avviene (la scansione delle due stringhe termina nel momento in cui una delle due termina). Per cui nel tuo caso abbiamo un overhead fisso di scansione completa delle stringhe, seguita eventualmente da un confronto diretto tra di esse (ossia una nuova scansione completa con confronto). Nel mio caso invece la scansione è una sola e interessa solo la parte di stringhe strettamente necessaria per determinare se le stringhe sono uguali o diverse.

Beh sì ma se vogliamo col "ciclo diretto" di confronti se ne fanno 3: termine prima stringa, termine seconda stringa, confronto tra caratteri. Insomma come ti dicevo dipende dalle stringhe che dobbiamo aspettarci in input... in fin dei conti, quanti caratteri è possibile che abbia una stringa (supponiamo: una parola della lingua italiana)? 1,2,3... diciamo fino a 16-17 in media, considerando il dizionario.

Ci sono quindi circa 16 lunghezze possibili, tutte approssimativamente "equiprobabili", il che significa che abbiamo una probabilità pari a 1/16 che le dimensioni coincidano e che quindi venga eseguito l'altro ciclo for "più impegnativo" (il secondo, quello che per te sarebbe l'unico da fare). In questo caso, abbiamo una probabilità molto alta (15/16) che quel ciclo for non sia mai eseguito, quindi vale la pena di fare un'analisi preliminare perché in tal caso faremmo due cicli con un incremento di puntatore ciascuno e un confronto per ogni iterazione (il predicato di uscita). Nel tuo caso, il predicato di uscita prevede tre confronti (2 per vedere se le stringhe non sono terminate e un altro per constatare l'uguaglianza del carattere i-esimo) quindi se ci limitassimo a fare solo il primo ciclo avremmo un piccolo risparmio... e se la probabilità è 15/16 questo è più che conveniente (come dicevo, dipende dal problema per il quale applichiamo l'algoritmo: nel caso di "parole della lingua italiana" potrebbe convenire, data la varietà di lunghezza delle parole... se invece stiamo considerando stringhe di 3-4 caratteri massimo, il discorso cambia).

[MItaly]

Originariamente inviato da YuYevon
Beh sì ma se vogliamo col "ciclo diretto" di confronti se ne fanno 3: termine prima stringa, termine seconda stringa, confronto tra caratteri.

I confronti tra dati già presenti nei registri della CPU (o nella cache) sono velocissimi, la cosa che porta via più tempo al computer è recuperare i dati dalla cache, dalla RAM (in caso di cache-miss) o addirittura dal disco fisso (in caso di page-fault), di conseguenza una volta che i dati sono già nei registri o nella cache del processore è estremamente efficiente effettuare tutti i confronti insieme, invece di rimandare altri confronti al ciclo successivo.
Troverai conferma della maggiore efficienza del mio metodo nel fatto che (quasi?) tutte le strcmp fornite dalle librerie standard C sono implementate in maniera analoga alla mia.
Qualche esempio:
MSVC++ 2003

int __cdecl strcmp (
        const char * src,
        const char * dst
        )
{
        int ret = 0 ;

        while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
                ++src, ++dst;

        if ( ret < 0 )
                ret = -1 ;
        else if ( ret > 0 )
                ret = 1 ;

        return( ret );
}

MinGW

int
_DEFUN (strcmp, (s1, s2),
	_CONST char *s1 _AND
	_CONST char *s2)
{ 
#if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
  while (*s1 != '\0' && *s1 == *s2)
    {
      s1++;
      s2++;
    }

  return (*(unsigned char *) s1) - (*(unsigned char *) s2);
#else
  unsigned long *a1;
  unsigned long *a2;

  /* If s1 or s2 are unaligned, then compare bytes. */
  if (!UNALIGNED (s1, s2))
    {  
      /* If s1 and s2 are word-aligned, compare them a word at a time. */
      a1 = (unsigned long*)s1;
      a2 = (unsigned long*)s2;
      while (*a1 == *a2)
        {
          /* To get here, *a1 == *a2, thus if we find a null in *a1,
	     then the strings must be equal, so return zero.  */
          if (DETECTNULL (*a1))
	    return 0;

          a1++;
          a2++;
        }

      /* A difference was detected in last few bytes of s1, so search bytewise */
      s1 = (char*)a1;
      s2 = (char*)a2;
    }

  while (*s1 != '\0' && *s1 == *s2)
    {
      s1++;
      s2++;
    }
  return (*(unsigned char *) s1) - (*(unsigned char *) s2);
#endif /* not PREFER_SIZE_OVER_SPEED */
}

ReactOS

int _tcscmp(const _TCHAR* s1, const _TCHAR* s2)
{
 while(*s1 == *s2)
 {
  if(*s1 == 0) return 0;

  s1 ++;
  s2 ++;
 }

 return *s1 - *s2;
}

[YuYevon]

Chiedo scusa se riapro il topic ma era giusto per riconoscere la ragione a Mitaly. Al di là delle ultime considerazioni che hai fatto (sicuramente intelligenti), riflettendo sulla complessità asintotica mi ritrovo che, se considerassimo - e non è così ma facciamo un'approssimazione - confronti e incrementi come operazioni che richiedono una complessità costante pari a 1 (1 microsecondo ad esempio, giusto per dire una sciocchezza), avremo che nel caso del ciclo di analisi preliminare la complessità sarebbe

4N

(dove N è la lunghezza dell'eventuale stringa più breve) e poi 4 perché avremo 2N incrementi e 2N confronti. E' evidente che se N termina (e l'altra stringa M no) noi usciamo dal ciclo e concludiamo che le stringhe non sono uguali, ma per dirlo dobbiamo appunto scorrere ALMENO tutta la stringa N.

Il ciclo che incrementa i contatori e fa direttamente i confronti, invece, impiega un tempo pari a

(5/2)N, o per meglio dire 5(N/2)

questo perché supponiamo sempre che la stringa più breve sia N (vale lo stesso anche se sono uguali). Mediamente, le stringhe avranno il primo carattere diverso nella "n/2-esima" posizione, quindi noi facciamo 2 incrementi e 3 confronti tutti per N/2 volte (in media), quindi ecco il risultato di cui sopra.

Tra l'altro, se si considera che nel caso peggiore, col metodo che proponevo io, non solo devo fare l'analisi preliminare ma anche il ciclo di confronto finale, la complessità in quel caso sarebbe addirittura 4N + (5/2)N, quindi ancora peggiore.

Non avevo calcolato questo fattore, insomma: nel ciclo che fa direttamente i confronti, non è detto che vengano considerati tutti i caratteri delle stringhe, ma mediamente ci si fermerà a metà della stringa N.

Forse la soluzione che proponevo io a quel punto sarebbe valida solo in casi di input ancora più particolari di prima (della serie: stringhe di varia lunghezza e con ben più dei solo primi N/2 caratteri uguali) ma sarebbe davvero un caso troppo ristretto e e l'algoritmo perderebbe molto di universalità.

[MItaly]

Non ho mai studiato nulla sulla complessità asintotica, ma mi fido.