Algorithm Complexity
-
Dang. What do you know. I found it: http://www.codeproject.com/lounge.asp?msg=2248592&ForumID=1159&searchkw=algorithm&sd=13%20Jul%202007&ed=11%20Oct%202007&stype=1&Page=2#xx2248592xx[^] I actually never realized there was a "search forum" link (I was expecting a textbox with a search button). Typed in "algorithm" and found it on the second page: Genetic Programming Marc
Hate to display my ignorance, but just where is this
Marc Clifton wrote:
"search forum" link
you refer too.
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
-
well, the results were surprising, so I am going back to check why... if htey are right it may make somethings easier for me. a+b 0.62 sec a-b 0.62 sec a*b 0.62 sec a/b 2.00 sec sin(b) 33.98sec cos(b) 35.59sec (those should be the same, which means maybe a cpu caching issue?) tan(b) 37.59sec atan2(a,b) 27.85sec atan(a/b) 38.43 (I knew it was better to do atan2 instead of division, but I didn't expect that) sqrt(b) 2.01 sec (that is the one that blew me away)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
well, the results were surprising, so I am going back to check why... if htey are right it may make somethings easier for me. a+b 0.62 sec a-b 0.62 sec a*b 0.62 sec a/b 2.00 sec sin(b) 33.98sec cos(b) 35.59sec (those should be the same, which means maybe a cpu caching issue?) tan(b) 37.59sec atan2(a,b) 27.85sec atan(a/b) 38.43 (I knew it was better to do atan2 instead of division, but I didn't expect that) sqrt(b) 2.01 sec (that is the one that blew me away)
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
There are plenty of optimized sqrt methods, I'm not sure which one's the least computation required. I would expect cos to be slightly less than sin since it starts with 1 (constant), but without knowing what they're doing, they could be slightly different. The rest are interesting. I'm surprised nobody has put all of those and the different processors in a table?
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon Web - Blog - RSS - Math - LinkedIn - BM
-
There are plenty of optimized sqrt methods, I'm not sure which one's the least computation required. I would expect cos to be slightly less than sin since it starts with 1 (constant), but without knowing what they're doing, they could be slightly different. The rest are interesting. I'm surprised nobody has put all of those and the different processors in a table?
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon Web - Blog - RSS - Math - LinkedIn - BM
Bassam Abdul-Baki wrote:
I'm surprised nobody has put all of those and the different processors in a table?
because they change per processor, and SSE series, etc. Add in cached loops and dropped caches, etc. and you have a mish-mash that most vendors just say "profile it" and see.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Bassam Abdul-Baki wrote:
I'm surprised nobody has put all of those and the different processors in a table?
because they change per processor, and SSE series, etc. Add in cached loops and dropped caches, etc. and you have a mish-mash that most vendors just say "profile it" and see.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
True, but I've seen similar statistics for using different programming languages and OS's and hardware. They just list as many different configurations as possible. Oh well, we'll modify our count slightly for the sqrt. Thanks.
"There are II kinds of people in the world, those who understand binary and those who understand Roman numerals." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
-
There are plenty of optimized sqrt methods, I'm not sure which one's the least computation required. I would expect cos to be slightly less than sin since it starts with 1 (constant), but without knowing what they're doing, they could be slightly different. The rest are interesting. I'm surprised nobody has put all of those and the different processors in a table?
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon Web - Blog - RSS - Math - LinkedIn - BM
Bassam Abdul-Baki wrote:
The rest are interesting. I'm surprised nobody has put all of those and the different processors in a table?
Because it's pretty much useless for comparing algorithms. An algorithm complexity is different than an algorithm running time; I can show some O(n!) algorithms that run fast for some mid to large size dataset, but once you pass a certain size the running time just jumps and prove the complexity of said algorithm.
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
You might have had better luck if you had posted this in the Algorithms/Math board!
-
True, but I've seen similar statistics for using different programming languages and OS's and hardware. They just list as many different configurations as possible. Oh well, we'll modify our count slightly for the sqrt. Thanks.
"There are II kinds of people in the world, those who understand binary and those who understand Roman numerals." - Bassam Abdul-Baki Web - Blog - RSS - Math - LinkedIn - BM
Bassam Abdul-Baki wrote:
True, but I've seen similar statistics for using different programming languages and OS's and hardware. They just list as many different configurations as possible. Oh well, we'll modify our count slightly for the sqrt. Thanks.
except that the one "extra" function that breaks the cache is more expensive than anything else. Knowing that is what the profilers are designed to help you with. Counting up the operations often leads you to think something is better than it really is. You can't divorce yourself from the architecture, only cooperate with it. When you try and put "all the options" on the table, there are too many to count.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Well then the solution is obvious. Just make up whatever numbers you want, and come up with a heinously complex algebraic "formula" that looks powerful, but is in fact meaningless. I'm pretty sure the Fed and the Stock Market have been getting away with this for years :)
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
-
Hate to display my ignorance, but just where is this
Marc Clifton wrote:
"search forum" link
you refer too.
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
I'm not positive if this is what Marc was referring to or not, but there's one near the top of the page on the right-hand side. There's a little magnifying glass and the words "Search comments" which is a link. If you click it from the Lounge, you can search the Lounge by author or subject. BDF
-
Hate to display my ignorance, but just where is this
Marc Clifton wrote:
"search forum" link
you refer too.
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
Chris Meech wrote:
Hate to display my ignorance, but just where is this
No problem, it isn't very obvious to me. You know where the "first, prev, next" links are for navigating the forum? Go up two lines and there's a magnifying glass with a link titled "search comments" to the left of the Set Options button. That should probably go into the WTF for bad UI design. Marc
-
Chris Meech wrote:
Hate to display my ignorance, but just where is this
No problem, it isn't very obvious to me. You know where the "first, prev, next" links are for navigating the forum? Go up two lines and there's a magnifying glass with a link titled "search comments" to the left of the Set Options button. That should probably go into the WTF for bad UI design. Marc
Thank you Marc. I had never noticed that before. Even odder I guess is that when you go to advanced search, the Lounge is not listed, but yet apparently it can be searched. That's a :wtf: to me. Thanks. :)
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
-
I'm not positive if this is what Marc was referring to or not, but there's one near the top of the page on the right-hand side. There's a little magnifying glass and the words "Search comments" which is a link. If you click it from the Lounge, you can search the Lounge by author or subject. BDF
Thanks, Big Daddy. :) Say did you ever meet the 'real' Big Daddy[^]. :)
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
-
Thanks, Big Daddy. :) Say did you ever meet the 'real' Big Daddy[^]. :)
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
Chris Meech wrote:
meet the 'real' Big Daddy
No, sadly, I have not. But if I'm ever in Ocala, I'll be sure to stop at his museum. Thanks for the link. BDF
-
Thank you Marc. I had never noticed that before. Even odder I guess is that when you go to advanced search, the Lounge is not listed, but yet apparently it can be searched. That's a :wtf: to me. Thanks. :)
Chris Meech I am Canadian. [heard in a local bar] Donate to help Conquer Cancer[^]
-
Well then the solution is obvious. Just make up whatever numbers you want, and come up with a heinously complex algebraic "formula" that looks powerful, but is in fact meaningless. I'm pretty sure the Fed and the Stock Market have been getting away with this for years :)
¡El diablo está en mis pantalones! ¡Mire, mire! Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)! SELECT * FROM User WHERE Clue > 0 0 rows returned Save an Orange - Use the VCF! VCF Blog
-
Bassam Abdul-Baki wrote:
Actually, the search engine has improved drastically as of late.
Fun with semantics: X has improved dramatically Y's new management has drastically affected programmer performance Or, the stock market went up dramatically today vs. the stock market took a drastic turn for the worse today. Anyways, I'm not taking pot shots or trying to be holier than thou or anything like that. It's simply that I was struck by the use of the word "drastic" as a modifier to "improved" and was thinking (if you can call it that) out loud in a meandering way. Marc
-
Bassam Abdul-Baki wrote:
True, but I've seen similar statistics for using different programming languages and OS's and hardware. They just list as many different configurations as possible. Oh well, we'll modify our count slightly for the sqrt. Thanks.
except that the one "extra" function that breaks the cache is more expensive than anything else. Knowing that is what the profilers are designed to help you with. Counting up the operations often leads you to think something is better than it really is. You can't divorce yourself from the architecture, only cooperate with it. When you try and put "all the options" on the table, there are too many to count.
_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
-
Bassam Abdul-Baki wrote:
Actually, the search engine has improved drastically as of late.
Fun with semantics: X has improved dramatically Y's new management has drastically affected programmer performance Or, the stock market went up dramatically today vs. the stock market took a drastic turn for the worse today. Anyways, I'm not taking pot shots or trying to be holier than thou or anything like that. It's simply that I was struck by the use of the word "drastic" as a modifier to "improved" and was thinking (if you can call it that) out loud in a meandering way. Marc
That's true. However, if you'd used the search engine before, you'd know it timed out more often than not. Thus, any improvement is a drastic improvement. Is it me or is the word meandering abused in this forum? :-D
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon Web - Blog - RSS - Math - LinkedIn - BM
-
Hi, maybe there is a way in between: Count the calls to non-trivial functions like trigonometrical ones in each algorithm and then time some iterations with only one of these calls so you can get an estimate on the weight of each of those function calls. This way you might not get a result like "A has O(n^2) and B has O(3n^2)" but "A's complexity is significantly higher than B's" or "both algorithms are about equal in complexity". Maybe put some tech talk on top of it noting that real-life complexity depends on platform used etc. :-)