O (NLogN) показывает лучшую производительность, чем O (N), если используется unordered_set - PullRequest
Новая
       26

O (NLogN) показывает лучшую производительность, чем O (N), если используется unordered_set

1 голос
/ 29 мая 2019 
//Time sorting O(nlogn) + binary search for N items logN = 2NLogN = 
//Time: O(NLogN). 
//space - O(1).
bool TwoSum::TwoSumSortAndBinarySearch(int* arr, int size, int sum)
{
    sort(arr, arr + size);

    for (int i = 0; i < size; i++)
    {
        if (binary_search(arr + i + 1, arr + size, sum - arr[i]))
            return true;
    }
    return false;
}


//Time: O(N) as time complexity of Add and Search in hashset/unordered_set is O(1).
//Space: O(N)
bool TwoSum::TwoSumHashSet(int* arr, int size, int sum)
{
    unordered_set<int> hash;
    for (int i = 0; i < size; i++)
    {
        if (hash.find(sum - arr[i]) != hash.end())
            return true;
        hash.insert(arr[i]);
    }
    return false;
}

int* TwoSum::Testcase(int size)
{
    int* in = new int[size];
    for (int i = 0; i < size; i++)
    {       
        in[i] = rand() % (size + 1);//random number b/w 0 to N.
    }
    return in;
}

int main()
{
    int size = 5000000;
    int* in = TwoSum::Testcase(size);

    auto start = std::chrono::system_clock::now();//clock start 
    bool output = TwoSum::TwoSumHashSet(in, size, INT_MAX);
    auto end = std::chrono::system_clock::now();//clock end

    std::chrono::duration<double> elapsed_seconds = end - start;
    cout << "elapsed time: " << elapsed_seconds.count() << "s\n";   
}

Я измерил производительность двух вышеупомянутых методов, где я хотел бы найти проблему TwoSum.В первом подходе я сортирую массив, а затем использую бинарный поиск.Время: O (NLogN).пробел - O (1).

Во втором подходе используется unordered_set , сложность которого в среднем постоянна, наихудший случай линейен по размеру контейнера.

// Время: O (N), поскольку сложность времени Add и Search в hashset / unordered_set равна O (1).// Пробел: O (N)

Вот три времени выполнения этих двух методов

TwoSumSortAndBinarySearch --------------- TwoSumHashSet

  1. 8.05 ---------------------------------------15.15
7,76 --------------------------------------- 14,47
7.74 --------------------------------------- 14.28

Итак, ясно, что TwoSumSortAndBinarySearch работает определенно лучше, чем unordered_Set.

Какой подход предпочтительнее и предложен в реальном сценарии и почему?

1 Ответ

0 голосов
/ 29 мая 2019

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

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

...