Сложность времени вставки строки в набор c ++ stl - PullRequest
Новая
       43

Сложность времени вставки строки в набор c ++ stl

0 голосов
/ 26 января 2019

Какова временная сложность вставки строки в набор контейнеров c ++ STL?По моему мнению, это должно быть O (xlogn), где x - длина вставляемой строки, а n - размер набора.Также копирование строки для установки должно быть линейным по длине строки.Но этот мой код работает мгновенно. 

#include<bits/stdc++.h>
using namespace std;
int main(){

    set<string> c;
    string s(100000,'a');
    for(int i=0;i<100000;i++){
        c.insert(s);
    }

}

Где я ошибаюсь, разве сложность не должна быть порядка 10 ^ 10?

Ответы [ 2 ]

0 голосов
/ 27 января 2019

Вы должны использовать set каким-либо образом, чтобы уменьшить риск оптимизации цикла, например, добавив return c.size();.

Также ваш выбор номераиз итераций может быть слишком низким.Добавьте цифру к счетчику циклов, и вы увидите заметное время выполнения.

Современный процессор может легко обрабатывать> 2 * 10 9 операций / с.Предполагая, что ваш компилятор использует memcmp, который, вероятно, векторизован вручную, с небольшим рабочим набором, таким как ваш, вы работаете полностью из кэша и можете достичь пропускной способности до 512 байт на сравнение (с AVX2).Предполагая умеренную скорость 10 циклов на итерацию, мы все равно можем сравнить> 10 10 байт / с.Таким образом, ваша программа должна работать в течение <1 с на умеренном оборудовании. </p>

Попробуйте вместо этого этот обновленный код: 

#include <string>
#include <set>
using namespace std;
int main(){

    set<string> c;
    string s(100000,'a');
    for(int i=0;i<1000000;i++) { // Add a digit here
        c.insert(s);
    }
    return c.size(); // use something from the set
}

При включенной оптимизации (-O3) для запуска потребуется ~ 5 секундмоя система.

Другими словами, да, вставка в двоичное дерево имеет сложность O (log n), но сравнение строки имеет сложность O (n).Эти n не совпадают, в случае map он представляет размер карты, а в случае string - длину строки.

В вашем конкретном случае карта имеет толькоодин элемент, поэтому вставка O (1).Вы получаете линейную сложность O (n) исключительно из сравнения строк, где n равно string_length * number_of_iterations .

0 голосов
/ 26 января 2019

Сложность вставки одного элемента в std::set равна O(log n), так как она основана на красно-черном дереве (https://en.wikipedia.org/wiki/Red%E2%80%93black_tree).

Так что да, вы можете предположить, что для этого требуется O(x * log n)где x - длина строки.

Когда вы пытаетесь вставить n отдельных элементов, сложность вашего алгоритма будет O(n * log n).

Вашcase:

Вы пытаетесь вставить одну и ту же строку снова и снова, но std::set может содержать только уникальные элементы, поэтому в вашем примере ваш набор будет содержать только 1 строку.

Таким образом, на каждой итерации (после первой, конечно) std::set делает только одно сравнение и решает не помещать одну и ту же строку.

Вот почему ваш код работает так быстро.

PS Также компилятор может внести некоторые оптимизации в этом случае.

...