O (N) медленнее алгоритма O (N logN)

Ответ 1

Это действительно зависит от реализации hash_map/hash_set. Заменив libstdС++ unordered_{map,set} на Google dense_hash_{map,set}, он значительно быстрее, чем sort. Недостатком для dense_hash_xxx является то, что они требуют наличия двух значений для ключа, которые никогда не будут использоваться. Подробнее см. В их документе.

Еще одна вещь, которую следует помнить: hash_{map,set} обычно выполняет много динамического распределения/освобождения памяти, поэтому лучше использовать лучшую альтернативу libc default malloc/free, например. Google tcmalloc или Facebook jemalloc.

hidden $ g++ -O3 -std=c++11 xx.cpp /usr/lib/libtcmalloc_minimal.so.4
hidden $ ./a.out 
For input_size 262144:
unordered-set: returns 123454321
unordered-set: took 35 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 18 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 34 milliseconds
unordered-map: returns 123454321
unordered-map: took 36 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 13 milliseconds
--------------------------
For input_size 1048576:
unordered-set: returns 123454321
unordered-set: took 251 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 77 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 153 milliseconds
unordered-map: returns 123454321
unordered-map: took 220 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 60 milliseconds
--------------------------
For input_size 4194304:
unordered-set: returns 123454321
unordered-set: took 1453 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 357 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 596 milliseconds
unordered-map: returns 123454321
unordered-map: took 1461 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 296 milliseconds
--------------------------
For input_size 16777216:
unordered-set: returns 123454321
unordered-set: took 6664 milliseconds
dense-hash-set: returns 123454321
dense-hash-set: took 1751 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 2513 milliseconds
unordered-map: returns 123454321
unordered-map: took 7299 milliseconds
dense-hash-map: returns 123454321
dense-hash-map: took 1364 milliseconds
--------------------------
tcmalloc: large alloc 1073741824 bytes == 0x5f392000 @ 
tcmalloc: large alloc 2147483648 bytes == 0x9f392000 @ 
tcmalloc: large alloc 4294967296 bytes == 0x11f392000 @ 
For input_size 268435456:
tcmalloc: large alloc 4586348544 bytes == 0x21fb92000 @ 
unordered-set: returns 123454321
unordered-set: took 136271 milliseconds
tcmalloc: large alloc 8589934592 bytes == 0x331974000 @ 
tcmalloc: large alloc 2147483648 bytes == 0x21fb92000 @ 
dense-hash-set: returns 123454321
dense-hash-set: took 34641 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 47606 milliseconds
tcmalloc: large alloc 2443452416 bytes == 0x21fb92000 @ 
unordered-map: returns 123454321
unordered-map: took 176066 milliseconds
tcmalloc: large alloc 4294967296 bytes == 0x331974000 @ 
dense-hash-map: returns 123454321
dense-hash-map: took 26460 milliseconds
--------------------------

код:

#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>

#include <google/dense_hash_map>
#include <google/dense_hash_set>

using std::cout;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::endl;
using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;
using google::dense_hash_map;
using google::dense_hash_set;

class ScopedTimer {
public:
    ScopedTimer(const string& name)
    : name_(name), start_time_(high_resolution_clock::now()) {}

    ~ScopedTimer() {
        cout << name_ << " took "
        << std::chrono::duration_cast<milliseconds>(
                                                    high_resolution_clock::now() - start_time_).count()
        << " milliseconds" << endl;
    }

private:
    const string name_;
    const high_resolution_clock::time_point start_time_;
};

int find_using_unordered_set(const vector<int>& input_data) {
    unordered_set<int> numbers(input_data.size());
    for(const auto& value : input_data) {
        auto res = numbers.insert(value);
        if(!res.second) {
            numbers.erase(res.first);
        }
    }
    return numbers.size() == 1 ? *numbers.begin() : -1;
}

int find_using_unordered_map(const vector<int>& input_data) {
    unordered_map<int,int> counter_map;
    for(const auto& value : input_data) {
        ++counter_map[value];
    }
    for(const auto& map_entry : counter_map) {
        if(map_entry.second % 2 == 1) {
            return map_entry.first;
        }
    }
    return -1;
}

int find_using_dense_hash_set(const vector<int>& input_data) {
    dense_hash_set<int> numbers(input_data.size());
    numbers.set_deleted_key(-1);
    numbers.set_empty_key(-2);
    for(const auto& value : input_data) {
        auto res = numbers.insert(value);
        if(!res.second) {
            numbers.erase(res.first);
        }
    }
    return numbers.size() == 1 ? *numbers.begin() : -1;
}

int find_using_dense_hash_map(const vector<int>& input_data) {
    dense_hash_map<int,int> counter_map;
    counter_map.set_deleted_key(-1);
    counter_map.set_empty_key(-2);
    for(const auto& value : input_data) {
        ++counter_map[value];
    }
    for(const auto& map_entry : counter_map) {
        if(map_entry.second % 2 == 1) {
            return map_entry.first;
        }
    }
    return -1;
}

int find_using_sort_and_count(const vector<int>& input_data) {
    vector<int> local_copy(input_data);
    std::sort(local_copy.begin(), local_copy.end());
    int prev_value = local_copy.front();
    int counter = 0;
    for(const auto& value : local_copy) {
        if(prev_value == value) {
            ++counter;
            continue;
        }

        if(counter % 2 == 1) {
            return prev_value;
        }

        prev_value = value;
        counter = 1;
    }
    return counter == 1 ? prev_value : -1;
}

void execute_and_time(const string& method_name, std::function<int()> method) {
    ScopedTimer timer(method_name);
    cout << method_name << " returns " << method() << endl;
}

int main()
{
    vector<int> input_size_vec({1<<18,1<<20,1<<22,1<<24,1<<28});

    for(const auto& input_size : input_size_vec) {
        // Prepare input data
        std::vector<int> input_data;
        const int magic_number = 123454321;
        for(int i=0;i<input_size;++i) {
            input_data.push_back(i);
            input_data.push_back(i);
        }
        input_data.push_back(magic_number);
        std::random_shuffle(input_data.begin(), input_data.end());
        cout << "For input_size " << input_size << ":" << endl;

        execute_and_time("unordered-set:",std::bind(find_using_unordered_set, std::cref(input_data)));
        execute_and_time("dense-hash-set:",std::bind(find_using_dense_hash_set, std::cref(input_data)));
        execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, std::cref(input_data)));
        execute_and_time("unordered-map:",std::bind(find_using_unordered_map, std::cref(input_data)));
        execute_and_time("dense-hash-map:",std::bind(find_using_dense_hash_map, std::cref(input_data)));

        cout << "--------------------------" << endl;
    }
    return 0;
}

Ответ 2

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

Я запустил программу на своей машине (HP Z420 с производным Ubuntu 14.04 LTE) и добавил вывод для 1<<26, поэтому у меня есть другой набор чисел, но коэффициенты выглядят удивительно похожими на отношения от данных в исходном посте. Сырые времена я получил (файл on-vs-logn.raw.data):

For input_size 262144:
hash-set: returns 123454321
hash-set: took 45 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 34 milliseconds
hash-map: returns 123454321
hash-map: took 61 milliseconds
--------------------------
For input_size 1048576:
hash-set: returns 123454321
hash-set: took 372 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 154 milliseconds
hash-map: returns 123454321
hash-map: took 390 milliseconds
--------------------------
For input_size 4194304:
hash-set: returns 123454321
hash-set: took 1921 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 680 milliseconds
hash-map: returns 123454321
hash-map: took 1834 milliseconds
--------------------------
For input_size 16777216:
hash-set: returns 123454321
hash-set: took 8356 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 2970 milliseconds
hash-map: returns 123454321
hash-map: took 9045 milliseconds
--------------------------
For input_size 67108864:
hash-set: returns 123454321
hash-set: took 37582 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 12842 milliseconds
hash-map: returns 123454321
hash-map: took 46480 milliseconds
--------------------------
For input_size 268435456:
hash-set: returns 123454321
hash-set: took 172329 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 53856 milliseconds
hash-map: returns 123454321
hash-map: took 211191 milliseconds
--------------------------

real    11m32.852s
user    11m24.687s
sys     0m8.035s

Я создал script, awk.analysis.sh, чтобы проанализировать данные:

#!/bin/sh

