Вопрос по performance, intersection, stl, c++ – Быстрое пересечение множеств: C ++ против C #

8

На моей машине (Quad Core, 8 ГБ оперативной памяти) под управлением Vista x64 Business с Visual Studio 2008 SP1 я пытаюсь очень быстро пересечь два набора чисел.

Я реализовал два подхода в C ++ и один в C #. Подход C # до сих пор быстрее, я хотел бы улучшить подход C ++, чтобы он был быстрее C #, что, я ожидаю, может сделать C ++.

Вот вывод C #: (Выпуск сборки)

Found the intersection 1000 times, in 4741.407 ms

Вот исходный вывод C ++ для двух разных подходов (сборка выпуска x64):

Found the intersection (using unordered_map) 1000 times, in 21580.7ms
Found the intersection (using set_intersection) 1000 times, in 22366.6ms

Вот последний вывод C ++ для трех подходов (сборка выпуска x64):

Последний бенчмарк:

Found the intersection of 504 values (using unordered_map) 1000 times, in 28827.6ms
Found the intersection of 495 values (using set_intersection) 1000 times, in 9817.69ms
Found the intersection of 504 values (using unordered_set) 1000 times, in 24769.1ms

Таким образом, подход set_intersection теперь примерно в 2 раза медленнее, чем C #, но в 2 раза быстрее, чем исходный подход C ++.

Последний код C ++:

Code:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>
#include <unordered_set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;
using namespace tr1;


int runIntersectionTest2(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_set<int> theSet;      

     theSet.insert( set1.begin(), set1.end() );

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        if ( theSet.find(*iterator) != theSet.end() )
        {
                intersectionSize++;
        }
    }

    return intersectionSize;
}

int runIntersectionTest(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;  

    vector<int>::const_iterator set1_end = set1.end();

    // Now intersect the two sets by populating the map
    for ( vector<int>::const_iterator iterator = set1.begin(); iterator != set1_end; ++iterator )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(const vector<int>& set1_unsorted, const vector<int>& set2_unsorted)
{   
    // Create two vectors
    std::vector<int> set1(set1_unsorted.size());
    std::vector<int> set2(set2_unsorted.size());

    // Copy the unsorted data into them
    std::copy(set1_unsorted.begin(), set1_unsorted.end(), set1.begin());
    std::copy(set2_unsorted.begin(), set2_unsorted.end(), set2.begin());

    // Sort the data
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    vector<int> intersection;
    intersection.reserve(1000);

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

    return intersection.size(); 
}

void createSets( vector<int>& set1, vector<int>& set2 )
{
    srand ( time(NULL) );

    set1.reserve(100000);
    set2.reserve(1000);

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

    // Try to get half of our values intersecting
    float ratio = 200000.0f / RAND_MAX;


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

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

    // Make sure set1 is in random order (not sorted)
    random_shuffle(set1.begin(),set1.end());
}

int _tmain(int argc, _TCHAR* argv[])
{
    int intersectionSize = 0;

    vector<int> set1, set2; 
    createSets( set1, set2 );

    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest2(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_set) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}

Код C #:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DictionaryPerformance
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> set1 = new List<int>(100000);
            List<int> set2 = new List<int>(1000);

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

            Random random = new Random(DateTime.Now.Millisecond);

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

            long start = System.Diagnostics.Stopwatch.GetTimestamp();
            for (int i = 0; i < 1000; i++)
            {
                runIntersectionTest(set1,set2);
            }
            long duration = System.Diagnostics.Stopwatch.GetTimestamp() - start;

            Console.WriteLine(String.Format("Found the intersection 1000 times, in {0} ms", ((float) duration * 1000.0f) / System.Diagnostics.Stopwatch.Frequency));

            Console.ReadKey();
        }

        static int runIntersectionTest(List<int> set1, List<int> set2)
        {

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

            // 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 ) )
                {
                    theMap[value] = 2;
                    intersectionSize++;
                }
            }

            return intersectionSize;
        }
    }
}

Код C ++:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;

int runIntersectionTest(vector<int> set1, vector<int> set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;

    // Now intersect the two sets by populating the map
    for ( vector<int>::iterator iterator = set1.begin(); iterator != set1.end(); iterator++ )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    for ( vector<int>::iterator iterator = set2.begin(); iterator != set2.end(); iterator++ )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(set<int> set1, set<int> set2)
{   
    set<int> intersection;

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

    return intersection.size(); 
}



int _tmain(int argc, _TCHAR* argv[])
{
    srand ( time(NULL) );

    vector<int> set1;
    vector<int> set2;

    set1.reserve(10000);
    set2.reserve(1000);

    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.push_back(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.push_back(value);
    }


    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    set<int> set21;
    set<int> set22;

    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set21.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;
        set22.insert(value);
    }

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        runSetIntersection(set21,set22);
    }
    timer.Stop();

    cout << "Found the intersection (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}

Хорошо, вот последний, с некоторыми изменениями:

The C++ sets are now properly setup so they have a 50% intersection (like the C#) Set1 is shuffled so its not sorted, set2 was already not sorted The set_intersection implementation now uses vectors, and sorts them first

C ++ (Выпуск, x64) Результаты:

Found the intersection of 503 values (using unordered_map) 1000 times, in 35131.1ms
Found the intersection of 494 values (using set_intersection) 1000 times, in 10317ms

Так что в 2 раза медленнее, чем C #. @Jalf: У тебя довольно быстрые цифры, я что-то здесь не так делаю?

Код C ++:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;

int runIntersectionTest(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;  

    vector<int>::const_iterator set1_end = set1.end();

    // Now intersect the two sets by populating the map
    for ( vector<int>::const_iterator iterator = set1.begin(); iterator != set1_end; ++iterator )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(const vector<int> set1_unsorted, const vector<int> set2_unsorted)
{   
    // Create two vectors
    std::vector<int> set1(set1_unsorted.size());
    std::vector<int> set2(set2_unsorted.size());

    // Copy the unsorted data into them
    std::copy(set1_unsorted.begin(), set1_unsorted.end(), set1.begin());
    std::copy(set2_unsorted.begin(), set2_unsorted.end(), set2.begin());

    // Sort the data
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    vector<int> intersection;
    intersection.reserve(1000);

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

    return intersection.size(); 
}

void createSets( vector<int>& set1, vector<int>& set2 )
{
    srand ( time(NULL) );

    set1.reserve(100000);
    set2.reserve(1000);

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

    // Try to get half of our values intersecting
    float ratio = 200000.0f / RAND_MAX;


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

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

    // Make sure set1 is in random order (not sorted)
    random_shuffle(set1.begin(),set1.end());
}

int _tmain(int argc, _TCHAR* argv[])
{
    int intersectionSize = 0;

    vector<int> set1, set2; 
    createSets( set1, set2 );

    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}
Я сомневаюсь, что C # может выполнить такую задачу значительно быстрее. Вы должны смотреть на очень похожие выступления. Noldorin
@JulianR: Согласен. В том же духе; Я хотел бы рассмотреть вопрос об увеличении размера теста или запустить тест в 1000 раз - гораздо легче быть уверенным в сроках, когда вы действительно можете увидеть, что они принимают & gt; 1 с. DaveR
Ваше время в обоих случаях неверно. Если вас интересует время, необходимое для выполнения пересечения, вы должны рассчитывать время, а не время, необходимое для построения и заполнения списков / векторов. jalf
Я бы рассчитал время теста C # с System.Diagnostics.Stopwatch, он намного точнее, чем метод DateTime, который может быть отключен на несколько миллисекунд. JulianR
Для начала я посмотрю на профилирование кода, чтобы определить, какие части занимают большую часть времени. Я не программист Win32, но думаю, что в Linux должно быть что-то похожее на OProfile / gprof. DaveR

Ваш Ответ

12   ответов
2

: set_intersection - не самый быстрый алгоритм. std :: set_intersection требует до 2 * (m + n) -1 сравнений, но алгоритмы, подобные алгоритму Baeza-Yates, могут быть быстрее. Для малых m Баэса-Йейтс равен O (m * log (n)), тогда как для n = alpha * m это O (n). Основная идея заключается в том, чтобы выполнить своего рода двухсторонний бинарный поиск.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.7899&rep=rep1&type=pdf

Экспериментальный анализ алгоритма быстрого пересечения для отсортированных последовательностей Рикардо Баеза-Йейтс и Алехандро Сэлинджер

ИЛИ ЖЕ

Р. Баеза-Йейтс. Алгоритм пересечения быстрых множеств для отсортированных последовательностей. В Материалы 15-го ежегодного симпозиума по комбинаторному сопоставлению образцов (CPM 2004), Springer LNCS 3109, стр. 400-408, Стамбул, Турция, июль 2004 г.

Ниже приводится объяснение и реализация Эрика Фрея, где он показывает значительно более быстрые результаты, чем std :: set_intersection с двоичным зондом. Я еще не пробовал его код.
http://fawx.com/

Pick the median element, A, in the smaller set. Search for its insertion-position element, B, in the larger set. If A and B are equal, append the element to the result. Repeat steps 1-4 on non-empty subsets on either side of elements A and B.

;

/* * baeza_intersect */ template< template class Probe, class RandomAccessIterator, class OutputIterator> void baeza_intersect(RandomAccessIterator begin1, RandomAccessIterator end1, RandomAccessIterator begin2, RandomAccessIterator end2, OutputIterator out) { RandomAccessIterator probe1, probe2;

if ( (end1 - begin1) < ( end2 - begin2 ) ) { if ( begin1 == end1 ) return; probe1 = begin1 + ( ( end1 - begin1 ) >> 1 ); probe2 = lower_bound< Probe >( begin2, end2, *probe1 ); baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out); // intersect left if (! (probe2 == end2 || *probe1 < *probe2 )) *out++ = *probe2++; baeza_intersect< Probe >(++probe1, end1, probe2, end2, out); // intersect right } else { if ( begin2 == end2 ) return; probe2 = begin2 + ( ( end2 - begin2 ) >> 1 ); probe1 = lower_bound< Probe >( begin1, end1, *probe2 ); baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out); // intersect left if (! (probe1 == end1 || *probe2 < *probe1 )) *out++ = *probe1++; baeza_intersect< Probe >(probe1, end1, ++probe2, end2, out); // intersect right } }

/* * with a comparator */ template< template class Probe, class RandomAccessIterator, class OutputIterator, class Comparator > void baeza_intersect(RandomAccessIterator begin1, RandomAccessIterator end1, RandomAccessIterator begin2, RandomAccessIterator end2, OutputIterator out, Comparator cmp) { RandomAccessIterator probe1, probe2;

  if ( (end1 - begin1) < ( end2 - begin2 ) )
  {
    if ( begin1 == end1 )
      return;
    probe1 = begin1 + ( ( end1 - begin1 ) >> 1 );
    probe2 = lower_bound< Probe >( begin2, end2, *probe1, cmp );
    baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out, cmp); // intersect left
    if (! (probe2 == end2 || cmp( *probe1, *probe2 ) ))
      *out++ = *probe2++;
    baeza_intersect< Probe >(++probe1, end1, probe2, end2, out, cmp); // intersect right
  }
  else
  {
    if ( begin2 == end2 )
      return;
    probe2 = begin2 + ( ( end2 - begin2 ) >> 1 );
    probe1 = lower_bound< Probe >( begin1, end1, *probe2, cmp );
    baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out, cmp); // intersect left
    if (! (probe1 == end1 || cmp( *probe2, *probe1 ) ))
      *out++ = *probe1++;
    baeza_intersect< Probe >(probe1, end1, ++probe2, end2, out, cmp); // intersect right
  }
}

// probe.hpp

/** * binary probe: pick the next element by choosing the halfway point between low and high */ template< class RandomAccessIterator, class T > struct binary_probe { RandomAccessIterator operator()(RandomAccessIterator begin, RandomAccessIterator end, const T & value) { return begin + ( (end - begin) >> 1); } };

/** * lower_bound: like stl's lower_bound but with different kinds of probing * note the appearance of the rare template parameter template! */ template< template class Probe, class RandomAccessIterator, class T > RandomAccessIterator lower_bound(RandomAccessIterator begin, RandomAccessIterator end, const T & value) { RandomAccessIterator pit; Probe< RandomAccessIterator, T > pfunc; // probe-functor (wants to get func'd up)

while ( begin < end ) { pit = pfunc(begin, end, value); if ( *pit < value ) begin = pit + 1; else end = pit; } return begin; }

/* * this time with a comparator! */ template< template class Probe, class RandomAccessIterator, class T, class Comparator > RandomAccessIterator lower_bound(RandomAccessIterator begin, RandomAccessIterator end, const T & value, Comparator cmp) { RandomAccessIterator pit; Probe< RandomAccessIterator, T > pfunc;

while ( begin < end ) { pit = pfunc(begin, end, value); if ( cmp(*pit, value) ) begin = pit + 1; else end = pit; } return begin; }

1

вам следует проверить, есть ли у вас_SECURE_SCL установите в 1 (обычно, если вы явно не установили его, это будет 1). Если он установлен, весь STL-код будет проверяться по диапазону, даже в выпусках сборки. Как правило, замедление кода на 10-15%.

Похоже, Microsoft не знала, что, например, у std :: vector уже есть интерфейс, если вы хотите проверить диапазон: std :: vector :: at ()!

(Извините, пришлось снять его с груди).

В любом случае главная неэффективность заключается в том, что вы копируете контейнеры вместо того, чтобы передавать их по значению. Используйте ссылки, чтобы (попытаться) сравнить яблоки и яблоки вместо яблок и бананов.

Я настрою и перепишу без копирования ... Я установил _SECURE_SCL в 0. (#define _SECURE_SCL 0) Alex Black
0

если бы вы их тоже не копировали.

Вкладчик не помещал значения в конец вектора, где это быстро. Он делал это только при первой вставке, после чего вставлял значение в начало массива (где конец указывал).

когда вы обновляли значение, вы дважды искали значение в версии хэш-карты. Почему это значение события обновляется?

запустите этот код и опубликуйте время.

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>

#include <boost\unordered\unordered_set.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;

int runIntersectionTest(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_set<int> theSet;      

     theSet.insert( set1.begin(), set2.end() );

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        if ( theSet.find(*iterator) != theSet.end() )
        {
                intersectionSize++;
        }
    }

    return intersectionSize;
}

int runSetIntersection( vector<int> set1, vector<int> set2)
{   
    // Sort the data
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    vector<int> intersection;
    intersection.reserve(1000);

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

    return intersection.size(); 
}

void createSets( vector<int>& set1, vector<int>& set2 )
{
    srand ( time(NULL) );

    set1.reserve(100000);
    set2.reserve(1000);

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

    // Try to get half of our values intersecting
    float ratio = 200000.0f / RAND_MAX;


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

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

    // Make sure set1 is in random order (not sorted)
    random_shuffle(set1.begin(),set1.end());
}

int _tmain(int argc, _TCHAR* argv[])
{
    int intersectionSize = 0;

    vector<int> set1, set2;     
    createSets( set1, set2 );

    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}
Error: User Rate Limit Exceeded Alex Black
9

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

Кроме того, я не буду использовать набор для целиset_intersection, Я бы использовал что-то вроде

int runSetIntersection(const set<int>& set1, const set<int>& set2)
{   
    vector<int> intersection;
    intersection.reserve(10000) // or whatever the max is

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

    return intersection.size(); 
}

Этот код, однако, по-прежнему размещается внутри функции. Еще быстрее будет

int runSetIntersection(const set<int>& set1, const set<int>& set2, vector<int>& scratch)
{   
    scratch.reserve(10000) // or whatever the max is

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), back_inserter(scratch));

    return scratch.size(); 
}

