Блог

Кто-нибудь может объяснить, как работает неупорядоченный набор? Я также не уверен, как работает set. Мой главный вопрос заключается в том, какова эффективность его функции find.

Например, каково общее время выполнения big O этого?

     vector<int> theFirst;
    vector<int> theSecond;
    vector<int> theMatch;

    theFirst.push_back( -2147483648 );
    theFirst.push_back(2);
    theFirst.push_back(44);


    theSecond.push_back(2);
    theSecond.push_back( -2147483648 );
    theSecond.push_back( 33 );


    //1) Place the contents into a unordered set that is O(m). 
    //2) O(n) look up so thats O(m   n). 
    //3) Add them to third structure so that's O(t)
    //4) All together it becomes O(m   n   t)
    unordered_set<int> theUnorderedSet(theFirst.begin(), theFirst.end());

    for(int i = 0; i < theSecond.size(); i  ) 
    {
        if(theUnorderedSet.find(theSecond[i]) != theUnorderedSet.end()) 
        {
        theMatch.push_back( theSecond[i] );
        cout << theSecond[i];
        }
   }
  

unordered_set и все другие unordered_ структуры данных используют хеширование, как упоминал @Sean. Хэширование требует амортизированного постоянного времени для вставки и близкого к постоянному времени для поиска. Хэш-функция, по сути, берет некоторую информацию и выдает из нее число. Это функция в том смысле, что один и тот же ввод должен выдавать один и тот же результат. Однако разные входные данные могут приводить к одному и тому же результату, что называется коллизией. Для «идеальной хэш-функции», то есть такой, в которой нет коллизий, было бы гарантировано постоянное время поиска. На практике входное число берется из элемента, который вы храните в структуре (скажем, это значение, это примитивный тип), и сопоставляет его местоположению в структуре данных. Следовательно, для данного ключа функция доставляет вас к месту, где хранится элемент, без необходимости каких-либо обходов или поисков (игнорируя столкновения здесь для простоты), следовательно, постоянное время. Существуют различные реализации этих структур (открытая адресация, объединение в цепочки и т.д.), См. хэш-таблицу, хэш-функцию. Я также рекомендую раздел 3.7 Руководства по разработке алгоритмов от Skiena. Теперь, что касается сложности big-O, вы правы в том, что у вас есть O (n) O (n) O (размер перекрытия). Поскольку перекрытие не может быть больше меньшего из m и n, общая сложность может быть выражена как O (kN), где N — наибольшее между m и n. Итак, O (N). Опять же, это «наилучший вариант», без коллизий и с идеальным хешированием.

set и multi_set с другой стороны, используются двоичные деревья, поэтому вставок и поисковых запросов обычно нет (logN). Фактическая производительность хэшированной структуры по сравнению с бинарной древовидной структурой будет зависеть от N, поэтому лучше всего попробовать два подхода и профилировать их в реалистичном сценарии выполнения.

Все типы данных std::unordered_*() используют хэш для выполнения поиска. Посмотрите документацию Boost по этому вопросу, и я думаю, вы очень быстро получите представление.

http://www.boost.org/doc/libs/1_46_1/doc/html/unordered.html