Newsgroup: it.comp.lang.c
Titolo: confronto di stringhe, case insensitive

Ciao,
qualcuno potrebbe darmi qualche suggerimento per ottimizzare questo
codice?
ed eventualmente se potete spiegarmi il perchč.
vi ringrazio.
Dave
//----------------------------------------------------------------------
// EQUAL: confronta se due stringhe sono uguali, case insensitive
//----------------------------------------------------------------------
BOOL equal(char *match1,  char *match2) {
  static UCHAR bb1;
  static UCHAR bb2;
  if (match1 && match2) {
     do {
       bb1=*match1++;
       bb2=*match2++;
       if (bb1>='a' && bb1 <= 'z') bb1+='A'-'a';
       if (bb2>='a' && bb2 <= 'z') bb2+='A'-'a';
       if (bb1 != bb2) return FALSE;
     } while (bb2);     //da qui esce nel caso (bb1==0 and bb2==0)
     return TRUE;
  }
  return FALSE;
}


Magari ci pensa gia' il compilatore, pero' io qui metterei il risultato di
'A'-'a' in una variabile, e poi utilizzerei quella al posto di fargli fare
tute le volte la sottrazione.
Ciao,
Ema

 }
Scrivi di meno, si rischia di sbagliare di meno, toupper e' standard,
il codice e' piu' chiaro.
HTH
C:\>iao Angelo
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG


grazie
ciao
Dave


d'accordo, ma i contenuti delle stringhe non devono cambiare però,
cmq la tua soluzione sembra ottima, ma cosi a naso non mi sembra molto
efficiente, credo, perchè fai delle chiamate a strcmp e toupper.
farò delle prove per vedere di quanto differisce nei tempi di
esecuzione.
grazie comunque.
Ciao
Dave

 sarebbe una buona idea, ma nel caso sia un carattere alfabetico
volevo scrivere: "ma nel caso NON sia un carattere alfabetico"

d'accordo, ma i contenuti delle stringhe non devono cambiare però,
allora perché non sono const char*?
sbirish.

 esecuzione.
Le considerazioni spannometriche lasciano il tempo che trovano. Se vuoi
avere delle statistiche precise usa un profiler... portesti avere delle
sorprese.


 ci devo pensare..
Ovviamente conviene mettere l'assegnamento
temp_var = 'A' - 'a'
fuori dal ciclo per farglielo eseguire una volta sola.
Poi all'interno del ciclo usi temp_var.
Non e' che per ogni iterazione te lo devi ricalcolare...
La tua considerazione vale se le due stringhe fossero tutte di caratteri non
alfabetici, ma sarebbe un solo assegnamento in piu'... nel computo della
complessita' e' una costante e non conta niente.
RiCiao,
Ema

   static UCHAR bb2;
Confermo l'ottima idea di dichiarare static bb1 e bb2, la seconda volta
che chiami la funzione no verranno riallocate (e deallocate all'uscita).
Per il resto la riscriverei cosi` (dovrebbe essere un po' piu` veloce):
BOOL equal(const char *match1,  const char *match2)
{
  // controllo che non si usino dei valori null
  if (!match1 || !match2) {
    return FALSE;
  }
  do {
    if (*match1 != *match2) {
      // se sono diverse una sola delle due puo` essere minuscola e l'altra per
      // forza di cose maiuscola, in ogni altro caso sono per forza diverse
      if (*match1 >= 'a' && *match1 <= 'z') {
        if (*match1 - 32 != *match2)
          return FALSE;
      } else if (*match2 >= 'a' && *match2 <= 'z') {
        if (*match2 - 32 != *match1)
          return FALSE;
      } else {
        return FALSE;
      }
    }
    match1++;
    match2++;
  } while (*match1 && *match2);
  return *match1 == *match2;
}
-- 
//\/\ Marco (LM) Lamberto (
marcol...@despammed.com
)
      SIForge.org     -  
http://www.siforge.org/
      The Sunny Spot  -  
http://the.sunnyspot.org/


Io farei cosi' (da alcune prove con stringhe lunghe tra 10 e 2000
caratteri sembra che la mia versione ci metta (sulla mia macchina)
circa la meta' del tempo:
unsigned char M[256];
int Uguali(char *a, char *b)
{
   if (a && b)
   {  while (*a)
        if (M[*(a++)]!=M[*(b++)]) return 0;
      return *b==0;
   }
   else return 0;
}
int main()
{
/* predispongo la tabella di conversione */
   int c;
   for (c=0; c<256; c++)
/* resto del programma */
  ........................
}
oppure, se non ti piacciono i globali:
int Uguali2(char *a, char *b)
{
   static unsigned char MM[256];
   if (a==0 || b==0)
     { int c;
       for (c=0; c<256; c++)
        MM[c]=(unsigned char) (c>='A' && c<='Z' ? c-'A'+'a' : c);
       return 0;
     }
   while (*a)
      if (MM[*(a++)]!=MM[*(b++)]) return 0;
   return *b==0;
}
e la prima volta lo inizializzi chiamando Uguali2(0,0);
ciao,
g.

   for (c=0; c<256; c++)