А затем выделите царапину, прежде чем запустить таймер.

Хотя, если вы просто ищете размер, рукописный цикл for в сочетании с set :: find может дать еще лучшие результаты.

Хороший споттинг! Это должно учитывать некоторую медлительность.
0

что ваше решение работает нормально, но вы пробовали использовать реализации STL:

includes set_intersection

Возможно, он уже оптимизирован под вашу платформу, поэтому я бы попробовал

Error: User Rate Limit Exceeded Alex Black
0

Я изменил код set_intersection для использования векторов и их сортировки (вместо использования класса отсортированных множеств), и теперь он НАМНОГО быстрее:

Found the intersection of 319 values (using unordered_map) 1000 times, in 22187.5ms
Found the intersection of 315 values (using set_intersection) 1000 times, in 2401.62ms

Имейте в виду: больший набор создается отсортированным, поэтому в этом примере сортировка может не занять много времени.

Код C ++:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;

int runIntersectionTest(vector<int> set1, vector<int> set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;

    // Now intersect the two sets by populating the map
    for ( vector<int>::iterator iterator = set1.begin(); iterator != set1.end(); iterator++ )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    for ( vector<int>::iterator iterator = set2.begin(); iterator != set2.end(); iterator++ )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(vector<int> set1, vector<int> set2)
{   
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    set<int> intersection;

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

    return intersection.size(); 
}



int _tmain(int argc, _TCHAR* argv[])
{
    srand ( time(NULL) );

    vector<int> set1;
    vector<int> set2;

    set1.reserve(10000);
    set2.reserve(1000);

    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.push_back(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.push_back(value);
    }

    int intersectionSize = 0;


    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}
Error: User Rate Limit Exceeded Alex Black
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
27

Во-первых, вы не тестируете пересечение множества, а "создаете пару массивов, заполняете их случайными числами и затем выполняете пересечение множества". Вам следует рассчитать только ту часть кода, которая вам действительно интересна. Даже если вы захотите сделать эти вещи, их не следует здесь сравнивать. Измеряйте одну вещь за раз, чтобы уменьшить неопределенность. Если вы хотите, чтобы ваша реализация на C ++ работала лучше, сначала вам нужно узнать, какая ее часть медленнее, чем ожидалось. Это означает, что вы должны отделить установочный код от теста пересечения.

Во-вторых, вы должны запускать тест большое количество раз, чтобы учесть возможные эффекты кэширования и другие неопределенности. (И, возможно, выведите одно общее время, скажем, 1000 прогонов, а не отдельное время для каждого. Таким образом вы уменьшите неопределенность таймера, который может иметь ограниченное разрешение, и сообщите о неточных результатах при использовании в диапазоне 0-20 мс.

Кроме того, насколько я могу читать из документов, входные данные для set_intersection должны быть отсортированы, что set2 не будет. Кажется, нет причин использоватьunordered_map, когдаunordered_set будет гораздо лучше соответствовать тому, что вы делаете.

Что касается кода установки, обратите внимание, что вы, вероятно,don't необходимо заполнить векторы, чтобы запустить пересечение. И ваша собственная реализация иset_intersection уже работайте с итераторами, так что вы можете просто передать им пару итераторов в структуры данных, в которых уже находятся ваши входные данные.

Несколько более конкретных комментариев к вашему коду:

Use ++iterator instead of iterator++ rather than calling vector.end() at each loop iteration, call it once and cache the result experiment with using sorted vectors vs std::set vs unordered_set (not unordered_map)

Edit:

Я не пробовал вашу версию C #, поэтому не могу правильно сравнить числа, но вот мой модифицированный тест. Каждый из них запускается 1000 раз на Core 2 Quad 2,5 ГГц с 4 ГБ ОЗУ:

std::set_intersection on std::set: 2606ms
std::set_intersection on tr1::unordered_set: 1014ms
std::set_intersection on sorted vectors: 171ms
std::set_intersection on unsorted vectors: 10140ms

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

И мой код:

#define _SECURE_SCL 0

#include <ctime>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <windows.h>

template <typename T, typename OutIter>
void stl_intersect(const T& set1, const T& set2, OutIter out){
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), out);
}

