Лучший алгоритм, чтобы проверить, отсортирован ли вектор

Question

Как лучше всего проверить, отсортирован ли std::vector? Есть ли что-то быстрее, чем проверка цикла v[i]<=v[i+1]? Это быстрее / чище с итераторами? Или на самом деле лучше просто каждый раз вызывать sort (хотя случай "v уже отсортирован" довольно распространен)?

Можно смело предположить, что вектор содержит только POD, обычно float с, а иногда double с и int с.

Размер вектора нетривиален (обычно несколько тысяч элементов), но не является экстремальным (не размером в гигабайт).

• в некоторых случаях мы сортируем вектор сразу после этого, однако в других случаях мы этого не делаем (это случай ошибки нашего алгоритма).
• мы уже используем флаг "IsSorted", когда это возможно.

Answer 1

Есть ли что-то быстрее, чем цикл проверка, что v [i] <= v [i + 1]? </p>

номер

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

Answer 2

Лучше всего использовать std::is_sorted:

is_sorted(v.begin(), v.end())

: -)

Answer 3

Рассмотрим несколько ядер процессора

Это зависит от вашей платформы и количества предметов в векторе. Вы должны были бы сравнить, чтобы найти лучшее.

Невозможно ответить: есть ли что-то быстрее, чем цикл, проверяющий, что v [i] <= v [i + 1]? <br> С: Нет.

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

Вероятно, лучше сделать это через библиотечную функцию, а не реализовывать ее самостоятельно. Новые версии библиотек будут эксплуатировать парализм. Так что, если вы пойдете на std :: sort, который вы, вероятно, обнаружите при сборке с использованием новых реализаций STL, они выполнят эту операцию параллельно, и вам не придется об этом беспокоиться. Я не знаю, есть ли уже доступные версии STL, которые уже делают это, но стоит придерживаться библиотечных функций, чтобы при обновлении до версии, которая делает это, эта оптимизация была для вас без каких-либо изменений. .

Answer 4

std::adjacent_find(v.begin(), v.end(), std::greater<type>()) == v.end()

Answer 5

Конечно, я ничего не знаю о вашей проблемной области, поэтому, пожалуйста, не обращайте на меня внимания, если то, что я говорю, не относится к делу, но мне кажется, что если мне требуется, чтобы коллекция всегда сортировалась при каждом обращении к ней, естественно не отсортированная Коллекция вроде vector<T> может быть не лучшим выбором.

Answer 6

Есть ли что-то быстрее, чем цикл, проверяющий, что v [i] <= v [i + 1]? </p>

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

Или на самом деле лучше каждый раз просто вызывать sort (хотя случай "v уже отсортирован" довольно распространен)?

Помните, что наихудшее поведение при быстрой сортировке происходит, когда список уже отсортирован (а точка выбора выбрана неправильно). Чтобы избежать такого поведения, вы можете использовать std :: stable_sort в качестве замены.

Answer 7

C ++ - 11 содержит is_sorted в .

Answer 8

Если вы ожидаете, что список будет очень близок к сортировке, может быть полезно попробовать модифицировать сортировку вставки . Если список уже отсортирован, он просто делает один проход и сообщает вам об этом. Если список почти отсортирован, он будет отсортирован очень быстро. Если список не отсортирован, прекратите сортировку после некоторого количества перестановок и переключитесь на быструю сортировку (или stable_sort).

Answer 9

Есть ли что-то быстрее, чем цикл, проверяющий, что v [i] <= v [i + 1]? </p>

номер

Однако, если вы собираетесь выполнить проверку, чтобы решить, следует ли сортировать вектор, вам может быть лучше просто всегда сортировать , если , вы используете правильный алгоритм сортировки, то есть std :: stable_sort и не std :: sort.

Answer 10

Если ваша реализация Стандартной библиотеки C ++ содержит alogrithm is_sorted (), это лучший вариант.