perché è set_intersection in STL è così lento?

Question

Sto intersecante un insieme di 100.000 numeri e un insieme di 1.000 numeri utilizzando set_intersection in STL e le sue 21s Prendere, dove prende 11ms in C #.

Codice C ++:

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.insert(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.insert(value);
    }

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}

C # Codice:

static int runIntersectionTest()
    {
        Random random = new Random(DateTime.Now.Millisecond);

        Dictionary<int,int> theMap = new Dictionary<int,int>();

        List<int> set1 = new List<int>();
        List<int> set2 = new List<int>();

            // Create 100,000 values for set1
            for ( int i = 0; i < 100000; i++ )
            {
                int value = 1000000000 + i;
                set1.Add(value);
            }

            // Create 1,000 values for set2
            for ( int i = 0; i < 1000; i++ )
            {
                int value = 1000000000 + (random.Next() % 200000 + 1);
                set2.Add(value);
            }

            // Now intersect the two sets by populating the map
        foreach( int value in set1 )
            {
                theMap[value] = 1;
            }

            int intersectionSize = 0;

        foreach ( int value in set2 )
        {
            int count;
            if ( theMap.TryGetValue(value, out count ) )
            {
                intersectionSize++;
                theMap[value] = 2;
            }
            }

            return intersectionSize;
    }
}

Answer 1

In questa antica 3GHz Pentium 4, ottengo 2734 millisecondi per l'intera funzione runIntersectionTestAlgo, in una build di debug con le ottimizzazioni disabilitate. Ho compilato con VS2008 SP1.

Se abilito ottimizzazioni, ottengo 93 millisecondi.

Ecco il mio codice:

#include <set>
#include <algorithm>

using namespace std;

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.insert(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.insert(value);
    }

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}

#include <windows.h>
#include <iostream>

int main(){
    DWORD start = GetTickCount();

    runIntersectionTestAlgo();

    DWORD span = GetTickCount() - start;

    std::cout << span << " milliseconds\n";
}

La disattivazione _SECURE_SCL fatto alcuna differenza per il build di rilascio, che ancora aleggiava intorno ai 100 ms.

GetTickCount non è l'ideale, ovviamente, ma dovrebbe essere sufficiente per distinguere i 21 secondi da meno di 100 millesimi di secondo.

Quindi ne deduco che c'è qualcosa di sbagliato con i vostri punti di riferimento.

Answer 2

Un paio di cose potrebbe rendere il vostro due esempi più comparabili.

In primo luogo, il vostro esempio in STL non è giusto, per una cosa che entrambi i gruppi devono essere in ordine crescente (in STL parlare un "ordinamento debole rigorosa").

In secondo luogo, la vostra utilizzando "set" che vengono implementati come alberi in STL, contro "elenchi", che sono liste collegate. inserimenti casuali in un insieme è più costoso di inserimento sull'estremità di un elenco.

Provare a usare una lista di int in esempio C ++ e anche ordinare l'elenco prima (altrimenti impostare inersection non funzionerà correttamente) e penso che vedrete i risultati più favorevoli.

Answer 3

ho eseguito il codice C ++ sulla mia macchina linux

$ time ./test

real    0m0.073s
user    0m0.060s
sys     0m0.003s

21s significa per me è stato compilato senza ottimizzazioni. Nel caso in cui si utilizzano MSVC assicurarsi di aver elencato  _SECURE_SCL=0 (vedi MSDN ) nella compilare definizioni. In caso contrario, tutte le operazioni di STL iteratori sono cane lento.

Answer 4

ho aggiornato il tuo esempio di utilizzare un codice timer che uso quando unit testing. Sulla mia macchina Ottengo i seguenti tempi (sulla base di -O3):

First loop 0.0040654
Second loop 4.8e-05
Intersection 0.000349
Intersection size: 50

In base a questo, se sto leggendo i miei decimali correttamente, ci vuole '4 ms' per inserire gli articoli nel primo set, 50 microsecondi per inserire gli articoli nel secondo set e un 1/3 di ms per eseguire l'incrocio.

Non sono in grado di eseguire il C # esempio sulla mia macchina, quindi non posso confrontare i tempi, ma non è sicuramente 21s come si posta.

Answer 5

Il vostro C # e C ++ lavoro codice diverso. Il codice C # usa trucchi magici di hashing per la velocità, il vostro codice C ++ usa trucchi degli alberi per la velocità. Una cosa che probabilmente accelerare le cose (ignorando il fatto che il test sembra essere rotto) potrebbe essere quella di utilizzare l'hashing, come segue:

1. Crea una hash_map di una delle due collezioni.
2. iterare su ogni elemento della seconda collezione. Se il `hash_map1 contiene quell'elemento, aggiungerlo al vostro risultato.