template <typename T, typename OutIter>
void sort_stl_intersect(T& set1, T& set2, OutIter out){
    std::sort(set1.begin(), set1.end());
    std::sort(set2.begin(), set2.end());
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), out);
}


template <typename T>
void init_sorted_vec(T first, T last){
    for ( T cur = first; cur != last; ++cur)
    {
        int i = cur - first;
        int value = 1000000000 + i;
        *cur = value;
    }
}

template <typename T>
void init_unsorted_vec(T first, T last){
    for ( T cur = first; cur != last; ++cur)
    {
        int i = rand() % 200000 + 1;
        i *= 10;

        int value = 1000000000 + i;
        *cur = value;
    }
}

struct resize_and_shuffle {
    resize_and_shuffle(int size) : size(size) {}

    void operator()(std::vector<int>& vec){
        vec.resize(size);

    }
    int size;
};

int main()
{
    srand ( time(NULL) );
    std::vector<int> out(100000);

    std::vector<int> sortedvec1(100000);
    std::vector<int> sortedvec2(1000);

    init_sorted_vec(sortedvec1.begin(), sortedvec1.end());
    init_unsorted_vec(sortedvec2.begin(), sortedvec2.end());
    std::sort(sortedvec2.begin(), sortedvec2.end());

    std::vector<int> unsortedvec1(sortedvec1.begin(), sortedvec1.end());
    std::vector<int> unsortedvec2(sortedvec2.begin(), sortedvec2.end());

    std::random_shuffle(unsortedvec1.begin(), unsortedvec1.end());
    std::random_shuffle(unsortedvec2.begin(), unsortedvec2.end());

    std::vector<int> vecs1[1000];
    std::vector<int> vecs2[1000];

    std::fill(vecs1, vecs1 + 1000, unsortedvec1);
    std::fill(vecs2, vecs2 + 1000, unsortedvec2);

    std::set<int> set1(sortedvec1.begin(), sortedvec1.end());
    std::set<int> set2(sortedvec2.begin(), sortedvec2.end());

    std::tr1::unordered_set<int> uset1(sortedvec1.begin(), sortedvec1.end());
    std::tr1::unordered_set<int> uset2(sortedvec2.begin(), sortedvec2.end());

    DWORD start, stop;
    DWORD delta[4];

    start = GetTickCount();
    for (int i = 0; i < 1000; ++i){
        stl_intersect(set1, set2, out.begin());
    }
    stop = GetTickCount();
    delta[0] = stop - start;

    start = GetTickCount();
    for (int i = 0; i < 1000; ++i){
        stl_intersect(uset1, uset2, out.begin());
    }
    stop = GetTickCount();
    delta[1] = stop - start;

    start = GetTickCount();
    for (int i = 0; i < 1000; ++i){
        stl_intersect(sortedvec1, sortedvec2, out.begin());
    }
    stop = GetTickCount();
    delta[2] = stop - start;

    start = GetTickCount();
    for (int i = 0; i < 1000; ++i){
        sort_stl_intersect(vecs1[i], vecs1[i], out.begin());
    }
    stop = GetTickCount();
    delta[3] = stop - start;

    std::cout << "std::set_intersection on std::set: " << delta[0] << "ms\n";
    std::cout << "std::set_intersection on tr1::unordered_set: " << delta[1] << "ms\n";
    std::cout << "std::set_intersection on sorted vectors: " << delta[2] << "ms\n";
    std::cout << "std::set_intersection on unsorted vectors: " << delta[3] << "ms\n";


    return 0;
}

