Установить поиск члена против использования поиска в списке

Question

Поскольку элементы в контейнере набора стандартной библиотеки отсортированы, будет ли использование элемента find в наборе работать быстрее, чем при использовании алгоритма поиска для тех же элементов в отсортированном списке?

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

Answer 1

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

Сортированный массив / вектор можно искать в O(log n) с помощью бинарного поиска. К сожалению, поскольку связанный список не поддерживает произвольный доступ, этот же метод нельзя использовать для поиска в отсортированном связанном списке в O(log n).

Answer 2

На самом деле стандарт: std::set::find() имеет сложность O(log n), где n - количество элементов в наборе. std::find(), с другой стороны, является линейным по длине диапазона поиска.

Если ваш общий диапазон поиска оказывается отсортированным и имеет произвольный доступ (например, отсортированный вектор), то вы можете использовать std::lower_bound() для эффективного поиска элемента (или, скорее, позиции).

Обратите внимание, что std::set поставляется со своим собственным членом - lower_bound(), который работает так же. Наличие позиции вставки может быть полезно даже в set, потому что insert() с правильным подсказкой имеет сложность O(1).

Answer 3

Я нашел эту статью полезной по теме. http://lafstern.org/matt/col1.pdf

Вы можете пересмотреть свои требования только для «списка» против «набора». Согласно этой статье, если ваша программа состоит в основном из набора вставок в начале, а затем после этого, только сравнения с тем, что вы сохранили, тогда вам лучше добавить все в вектор, используя std :: sort ( vector.begin (), vector.end ()) один раз, а затем с использованием lower_bound. В моем конкретном приложении я загружаю из текстового файла список имен при запуске программы, а затем во время выполнения программы я определяю, есть ли пользователь в этом списке. Если они есть, я что-то делаю, иначе я ничего не делаю. Другими словами, у меня была одна отдельная фаза вставки, затем я отсортировал, затем после этого я использовал std :: binary_search (vector.begin (), vector.end (), std :: string username), чтобы определить, является ли пользователь в списке.

Answer 4

set::find имеет сложность O (log (n)), в то время как std::find имеет сложность O (n). Это означает, что std::set::find() асимптотически быстрее, чем std::find(std::list), но это не значит, что оно быстрее для любого конкретного набора данных или для любого конкретного поиска.

Answer 5

Обычно можно ожидать, что операция find будет быстрее на Set, чем на List, поскольку списки имеют линейный доступ (O (n)), в то время как наборы могут иметь почти постоянный доступ для HashSets (O (1)) или логарифмический доступ для TreeSets (O (log n)).