Какой алгоритм стоит найти STL?

Question

Я только что создал пользовательскую функцию поиска для строк на карте. Я разработал какой-то алгоритм линейного поиска (который я узнал позже) и не был удовлетворен скоростью функции. Поэтому я искал более быструю функцию и нашел собственную функцию карты: map :: find.

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

В другом примере функция STL найти была также намного быстрее, чем другая линейная функция, которую я использую.

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

Также как узнать алгоритмы, лежащие в основе этих основных функций? Есть ли список или какая-то база данных, чтобы узнать об этом?

Спасибо за все ваши ответы! Я поддержал лучшие ответы и принял ответ Макса Либберта, потому что он был самым подробным.

Paul :)

Answer 1

Я разработал какой-то алгоритм линейного поиска (который я узнал позже) и не был удовлетворен скоростью функции. Поэтому я искал более быструю функцию и нашел собственную функцию карты: map::find.

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

std::map предназначен для хранения данных, отсортированных по мере их вставки в контейнер. Это одна из его главных задач. Это также причина того, что вы должны определить какой-то частичный заказ для данных, которые вы ввели в std::map.

Это означает, что каждая вставка занимает немного больше времени, чем вставка в другие контейнеры (вставки в std::list - как только вы имеете точку вставки - например, является O (1), как добавление к std::vector или добавления/добавляя слева до std::deque). Но поиск гарантированно будет использовать двоичный поиск (или, скорее, до navigate the red-black tree behind the std::map (в разделе «Предварительная или разумная оптимизация»)).

В другом примере функция поиска STL была намного быстрее, чем другая линейная функция, которую я использую.

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

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

std::find способен обрабатывать несортированные данные, поэтому его необходимо реализовать как линейный поиск (сравнить std::binary_search/std::lower_bound). Но std::find разрешено скрывать и разворачивать петли, сравнивать несколько предметов за раз (если элементы небольшие, и особенно если они являются примитивными типами, которые поддаются низкоуровневому разгону бит) и т. Д.

Также как узнать алгоритмы, лежащие в основе этих основных функций? Есть ли список или какая-то база данных, чтобы узнать об этом?

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

Answer 2

std::map хранит свои элементы в отсортированном порядке (почти всегда в самобалансирующемся бинарном дереве поиска).

std::map::find использует это и использует dichotomic search.

Answer 3

Реализация хорошо, зависит от реализации.

Но насколько общие классы сложности идти, вы можете проверить, например, эту страницу с обзором для общих методов STL:

http://www.cplusplus.com/reference/stl/

Answer 4

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

Это, как говорится, есть свободные реализации STL. Вы можете посмотреть на их код. Например, STL Port.

Также как найти алгоритмы, лежащие в основе этих основных функций? Есть ли список или какая-то база данных, чтобы узнать об этом?

Ну, есть Dictionary of Algorithms and Data Structures, но это немного грязно.

Answer 5

Алгоритмы STL почти всегда быстрее, чем все, что вы могли бы написать, потому что оно делает много оптимизаций под обложками. Кроме того, быстрее использовать итераторы, чем оператор [], при повторении через векторный или другой контейнер с произвольным доступом, поскольку накладные расходы меньше.

Вы должны проверить книги Скотта Мейерса Эффективное C++ Third Edition и Effective STL. (Материал в More Effective C++ содержится в 3-м выпуске Effective C++.)