Нет причин, по которым C ++ всегда должен быть быстрее, чем C #. C # имеет несколько ключевых преимуществ, которые требуют большой осторожности, чтобы конкурировать с C ++. Первое, о чем я могу подумать, это то, что динамическое распределение смехотворно дешево в .NET-земле. Каждый раз, когда вектор C ++, set или unordered_set (или любой другой контейнер) должен изменять размер или расширяться, это очень дорогоmalloc операция. В .NET выделение кучи - чуть больше, чем добавление смещения к указателю.

Поэтому, если вы хотите, чтобы версия C ++ конкурировала, вам, вероятно, придется решить эту проблему, позволив вашим контейнерам изменить размер без необходимости выполнять фактическое выделение кучи, возможно, с помощью пользовательских распределителей для контейнеров (возможно, Boost :: Pool может быть хорошим Вы можете сделать ставку самостоятельно)

Другая проблема заключается в том, чтоset_difference работает только с отсортированным вводом, и для того, чтобы воспроизвести результаты тестов, которые включают сортировку, мы должны делать свежую копию несортированных данных на каждой итерации, что является дорогостоящим (хотя, опять же, использование пользовательских распределителей очень поможет). Я не знаю, какую форму принимает ваш ввод, но возможно, что вы можете отсортировать входные данные напрямую, не копируя их, а затем запуститьset_difference прямо на это. (Это было бы легко сделать, если бы ваш ввод был как минимум массивом или контейнером STL.)

