вопросы об алгоритмах поиска и сортировки

Question

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

• Изменится ли поведение поиска, если данные не отсортированы по сравнению с данными, которые отсортированы?

• Как я могу узнать, лучше ли использовать std::sort() на векторе, а не, возможно, скопировать вектор в уже отсортированный набор? Это всего лишь пример. Я надеялся найти в Интернете некоторые объяснения, какие способы лучше всего подходят для поиска или сортировки, но я не смог.

• Как я могу адаптировать поведение алгоритмов поиска и сортировки, чтобы сделать его более эффективным?

Answer 1

Изменится ли поведение поиска, если данные не отсортированы по сравнению на тот, который отсортирован?

Зависит. Если вы обращаетесь к своим данным в векторе / массиве по позициям, улучшения производительности нет, и нет необходимости ни в сортировке.

Поиск может быть выполнен линейно , двоичным , клавишами и хэш-функцией .

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

Двоичный поиск имеет сложность O (log N), которая, вероятно, является наилучшей, которую вы можете получить ... Я думаю, в Теория информации . Требуется предварительно отсортировать контейнер. Это полезно для свободного поиска в одном контейнере.

A std::set (и его двоюродный брат std::map) внутренне использует дерево, что также усложняет поиск O (log N). Полезно, если вы ищете по ключам, а не по некоторым критериям ваших товаров. Недостаток заключается в том, что при построении он выполняется немного медленнее (всегда сохраняйте сортировку), чем заполнять вектор, а затем сортировать его.

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

Как видите, выбор типа контейнера зависит от того, как вы собираетесь обрабатывать ваши данные. Выберите тот, который соответствует вашим требованиям.

Как я могу узнать, лучше ли вместо этого использовать std :: sort () для вектора возможно скопировать вектор в уже отсортированный набор?

std::sort меняет контейнер, поэтому результат, очевидно, сортируется. Если вам нужен оригинальный неупорядоченный контейнер, сделайте копию и отсортируйте ее. Сортировка всего контейнера лучше, чем «вставка-элемент-так-контейнер-всегда-сортируемый» для всех элементов, особенно с вектором (много перераспределений памяти); процесс заполнения набора / карты может быть не таким медленным.

Как мне адаптировать поведение алгоритмов поиска и сортировки сделать его более эффективным?

Мне не понятно, что вы имеете в виду. Но «цель оправдывает средства». Опять же, выберите контейнер, который лучше всего подходит для вашей обработки данных.

Answer 2

Изменится ли поведение при поиске, если данные не отсортированы по сравнению с отсортированными?

Нет. Это зависит от выбранного вами алгоритма. Общий поиск std::find - это O (n), двоичный поиск std::lower_bound - это O (log n), но он работает только в отсортированных диапазонах.

Как я могу узнать, лучше ли использовать std :: sort () для вектора, а не, возможно, для копирования вектора в уже отсортированный набор? Это всего лишь пример. Я надеялся найти в Интернете некоторые объяснения, какие способы лучше всего подходят для поиска или сортировки, но я не смог.

Вы можете написать эталон и измерить. Вы можете отсортировать std::vector (без дублированных элементов), скопировав его в std::set, который поддерживает внутренний порядок сортировки. std::set обычно реализуется как красно-черное дерево и имеет в целом высокую фрагментацию памяти в отличие от смежного std::vector. Так что легко предсказать результат. Александр Степанов обсуждает (если я правильно помню) этот конкретный пример в своих лекциях, доступных на YouTube.