Ahemm, qui ho ovviamente dimenticato la riga:
M[c]=(unsigned char) (c>='A' && c<='Z' ? c-'A'+'a' : c);
ciao,
g.


Puoi provare a dichiarare register le variabili a cui accedi di frequente e
se spesso le due stringhe sono differenti per lunghezza prima di procedere
con il tuo algoritmo fai un check per verificare che siano entrambe lunghe
uguali.
Luca

Puoi provare a dichiarare register le variabili a cui accedi 
certo.. tanto per scrivere una parola in più visto che register viene
ignorato.
sbirish


register viene ignorato (gcc) se in qualche punto del programma si accede
all'indirizzo della variabile a cui fa riferimento. Sia bb1 che bb2 non
vengono mai chiamate con &.
Luca


mi sa che c'hai ragione! :-)
thanks.
Dave

 allora perché non sono const char*?
oops, mi ero dimenticato.. :-)
ciao
Dave

  .....
come stratagemma oserei dire geniale..
grazie per l'algoritmo.
Ciao
Dave

 C:\>iao Angelo
ma LCCwin32 ce l'ha il profiler?
non ci ho mai fatto caso,
adesso provo a guardarci. :-)
Ciao.
Dave


sono sconvolto dalla tua idea,
sto ancora cercando di capire come funziona... =:-|
mi sembra che hai precalcolato qualcosa. ;-)
cmq grazie per l'algoritmo.
ciao
Dave


interessante...
io sapevo che praticamente register veniva ignorato quando si usava
il parametro di ottimizzazione del compilatore, ad esempio.
io uso lccwin32 con -O e
mi sembrava, anche leggendo la docum., che register veniva ignorato
proprio dappertutto
perchč il compilatore ottimizzava gia tutto.
ciao
Dave

vengono mai chiamate con &.
te la riformulo, 
nel migliore dei casi, quei register vengono ignorati ( e grazie a dio
i compiler sono autorizzati a farlo. )
sbirish.


La mia idea e' banalissima, ma sulla mia macchina e' decisamente
piu' veloce, probabilmente perche' fa un solo if per ogni ciclo e
l'indirizzamento di un array di char e' veloce.
Semplicemente mi precalcolo un array di caratteri M tali in cui
in posizione c c'e' il carattere c in versione low-case (o up-case).
Allora M[c] e' come dire "prendi la versione minuscola di c".
Quindi se M[c] == M[d] i due caratteri c e d hanno la stessa versione
minuscola e quindi sono uguali (o differiscono solo per il case).
Una volta calcolata la tabella mi basta scandire i caratteri
delle due stringhe e calcolare se le posizioni corrispondenti
hanno lo stesso valore di M[*a] e M[*b].
Il test finale (*b==0) e' dovuto al fatto che
esco dal ciclo principale quando *a==0 e in quel caso il confronto
e' soddisfatto solo se anche la stringa b e' finita.
ciao,.
g.


Questo non lo so. Adesso sto usando win e non ho il gcc, quindi non posso
controllare la documentazione. Prova magari anche a dichiarare la funzione
di Giovanni Resta inline, dovrebbe evere un incremento di velocita' se
chaiamata parecche volte.
Luca

 oppure, se non ti piacciono i globali:
Puoi anche fare 2 funzioni: una per inizializzare e una per la ricerca,
cosi' eviti gli artifici.
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

 cioè? :-|
dicesi funzione rientrante una funzione che puo' essere sospesa senza
portare errori nell'area dati, nel tuo caso se la funzione la usi solo in un
punto del tuo codice e non la usa nessun altro tread o processo di sistema
non avresti cmq problemi.
il punto e' che disolito le funzioni vengono usate appunto per creare
librerie da usare il piu' possibile, quindi una funzione non rientrante in
programmi multi tread o di sistema farebbe solo massacri nello stack.
spero di essere stao chiaro ? se non ho spiegato bene dimmelo che cerchero'
di farti magari un esempietto.
ciao

 perchè il compilatore ottimizzava gia tutto.
se usi -O0 vengono tutte ignorate register volatile ecc ... e vengono tenute
tutte in memoria e testate ogni volta
con -O2 gia' vengono testate se il compilatore vede che e' meglio usarle in
un'altro modo le maneggia come vuole
ora non vorrei dire castronerie ma l'unico modo per mantenere
l'ottimizzazione del programmatore e' con -O1
-O3 e -Os invece fanno pure altre ottimizzazioni che alle volte portano dei
bug che non ci sarebbero nel codice pensato dal programmatore, pero' non ho
ben presente la versione 3.2 io mi ricordavo che le 2.8 2.9 erano
sconsigliatissime le opzioni massime soprattutto su server e kernel.
ciao

 chaiamata parecche volte.
