Почему сложность оператора std :: unordered_set == () N ^ 2? - PullRequest
Новая
       120

Почему сложность оператора std :: unordered_set == () N ^ 2?

0 голосов
/ 23 декабря 2018

У меня есть два вектора v1 и v2 типа std::vector<std::string>.Оба вектора имеют уникальные значения и должны сравниваться равными, если значения сравниваются равными, но независимо от значений порядка появляются в векторе.

Я предполагаю, что два набора типа std::unordered_set были бы лучшим выбором, но я принимаю этокак есть, так и два вектора.

Тем не менее, я подумал, что для необходимого сравнения без учета порядка я просто буду использовать operator== из std::unordered_set, копируя в два std::unordered_set.Очень похоже на это: 

bool oi_compare1(std::vector<std::string> const&v1,
                 std::vector<std::string> const&v2)
{
    std::unordered_set<std::string> tmp1(v1.begin(),v1.end());
    std::unordered_set<std::string> tmp2(v2.begin(),v2.end());
    return tmp1 == tmp2;
}

Во время профилирования я заметил, что эта функция отнимает много времени, поэтому я проверил doc и увидел здесь сложность O(n*n).Я запутался, я ожидал O(n*log(n)), как, например, для следующего наивного решения, которое я придумал: 

bool oi_compare2(std::vector<std::string> const&v1,
                 std::vector<std::string> const&v2)
{
    if(v1.size() != v2.size())
        return false;
    auto tmp = v2;
    size_t const size = tmp.size();
    for(size_t i = 0; i < size; ++i)
    {
        bool flag = false;
        for(size_t j = i; j < size; ++j)
            if(v1[i] == tmp[j]){
                flag = true;
                std::swap(tmp[i],tmp[j]);
                break;
            }
        if(!flag)
            return false;
    }
    return true;
}

Почему сложность O(n*n) для std::unordered_set и есть ли встроенная функция Iможно использовать для сравнения без учета порядка?

РЕДАКТИРОВАТЬ ---- BENCHMARK 

#include <unordered_set>
#include <chrono>
#include <iostream>
#include <vector>

bool oi_compare1(std::vector<std::string> const&v1,
        std::vector<std::string> const&v2)
{
    std::unordered_set<std::string> tmp1(v1.begin(),v1.end());
    std::unordered_set<std::string> tmp2(v2.begin(),v2.end());
    return tmp1 == tmp2;
}
bool oi_compare2(std::vector<std::string> const&v1,
                std::vector<std::string> const&v2)
{
    if(v1.size() != v2.size())
        return false;
    auto tmp = v2;
    size_t const size = tmp.size();
    for(size_t i = 0; i < size; ++i)
    {
        bool flag = false;
        for(size_t j = i; j < size; ++j)
            if(v1[i] == tmp[j]){
                flag = true;
                std::swap(tmp[i],tmp[j]);
                break;
            }
        if(!flag)
            return false;
    }
    return true;
}

int main()
{
    std::vector<std::string> s1{"1","2","3"};
    std::vector<std::string> s2{"1","3","2"};
    std::cout << std::boolalpha;
    for(size_t i = 0; i < 15; ++i)
    {
        auto tmp1 = s1;
        for(auto &iter : tmp1)
            iter = std::to_string(i)+iter;
        s1.insert(s1.end(),tmp1.begin(),tmp1.end());
        s2.insert(s2.end(),tmp1.begin(),tmp1.end());
    }
    std::cout << "size1 " << s1.size() << std::endl;
    std::cout << "size2 " << s2.size() << std::endl;

    for(auto && c : {oi_compare1,oi_compare2})
    {
        auto start = std::chrono::steady_clock::now();
        bool flag = true;
        for(size_t i = 0; i < 10; ++i)
            flag = flag && c(s1,s2);
        std::cout << "ms=" << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - start).count() << " flag=" << flag << std::endl;
    }
    return 0;
}

дает 

size1 98304
size2 98304
ms=844 flag=true
ms=31 flag=true

-> наивный подход быстрее.

Для всех экспертов по сложности O (N * N) здесь ... Позвольте мне пройти через этот наивный подход.У меня там две петли.Первый цикл выполняется от i=0 до размера, равного N. Внутренний цикл вызывается из j = i !!!!!!на N. В разговорном языке это означает, что я называю Внутренний цикл N раз.Но сложность внутреннего цикла заключается в log (n) из-за начального индекса j = i !!!!.Если вы все еще не верите мне, вычислите сложность по тестам, и вы увидите ...

EDIT2 --- LIVE ON WANDBOX https://wandbox.org/permlink/v26oxnR2GVDb9M6y

Ответы [ 2 ]

0 голосов
/ 23 декабря 2018

Прошу прощения за сообщение, ваш эталонный тест operator== неисправен.

oi_compare1 принимает 2 вектора и должен создать 2 полных unordered_set экземпляра, чем вызов operator==и снова уничтожить всю связку.

oi_compare2 также принимает 2 вектора и немедленно использует их для сравнения по размеру.Только копирует 1 экземпляр (v2 в tmp), что намного эффективнее для вектора.

operator ==

Глядя на документацию: https://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp мы можем увидеть ожидаемыйсложность:

Пропорционально N обращений к оператору == для value_type, обращений к предикату, возвращенному key_eq, и обращений к хешу, возвращаемому hash_function, в среднем случае, пропорциональном N2 в худшем случаеслучай, когда N - размер контейнера.

edit Существует простой алгоритм, вы можете перебрать unordered_set и сделать простой поиск в другом.Без коллизий хеша он найдет каждый элемент в своем собственном внутреннем сегменте и сравнит его на равенство, так как хеширования недостаточно.

Если у вас нет коллизий хэшей, каждый элемент unordered_set имеет стабильный порядок, в котором они хранятся.Можно перебрать внутренние ведра и сравнить элементы 2 на 2 (1-й из 1-го с 1-м из второго, 2-й из 1-го с 2-м из 2-го ...).Это приятно дает O(N). Это не работает, когда у вас есть разные размеры сегментов, в которых вы храните значения, или когда при назначении сегментов используются другие вычисления для обработки коллизий.

Предположим, вам не повезло, и каждый элемент приводит к тому же хешу.(Известный как hash flooding) Вы получите список элементов без порядка.Для сравнения вы должны проверить для каждого элемента, существует ли он в другом, вызывая O(N*N).

Этот последний легко воспроизводим, если вы устанавливаете свой хеш, чтобы всегда возвращать одно и то же число.Постройте один набор в обратном порядке, как и другой.

0 голосов
/ 23 декабря 2018

Поскольку unordered_set создается с использованием hashmap, логика для сравнения lhs == rhs будет:

  • Проверить размер lhs и rhs, если не равен, вернуть false
  • Длякаждый элемент в lhs, найдите его в rhs и сравните

Для hashmap сложность единственного времени поиска для элемента в rhs в худшем случае будет O (n).Таким образом, сложность времени наихудшего случая будет O (n ^ 2).Однако обычно вы получаете временную сложность O (n).

...