Одним из ключевых преимуществ STL является то, что он настолько гибок, что может работать практически с любой последовательностью ввода. В C # вам в значительной степени приходится копировать входные данные в List или Dictionary или что-то в этом роде, но в C ++ вы можете сойти с работыstd::sort а такжеset_intersection на необработанном входе.

Наконец, конечно, попробуйте запустить код через профилировщик и посмотреть, где именно тратится время. Вы также можете попробовать запустить код через GCC. У меня сложилось впечатление, что производительность STL в MSVC иногда немного странная. Возможно, стоит протестировать под другим компилятором, просто чтобы увидеть, есть ли у вас аналогичные тайминги.

Наконец, вы можете найти эти сообщения в блоге, имеющие отношение к производительности C ++ против C #: http://blogs.msdn.com/ricom/archive/2005/05/10/416151.aspx

Мораль тех в основном заключается в том, что да, вы можете получить лучшую производительность в C ++, но это удивительный объем работы.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededsgi.com/tech/stl/set.html Alex Black
Error: User Rate Limit ExceededthisError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded Alex Black
Error: User Rate Limit Exceeded Alex Black
2

Несвязанный набор контейнер, который специально оптимизирован для определенных видов операций с множествами.

Он работает, рассматривая группу множеств как объединения нескольких непересекающихся множеств, что позволяет очень дешево строить другие множества, такие как пересечения или объединения, после того, как начальный набор непересекающихся множеств построен. Если вы ожидаете выполнения множества операций над множествами, которые не сильно меняются, вы можете ожидать, что это будет очень быстро. Если, с другой стороны, вы будете использовать каждый набор один раз и выбрасывать его, это, вероятно, не будет делать слишком много.

