Speculative execution

Aiuto
1

Ho fatto un programma per risolvere “speculative execution” ma ottengo 50/100 perché supero il tempo di esecuzione.
Mi consigliate un modo per ottimizzare il programma.
Il mio programma è il seguente:

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int main()
{

    ifstream in("input.txt");
    ofstream out("output.txt");
    int N, immediate = 0;
    bool opUsed = false;
    string tar, v1, v2;
    in >> N;
    string var[N];


    for(int n = 0; n < N; n ++)
    {
        in >> tar >> v1 >> v1 >> v2 >> v2;
        var[n] = tar;

        for(int i = 0; i < n; i ++)
            if(v1 == var[i] || v2 == var[i]){
                opUsed = true;
                break;
            }

        if(opUsed == false)
            immediate++;
        else
            opUsed = false;

    }
    out << immediate;
    return 0;
}
2

Devi trovare un modo più veloce per sapere se una stringa è già stata presa in input, un BBST è l’ideale.
Potresti usare un multiset < string > se vuoi evitarti l’implementazione.

1 Mi Piace
3

Vorrei precisare che l’inserimento in un BBST ha complessità \mathcal O(\log N) se gli elementi che compongono il BBST si possono confrontare in \Theta(1). Nel caso delle stringhe il confronto ha complessità \mathcal O(|S|) e, sebbene in questo task la lunghezza do ogni stringa sia inferiore a 10, in generale risulta più efficiente un hash set.
Inoltre non ho capito perché usi un std::multiset quando basterebbe un std::set che ha fattori costanti leggermente più piccoli.

2 Mi Piace
4

cos’è e a cosa serve un BBST?

5

Questo è il tipo di implementazione più conosciuta (e anche più semplice)

6

Un self-Balancing Binary Search Tree, ovvero un albero di ricerca dove l’altezza viene limitata a \mathcal O(\log N) in modo da eseguire inserimento, estrazione e ricerca in \mathcal O(\log N).

2 Mi Piace
7

Ho parlato del std::multiset anche se effettivamente non ha nessun guadagno, anche se non si notano quasi nemmeno le differenze con il std::set per quanto riguarda i tempi.

1 Mi Piace
8

grazie a tutti, su quali esercizi sul cms si può applicare?

9

Di fatto in tutti gli esercizi che richiedono inserimento/eliminazione/ricerca di un elemento in tempo logaritmico, alcuni esercizi sono duplicato , saddest friend , wheel , filiali , dominion. Sono due strutture molto efficienti ma in alcuni casi ci sono strutture/algoritmi più specifiche/i.
Quello che sarebbe anche utile fare è scrivere una proprio implementazione dell’albero in modo da poterlo costruire in base alle proprio esigenze.

1 Mi Piace
10

Chiedo venia me la mia ignoranza, ma di cosa si tratta?

1 Mi Piace
11

È una struttura dati che implementa le stesse operazioni di un BBST, utilizzando però l’hashing, nel C++ è implementato sotto il nome di std::unordered_set.

2 Mi Piace
12

Grazie , l’ho già sentito , dopo vado ad informarmi meglio sulla sua utilità.:grinning:

1 Mi Piace
13

Se con hash set intendi un unordered_set, allora gli inserimenti hanno comunque un costo medio di O(|S|) in quanto vengono comunque create copie delle stringhe che vengono inserite.
Se invece calcoliamo gli hash come interi, è un altro discorso ma la nostra soluzione non sarà più deterministica.

Per quanto riguarda il caso pessimo, gli unordered_set/map l’inserimento ha un costo di O(N) e nulla vieta all’autore di un problema di introdurre dei testcase “anti-hashing” in grado di penalizzare le soluzioni di questo tipo, cosa che qui penso non si sia mai verificata ma che si verifica abitualmente in altri siti come ad esempio codeforces :slight_smile:

1 Mi Piace
14

grazie mille a tutti

15

Le copie (eccetto se usi std::move) vengono create anche in un std::set normale, quello a cui mi riferivo io è che la complessità dell’inserimento in un std::set<std::string> è \mathcal O(|S|\log N) che nel caso peggiore dove tutte le stringhe possiedono lo stesso prefisso può diventare molto lento.

Un’alternativa è giocare un po’ con reserve e max_load_factor o ancora meglio cambiare la funzione di hash, propongo un esempio:

auto my_hash=[](const std::string& str)
{
    typedef unsigned long long ull;
    ull res=0, e=(ull)1e12+39, mod=(ull)1e18+3;
    for(size_t i=0, j=str.size()-1; i<j; i++, j--)
        res = ((res<<15)+(res<<31)+e*str[i]*str[j])%mod;
    return res;
};
std::unordered_set<std::string,decltype(my_hash)> my_set(N,my_hash);
my_set.max_load_factor(0.5);
2 Mi Piace
16

Sì avevo capito ti riferissi anche a quello, però comunque anche nel caso dell’unordered_set vengono confrontate tutte le stringhe all’interno del “bucket” corrispondente e nel caso in cui questo sia grande (molte collisioni, che sicuramente un hash “ad-hoc” può diminuire ma senza avere mai quella certezza matematica) e le stringhe abbiano lunghi prefissi in comune quel comportamento si potrebbe verificare lo stesso.

Per un set di stringhe, l’approccio asintoticamente migliore si dovrebbe ottenere con un trie :slight_smile:

Comunque in questo caso log2(27^{10}) = 47.549 < 48, un unordered_set<long long> potrebbe essere un’altra valida alternativa :smile:

1 Mi Piace