Почему std :: find (s.begin (), s.end (), val) в 1000 раз медленнее, чем s.find (val) для набора <int>s? - PullRequest
Новая
       41

Почему std :: find (s.begin (), s.end (), val) в 1000 раз медленнее, чем s.find (val) для набора <int>s?

0 голосов
/ 28 августа 2018

Я недавно начал переучивать C ++, поскольку я не программировал на C ++ более десяти лет. Я редко использовал STL, даже когда работал в SGI, и хочу освоить его. Я заказал книгу, и в настоящее время я использую разные онлайн-уроки.

В одном учебном пособии было введено std::find(begin(),end(),value), и я был шокирован тем, насколько медленно он работал в тестовом коде, который я написал. После некоторых проб и ошибок я обнаружил, что s.find(value) - это то, что я должен использовать.

Почему первая находка в коде так резко медленная? 

set<int> s;

for (int i = 0; i < 100000; i++)
    s.insert(rand());

for (int i = 0; i < 10000; i++) {
    int r = rand();

    //first find is about 1000x slower than the next one
    auto iter1 = std::find(s.begin(), s.end(), r);
    auto iter2 = s.find(r);
}

РЕДАКТИРОВАТЬ: добавлено время эксперимента результаты

@ juanchopanza спросил о сроках в комментариях, поэтому я рассчитал std::find() на множествах, списках, векторах и set.find() (Я только измерил находку - разница между прогонами была ниже 10%)

Vector работает намного лучше, чем List или Set, но специализированный поиск по множеству выигрывает с большими наборами данных. 

 Elements  Vector     List      Set    | Set.Find()
      10   0.0017    0.0017    0.0020  |  0.0017
     100   0.0028    0.0051    0.0120  |  0.0019
    1000   0.0105    0.0808    0.1495  |  0.0035
   10000   0.0767    0.7486    2.7009  |  0.0068
  100000   0.2572    2.4700    6.9636  |  0.0080
 1000000   0.2674    2.5922    7.0149  |  0.0082
10000000   0.2728    2.6485    7.0833  |  0.0082

Ответы [ 3 ]

0 голосов
/ 28 августа 2018

Чтобы расширить мой комментарий.

Потому что set::find имеет больше информации об элементах в диапазоне поиска. Он знает, что оно (вероятно) реализовано в виде отсортированного двоичного дерева, и может искать его в логарифмическом времени.

std::find, с другой стороны, получает только два двунаправленных итераторов, поэтому лучшее, что он может сделать, это просто цикл for. Если бы набор возвратил итератор с произвольным доступом , std::find также был бы логарифмическим. РЕДАКТИРОВАТЬ: Исправил мои неправильные претензии.

0 голосов
/ 29 августа 2018

Первая причина в том, что std::find указан в терминах линейного поиска. Между тем, std::set.find указывается в терминах поиска логарифмического времени.

Но если вы замените std::find на std::equal_range, который будет выполнять бинарный поиск, вы обнаружите, что он медленный, как std::find.

Так что я отвечу на вопрос лучше, чем вы:

Почему std::equal_range смехотворно медленен на итераторах множества?

Ну, на самом деле нет веской причины.

std::set итераторы - это двунаправленные итераторы. Это означает, что они позволяют идти вперед на один шаг или назад на один шаг.

std::equal_range на двунаправленных итераторах чрезвычайно медленный , потому что он должен шаг за шагом проходить через диапазон.

Метод std::set.find, с другой стороны, использует древовидную структуру std::set, чтобы быстро найти элемент. По сути, он может очень быстро получить середины диапазона.

C ++ не раскрывает эту древовидную структуру при доступе к std::set через его итераторы. Если бы это было так, то могла бы существовать такая операция, как std::somewhere_between( start, finish ), которая за O (1) время получала бы итератор между start и finish, возвращая finish, если такого итератора не существует.

Такая операция на самом деле очень дешева при реализации древовидной структуры std::set.

Однако эта операция не существует. Так что std::equal_range( begin(set), end(set) ) смехотворно медленный.

Возможно, отсутствие такой операции, как std::somewhere_between для отсортированных ассоциативных контейнеров, делает некоторые реализации set / map более эффективными; многие использовали специальные узлы для замены некоторых конечных случаев. И, возможно, вам потребуется доступ к этому специальному узлу для эффективного бинарного поиска в дереве.

Но я серьезно сомневаюсь, что эта операция не стоит того. С помощью этой операции вы можете эффективно работать в подразделе std::set или std::map; без этого у тебя ничего нет.

0 голосов
/ 28 августа 2018

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

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

...