si e se rimane cmq minore di 600 call ... seno' dovresti impostare i call
massimi per l'inliner, cmq e' un ottimizzazione che fa gia' gcc di suo
quello di mettere funzioni brevi inliner, forse per questo caso la
dichiarazione static potrebbe non farglielo fare,bho ...
cmq se la chiamata di tale funzione e' superiore gia' alle 300-400 il peso
del suo codice inliner lo senti sull'eseguibile finale che lievita di
dimensioni anche se rimane prestante, poi dipende se lo deve mettere in un
pic o su un pc con 1gb.
ciao

         if (*match2 - 32 != *match1)
idem come sopra. 
- -- 
No matter. Try again. Fail again. Fail better.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)
iD8DBQE/E3h1Qb6qi6QXZLkRAmRcAJ9xMmqMXkt/nqIcx65NUaJxHo1+UACdGHDg
/CwqOgzCPOCCnxMR2h9lcsM=
=sJfQ
-----END PGP SIGNATURE-----

 cosi' eviti gli artifici.
Scusa la mia ignoranza, ma come faresti ad inizializzare un array static
dichiarato all'interno  di una funzione senza invocare la funzione
stessa ?
ciao,
g.

 che chiami la funzione no verranno riallocate (e deallocate all'uscita).
Tipico caso  di sovraottimizzazione. Hai *misurato* quando  costa questa
"allocazione" [1]? Hai *misurato* l'impatto che una variabile non locale
(anche in senso spaziale) ha sulla cache?
Piuttosto  che  preoccuparsi  di  cose simili  bisognerebbe  cercare  di
scrivere codice corretto. E quello dell'OP non lo e`. (hint: chi ti dice
che i  caratteri siano contigui?). Se  proprio si vuole  scrivere codice
estremamente ottimizzato per una singola  combinazione di OS/CPU si puo`
fare ricorso  all'assembly (e gli  x86 hanno istruzioni  molto efficenti
per la manipolazione di stringhe).
ciao
Kronos
[1]  Si  tratta   di  una  solo  istruzione  assembly...   il  costo  e`
insignificante rispetto al resto dell'algoritmo.
-- 
Home: 
http://kronoz.cjb.net
Non sempre quello che viene dopo e` progresso.
Alessandro Manzoni

 all'indirizzo della variabile a cui fa riferimento. 
Suvvia,  l'x86 ha  8 registri  GPR, alcuni  dei quali  usabili solo  per
scopi particolari. Credi  davvero che un compilatore  qualsiasi onori un
qualificatore register? Il controllo sui registri e` solo resposabilita`
dello scheduler.
register ha senso solo quando ci sono registri in abbondanza.
ciao
Kronos
-- 
Home: 
http://kronoz.cjb.net
K.R.O.N.O.S
Kinetic Replicant Optimized for Nocturnal Observation and Sabotage

 stessa ?
Premessa: non e' un errore, e' solo una cosa che stilisticamente mi suona
male.
Una funzione del genere dovrebbe avere un solo scopo, non variare a seconda
dei parametri :)
Se ti piace l'idea della variabile static allora fai:
<code>
int funzione(param)
{
    int init = 0;
    static char M[(unsigned char)1<<CHAR_BIT]
    if (!init)
        inizializza_M;
    resto_della_funzione;
    return risultato;
}
</code>
Il costo e' minimo.
I test e la mia memoria dicono che le variabili static subiscono
l'inizializzazione durante la dichiarazione solo una volta, quindi il tutto
funziona. Spero che non sia solo un caso abbinato ad un mio vuoto di
memoria :)
Altrimenti (sempre se non lo vogliamo globale), passi un parametro
esplicito:
<code>
#define MAX (unsigned char)1 << CHAR_BIT
int init(char *M)
{
  int c;
  for (c=0; c<MAX; c++)
    M[c]=tolower(c);
}
</code>
e poi
<code>
int uguali(char *a, char *b, char *M);
</code>


 per la manipolazione di stringhe).
Esatto, stavo pensando proprio all'inline asm quando ho letto la prima
volta il post.
Ciao,
Marco



Assolutamente vero, in assembler (continuo a chiamarlo così, fin da quando
avevo 13 anni e un 6502...) si ottiene ovviamente la massima efficienza e
velocità possibile.
Devo raccontare, però, di quella volta che ho scritto per un Pentium3 una
funzione interamente in assembler per esigenze di velocità e poi, per
curiosità, l'ho riscritta in C.
Sono rimasto sorpreso, non c'era differenza apprezzabile. Il motivo ipotizzo
sia la ormai incredibile procedura di esecuzione fuori-sequenza degli
attuali processori, in grado di "preparare il terreno" alle istruzioni
successive.
Se tali funzioni le avessi fatte girare su uno Z80 non ho dubbi che il
divario di prestazioni sarebbe stato quasi doppio.
Ciao,
Paolo PAL

 OP??
Original Poster.
C:\>iao Angelo
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG