Algorithm Complexity
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
There are a lot of different code metrics that can measure complexity, but I'm not sure they will measure it in the way you are looking for. It seems like you have specific things you are trying to measure.
Scott.
—In just two days, tomorrow will be yesterday. [Forum Guidelines] [Articles] [Blog]
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
Relative weights would vary by CPU architecture. Depending on your data set size and linearity cache sizes would also come into play. Your best bet is the compare actual runtimes, iterating enough that timer noise isn't an issue.
TimerA.Start()
for (int i = 0; i < bigNum; i++)
DoAlgorithmA()
TimerA.Stop()
TimerB.Start()
for (int i = 0; i < bigNum; i++)
DoAlgorithmB()
TimerB.Stop()if (TimerA.Time > TimerB.Time)
Print ("A is slower");
else
Print ("B is slower");-- If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.
-
There are a lot of different code metrics that can measure complexity, but I'm not sure they will measure it in the way you are looking for. It seems like you have specific things you are trying to measure.
Scott.
—In just two days, tomorrow will be yesterday. [Forum Guidelines] [Articles] [Blog]
-
Relative weights would vary by CPU architecture. Depending on your data set size and linearity cache sizes would also come into play. Your best bet is the compare actual runtimes, iterating enough that timer noise isn't an issue.
TimerA.Start()
for (int i = 0; i < bigNum; i++)
DoAlgorithmA()
TimerA.Stop()
TimerB.Start()
for (int i = 0; i < bigNum; i++)
DoAlgorithmB()
TimerB.Stop()if (TimerA.Time > TimerB.Time)
Print ("A is slower");
else
Print ("B is slower");-- If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
Bassam Abdul-Baki wrote:
Is anyone aware of such a method?
I generally use a profiler. if you really want a number, test it. Call 1 MILLION calls of a given operation, time it, come up wth a numerical scale for each operand based on the time it takes to call each operation. Now you have a good number.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
You need to compute the number of operations that each algorithm is doing depending on the size of the inputs. (edit) usually, all binary operations are constant in time. for example : 1+1 is O(1) loops are linear in complexity : j = 0; for ( i = 0; i < n; i++ ) { j++;} is O(n) and so on and so forth.
Maximilien Lincourt Your Head A Splode - Strong Bad
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
Are there any decisons or loops or just formulas?
Co-Author ASP.NET AJAX in Action
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
If you want to know the number of cycles you could check the chip documentation to determine how many micro cycles a given op will use. With the relatively simple complexity of those algorithms I doubt even big analysis will help. I believe all of those functions use look up tables and identities.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
Are there any decisons or loops or just formulas?
Co-Author ASP.NET AJAX in Action
-
Interesting, if you do find an article for sheet with the 'weights' of each operator/function I'd be interested to know. Surely someone, somewhere must of done this kind of thing.
WPF - Imagineers Wanted Follow your nose using DoubleAnimationUsingPath
-
Bassam Abdul-Baki wrote:
Is anyone aware of such a method?
I generally use a profiler. if you really want a number, test it. Call 1 MILLION calls of a given operation, time it, come up wth a numerical scale for each operand based on the time it takes to call each operation. Now you have a good number.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
If you want to know the number of cycles you could check the chip documentation to determine how many micro cycles a given op will use. With the relatively simple complexity of those algorithms I doubt even big analysis will help. I believe all of those functions use look up tables and identities.
Need a C# Consultant? I'm available.
Happiness in intelligent people is the rarest thing I know. -- Ernest Hemingway -
You need to compute the number of operations that each algorithm is doing depending on the size of the inputs. (edit) usually, all binary operations are constant in time. for example : 1+1 is O(1) loops are linear in complexity : j = 0; for ( i = 0; i < n; i++ ) { j++;} is O(n) and so on and so forth.
Maximilien Lincourt Your Head A Splode - Strong Bad
-
Can you give an example or two?
Co-Author ASP.NET AJAX in Action
-
Bassam Abdul-Baki wrote:
but they wanted something algebraic and not computed.
you compute an algebraic weight to be attached to any given function based on its performance time. :)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Can you give an example or two?
Co-Author ASP.NET AJAX in Action
-
Bassam Abdul-Baki wrote:
but they wanted something algebraic and not computed.
you compute an algebraic weight to be attached to any given function based on its performance time. :)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Is there a known method for comparing different algorithms? What we're looking for is a way to assign weights to different operands (+,-,*,/) and functions (sin,cos,tan,cot,sqrt) and see how they compare to each other. Is anyone aware of such a method? Thanks
"Religion is assurance in numbers." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
If all you want is a quick "cocktail napkin" comparison, then just count operations by hand, using some large, consistent weight (say, 100) for the trig methods. If the results are close, then you can decide on other factors (clarity, accuracy, ease of optimization, etc.)
every night, i kneel at the foot of my bed and thank the Great Overseeing Politicians for protecting my freedoms by reducing their number, as if they were deer in a state park. -- Chris Losinger, Online Poker Players?