[C] trovare 2° stringa con 2 consonanti in fila

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
ixamit
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 499
Iscrizione: giovedì 14 novembre 2013, 10:16

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da ixamit »

Una lookup-up table di dimensione ridotta può richiedere almeno un controllo di bounds checking

Codice: Seleziona tutto

int isvoc (char c)
{
    c=(c&0xdf)^0x41;
    return (~c&0x80 && c<0x15)?0x30-c["100010001000001000001"]:0;
}
mentre una piccola serie di condizioni puo' essere risolta con una operazione di modulo.

Codice: Seleziona tutto

int isvoc (char c)
{
    return !(0x14d703d7a86e7ULL%(0x2c8+tolower(c)));
}
...anche se la forma più leggibile rimane sicuramente questa

Codice: Seleziona tutto

int isvoc (char c)
{
    return (isalpha(c=toupper(c)) && strchr("AEIOU",c));
}
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da Claudio_F »

Ooooo, lo sapevo che veniva fuori qualcosa di interessante da studiare ;)

Caso 1:
& 0xdf in effetti è più spiccio del mio if (c>90) ...
Non conosco la sintassi c["100010001000001000001"]
Per arrivare al bound test immagino che tu abbia giocato con i corner case della rappresentazione binaria delle vocali, ma non riesco ancora a capire se sarebbe applicabile a qualsiasi sottoinsieme.

Caso 2:
Interessante la divisibilità sulle sole vocali maiuscole con una specie di minimo comune multiplo, ma non capisco la procedura per ricavare il coefficiente 712.

Caso 3:
Simile a come lo scriverei in Python, solo che (almeno in Python) ho notato una maggiore velocità cercando in un insieme completo di vocali maiuscole e minuscole piuttosto che chiamare upper/lower.
:ciao:
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da M_A_W_ 1968 »

Trovi la maggior parte dei dettagli sugli idiomi di questo genere in vari testi. Probabilmente il più lightweight è il pluricitato "Hacker's Delight", nel quale le dimostrazioni sono mantenute al minimo fisiologico e usano comunque solo nozioni elementari, mentre il resto della letteratura (incluso ovviamente il TAoCP) è meno divulgativo e maggiormente formale. Comunque l'algebra degli anelli booleani non è particolarmente esoterica, in generale.

Riguardo al primo caso, molti cross-compiler sono congegnati per produrre di default tale tipo di ottimizzazione, sulle piattaforme nelle quali il confronto con una costante e relativo salto condizionato sia per qualche motivo più costoso di una operazione booleana atomica seguita dal medesimo flagcheck e salto condizionato. In ambito mainstream, alcuni ottimizzatori peephole riescono tranquillamente a fare altrettanto.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
ixamit
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 499
Iscrizione: giovedì 14 novembre 2013, 10:16

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da ixamit »

Claudio_F ha scritto: [...]
Non conosco la sintassi c["100010001000001000001"]
[...]
Ho invertito l'array con l'indice per evidenziare la parte costante.
Comunque non cambia niente, arr è equivalente a i+*arr
Claudio_F ha scritto: ma non riesco ancora a capire se sarebbe applicabile a qualsiasi sottoinsieme

In quel modo credo di no, ma un boundary check o una divisione è comunque possibile.

Claudio_F ha scritto: [...]
Interessante la divisibilità sulle sole vocali maiuscole con una specie di minimo comune multiplo, ma non capisco la procedura per ricavare il coefficiente 712.
[...]

Esatto, il dividendo è il prodotto delle 5 codifiche, e il "magic number" l'ho ricavato dal minor numero di occorrenze dell'insieme. Credo si possa fare di meglio, visto che il costo della divisione non ne migliora i tempi.