awk '
BEGIN { printf("%9s  %8s  %8s  %8s  %8s  %8s  %8s  %9s  %9s  %9s  %9s\n",
               "Size", "Sort Cnt", "R:Sort-C", "Hash Set", "R:Hash-S", "Hash Map",
               "R:Hash-M", "O(N)", "O(NlogN)", "O(N^3/2)", "O(N^2)")
}
/input_size/           { if (old_size   == 0) old_size   = $3; size       = $3 }
/hash-set: took/       { if (o_hash_set == 0) o_hash_set = $3; t_hash_set = $3 }
/sort-and-count: took/ { if (o_sort_cnt == 0) o_sort_cnt = $3; t_sort_cnt = $3 }
/hash-map: took/       { if (o_hash_map == 0) o_hash_map = $3; t_hash_map = $3 }
/^----/ {
    o_n = size / old_size
    o_nlogn = (size * log(size)) / (old_size * log(old_size))
    o_n2    = (size * size) / (old_size * old_size)
    o_n32   = (size * sqrt(size)) / (old_size * sqrt(old_size))
    r_sort_cnt = t_sort_cnt / o_sort_cnt
    r_hash_map = t_hash_map / o_hash_map
    r_hash_set = t_hash_set / o_hash_set
    printf("%9d  %8d  %8.2f  %8d  %8.2f  %8d  %8.2f  %9.0f  %9.2f  %9.2f  %9.0f\n",
           size, t_sort_cnt, r_sort_cnt, t_hash_set, r_hash_set,
           t_hash_map, r_hash_map, o_n, o_nlogn, o_n32, o_n2)
}' < on-vs-logn.raw.data

Вывод из программы довольно широк, но дает:

     Size  Sort Cnt  R:Sort-C  Hash Set  R:Hash-S  Hash Map  R:Hash-M       O(N)   O(NlogN)   O(N^3/2)     O(N^2)
   262144        34      1.00        45      1.00        61      1.00          1       1.00       1.00          1
  1048576       154      4.53       372      8.27       390      6.39          4       4.44       8.00         16
  4194304       680     20.00      1921     42.69      1834     30.07         16      19.56      64.00        256
 16777216      2970     87.35      8356    185.69      9045    148.28         64      85.33     512.00       4096
 67108864     12842    377.71     37582    835.16     46480    761.97        256     369.78    4096.00      65536
268435456     53856   1584.00    172329   3829.53    211191   3462.15       1024    1592.89   32768.00    1048576

Достаточно ясно, что на этой платформе алгоритмы хеш-набора и хэш-карты не являются O (N), и они не хуже O (N.logN), но они лучше, чем O (N ^3/2), не говоря уже о (N ²). С другой стороны, алгоритм сортировки очень близок к O (N.logN).

Вы можете применить это только к теоретическому дефициту в хэш-наборе и коду хеш-карты или к неадекватной калибровке хеш-таблиц, чтобы они использовали субоптимальный размер хеш-таблицы. Было бы интересно исследовать, какие существуют механизмы для предварительной настройки хеш-набора и хэш-карты, чтобы определить, влияет ли использование на производительность. (См. Также дополнительную информацию ниже.)

И, как раз для записи, здесь вывод из анализа script по исходным данным:

     Size  Sort Cnt  R:Sort-C  Hash Set  R:Hash-S  Hash Map  R:Hash-M       O(N)   O(NlogN)   O(N^3/2)     O(N^2)
   262144        37      1.00       107      1.00       109      1.00          1       1.00       1.00          1
  1048576       173      4.68       641      5.99       731      6.71          4       4.44       8.00         16
  4194304       745     20.14      3250     30.37      3631     33.31         16      19.56      64.00        256
 16777216      3238     87.51     14528    135.78     16483    151.22         64      85.33     512.00       4096
268435456     60396   1632.32    350305   3273.88    427841   3925.15       1024    1592.89   32768.00    1048576

Дальнейшее тестирование показывает, что изменение хеш-функций показано:

