PhiL99 ha scritto:
A me risulta che p2 è compatibile
Probabilmente avrò estrapolato male la funzione fun_compatibilita_Phil99() dal tuo codice.
In ogni caso, visto che ora sembra andare, ho scritto un breve codice per confrontare i tuoi algoritmi di confronto e compatibilità con quelli da me implementati:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
void fun_confronto_Phil99(char word[], char ref[], char res[])
{
int count;
int count1;
int exist;
int reps;
int rpos;
int wpos;
int length;
length = strlen(word);
for(count = 0; count < length; ++count)
{
if(word[count] == ref[count])
{
res[count] = '+';
}
else
{
reps = 0;
rpos = 0;
wpos = 0;
exist = -1;
for(count1 = 0; count1 < length; ++count1)
{
if(word[count] == ref[count1])
{
exist = 1;
++reps;
if(word[count1] == ref[count1])
{
++rpos;
}
}
else if((count1 < count) && (word[count1] == word[count]))
{
++wpos;
}
}
if((exist == -1) || (wpos >= (reps - rpos)))
{
res[count] = '/';
}
else
{
res[count] = '|';
}
}
}
res[length] = '\0';
}
int fun_compatibilita_Phil99(char cmp[], char word[], char word2[])
{
int wpos;
int rpos;
int reps;
int count;
int count1;
int length;
length = strlen(word2);
for(count = 0; count < length; ++count)
{
if(cmp[count] == '+')
{
if(word2[count] != word[count])
{
return 0;
}
}
else if(cmp[count] == '|')
{
if(word2[count] == word[count])
{
return 0;
}
wpos = 0;
rpos = 0;
reps = 0;
for(count1 = 0; count1 < length; ++count1)
{
if(word[count] == word[count1])
{
if(cmp[count1] == '|')
{
++wpos;
}
else if(cmp[count1] == '+')
{
++rpos;
}
}
if(word2[count1] == word[count])
{
++reps;
}
}
if(reps < (wpos + rpos))
{
return 0;
}
}
else
{
if(word2[count] == word[count])
{
return 0;
}
wpos = 0;
rpos = 0;
reps = 0;
for(count1 = 0; count1 < length; ++count1)
{
if(word[count] == word[count1])
{
if(cmp[count1] == '|')
{
++wpos;
}
else if(cmp[count1] == '+')
{
++rpos;
}
}
if(word[count] == word2[count1])
{
++reps;
}
}
if((wpos + rpos) != reps)
{
return 0;
}
}
}
return 1;
}
void fun_confronto_Nippolo(char *r, char *p, char *res, uint8_t *SI, uint8_t *NO, uint8_t *u, unsigned int *m)
{
memset(SI, *m = 0, sizeof(*SI) * 256);
memset(NO, 0, sizeof(*NO) * 256);
uint8_t v[256] = {0};
for(unsigned int i = 0; r[i]; ++i)
{
if(p[i] == r[i])
{
res[i] = '+';
}
else
{
res[i] = '/';
++v[r[i]];
}
}
for(unsigned int i = 0; r[i]; ++i)
{
if(res[i] == '/')
{
if(v[p[i]])
{
res[i] = '|';
--v[p[i]];
if(!SI[p[i]]++)
{
u[(*m)++] = p[i];
}
}
else
{
++NO[p[i]];
}
}
}
}
int fun_compatibilita_Nippolo(char *p2, char *p, char *res, uint8_t *SI, uint8_t *NO, uint8_t *u, unsigned int m)
{
uint8_t v[256] = {0};
unsigned int i;
for(i = 0; p[i] && (res[i] == '+' ? p2[i] == p[i] : p2[i] != p[i] && ++v[p2[i]] && (!NO[p2[i]] || SI[p2[i]] - v[p2[i]] >= 0)); ++i);
for(i = !p[i] ? 0 : m + 1; i < m && v[u[i]] - SI[u[i]] >= 0; ++i);
return(i == m);
}
int main()
{
char *r = "D9k834k249ka9e_";
char *p = "48k9kkk9-saa9Da";
char *p2 = "A9k8Dtk_499a94k";
unsigned int len = strlen(r);
char *res = (char*)malloc(sizeof(char) * (len + 1));
unsigned int a = 10000000;
{//Phil99
fun_confronto_Phil99(p, r, res);
printf("Phil99\n\nr: %s\np: %s\nres: %s\np2: %s\n\nCOMPATIBILITA': %d\n", r, p, res, p2, fun_compatibilita_Phil99(res, p, p2));
clock_t begin = clock();
for(unsigned int i = 0; i < a; ++i)
{
fun_confronto_Phil99(p, r, res);
fun_compatibilita_Phil99(res, p, p2);
}
clock_t end = clock();
printf("\nTEMPO IMPIEGATO PER %u CONFRONTI+COMPATIBILITA': %lfs\n", a, (double)(end - begin) / CLOCKS_PER_SEC);
}
printf("\n--------------------------------------------------------------------\n\n");
{//Nippolo
uint8_t SI[256];
uint8_t NO[256];
uint8_t u[256];
unsigned int m;
res[len] = '\0';
fun_confronto_Nippolo(r, p, res, SI, NO, u, &m);
printf("Nippolo\n\nr: %s\np: %s\nres: %s\np2: %s\n\nCOMPATIBILITA': %d\n", r, p, res, p2, fun_compatibilita_Nippolo(p2, p, res, SI, NO, u, m));
clock_t begin = clock();
for(unsigned int i = 0; i < a; ++i)
{
fun_confronto_Nippolo(r, p, res, SI, NO, u, &m);
fun_compatibilita_Nippolo(p2, p, res, SI, NO, u, m);
}
clock_t end = clock();
printf("\nTEMPO IMPIEGATO PER %u CONFRONTI+COMPATIBILITA': %lfs\n", a, (double)(end - begin) / CLOCKS_PER_SEC);
}
return 0;
}
Questo l'output risultante:
Phil99
r: D9k834k249ka9e_
p: 48k9kkk9-saa9Da
res: ||+||/+|///++|/
p2: A9k8Dtk_499a94k
COMPATIBILITA': 1
TEMPO IMPIEGATO PER 10000000 CONFRONTI+COMPATIBILITA': 6.749000s
--------------------------------------------------------------------
Nippolo
r: D9k834k249ka9e_
p: 48k9kkk9-saa9Da
res: ||+||/+|///++|/
p2: A9k8Dtk_499a94k
COMPATIBILITA': 1
TEMPO IMPIEGATO PER 10000000 CONFRONTI+COMPATIBILITA': 1.921000s
Process returned 0 (0x0) execution time : 8.825 s
Press any key to continue.
Visto che ti interessava la questione dell'efficienza, le funzioni da me scritte (che sembrano funzionare, ma se trovi qualche bug fammi sapere) oltre ad essere più compatte, sembrano essere quasi 4 volte più veloci.
Secondo voi si potrebbe fare ancora di meglio?
Se hai qualche dubbio chiedi pure.
P.S.
Ovviamente dai un'occhiata alla funzione fun_compatibilita_Phil99() e vedi se l'ho riportata correttamente.