M_A_W_1968 ha scritto: Trovi la maggior parte dei dettagli sugli idiomi di questo genere in vari testi. Probabilmente il più lightweight è il pluricitato "Hacker's Delight", nel quale le dimostrazioni sono mantenute al minimo fisiologico e usano comunque solo nozioni elementari, mentre il resto della letteratura (incluso ovviamente il TAoCP) è meno divulgativo e maggiormente formale. Comunque l'algebra degli anelli booleani non è particolarmente esoterica, in generale.
[...]

Infatti, "Hacker's Delight" è un concentrato di formule, a volte ripresentate dagli stessi lettori.
C'era un testo in particolare che trattava l'argomento in modo più approfondito, dal punto di vista algoritmico, un migliaio di pagine, ma non ricordo il titolo. Credo di averlo prestato a qualcuno che non me lo ha più restituito :cry: .

@all
Tra tutte le soluzioni proposte, quella di Claudio_F mi risulta essere circa il doppio più veloce rispetto alle mie.
Chi ha tempo e voglia può vedere come il compilatore ottimizza ai vari livelli di -O con un semplice switch+case, usando -S -fverbose-asm ed interlacciando le linee di codice -alhnd.

Pace e bene,
Max
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da M_A_W_ 1968 »



Vedasi in proposito anche questo.


ixamit ha scritto: C'era un testo in particolare che trattava l'argomento in modo più approfondito, dal punto di vista algoritmico, un migliaio di pagine, ma non ricordo il titolo. Credo di averlo prestato a qualcuno che non me lo ha più restituito :cry: .


Non ricordi l'autore, l'editore o qualche altro dettaglio utile? C'è una ragionevole certezza che si tratti di uno dei vari testi che ho già consigliato in passato.


ixamit ha scritto: Tra tutte le soluzioni proposte, quella di Claudio_F mi risulta essere circa il doppio più veloce rispetto alle mie.


Era piuttosto evidente, ma hai fatto bene a sottolinearlo comunque: per qualche lettore poteva essere meno palese il fatto che con Claudio abbiamo finora parlato di una soluzione ottima o comunque ottimale sulla maggioranza delle piattaforme mainstream. Ma è sempre bene ricordare che il bit fiddling può portare incrementi prestazionali inattesi, e che vale comunque la pena di studiare a fondo le relative tecniche algebriche, booleane e di teoria elementare del numero (vedi mcm e MCD, fattorizzazione etc.).
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
ixamit
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 499
Iscrizione: giovedì 14 novembre 2013, 10:16

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da ixamit »

M_A_W_1968 ha scritto:
ixamit ha scritto: Comunque non cambia niente, arr è equivalente a i+*arr


Vedasi in proposito anche questo.

Ho letto e ti ringrazio per i chiarimenti, ma come detto precedentemente l'ho fatto intenzionalmente solo per evidenziare la parte costante. Non ho mai divulgato questo genere di codice se non in giochi di offuscamento. Spero sia chiaro

M_A_W_1968 ha scritto: Non ricordi l'autore, l'editore o qualche altro dettaglio utile? C'è una ragionevole certezza che si tratti di uno dei vari testi che ho già consigliato in passato.

Purtroppo no... ho un'altra professione e la mia testa è su altri problemi, ma spero di ricordarmi a chi l'ho prestato o qualcosa che possa essere di indizio per risalire al testo. Del resto ero anche pieno di tracciati record scritti dal sottoscritto che sono andati persi, smarriti in chissà quale posto...

Approfitto di questo post per aggiungere una funzione più veloce tra tutte quelle proposte, estratta e tradotta dall'ottimizzazione del compilatore:

Codice: Seleziona tutto

int isvoc (char c)
{
    int i = toupper(c)-'A';
    return (i<0 || i>25)? 0:(0x104111 & (1<<i));
}
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da M_A_W_ 1968 »

