Лучший алгоритм для проверки сортировки вектора

Is there something faster than a loop checking that v[i]<=v[i+1] ?

Нет.

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

Is there something faster than a loop checking that v[i]<=v[i+1] ?

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

Or is it actually better to just call sort every time (though the "v is already sorted" case is quite common) ?

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

Чтобы проверить сортировку, вы должны проверить каждый элемент. Таким образом, v [i] <= v [i + 1] - самая быстрая из возможных проверок.

Is there something faster than a loop checking that v[i]<=v[i+1] ?

Нет.

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

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

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

:-)

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

Как отмечали другие, предикатом для определения отсортированного состояния является O (n). Но из-за вашего упоминания о сортированном флаге я задаюсь вопросом, не нужно ли вам что-то вроде этого:

Базовые библиотеки нашего приложения включают в себя класс контейнера, членство в котором можно запросить. Вот краткий набросок:

class ObjList {
public:
    ObjList() {};
    ~ObjList() {};

    bool isMember(const Item *);
    void add(const Item *, bool sort = false);

private:

    unsigned int last_sorted_d;

    bool sorted_d;
    unsigned int count_d;
    Item *store_d;
};

isMember () использует двоичный поиск по отсортированный диапазон элементов, а затем линейный поиск элементов после отсортированного диапазона. Вставка может запускать сортировку элементов или нет, по выбору программиста. Например, если вы знаете, что будете добавлять тысячи элементов в плотный цикл, не выполняйте сортировку до окончательной вставки.

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

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

Рассмотрим несколько ядер ЦП

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

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

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

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

Если при вставке элементов вы используете двоичный поиск, чтобы найти точку вставки, то он никогда не упорядочивается.

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

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

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