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

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

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

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

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

Ответ 1

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

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

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

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

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

Ответ 2

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

Нет.

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

Ответ 3

Лучший способ - использовать std::is_sorted:

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

: -)

Ответ 4

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

Ответ 5

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

Ответ 6

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

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

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

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

Нет.

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

Ответ 10

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

Ответ 11

Как отмечали другие, предикат для определения отсортированного состояния - это 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() использует двоичный поиск в отсортированном диапазоне элементов, а затем линейный поиск элементов после отсортированного диапазона. Вставка может вызвать некоторые элементы или нет, в соответствии с выбором программиста. Например, если вы знаете, что вы будете добавлять тысячи элементов в узком цикле, не сортируйте до окончательной вставки.

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

Ответ 12

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

Ответ 13

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