# Speculative execution

**URL:** <https://forum.olinfo.it/t/speculative-execution/5053>\
**Category:** Aiuto\
**Created:** [12 Marzo 2018, 2:05pm UTC](https://forum.olinfo.it/t/speculative-execution/5053 "2018-03-12T14:05:34Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![ahmed1](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/6f9a4e/32.png) [@ahmed1](https://forum.olinfo.it/u/ahmed1)\
**Post date:** [12 Marzo 2018, 2:05pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/1 "2018-03-12T14:05:34Z")

</div>

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:

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [12 Marzo 2018, 2:29pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/2 "2018-03-12T14:29:14Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [12 Marzo 2018, 3:45pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/3 "2018-03-12T15:45:37Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\
**Post date:** [12 Marzo 2018, 4:06pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/4 "2018-03-12T16:06:48Z")

</div>

cos’è e a cosa serve un BBST?

---

<div class="post-metadata">

**Author:** ![marco.rocchi](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/f14d63/32.png) [@marco.rocchi](https://forum.olinfo.it/u/marco.rocchi)\
**Post date:** [12 Marzo 2018, 4:12pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/5 "2018-03-12T16:12:30Z")

</div>

> **[Albero AVL](https://it.wikipedia.org/wiki/Albero_AVL)**
>
> L'albero AVL è, in informatica, un albero binario di ricerca bilanciato in cui il coefficiente di bilanciamento per ciascun nodo vale 1, 0 oppure -1 (nel caso di un albero AVL completo tutti i coefficienti di bilanciamento sono uguali a 0).
> Il nome AVL viene dai suoi inventori Adelson-Velskij e Landis, che pubblicarono il loro algoritmo nel saggio in russo "Odin algoritm organizacii informacii" ("un algoritmo di organizzazione dell'informazione") del 1962.
> Viene definito il coefficiente di bila...

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

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [12 Marzo 2018, 4:13pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/6 "2018-03-12T16:13:18Z")

</div>

Un self- **B** alancing **B** inary **S** earch **T** ree, 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).

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [12 Marzo 2018, 4:22pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/7 "2018-03-12T16:22:23Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\
**Post date:** [12 Marzo 2018, 5:22pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/8 "2018-03-12T17:22:40Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [12 Marzo 2018, 5:41pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/9 "2018-03-12T17:41:26Z")

</div>

Di fatto in tutti gli esercizi che richiedono inserimento/eliminazione/ricerca di un elemento in tempo logaritmico, alcuni esercizi sono [duplicato](https://training.olinfo.it/#/task/ois_duplicato/statement) , [saddest friend](https://training.olinfo.it/#/task/ois_maxim/statement) , [wheel](https://training.olinfo.it/#/task/ois_wheel/statement) , [filiali](https://training.olinfo.it/#/task/ois_filiali/statement) , [dominion](https://training.olinfo.it/#/task/ois_dominion/statement). 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.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [12 Marzo 2018, 5:42pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/10 "2018-03-12T17:42:22Z")

</div>

> [@bortoz](#):
>
> in generale risulta più efficiente un hash set.

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

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [12 Marzo 2018, 5:53pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/11 "2018-03-12T17:53:32Z")

</div>

È 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`.

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [12 Marzo 2018, 6:04pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/12 "2018-03-12T18:04:25Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [12 Marzo 2018, 7:06pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/13 "2018-03-12T19:06:03Z")

</div>

> [@bortoz](#):
>
> Vorrei precisare che l’inserimento in un BBST ha complessità O(logN) se gli elementi che compongono il BBST si possono confrontare in Θ(1). Nel caso delle stringhe il confronto ha complessità O(|S|) e, sebbene in questo task la lunghezza do ogni stringa sia inferiore a 10, in generale risulta più efficiente un hash set.

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](http://codeforces.com/) 🙂

---

<div class="post-metadata">

**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\
**Post date:** [12 Marzo 2018, 7:43pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/14 "2018-03-12T19:43:02Z")

</div>

grazie mille a tutti

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [13 Marzo 2018, 5:51pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/15 "2018-03-13T17:51:32Z")

</div>

> [@filippos](#):
>
> gli inserimenti hanno comunque un costo medio di O(|S|) in quanto vengono comunque create copie delle stringhe che vengono inserite

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.

> [@filippos](#):
>
> 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”

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

```auto
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);

```

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [13 Marzo 2018, 6:40pm UTC](https://forum.olinfo.it/t/speculative-execution/5053/16 "2018-03-13T18:40:30Z")

</div>

> [@bortoz](#):
>
> 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\> è O(|S|logN)\mathcal O(|S|\log N) che nel caso peggiore dove tutte le stringhe possiedono lo stesso prefisso può diventare molto lento.

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 🙂

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