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

Многие объяснения уже присутствуют, чтобы объяснить, как это происходит и как это исправить, но вы также должны следовать рекомендациям, чтобы избежать NullPointerException вообще.

См. также: A хороший список лучших практик

Я бы добавил, очень важно, хорошо использовать модификатор final. Использование "окончательной" модификатор, когда это применимо в Java

Сводка:

  1. Используйте модификатор final для обеспечения хорошей инициализации.
  2. Избегайте возврата null в методы, например, при возврате пустых коллекций.
  3. Использовать аннотации @NotNull и @Nullable
  4. Быстрое завершение работы и использование утверждений, чтобы избежать распространения нулевых объектов через все приложение, когда они не должен быть пустым.
  5. Сначала используйте значения с известным объектом: if("knownObject".equals(unknownObject)
  6. Предпочитают valueOf() поверх toString ().
  7. Используйте null safe StringUtils StringUtils.isEmpty(null).

18
задан Lightness Races with Monica 11 October 2011 в 13:20
поделиться

11 ответов

Рассматривают Несколько Ядер CPU

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

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

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

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

16
ответ дан 30 November 2019 в 05:39
поделиться

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

0
ответ дан 30 November 2019 в 05:39
поделиться

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

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

0
ответ дан 30 November 2019 в 05:39
поделиться

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

0
ответ дан 30 November 2019 в 05:39
поделиться

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

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

1
ответ дан 30 November 2019 в 05:39
поделиться

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

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

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

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

5
ответ дан 30 November 2019 в 05:39
поделиться

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

6
ответ дан 30 November 2019 в 05:39
поделиться

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

2
ответ дан 30 November 2019 в 05:39
поделиться

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

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

28
ответ дан 30 November 2019 в 05:39
поделиться

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

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

:-)

20
ответ дан 30 November 2019 в 05:39
поделиться
std::adjacent_find(v.begin(), v.end(), std::greater<type>()) == v.end()
12
ответ дан 30 November 2019 в 05:39
поделиться
Другие вопросы по тегам:

Похожие вопросы: