Время работы функции с массивом.

[Daedro]

У нас есть ассоциативный массив map<int, int > m из n элементов. Как оценить время работы функции m.find(5) и find(m.begin(), m.end(), 5)??

Буду признателен за помощь! Заранее спасибо!

[megachuhancer]

Вообще, это зависит от реализации. Полагаю, что не хуже, чем O(log n). Особой разницы между m.find(5) и find(m.begin(), m.end(), 5) не вижу, т.к. они всё равно хранятся как дерево.

[Utkin]

Можно провести эксперимент - зарегистрировать время старта и время окончания работы данных функций при сравнительно больших m и n. Для этого нужно сформировать различные варианты map и зарегистрировать время для каждой функции. Думаю 10-ти вариантов массива юудет достаточно чтобы выявить среднее время работы для каждой функции (это необходимо, поскольку современные ОС являются многозадачными и есть вероятность, что Ос в этот момент будет выполнять ресурсоемкую работу).

[megachuhancer]

Кстати, прототип map::find такой:

iterator find(const Key& key);
const_iterator find(const Key& key) const;

То есть никаких границ, как в find(m.begin(), m.end(), 5) не предусмотрено (оно и не удивительно, т.к. узнать что где хранится в map'е можно только из отладчика(или используя map::find, хотя с помощью этой функции можно узнать где, но не что; можно пробежатся циклом по всем элементам, но это O(n)) - в map'е всё хранится в отсортированном виде). Да и необязательные параметры в C++ указываются в конце, если что.
Время поиска O(log n), т.к. там используются структуры данных типа АВЛ-деревьев, благодаря чему реально поддерживается древовидная структура.

[Utkin]

Мой способ лучше - поскольку математические выкладки не всегда соответствуют действительности по одной простой причине. Математические модели предпологают атомарность операций - каждая операция должна выполняться строго определенный квант времени. Но так ли это на самом деле? Вы не забывайте про внутренние обслуживающие операции внутри программы (отвлеченный пример - выделение динамической памяти, а память фрагментирована. Программе пофигу, поскольку будет запущена подпрограмма для оптимизации памяти, которая будет запущена кстати без вашего участия, но самое главное время будет потеряно).

[megachuhancer]

Utkin, полностью согласен, что наиболее объективным способом оценки времени работы программы является измерение этого самого времени. Но я не вижу программы, а вижу только вызов функции, который мало о чём говорит. Поэтому оценить время в этом случае можно опираясь только на метематическую оценку и детали реализации STL. Это во-первых. Во-вторых только математическая оценка может дать общее представление о времени работы программы. Вот сейчас в map'е есть 10 элементов. А в следующий раз 60000. Измерение времени позволяет оценить время выполнения только на одном классе входных данных. Тем более, что мы, в процессе написания программы не можем точно знать все детали будущей среды её выполнения: что и где будет расположено в памяти, чем будет загружен процессор и т.д. и т.п.

Я клоню к тому, что профилировка подвержена непостоянству. Профилируйте программу, потом ещё раз. Время работы может отличатся в несколько раз! А теперь запустите-ка штук 50 WinAmp'ов и профилируйте ещё раз. Конечно никому не придёт в голову(мне пришло ) профилировать программу с 50 запущенными WinAmp'ами, но всё таки. Математическая оценка обладает желательным свойством - некоторой универсальностью. Если в программе реализованы медленные алгоритмы, время её работы будет отличатся на порядки, и это будет видно без всякой профилировки. Интересно, дождётесь ли вы конца профилировки программы, сортирующей 100 000 000(или даже меньшее количество) элементов методом пузырька

[Utkin]

Но я как раз о "чистом" варианте эксперимента, без учета многозадачности. Представьте что мы работаем в голом ДОСе и драйвера у нас только на клаву с мышой. Программа в некотором смысле "вещь в себе", черный ящик если хотите. И время будет действительно зависить от алгоритма, но это будет другая формула, возможно не выражаемая в математическом смысле.
Все тот же пример про динамическую память. Возьмите операции над массивом обычным и массивом динамическим. Вы будете приятно удивлены разницей во времени и она будет далеко не линейного характера. Это объясняется тем, что современные технологии осуществляют ряд вспомогательных процессов в программе без непосредственного участия программиста - это например, сборка мусора, дефрагментация кучи и прочее. И такие процессы занимают далеко не один такт процессора.

[megachuhancer]

Ну раз речь идёт о "чистом" варианте эксперимента, то ладно. Просто у каждого подхода своя область применимости. В программировании очень важен обоснованный выбор средств. Пусть Daedro решает(если вообще ещё заглянет сюда), что для него лучше(хотя одно другому не мешает). Просто мне показалось, исходя из формулировки вопроса, что необходима именно математическая оценка, хотя я, конечно же, могу ошибаться.

[Daedro]

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

Пасибо большое!!!)) Ещё есть в интернете знающие прогеры)