Доброго времени суток. Решил я посмотреть есть ли причины использовать 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й версии, тогда можно сравнивать

Пошел еще немного дальше


find_if отрабатывает на порядок быстрее (вектор заполнен интами от 0 до 1000000)!!!!


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

Это сообщение отредактировал(а) xTr1m - 26.2.2010, 23:25

посмотрел я файл <algorithm> и там такое

я что то не понял, STL везде разный? это я про

кстати, разница во времени какая?

Так в том то и дело, что та разница, которую я указал в первом посте и достигается за счет это (микрософтской) реализации find_if, и в ней нет оптимизации цикла,
так за счет чего тогда она выигрывает? =))

детский сад  
ms версия содержит средства для отладки, что-бы их отключить, нужно до включения заголовочных файлов STL написать - 


Добавлено через 3 минуты и 50 секунд

возможно это из-за того, что во время работы find_if - данные уже "горячие", то-есть лежат в кэше, а при первом проходе find - они "холодные", из-за чего происходит большое количество кэш промахов

Так в том то и дело, что та разница, которую я указал в первом посте и достигается за счет это (микрософтской) реализации find_if, и в ней нет оптимизации цикла,
так за счет чего тогда она выигрывает? =))

Так в том то и дело, что та разница, которую я указал в первом посте и достигается за счет это (микрософтской) реализации find_if, и в ней нет оптимизации цикла,
так за счет чего тогда она выигрывает? =))

Попробуй сравнить свой исходный код с этим:

в общем то сейчас не особо заметна разница (мерил на глаз без времени)

в общем то сейчас не особо заметна разница (мерил на глаз без времени)

ты code review проводил? 

andrew_121, твои громкие и при этом столь же голословные заявления уже порядком поднадоели

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

ссылку, или небыло

в одном соврал. не недавно это было.
http://forum.vingrad.ru/forum/topic-272092...родействие.html

и каким образом ты сделал такие выводи по этой теме?



 

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

зачем себя цитировать? нелепо выглядит.

andrew_121, давай тесты качества бинарного кода который генерит msvc юзая STL майкрософта VS g++ юзая STL gcc
разумеется с учетом различных опций компиляции, в том числе дебаг-версии

Это сообщение отредактировал(а) GoldFinch - 1.3.2010, 19:09

GoldFinch,
1. нужно утвердить какой-то код.
2. каким образом сравнивать бинарники?(или же асмовый выход?)

andrew_121, 
1. не  вижу принципиальной разницы какой код сравнивать, лишь бы там было побольше STL и поменьше CRT, других либ и пользовательского кода.
2. асм вывод компилятора, или дизасм - имхо без разницы, выглядит почти одинаково, хотя лучше бы Intel синтаксис, а не AT&T

а что мне признавать? в той теме сравнивали массив и вектор, а вовсе не разные реализации STL. Я перечитал тему, и не нашел нормальное сравнение стандартных библиотек.

Зачем мне что-то тебе доказывать? К тому же скорость - далеко не самый важный показатель для меня. К примеру, отладка итераторов для меня важнее небольшого выигрыша в скорости. Скажу по секрету, я специально отключаю в релизе некоторые оптимизации и оставляю отладочную информацию, что-бы было удобнее анализировать дампы и отлаживать код. Если скорость работу генерируемого кода у GCC - на уровне (я не говорю - больше или меньше, так как скорее всего они мало отличаются друг от друга, да я и не сравнивал, так как не интересно), то по другим параметрам, GCC меня абсолютно не устраивает.

в самом деле, вряд ли существует много способов оптимально сгенерировать один и тот же алгоритм, особенно если он простой

опять переиначил. себе.


с простыми - да.
так какой код сравнивать будем? есть что-то подходящее?

я всего-лишь попросил тебя не бросаться такими громкими фразами безосновательно, так почему я теперь должен что-то доказывать себе? лол

если для тебя так важно, кричать на форумах, что dinkumware stl - отстой, то докажи это, иначе - кыш отсюда трололо 

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

На самом деле существенно различаться реализации STL не могут, так как стандарт диктует свои правила, практически все алгоритмы ограничены в сложности, а если find работает с логарифмической сложностью, то большой разницы быть не может, не так уж и много возможных реализаций, в реализации STL от gcc используют Устройство Даффа для оптимизации некоторых циклов, это дает небольшой прирост производительности, но я не думаю что разница будет заметна и скорее всего каждый пишет STL с учетом специфики оптимизатора родного компилятора.

Это сообщение отредактировал(а) azesmcar - 3.3.2010, 09:47