почему set_intersection в STL такой медленный? - PullRequest
Новая
       20

почему set_intersection в STL такой медленный?

1 голос
/ 29 июня 2009

Я пересекаю набор из 100 000 номеров и набор из 1000 номеров, используя set_intersection в STL и его получение 21 с, где это занимает 11 мс в C #.

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 # код: 

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;
    }
}

Ответы [ 5 ]

8 голосов
/ 29 июня 2009

Пара вещей сделает ваши два примера более сопоставимыми.

Во-первых, ваш пример в STL не совсем верный, во-первых, оба набора должны быть отсортированы в порядке возрастания (в STL говорят «строго слабый порядок»).

Во-вторых, вы используете «наборы», которые реализованы как деревья в STL, а не «списки», которые являются связанными списками. Случайные вставки в набор дороже, чем вставка в конец списка.

Попробуйте использовать список целых чисел в примере C ++, а также сначала отсортируйте список (иначе установка инсерции не будет работать должным образом), и я думаю, вы увидите более благоприятные результаты.

5 голосов
/ 29 июня 2009

Я запустил ваш код C ++ на моей Linux-машине 

$ time ./test

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

21s означает для меня, что вы скомпилировали без оптимизации. Если вы используете MSVC, убедитесь, что вы перечислили _SECURE_SCL=0 (см. msdn ) в определениях компиляции. В противном случае все операции итератора STL будут медленными.

2 голосов
/ 29 июня 2009

На этом старом 3GHz Pentium 4 я получаю 2734 миллисекунды для всей функции runIntersectionTestAlgo в отладочной сборке с отключенной оптимизацией. Я скомпилировал с VS2008 SP1.

Если я включаю оптимизацию, я получаю 93 миллисекунды.

Вот мой код: 

#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";
}

Отключение _SECURE_SCL не имело значения для сборки выпуска, которая все еще зависала около 100 мс.

GetTickCount, конечно, не идеал, но он должен быть достаточно хорош, чтобы отличить 21 секунду от менее 100 миллисекунд.

Итак, я заключаю, что с вашими тестами что-то не так.

1 голос
/ 29 июня 2009

Я обновил ваш пример, чтобы использовать некоторый код таймера, который я использую при модульном тестировании. На моей машине я получаю следующие значения времени (на основе -O3): 

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

Исходя из этого, если я правильно читаю свои десятичные дроби, для вставки элементов в первый набор требуется 4 мс, для вставки элементов во второй набор - 50 мкс, а для выполнения - 1/3 мсек. пересечение.

Я не могу запустить ваш пример C # на своей машине, поэтому я не могу сравнить время, но это точно не 21сек, как вы публикуете.

0 голосов
/ 29 июня 2009

Ваш код на C # и C ++ работает по-разному. Код C # использует магические трюки для скорости, ваш код C ++ использует трюки для скорости. Одна вещь, которая, вероятно, ускорит процесс (игнорируя тот факт, что ваше тестирование, похоже, не работает), это использование хеширования, как показано ниже:

  1. Создайте hash_map из одной из двух коллекций.
  2. Итерация по каждому элементу во 2-й коллекции. Если `hash_map1 содержит этот элемент, добавьте его в свой результат.
...