O(N) algorithm slower than O(N logN) algorithm

Question

In array of numbers, each number appears even number of times, and only one number appears odd number of times. We need to find that number (question was previously discussed on Stack Overflow).

Here is a solution that solves the question with 3 different methods — two methods are O(N) (hash_set and hash_map), while one is O(NlogN) (sorting). However, profiling for arbitrarily large input shows that sorting is faster, and gets more and more faster (in comparison) as input increases.

What is wrong with implementation or complexity analysis, why is O(NlogN) method faster?

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

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;

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_hash(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_hashmap(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_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("hash-set:",std::bind(find_using_hash, input_data));
        execute_and_time("sort-and-count:",std::bind(find_using_sort_and_count, input_data));
        execute_and_time("hash-map:",std::bind(find_using_hashmap, input_data));

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

Profiling results:

sh$ g++ -O3 -std=c++11 -o main *.cc
sh$ ./main 
For input_size 262144:
hash-set: returns 123454321
hash-set: took 107 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 37 milliseconds
hash-map: returns 123454321
hash-map: took 109 milliseconds
--------------------------
For input_size 1048576:
hash-set: returns 123454321
hash-set: took 641 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 173 milliseconds
hash-map: returns 123454321
hash-map: took 731 milliseconds
--------------------------
For input_size 4194304:
hash-set: returns 123454321
hash-set: took 3250 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 745 milliseconds
hash-map: returns 123454321
hash-map: took 3631 milliseconds
--------------------------
For input_size 16777216:
hash-set: returns 123454321
hash-set: took 14528 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 3238 milliseconds
hash-map: returns 123454321
hash-map: took 16483 milliseconds
--------------------------
For input_size 268435456:
hash-set: returns 123454321
hash-set: took 350305 milliseconds
sort-and-count: returns 123454321
sort-and-count: took 60396 milliseconds
hash-map: returns 123454321
hash-map: took 427841 milliseconds
--------------------------

Addition

Fast solution with xor suggested by @Matt is of course out of contest — under 1 sec for worst case in example:

int find_using_xor(const vector<int>& input_data) {
    int output = 0;
    for(const int& value : input_data) {
        output = output^value;
    }
    return output;
}
For input_size 268435456:
xor: returns 123454321
xor: took 264 milliseconds

but the question still stands — why is hash so inefficient compared to sorting in practice despite theoretical algorithmic complexity advantage?

Answer 1

It really depends on hash_map/hash_set implementation. By replacing libstdc++'s unordered_{map,set} with Google's dense_hash_{map,set}, and it is significantly faster than the sort. The drawback for dense_hash_xxx is that they require there are two values for key that will never be used. See their document for details.

Another thing to remember is: hash_{map,set} usually does a lot of dynamic memory allocation/deallocation, so it is better to use a better alternative to libc's default malloc/free, e.g. Google's tcmalloc or Facebook's 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
--------------------------

Code:

#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;
}