Оценка производительности алгоритмов

← →
Piero © (2005-12-09 16:20) [0]

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

← →
Игорь Шевченко © (2005-12-09 16:21) [1]

> если предложите мне ссылки по данному материалу

Гудман, Хидетниеми: "Введение в разработку и анализ алгоритмов". Книга.

← →
Piero © (2005-12-09 16:28) [2]

Спасибо, поищу

← →
Джо © (2005-12-09 16:28) [3]

Ахо, Хопкрофт, Ульман. Структуры данных и алгоритмы. Тоже книга.

← →
cyborg © (2005-12-09 16:50) [4]

> можно ли как-то програмно, или спец утилитами или по формулам
> исследовать количество элементарных операций, выполняемых программой (отдельной процедурой).

Можно считать такты процессора.
Function GetCPUTick : int64; assembler; asm rdtsc; end;

← →
Digitman © (2005-12-09 17:35) [5]

> cyborg © (09.12.05 16:50) [4]

> такты процессора

малацца.
садись, два.

КАКОГО процессора (в мультипроцессорной арх-ре) или КАКОГО ядра (в мультиядерной арх-ре) ?

← →
cyborg © (2005-12-09 17:37) [6]

> [5] Digitman © (09.12.05 17:35)

:)

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

← →
Digitman © (2005-12-09 17:41) [7]

> КАКОГО процессора

> того, который запрашивает и получает результат

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

← →
cyborg © (2005-12-09 17:45) [8]

У меня он ничего не запрашивает.

← →
Piero © (2005-12-09 17:46) [9]

Большая точность не обязательна
а это:

Function GetCPUTick : int64; assembler;
asm
rdtsc;
end;

интересно, а можно поподробнее, чего такое rdtsc, и как им пользоваться, ассемблер я почти не знаю

← →
cyborg © (2005-12-09 17:48) [10]

> [9] Piero © (09.12.05 17:46)

Как оказалось, это тебе не нужно. Забудь.

← →
default © (2005-12-09 17:48) [11]

Piero © (09.12.05 17:46) [9]
почитай про O большое
например, в [3]

> [9] Piero © (09.12.05 17:46)

Чтобы пользоваться функцией в [4] cyborg ассемблер знать совсем не обязательно. А вот какую пользу она может принести для оценки производительности алгоритмов - это вопрос отдельный :) Там теория не слабая, и если ее хотя бы в общих чертах не разобрать, то считать тики процессора - это просто профанация понятия "оценка производительности алгоритмов."

← →
vrem (2005-12-09 17:59) [13]

> [12] Джо © (09.12.05 17:58)

Эта функция была приведена на слова количество элементарных операций, выполняемых программой (отдельной процедурой).

Если можно как-то по другому измерить колличество выполняемых операций отдельной процедурой? Разве только дизассамблировать код и считать процессорные инструкции?

Кормен. Алгоритмы: построение и анализ.
Кнут и еще кто-то. Математические основы анализа алгоритмов.

Думаю, на дипломе при обосновывании эффективности алгоритма надо приводить теоретическое обоснование, а не измерять эффективность процедуры или число тактов.

> [14] cyborg © (09.12.05 18:02)

Я к тому, что считать "колличество выполняемых операций отдельной процедурой"
1. Имеет весьма мало отношения к тому, что значится в топике, а именно "Оценка производительности алгоритмов".
2. В такой ОС, как Windows считание тиков при помощи rdtsc даст весьма мало для заключения о колличестве выполняемых операций отдельной процедурой.

> [13] vrem (09.12.05 17:59)
> Неужели Digitman подобное имел в виду? ;-)

А это я не знаю. Дигитмэн, думаю, сам за себя сказать может.

П.С. Я не придираюсь, просто высказываю лично мнение.

Оценка производительности алгоритмов Найти похожие ветки