В любом случае, вы сделаете себе одолжение, по крайней мере, поэкспериментируйте с этим, чтобы увидеть, не дает ли это вам какого-либо удара в вашем конкретном случае.

Error: User Rate Limit Exceeded
0

Found the intersection of 504 values (using unordered_map) 1000 times, in 28827.6ms
Found the intersection of 495 values (using set_intersection) 1000 times, in 9817.69ms
Found the intersection of 504 values (using unordered_set) 1000 times, in 24769.1ms

Я думаю, что разница 504 - 495 происходит, потому что есть пара значений двойника.

Code:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>
#include <unordered_set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;
using namespace tr1;


int runIntersectionTest2(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_set<int> theSet;      

     theSet.insert( set1.begin(), set1.end() );

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        if ( theSet.find(*iterator) != theSet.end() )
        {
                intersectionSize++;
        }
    }

    return intersectionSize;
}

int runIntersectionTest(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;  

    vector<int>::const_iterator set1_end = set1.end();

    // Now intersect the two sets by populating the map
    for ( vector<int>::const_iterator iterator = set1.begin(); iterator != set1_end; ++iterator )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(const vector<int>& set1_unsorted, const vector<int>& set2_unsorted)
{   
    // Create two vectors
    std::vector<int> set1(set1_unsorted.size());
    std::vector<int> set2(set2_unsorted.size());

    // Copy the unsorted data into them
    std::copy(set1_unsorted.begin(), set1_unsorted.end(), set1.begin());
    std::copy(set2_unsorted.begin(), set2_unsorted.end(), set2.begin());

    // Sort the data
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    vector<int> intersection;
    intersection.reserve(1000);

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

    return intersection.size(); 
}

void createSets( vector<int>& set1, vector<int>& set2 )
{
    srand ( time(NULL) );

    set1.reserve(100000);
    set2.reserve(1000);

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

    // Try to get half of our values intersecting
    float ratio = 200000.0f / RAND_MAX;


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

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

    // Make sure set1 is in random order (not sorted)
    random_shuffle(set1.begin(),set1.end());
}

int _tmain(int argc, _TCHAR* argv[])
{
    int intersectionSize = 0;

    vector<int> set1, set2; 
    createSets( set1, set2 );

    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest2(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_set) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}
Error: User Rate Limit Exceeded Alex Black
Error: User Rate Limit Exceeded
4

vector<int> set1(10000);
vector<int> set2(1000);

... чтобы получить векторы с ненулевым начальным размером. Тогда не используйте push_back, а просто обновите значения напрямую.

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded Alex Black
2

runIntersectionTest & quot; принимать константные ссылки на контейнеры, а не создавать их копируемые при каждом вызове. (Код C # будет использовать ссылки.)

0

после большого количества отзывов я обновлял исходный вопрос несколько раз:

The tests are now each run 1,000 times The C# code now uses a higher resolution timer The data structures are now populated BEFORE the tests

Результатом этого является то, что C # все еще в 5 раз быстрее, чем C ++.

Спасибо всем за ваши идеи / предложения.

Похожие вопросы