Operazioni su vettori di stringhe con un numero elevato di elementi

di
stefanoferrario
il
5 risposte
S
stefanoferrario
Pochi posts
Iscritto da
dic, 2015
Messaggi:
26

Operazioni su vettori di stringhe con un numero elevato di elementi

Ciao,

devo eseguire alcune operazioni su un vettore di stringhe caratterizzato da un elevato numero di elementi (giusto per farsi un'idea... gli elementi sono 108505100).
In pratica devo verificare che le stringhe contenute nel momento in cui riscontrano la presenza di un carattere 'h' verifichino che il successivo sia o il carattere alfabetico esattamente dopo 'h' secondo la tabella ASCI oppure uno qualsiasi prima di 'h'. A questo punto il carattere successivo dovrà essere quello successivo ad 'h'+1 secondo la tabella ASCI oppure uno qualsiasi prima di 'h'.
Qualora tale condizione venga a meno la stringa viene eliminata dal vettore.

Io ho pensato al seguente codice (dove allComb è il vettore di stringhe passato come puntatore) ma impiega davvero un'infinità di tempo... 

char temp_char;
    bool check_valid;
    for (int i=0; i<allComb->size(); i++){
        check_valid=false;
        for (int k=0; k<allComb->at(i).size(); k++){
            if (check_valid){
                if (allComb->at(i)[k]>='h'){
                    if (allComb->at(i)[k]==temp_char+1){
                        temp_char++;
                    } else {
                        allComb->erase(allComb->begin()+i);
                        break;
                    }
                }
                if (allComb->at(i)[k]<'h'){
                    temp_char++;
                }
            }
            if (!check_valid){
                if (allComb->at(i)[k]>='h'){
                    temp_char=allComb->at(i)[k];
                    check_valid=true;
                }
            }
        }
    }

5 Risposte

  • +
    +m2+
    Utente Famoso
    Iscritto da
    mag, 2017
    Messaggi:
    3548

    Re: Operazioni su vettori di stringhe con un numero elevato di elementi

    Togli erase dal ciclo e fallo fuori
  • S
    stefanoferrario
    Pochi posts
    Iscritto da
    dic, 2015
    Messaggi:
    26

    Re: Operazioni su vettori di stringhe con un numero elevato di elementi

    Ho estratto eresse dal ciclo in questo modo 
    char temp_char;
    bool check_valid;
    bool erease=false;
    for (int i=0; i<allComb->size(); i++){
        check_valid=false;
        for (int k=0; k<allComb->at(i).size(); k++){
            if (check_valid){
                if (allComb->at(i)[k]>='h'){
                    if (allComb->at(i)[k]==temp_char+1){
                        temp_char++;
                    } else {
                        erease=true;
                        break;
                    }
                }
                if (allComb->at(i)[k]<'h'){
                    temp_char++;
                }
            }
            if (!check_valid){
                if (allComb->at(i)[k]>='h'){
                    temp_char=allComb->at(i)[k];
                    check_valid=true;
                }
            }
        }
        if (erease){
            allComb->erase(allComb->begin()+i);
            erease=false;
        }
    }
    ma il problema persiste
  • +
    +m2+
    Utente Famoso
    Iscritto da
    mag, 2017
    Messaggi:
    3548

    Re: Operazioni su vettori di stringhe con un numero elevato di elementi

    Qual'è esattamente il problema?
    Per cominciare togli erase del tutto, non ti serve (in questa fase)
    Poi la complessità è data dal prodotto, quindi dipende quanto è grande.
    Infine puoi togliere la "croppa" C++ a favore di quella C (cioè accedendo alla stringa come array di caratteri)
  • S
    stefanoferrario
    Pochi posts
    Iscritto da
    dic, 2015
    Messaggi:
    26

    Re: Operazioni su vettori di stringhe con un numero elevato di elementi

    Il problema è la lentezza nell'esecuzione... ho un vettore di 108505100

    Ma se tolgo l'erease come faccio poi a cancellare la stringa che non supera il controllo?
  • +
    +m2+
    Utente Famoso
    Iscritto da
    mag, 2017
    Messaggi:
    3548

    Re: Operazioni su vettori di stringhe con un numero elevato di elementi

    stefanoferrario ha scritto:

    Il problema è la lentezza nell'esecuzione... ho un vettore di 108505100

    Ma se tolgo l'erease come faccio poi a cancellare la stringa che non supera il controllo?
    Cosa è per te "lentezza di esecuzione"?
    E quanto sono lunghe, le stringhe?

    ---
    L'erase toglilo del tutto, e fai tutti i test senza di esso.
    Per l'eliminazione ti farai un vettore a parte dove memorizzerai l'elenco delle stringhe da cancellare.
    Solo dopo la fase di elaborazione le cancellerai, tutte in un colpo solo.

    Ma devi capire se
    - semplicemente i dati sono così tanti da elaborare che non c'è molto da fare (a parte un programma multithread)
    - è lenta la fase di accesso ai singoli caratteri
    - è lenta la cancellazione

    In sostanza devi "smontare" il tuo programma per esaminarne i singoli "pezzi".
    Dal momento che utilizzi oggetti non fatti da te, di cui quindi non sai nulla, conviene operare partizionando il dominio.

    O, se preferisci, "fanculizzando" le stringhe C++ (cosa in generale buona e giusta, nel tuo caso)
    ---
    Chiaramente, essendo in una situazione ideale, puoi partizionare (più precisamente shardare orizzontalmente) e fare tanti thread quanti core hai, per elaborazione parallela.
    Ma è il passo successivo
Devi accedere o registrarti per scrivere nel forum
5 risposte