Доброго времени суток. Решил я посмотреть есть ли причины использовать std::find_if (за одну такую фразу, думаю, многие меня побьют =))
Сделал тестовый пример. Положил в vector 10000 строк "test" и сделал два варианта поиска:
find_if


поиск перебором

при m_count = 1000, find_if отработал за 4 секунды, а поиск перебором аж за 10. за счет чего так получается? Может я конечно многого не знаю, но я считал, что find_if также должен пройтись по всем элементам массива + ведь еще "тратится время" на вызов функтора. а в результате имеем, что быстрее. В чем причина?

Можно глянуть исходники STL

потому как std::find_if() не ищет тупым перебором.
а вообще, STL не зря так назвали! и не идиоты пишут стандартные алгоритмы!


Это сообщение отредактировал(а) andrew_121 - 26.2.2010, 14:11

А разве возможно искать что то не в отсортированном массиве, не используя перебор?  

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

xTr1m, а почему ты решил что узкое место именно перебор? может тормоз сравнение?!

Добавлено через 1 минуту и 17 секунд
ЗЫ какова смысловая нагрузка "for(int y=0; y<m_count; ++y)" ?

Смысловая нагрузка

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

А сравнение то везде одинаково. собственно бог с ним, со сравнением. меня интересует, что же такое происходит во время find_if, может он просто не по всем элементам проходит =)))
Чего исходник пока найти не могу

Искать в неотсортированном массиве быстрее чем за линейное время не возможно. Используя бинарный поиск мы за log N(N - длина массива) можем найти элемент но массив должен быть отсортирован.

я ставил акцент на слово - тупым.

вот код из STL поставляемой с gcc-4.5.0

хороша оптимизация?  

О, спасибо. С ходу не осилил, приду домой - буду курить.

Прибавь к этому ещё два небольших момента.


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


Код функтора встраивается и оверхеда на его вызов нет.


Цикл сам по себе штука медленная, поэтому для оптимизации их разворачивают. Где-то это делает умный компилятор, где-то разработчики time critical библиотек общего назначения (как в данном случае), в отдельных грустных случаях разворачивать цикл приходится самому программисту.
В данном случае на один шаг цикла происходит четыре операции сравнения.

Может за счет того, что твой Functor всегда возвращает false? Компилятор вообще имеет право вообще удалить вызов и find_if и охватывающего цикла

xvr,  надеюсь он так не самовольничает =)

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

Это сообщение отредактировал(а) Леопольд - 26.2.2010, 18:29

Почему бы нет - все функции inline, не имеют побочных эффектов, функтор константа. Вполне может все свернуть.
Вот если привести функтор в соотвествие с тем, что было написано для 2й версии, тогда можно сравнивать