ixamit [url=http://forum.ubuntu-it.org/viewtopic.php?p=4696841#p4696841][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto: Ho letto e ti ringrazio per i chiarimenti, ma come detto precedentemente l'ho fatto intenzionalmente solo per evidenziare la parte costante. Non ho mai divulgato questo genere di codice se non in giochi di offuscamento. Spero sia chiaro
Non c'era dubbio in proposito, Max: il richiamo al thread era ovviamente ad usum delphini, a beneficio di Claudio e degli altri lettori! ;)
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
Avatar utente
M_A_W_ 1968
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 856
Iscrizione: venerdì 15 febbraio 2013, 3:57
Desktop: KDE
Distribuzione: SuSE
Sesso: Maschile
Località: Un luogo geometrico
Contatti:

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da M_A_W_ 1968 »

ixamit [url=http://forum.ubuntu-it.org/viewtopic.php?p=4696841#p4696841][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Approfitto di questo post per aggiungere una funzione più veloce tra tutte quelle proposte, estratta e tradotta dall'ottimizzazione del compilatore:

Codice: Seleziona tutto

int isvoc (char c)
{
    int i = toupper(c)-'A';
    return (i<0 || i>25)? 0:(0x104111 & (1<<i));
}
Hai già fatto il profiling anche di una variante del tipo che segue?

Codice: Seleziona tutto

int isvoc (char c)
{
    int i = (toupper(c)-'A') & 0x1F;
    return (i<0)? 0:(0x104111UL & (1<<i));
}
In teoria, è ancora più veloce su x86 > 386 e IA64. Comunque, vediamo i numeretti.

Per i più giovani: concentratevi sempre sul fatto che, anche nel terzo millennio, i confronti con lo zero e il range shift (che finisce per coinvolgere il solo sign flag nel lower bound check) sono vincenti rispetto ad ogni altra forma di bounds checking per valori che non sono potenze intere del due. Qui, peraltro, possiamo comunque lavorare con una costante a 32 bit, da cui l'and binario che elimina il confronto per il test dell'upper bound.
Sì, un blog ce l'ho perfino io: gli è che mi manca il tempo...

"...in una società che sembra sempre più spaventata dai problemi troppo articolati e che rigetta come un corpo estraneo ogni elemento di complessità, sapremo ancora come utilizzare il parere degli esperti?"
Avatar utente
vbextreme
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1214
Iscrizione: domenica 12 gennaio 2014, 14:06
Desktop: lxde
Distribuzione: xubuntu 14.10

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da vbextreme »

questo si discosta molto dalle mappe?

Codice: Seleziona tutto

int isvoc1(int c)
{
   c = tolower(c);
	int map[5] = {'a',4,4,6,6};
	int i = 0;
	while ( (c -= map[i++]) > 0);
	return !c;
}
appena ho un pelo piu di tempo provo anche io giocando con i numeri...

Codice: Seleziona tutto

int isvoc2(int c)
{
	c = tolower(c);
	return !((c-'a') && (c-'e') && (c-'i') && (c-'o') && (c-'u'));
}
anche questa è valida???
No,giusto per capire le differenze....




Ho eseguito un test rapido sulla velocità, riempiendo un vettore di 1024 valori ripetuti nel range da 0-255, in sostanza ho eseguito la funzione "isvoc" * 4 volte su tutti i valori ascii. solo con -O2
Ecco il risultato del tempo clompessivo che andrebbe diviso per 1024 per trovare il singolo tempo:

Codice: Seleziona tutto

vb1:0.00009489
vb2:0.00004315
maw:0.00005507
ixa:0.00005078
cla:0.00004601
Il tutto su una cpu RISC
Ultima modifica di vbextreme il domenica 21 dicembre 2014, 10:58, modificato 1 volta in totale.
Easy framework per il linguaggio C.
vbextreme hack your life
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da Claudio_F »

ixamit ha scritto: Tra tutte le soluzioni proposte, quella di Claudio_F mi risulta essere circa il doppio più veloce rispetto alle mie.
vbextreme ha scritto: cla:0.00004601
Quale delle due che ho proposto? Quella con l'espressione logica in fondo a http://forum.ubuntu-it.org/viewtopic.php?f=33&t=590727#p4694629?
:ciao:
Avatar utente
vbextreme
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1214
Iscrizione: domenica 12 gennaio 2014, 14:06
Desktop: lxde
Distribuzione: xubuntu 14.10

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da vbextreme »

ho modificato i codici aggiungendo register e questi sono i risultati:

Codice: Seleziona tutto

vb2:0.00003695
maw:0.00004005
ixa:0.00004292
cla:0.00003505
@claudio io ho usato questo:

Codice: Seleziona tutto

unsigned char MAP[] = {0x88, 0x82, 0x08, 0x00};

int isvoccla (register char c) {
    if (c > 90) c ^= 32;
    c -= 65;
    register int ib = c >> 3;
    c %= 8;
    return (MAP[ib] >> (7 - c)) & 1;
}

sono contento che la mia soluzione sta al vostro passo...anche se vorrei venisse analizzato da maw....
Easy framework per il linguaggio C.
vbextreme hack your life
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da Claudio_F »

vbextreme ha scritto:

Codice: Seleziona tutto

unsigned char MAP[] = {0x88, 0x82, 0x08, 0x00};

int isvoccla (register char c) {
    if (c > 90) c ^= 32;
    c -= 65;
    register int ib = c >> 3;
    c %= 8;
    return (MAP[ib] >> (7 - c)) & 1;
}
Quella corretta e` questa:

Codice: Seleziona tutto

unsigned char MAP[] = {0x88, 0x82, 0x08, 0x00};

int isvoccla (register char c) {
    c &= 0xdf;
    c -= 65;
    if (c & 128) return 0;
    register int ib = c >> 3;
    c %= 8;
    return (MAP[ib] >> (7 - c)) & 1;
}
Sarei curioso anche di confrontare la velocita` di:

Codice: Seleziona tutto

char isvoc(char c)
{
    char d0 = c & 1;
    char d1 = c >> 1;
    char d2 = c >> 2;
    char d3 = c >> 3;
    char d4 = c >> 4;
    char d6 = c >> 6;
    char d7 = c >> 7;
    return ~d7 & d6 & d0 & (~d3 & d2 & ~d1 | ~d4 & (~d2 & ~d1 | d3 & d2 & d1));
}
:ciao:
Avatar utente
vbextreme
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1214
Iscrizione: domenica 12 gennaio 2014, 14:06
Desktop: lxde
Distribuzione: xubuntu 14.10

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da vbextreme »

corretto, allora la prima che hai postato comunque ritorna che è una vocale anche su questi valori:

Codice: Seleziona tutto

128-�
130-�
131-�
132-�
133-�
138-�
141-�
143-
145-�
146-�
147-�
148-�
153-�
155-�
156-�
158-�
159-�
169-�
170-�
171-�
173-�
176-�
177-�
181-�
183-�
185-�
187-�
190-�
la seconda invece ritorna solo le vocali correttamente.
Anche quella di maw sbaglia:

Codice: Seleziona tutto

1-
5-
9-	
15-
21-
33-!
37-%
41-)
47-/
53-5
129-�
133-�
137-�
143-
149-�
161-�
165-�
169-�
175-�
181-�
193-
197-
201-
207-
213-
225-
229-
233-
239-
245-
i tempi sono già divisi per 1024 quindi x ogni singolo controllo ci mettono circa:

Codice: Seleziona tutto

vb1:0.000000094762
vb2:0.000000037951
maw:0.000000040047
ixa:0.000000041211
cl1:0.000000035157
cl2:0.000000063330
per il momento allora sono corrette solo vb1,vb2,ixa,cl2.
Easy framework per il linguaggio C.
vbextreme hack your life
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da Claudio_F »

Noto differenze tra usare char, register int, register char... e non ottengo gli stessi tuoi output (ma solo tre o quattro valori oltre le vocali e solo con la versione vecchia), credo che con shift e assegnazioni (cast impliciti) usati in questo modo stiamo mettendo in crisi le diverse implementazioni/architetture.
:ciao:
ixamit
Scoppiettante Seguace
Scoppiettante Seguace
Messaggi: 499
Iscrizione: giovedì 14 novembre 2013, 10:16

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da ixamit »

Claudio_F [url=http://forum.ubuntu-it.org/viewtopic.php?p=4697026#p4697026][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:
ixamit ha scritto: Tra tutte le soluzioni proposte, quella di Claudio_F mi risulta essere circa il doppio più veloce rispetto alle mie.
vbextreme ha scritto: cla:0.00004601
Quale delle due che ho proposto? Quella con l'espressione logica in fondo a http://forum.ubuntu-it.org/viewtopic.php?f=33&t=590727#p4694629?
Si, quella

@all
Premetto che le statistiche seguenti sono relative solo alle 3 migliori funzioni.
La terza l'ho corretta in questa forma perché includeva altri valori in testa e coda:

Codice: Seleziona tutto

int isvoc (char c)
{
    int i = (toupper(c)-'A');
    return (i & 0xe0)? 0:(0x104111UL & (1<<i));
}
Ho usato perf come profiler, con l'opzione --sync che viene eseguita prima di ogni ri-esecuzione.
Ho inoltre creato vari livelli di TEST, sia sul l'intero charset, sia usando testi campione (lorem ipsum, ecc).
Input static, output quasi nullo (solo qualche byte di controllo)

Legenda:

Codice: Seleziona tutto

max@studio:~/tmp/foo$ ll claudio max MAW
lrwxrwxrwx 1 max max 1 dic 21 11:56 claudio -> 2
lrwxrwxrwx 1 max max 1 dic 21 11:56 MAW -> 3
lrwxrwxrwx 1 max max 1 dic 21 11:56 max -> 1
max@studio:~/tmp/foo$ 
max@studio:~/tmp/foo$ alias perfstat
alias perfstat='perf stat'
1 TEST x CHARSET - 10,000 ri-esecuzioni

Codice: Seleziona tutto

max@studio:~/tmp/foo$ CFLAGS=-DTEST1
max@studio:~/tmp/foo$ export CFLAGS && c 1 2 3

cc -DTEST1 1.c -o 1: OK

cc -DTEST1 2.c -o 2: OK

cc -DTEST1 3.c -o 3: OK
max@studio:~/tmp/foo$ 

Codice: Seleziona tutto

max@studio:~/tmp/foo$ perfstat -S -r 10000 ./claudio 
    
 Performance counter stats for './claudio' (10000 runs):

          0,246306 task-clock                #    0,578 CPUs utilized            ( +-  0,33% )
                 0 context-switches          #    0,000 M/sec                    ( +-  7,85% )
                 0 CPU-migrations            #    0,000 M/sec                    ( +-  6,06% )
               107 page-faults               #    0,433 M/sec                    ( +-  0,00% )
            708350 cycles                    #    2,876 GHz                      ( +-  0,13% )
   <not supported> stalled-cycles-frontend 
   <not supported> stalled-cycles-backend  
            403021 instructions              #    0,57  insns per cycle          ( +-  0,02% )
             87688 branches                  #  356,012 M/sec                    ( +-  0,02% )
              3125 branch-misses             #    3,56% of all branches          ( +-  0,07% )

       0,000425872 seconds time elapsed                                          ( +-  0,43% )

max@studio:~/tmp/foo$ perfstat -S -r 10000 ./max

 Performance counter stats for './max' (10000 runs):

          0,246089 task-clock                #    0,579 CPUs utilized            ( +-  0,29% )
                 0 context-switches          #    0,000 M/sec                    ( +-  8,62% )
                 0 CPU-migrations            #    0,000 M/sec                    ( +-  6,24% )
               110 page-faults               #    0,446 M/sec                    ( +-  0,00% )
            723199 cycles                    #    2,939 GHz                      ( +-  0,12% )
   <not supported> stalled-cycles-frontend 
   <not supported> stalled-cycles-backend  
            400389 instructions              #    0,55  insns per cycle          ( +-  0,02% )
             90140 branches                  #  366,291 M/sec                    ( +-  0,02% )
              3176 branch-misses             #    3,52% of all branches          ( +-  0,07% )

       0,000425189 seconds time elapsed                                          ( +-  0,41% )

max@studio:~/tmp/foo$ perfstat -S -r 10000 ./MAW

 Performance counter stats for './MAW' (10000 runs):

          0,245179 task-clock                #    0,568 CPUs utilized            ( +-  0,27% )
                 0 context-switches          #    0,000 M/sec                    ( +-  6,84% )
                 0 CPU-migrations            #    0,000 M/sec                    ( +-  6,22% )
               110 page-faults               #    0,448 M/sec                    ( +-  0,00% )
            746863 cycles                    #    3,046 GHz                      ( +-  0,15% )
   <not supported> stalled-cycles-frontend 
   <not supported> stalled-cycles-backend  
            399899 instructions              #    0,54  insns per cycle          ( +-  0,02% )
             89901 branches                  #  366,676 M/sec                    ( +-  0,02% )
              3149 branch-misses             #    3,50% of all branches          ( +-  0,07% )

       0,000431358 seconds time elapsed                                          ( +-  0,50% )

max@studio:~/tmp/foo$ 
2 TEST LOREM IPSUM - 1,000 ri-esecuzioni

Codice: Seleziona tutto

max@studio:~/tmp/foo$ wc text.txt 
  31 1215 8296 text.txt
max@studio:~/tmp/foo$ export CFLAGS=-DTEST3 && c 1 2 3

cc -DTEST3 1.c -o 1: OK

cc -DTEST3 2.c -o 2: OK

cc -DTEST3 3.c -o 3: OK

Codice: Seleziona tutto

max@studio:~/tmp/foo$ perfstat -S -r 1000 ./claudio > /dev/null 

 Performance counter stats for './claudio' (1000 runs):

          0,392835 task-clock                #    0,687 CPUs utilized            ( +-  1,28% )
                 0 context-switches          #    0,000 M/sec                    ( +- 21,07% )
                 0 CPU-migrations            #    0,000 M/sec                    ( +- 17,95% )
               128 page-faults               #    0,325 M/sec                    ( +-  0,01% )
           1109991 cycles                    #    2,826 GHz                      ( +-  0,27% )
   <not supported> stalled-cycles-frontend 
   <not supported> stalled-cycles-backend  
           1059855 instructions              #    0,95  insns per cycle          ( +-  0,02% )
            127127 branches                  #  323,615 M/sec                    ( +-  0,04% )
              5651 branch-misses             #    4,44% of all branches          ( +-  0,12% )

       0,000571406 seconds time elapsed                                          ( +-  1,31% )

max@studio:~/tmp/foo$ perfstat -S -r 1000 ./max > /dev/null 

 Performance counter stats for './max' (1000 runs):

          0,373758 task-clock                #    0,690 CPUs utilized            ( +-  1,04% )
                 0 context-switches          #    0,000 M/sec                    ( +- 18,18% )
                 0 CPU-migrations            #    0,000 M/sec                    ( +- 16,92% )
               131 page-faults               #    0,350 M/sec                    ( +-  0,01% )
           1108049 cycles                    #    2,965 GHz                      ( +-  0,31% )
   <not supported> stalled-cycles-frontend 
   <not supported> stalled-cycles-backend  
            885881 instructions              #    0,80  insns per cycle          ( +-  0,03% )
            182492 branches                  #  488,261 M/sec                    ( +-  0,03% )
              6305 branch-misses             #    3,46% of all branches          ( +-  0,10% )

       0,000541572 seconds time elapsed                                          ( +-  1,02% )

max@studio:~/tmp/foo$ perfstat -S -r 1000 ./MAW > /dev/null

 Performance counter stats for './MAW' (1000 runs):

          0,361012 task-clock                #    0,677 CPUs utilized            ( +-  0,76% )
                 0 context-switches          #    0,000 M/sec                    ( +- 14,87% )
                 0 CPU-migrations            #    0,000 M/sec                    ( +- 17,13% )
               131 page-faults               #    0,362 M/sec                    ( +-  0,01% )
           1116083 cycles                    #    3,092 GHz                      ( +-  0,35% )
   <not supported> stalled-cycles-frontend 
   <not supported> stalled-cycles-backend  
            887663 instructions              #    0,80  insns per cycle          ( +-  0,02% )
            175564 branches                  #  486,311 M/sec                    ( +-  0,03% )
              6279 branch-misses             #    3,58% of all branches          ( +-  0,11% )

       0,000533325 seconds time elapsed                                          ( +-  1,34% )

max@studio:~/tmp/foo$ 

EDIT:
vbextreme ha scritto: Ho eseguito un test rapido sulla velocità, riempiendo un vettore di 1024 valori ripetuti nel range da 0-255, in sostanza ho eseguito la funzione "isvoc" * 4 volte su tutti i valori ascii. solo con -O2
Ecco il risultato del tempo clompessivo che andrebbe diviso per 1024 per trovare il singolo tempo:
[...]
Presta attenzione alle ottimizzazioni del compilatore. Una semplice chiamata di una funzione che non fa niente viene tolta. Puoi controllare disassemblando il codice ;)
Avatar utente
vbextreme
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1214
Iscrizione: domenica 12 gennaio 2014, 14:06
Desktop: lxde
Distribuzione: xubuntu 14.10

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da vbextreme »

Noto differenze tra usare char, register int, register char... e non ottengo gli stessi tuoi output (ma solo tre o quattro valori oltre le vocali e solo con la versione vecchia), credo che con shift e assegnazioni (cast impliciti) usati in questo modo stiamo mettendo in crisi le diverse implementazioni/architetture.
Ho notato anche io quelle discrepanze, immaginavo anche che il codice di maw sul mio risc potesse non andare bene e mi piacerebbe avere una conferma da voi.
Dato però che l'errore della tua funzione ricade solo nei valori negativi di char quindi inutili alla funzione stessa, basta spostare l'if pocanzi ottenendo anche un microscopico miglioramento in efficenza:

Codice: Seleziona tutto

int isvoccla11 (register char c) {
    if (c & 128) return 0;
    if (c > 90) c ^= 32;
    c -= 65;
    register int ib = c >> 3;
    c %= 8;
    return (MAP[ib] >> (7 - c)) & 1;
}
Cosi funziona alla grande anche sul risc.
Premetto che le statistiche seguenti sono relative solo alle 3 migliori funzioni.
[polemica]
Migliori è un aggettivo che sta allo stesso livello di Bello."De gustibus non disputandum"
Sarebbe quindi opportuno spiegare la base della scelta del "migliore". sempre comunque opinabile.
Leggibilità? Uso Matematico? Prestazioni? Uso Memoria? Bho....
[/polemica]

Come da lunghi anni sentito da Maw, ma poi imparato d'esperienza, la misurazione temporale è solamente indicativa e presa singolarmente è priva di significato anche usando profiling accurati, che cambieranno su ogni chip in maniera anche sostanziale.
Può essere però un buon indice, ad esempio la mia funzione voc1 gira 3 volte piu lenta di tutte le altre funzioni e quindi è decisamente da scartare.
tutte le altre funzioni invece che hanno lo stesso tempo di esecuzione sono da considerarsi valide e vanno scelte secondo altri criteri, ad esempio quella di claudio usa un vettore che nessun' altra usa.
Per quello continuo a calcolare il tempo con una semplicissima funzione quale "gettimeofday" che in linea di massima ritorna lo stesso risultato dei vari profiling.Naturalmente tali tool sono d'obbligo per approfondire e migliorare il codice.

Ecco ad esempio il risultato di una elaborazione lunga sul codice senza dividere il tempo.

Codice: Seleziona tutto

vb1:1.286693811417
vb2:0.759266853333
maw:0.762727022171
ixa:0.752117872238
cl1:0.653047084808
cl2:1.031140089035
ed un profiling qualunque:

Codice: Seleziona tutto

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ns/call  ns/call  name    
 41.34      1.05     1.05                             main
 23.23      1.64     0.59  9000000    65.56    65.56  isvoc1
 16.93      2.07     0.43  9000000    47.78    47.78  isvoccla2
  5.91      2.22     0.15  9000000    16.67    16.67  isvocmaw
  5.12      2.35     0.13  9000000    14.44    14.44  isvocixa
  4.33      2.46     0.11  9000000    12.22    12.22  isvoc2
  3.15      2.54     0.08  9000000     8.89     8.89  isvoccla11
l'unica differenza è che il prof indica che la mia sia piu veloce di quella di ixa rispetto al precedente modello.L'errore in gioco su questa quantità di calcolo ripetitivo è enorme e quindi le considero alla pari.
Presta attenzione alle ottimizzazioni del compilatore. Una semplice chiamata di una funzione che non fa niente viene tolta. Puoi controllare disassemblando il codice
Non sapendo il RISC non ho potuto approfondire, tale controllo l'ho comunque fatto nel programma con printf specifiche su tutte le funzioni prima di calcolarne il tempo, la piccola differenza con il -O2 o -O3 non lascia poi intendere che nel ciclo non venga eseguito niente...
Easy framework per il linguaggio C.
vbextreme hack your life
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da Claudio_F »

vbextreme ha scritto: Ho notato anche io quelle discrepanze
Magari è per lo sforamento degli indici che in C passa silente :muro: Se ad esempio si entra con il carattere 32 ib vale -9. Il controllo sul bit 7 va fatto anche dopo la sottrazione:

Codice: Seleziona tutto

int isvoccla11 (register char c) {
    if (c & 128) return 0;
    c -= 65;
    if (c & 128) return 0;
    c &= 0xdf;
    register int ib = c >> 3;
    c %= 8;
    return (MAP[ib] >> (7 - c)) & 1;
}
:ciao:
Avatar utente
vbextreme
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1214
Iscrizione: domenica 12 gennaio 2014, 14:06
Desktop: lxde
Distribuzione: xubuntu 14.10

Re: [C] trovare 2° stringa con 2 consonanti in fila

Messaggio da vbextreme »

Dimenticavo una cosa importante, la lentezza che affligge i codici diversi da quello di claudio nasce dal fatto che tutti tranne claudio usano la tolower per sistemare il carattere.
Togliendo tale funziione e rimpiazzandola con uno semplice Or in Bitwise otteniamo gli stessi risultati temporali.
Ad esempio alla stregua dell'ottimizzazione la mia funzione(rinominata isvoc1) diventa veloce alla stregua di quella di cla.

Codice: Seleziona tutto

int isvoc1(register int c)
{
	c |= 0x20;
	return !((c ^ 0x61) && (c ^ 0x65) && (c ^ 0x69) && (c ^ 0x6F) && (c ^ 0x75));
}
con tempi di:

Codice: Seleziona tutto

vb1:0.624837160110
vb2:0.777431964874
maw:0.762954950333
ixa:0.741670131683
cl1:0.656954050064
cl2:1.022527933121
Naturalmente prima di eseguire i test sempre all'interno del programma viene eseguitio un loop che fa innalzare il clock della cpu in modo che la prima funzione non risenta il fatto di essere eseguita per prima.
Modificando quindi la posizione di esecuzione ottengo i medesimi risultati.
Easy framework per il linguaggio C.
vbextreme hack your life
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 13 ospiti