Ricerca binaria su stringhe

YmirYmir Posts: 183
edited July 2015 in Algoritmica e laboratorio
La mia soluzione per questo esercizio è troppo lenta. Consigli per renderla più efficiente?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N (1000)

int RicBinString(char **a,char *s, int sx,int dx){
if(sx>dx) return -1;
int cx=(sx+dx)/2;
int cmp=strcmp(s,a[cx]);
if(cmp==0) return cx;
if(cmp>0) return RicBinString(a,s,cx+1,dx);
if(cmp<0) return RicBinString(a,s,sx,cx-1);
}

int main(){
int i, x, len, arr[N], dim; char **a, s[101];

scanf("%d",&len);
a = (char**) malloc(len*sizeof(char**));
for(i=0;i<len;i++) {a[i]=(char*)malloc(N*sizeof(char*));
                    scanf("%s", a[i]);}

i=0;dim=0;
scanf("%d", &x); 
while(x!=0){scanf("%s", s);
            arr [ i ] =RicBinString(a,s,0,len);
            i++;dim++;
            scanf("%d",&x);
           }

for(i=0;i<dim;i++) printf("%d\n", arr[i]);
for(i=0;i<len;i++)free(a[i]);
free(a);
return 0;
}

Comments

  • MindFlyerMindFlyer Posts: 436
    edited July 2015
    Puoi fare un po' di preprocessing e disordinare l'array come spiegato qui.

    Scherzi a parte, non so cosa ci sia di fondamentalmente brutto nella strcmp... Ma se un collo di bottiglia c'è, è sicuramente quello. Per cominciare invocherei RicBinString con parametro len-1 anziché len. O non vorrai segfaultarti anche l'anima quando, presa dal sonno per l'attesa eterna di queste ricerche binarie, deciderai di cercare la stringa "zzzzzzzz".

    Al posto di questa ricerca binaria naive puoi provare altre cose. Una che mi viene in mente è questa:
    diciamo che la stringa che vuoi cercare è "frenulo". Allora cerchi prima il segmento esatto delle parole che cominciano con "f". Per fare questo devi trovare un indice j tale che a[j] cominci per "f", e a[j-1] cominci per un'altra lettera (oppure j=sx). Questo j lo trovi con la ricerca binaria. Dopodiché ripeti la ricerca tra j+1 e dx, trovando un indice j' tale che a[j'] cominci per "f" e a[j'+1] cominci per un'altra lettera (oppure j'=dx). Fatto questo, ripeti il tutto chiamando la stessa funzione con sx:=j e dx:=j', e dicendole di cercare la lettera "r" come secondo carattere, e così via. Non sarà facilissimo da implementare, ma asintoticamente dovrebbe andare leggermente meglio di un brutale strcmp.

    Alternativamente, se le stringhe dell'array di input sono ben distribuite, puoi "educare" la ricerca binaria: per esempio, se la prima lettera della parola che cerchi è "f", invece di cercarla bovinamente all'indice (sx+dx)/2, la puoi cercare per prima cosa tipo in (sx*6+dx*20)/26. Questo supponendo che le stringhe contengano solo lettere minuscole. Se contengono anche lettere maiuscole e/o numeri, fai la stessa cosa, mutatis mutandis (perché l'igiene intima è comunque una cosa importante). Se al primo tentativo non trovi "f", ma trovi per esempio "q", allora al secondo tentativo cercherai tipo in (sx*6+dx*11)/17, e via di questo passo.

    Oppure puoi andare direttamente di tabella hash, che forse alla fine è la cosa migliore in questi casi (anche se vanifica lo scopo di avere l'array già ordinato). La verità è che l'approccio ottimale dipende molto dall'input che hai. Se non sai niente di niente né sull'array di input né sulle query, un metodo vale l'altro, più o meno...
  • MindFlyerMindFlyer Posts: 436
    edited July 2015
    L'ho ripulito di varie brutture, e adesso rientra nei tempi. Non so esattamente cosa fosse a rallentarlo, ma tant'è.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int RicBinString(const char **a,const char *s, int sx,int dx){
    if(sx>dx) return -1;
    int cx=(sx+dx)/2;
    int cmp=strcmp(s,a[cx]);
    if(cmp==0) return cx;
    if(cmp>0) return RicBinString(a,s,cx+1,dx);
    if(cmp<0) return RicBinString(a,s,sx,cx-1);
    }
    
    int main(){
    int i, x, len;
    char **a;
    char s[100];
    
    scanf("%d",&len);
    a = (char**) malloc(len*sizeof(char*));
    for(i=0;i<len;i++) {a[i]=(char*)malloc(100*sizeof(char));
                        scanf("%s",a[i]);}
    
    scanf("%d",&x); 
    while(x!=0){scanf("%s",s);
    		printf("%d\n", RicBinString(a,s,0,len-1));
                    scanf("%d",&x);
               }
    for(i=0;i<len;i++)free(a[i]);
    free(a);
    return 0;
    }
    
  • MindFlyerMindFlyer Posts: 436
    edited July 2015
    Ho capito dov'era il problema di performance: era quel malloc con un esagerato N*sizeof(char*), dove N è addirittura 1000. E' bastato guardare gli input per rendermene conto: l'array di input è gigantesco in confronto al numero di query (le quali prendono tempo log n ciascuna), e quindi il grosso del lavoro lo fa la malloc. E se la malloc deve allocare un'enormità inutile di memoria, spreca un fottio di tempo.

    Certo che, per dare un esercizio di ottimizzazione dove non è l'algoritmo centrale a dover essere ottimizzato, ma è LA LETTURA DELL'INPUT, bisogna essere dei genialoidi totali. Anche questo caso lo archiviamo tra gli x-files dei fail informatici.
Sign In or Register to comment.