int find_using_hash(const vector<int>& input_data) {
    unordered_set<int> numbers;
    numbers.reserve(input_data.size());

и

int find_using_hashmap(const vector<int>& input_data) {
    unordered_map<int,int> counter_map;
    counter_map.reserve(input_data.size());

производит такой анализ:

     Size  Sort Cnt  R:Sort-C  Hash Set  R:Hash-S  Hash Map  R:Hash-M       O(N)   O(NlogN)   O(N^3/2)     O(N^2)
   262144        34      1.00        42      1.00        80      1.00          1       1.00       1.00          1
  1048576       155      4.56       398      9.48       321      4.01          4       4.44       8.00         16
  4194304       685     20.15      1936     46.10      1177     14.71         16      19.56      64.00        256
 16777216      2996     88.12      8539    203.31      5985     74.81         64      85.33     512.00       4096
 67108864     12564    369.53     37612    895.52     28808    360.10        256     369.78    4096.00      65536
268435456     53291   1567.38    172808   4114.48    124593   1557.41       1024    1592.89   32768.00    1048576

Ясно, что резервирование пространства для хэш-карты полезно.

Код набора хэшей довольно отличается; он добавляет элемент примерно в половину времени (в целом), а "добавляет", а затем удаляет элемент в другую половину времени. Это больше, чем нужно делать с кодом хеш-карты, поэтому он медленнее. Это также означает, что зарезервированное пространство больше, чем действительно необходимо, и может учитывать ухудшенную производительность с зарезервированным пространством.

Ответ 3

Давайте начнем с просмотра чисел для решения сортировки. В приведенной ниже таблице первый столбец - это отношение размера. Он вычисляется путем вычисления NlogN для данного теста и деления на NlogN для первого теста. Второй столбец - это отношение времени между данным тестом и первым тестом.

 NlogN size ratio      time ratio
   4*20/18 =  4.4     173 / 37 =  4.7
  16*22/18 = 19.6     745 / 37 = 20.1
  64*24/18 = 85.3    3238 / 37 = 87.5
1024*28/18 = 1590   60396 / 37 = 1630

Вы можете видеть, что между двумя отношениями существует очень хорошее совпадение, что указывает на то, что процедура сортировки действительно O (NlogN).

Итак, почему хеш-подпрограммы не работают так, как ожидалось. Простое представление о том, что извлечение элемента из хэш-таблицы - это O (1), - это чистая фантазия. Фактическое время извлечения зависит от качества функции хэширования и количества бункеров в хеш-таблице. Фактическое время извлечения составляет от O (1) до O (N), где наихудший случай возникает, когда все записи в хэш-таблице заканчиваются в одном и том же ящике. Поэтому, используя хэш-таблицу, вы должны ожидать, что ваша производительность будет находиться где-то между O (N) и O (N ^ 2), которые, по-видимому, соответствуют вашим данным, как показано ниже

 O(N)  O(NlogN)  O(N^2)  time
   4     4.4       16       6
  16      20      256      30
  64      85     4096     136
1024    1590     10^6    3274

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

Ответ 4

Я запускал программу через valgrind с разными размерами ввода, и я получил эти результаты для подсчета циклов:

with 1<<16 values:
  find_using_hash: 27 560 872
  find_using_sort: 17 089 994
  sort/hash: 62.0%

with 1<<17 values:
  find_using_hash: 55 105 370
  find_using_sort: 35 325 606
  sort/hash: 64.1%

with 1<<18 values:
  find_using_hash: 110 235 327
  find_using_sort:  75 695 062
  sort/hash: 68.6%

with 1<<19 values:
  find_using_hash: 220 248 209
  find_using_sort: 157 934 801
  sort/hash: 71.7%

with 1<<20 values:
  find_using_hash: 440 551 113
  find_using_sort: 326 027 778
  sort/hash: 74.0%

with 1<<21 values:
  find_using_hash: 881 086 601
  find_using_sort: 680 868 836
  sort/hash: 77.2%

with 1<<22 values:
  find_using_hash: 1 762 482 400
  find_using_sort: 1 420 801 591
  sort/hash: 80.6%

with 1<<23 values:
  find_using_hash: 3 525 860 455
  find_using_sort: 2 956 962 786
  sort/hash: 83.8%

Это означает, что время сортировки медленно обгоняет хэш-время, по крайней мере теоретически. С моим конкретным компилятором/библиотекой (gcc 4.8.2/libsddС++) и оптимизацией (-O2) методы сортировки и хэша будут иметь одинаковую скорость со значениями около 2 ^ 28, что находится на пределе того, что вы пытаетесь. Я подозреваю, что другие системные факторы вступают в игру при использовании большого количества памяти, что затрудняет оценку в реальном времени стены.

Ответ 5

Тот факт, что O(N) был, по-видимому, медленнее, чем O(N logN), сводил меня с ума, поэтому я решил глубоко погрузиться в проблему.

Я сделал этот анализ в Windows с Visual Studio, но я уверен, что результаты будут очень похожими на Linux с g++.

Прежде всего, я использовал Very Sleepy, чтобы найти фрагменты кода, которые наиболее полно выполняются в цикле for в find_using_hash(). Вот что я увидел:

Как вы можете видеть, верхние записи связаны со списками (RtlAllocateHeap вызывается из списка кодов). По-видимому, проблема заключается в том, что для каждой вставки в unordered_set, и поскольку ведра реализованы в виде списков, выполняется выделение для node, и это sky-ракеты продолжительность алгоритма, в отличие от сортировки, которая не делает распределение.

Чтобы быть уверенным, что это была проблема, я написал ОЧЕНЬ простую реализацию хеш-таблицы без выделения, и результаты были гораздо более разумными:

Таким образом, коэффициент log N, умножающий N, который в вашем самом большом примере (т.е. 1<<28) равен 28, по-прежнему меньше, чем "постоянный" объем работы, необходимый для распределения.

Ответ 6

Здесь уже много замечательных ответов, но это особый вопрос, который, естественно, генерирует много действительных ответов.

И я пишу, чтобы дать ответ с математической точки зрения (что трудно обойтись без LaTeX), потому что важно исправить неподтвержденное заблуждение, что решение данной проблемы с хэшами представляет собой проблему, которая является "теоретически" , O(n), но как-то "практически" хуже, чем O(n). Такая вещь была бы математической невозможностью!

Для тех, кто хочет продолжить эту тему более подробно, я рекомендую это книгу, которую я сохранил и купил как очень бедную среднюю школу студент, и который вызвал мой интерес к прикладной математике для многих грядущие годы, существенно меняя исход моей жизни: http://www.amazon.com/Analysis-Algorithms-Monographs-Computer-Science/dp/0387976876

Чтобы понять, почему проблема не является "теоретически" O(n), необходимо отметить, что базовое предположение также неверно: неверно, что хеши являются "теоретически" структурой данных O(1).

Противоположное на самом деле верно. Хэши в чистом виде являются "практически" структурой данных O(1), но теоретически все еще являются структурой данных O(n). (Примечание: в гибридной форме они могут достичь теоретической производительности O(log n).)

Следовательно, решение в лучшем случае по-прежнему остается проблемой O(n log n), так как n приближается к бесконечности.

Вы можете начать отвечать, но всем известно, что хэши O (1)!

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

Для любого приложения (независимо от n до тех пор, пока n известно раньше времени - то, что они называют "фиксированным", а не "произвольным" в математических доказательствах), вы можете создать свою хеш-таблицу в соответствии с приложения и получить производительность O(1) в рамках ограничений этой среды. Каждая чистая структура хэширования предназначена для того, чтобы хорошо работать в пределах априорного диапазона размеров набора данных и с предполагаемой независимостью ключей от хэш-функции.

Но когда вы позволяете n приближаться к бесконечности, как того требует определение Big- O, тогда ведра начинают заполняться (что должно происходить по принципу голубины), а всякая чистая структура хэша распадается на Алгоритм O(n) (нота Big-O здесь игнорирует постоянный множитель, который зависит от количества ведер).

Вау! Там много в этом предложении.

И поэтому в этот момент, а не в уравнениях, более подходящая аналогия была бы более полезной:

Очень точное математическое понимание хэш-таблиц получается путем представления шкафа для хранения, содержащего 26 ящиков, по одному для каждой буквы алфавита. Каждый файл хранится в ящике, который соответствует первой букве в имени файла.

• "Хэш-функция" - это операция O(1), смотрящая на первую письмо.

• Хранение - это операция O(1): размещение файла внутри ящика для этой буквы.

• И пока в каждом ящике не более одного файла, поиск - это операция O(1): открытие ящика для этой буквы.

В рамках этих конструктивных ограничений эта структура хэша O(1).

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

По сравнению с бросанием всех файлов в одну огромную кучу, средняя производительность в целом примерно в 1/26-м раза больше времени. Но помните, математически, нельзя сказать O(n/26), потому что обозначение O(n) по определению не учитывает постоянные факторы, которые влияют на производительность, а только алгоритмическую сложность как функцию n. Поэтому, когда ограничения дизайна превышены, структура данных O(n).