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

Question

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

Код на 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;
    }
}

Answer 1

На этом древнем Pentium 4 с частотой 3 ГГц я получаю 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 миллисекунд.

Итак, я прихожу к выводу, что с вашими бенчмарками что-то не так.

Answer 2

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

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

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

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

Answer 3

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

$ time ./test

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

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

Answer 4

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

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

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

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

Answer 5

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

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