Основа сравнения двух алгоритмов сводится к простому факту, как соотносятся их временные и пространственные сложности. Существуют разные способы их выражения, наиболее часто используемым из них является O-нотация(Big-Oh). Короче говоря, O-нотация говорит нам о сложности в наихудшем случае. Но это не обязательно преобразуется в реальные обстоятельства, когда каждый раз это не самый худший случай.
Хотя анализ сложности — отличный инструмент, он часто не говорит нам всей правды. Сегодня мы будем сравнивать реальную эффективность структур данных set и map при сравнении с алгоритмом сортировки.
Наборы против сортировки:
Многие проблемы можно решить либо с помощью наборов, либо с помощью сортировки, и одной из таких проблем является определение количества уникальных элементов в заданных данных.
Одним из способов решения этой проблемы было бы вставить каждый элемент в set и вернуть размер set. Здесь мы также можем использовать unordered_set, потому что порядок элементов не имеет значения. Другой способ — отсортировать заданный вектор и подсчитать количество вхождений, в которых два последовательных элемента различны. Временная сложность обоих решений (с набором или с сортировкой) составляет O(n log n).
Давайте посмотрим, как они сравниваются.
Мы видим, что решение той же задачи с набором занимает более чем в два раза больше времени, чем если бы мы использовали unordered_set. И это примерно в десять раз медленнее по сравнению с сортировкой. Несмотря на то, что они имеют одинаковую временную сложность, время, затрачиваемое на обработку, сильно различается, и оно будет только увеличиваться, если мы увеличим размер данных.
Карты против сортировки:
Карты используются для хранения пар ключ-значение и очень удобны в использовании. Здесь мы будем генерировать несколько случайных чисел и вычислять частоту каждого числа. Эту задачу также можно решить с помощью векторов. Временная сложность обоих решений составляет O(n log n).
Давайте посмотрим, как они сравниваются.
Мы видим, что unordered_map примерно в три раза быстрее, чем map, и это тоже ожидаемо из-за O(1) на операцию в первом случае по сравнению с O (log n) за операцию в последнем. Но все же мы видим, что использование отсортированных векторов примерно в 25 раз быстрее, чем unordered_map, и примерно в 87 раз быстрее, чем использование карты.
Почему?
Мы видим схожие тенденции как при сравнении наборов с отсортированными векторами, так и карт с отсортированными векторами. В обоих случаях отсортированный вектор значительно превосходит результаты. Но почему это так?
Возможный ответ заключается в том, что постоянные факторы, которыми мы пренебрегаем при расчете временной сложности set & map, намного больше, чем те, которые присутствуют при сортировке. Кроме того, сортировка является очень простой вычислительной операцией, в то время как набор и отображение составляются с использованием очень сложных базовых структур данных (например, деревьев и пар RB) и, следовательно, они более дорогие.
Спасибо за прочтение статьи. Надеюсь, вам было интересно и познавательно. Следите за другими такими статьями. Для ежедневных обновлений кода вы можете следить за мной в моем Instagram (@utsavsingh899), где я ежедневно публикую код.
