Diplomatically speaking, it's always better to criticize code by offering a better solution. However, I have yet to meet a diplomatic programmer.
Well to be perfectly honest, your failure is in assuming this is how I would write my own program. In reality, I rarely need anything this simple. Should I have cared enough for this person's program, I would have opened my compiler and made sure the code worked at the very least.
No, I didn't even do that. I just wrote some lines that would work and that was that. If I really felt like it I could have optimized the code just like you're suggesting I can't do, and quite honestly I'm not sure why you think this. I've stated repeatedly this is just some program I couldn't care less about so I just typed something out for him.
If I really want to optimize code I like to make sure it works, otherwise I'll just write something for someone else that helps them out with an assignment. As people grow, you realize if they are really interested in something, they will take the time to learn it. Obviously this person just wanted help. Why bother providing coding techniques and etc? Should the person request such code out of sincere interest, I'll do it.
In either event, I can write optimized code. Quit making assumptions.
Folks, remember that this was supposed to be his homework assignment and he may not have given much thought.
That is why I and others did not post a solutions; just point him in the proper direction.
PLEASE do not do homework assignments for people.
They will have a hard time learning the underlying concepts and thinking for themselves.
Common Courtesy
At Admin
Not trying to be an ass, but for this I wouldn't consider it to be an issue of optimization, just more of quality of design. There is a much simpler way to count the frequency characters which I am guessing is what Cogman is alluding to, and is what Common Courtesy posted an outline for. It is O(n) time in the number of characters in the input string, O(1) memory (albeit with a decently sized constant factor depending on how many different characters you want to count), and it's easy to understand/read. "Optimized" code doesn't necessarily mean tricky or complex.
I guess an easier solution would be to just use MapReduce
Sorry, but the guys are right - using an O(n^2) solution where an equally simple O(n) solution exists (and is described by several people) is just a wrong approach, and nothing to do with (premature) optimization. Especially so for homework type of things where principles and algorithms are being taught on toy examples. And even on a commercial product produced by a team that does code reviews, you would get the same kind of criticism you got from Cogman and others with at least semi-competent developers going over it. Learn from it, don't be defensive...
I'm not sure that his solution is O(n^2)...
I do appreciate the fact that a beginner C++ help thread has deteriorated into a discussion of algorithmic complexity....
This discussion is making me glad I just put something together. Didn't think it would turn into one.
It is a O(n^2) because of the double for loops. Just because it is programmed to go to 26 it doesn't mean it will or will remain that way. Have you seen how some compilers will state that 0 is not equal to 0.00? Depends on how it is handled.
I think you are in denial. So, here are some test numbers.That being said, this particular program would most likely run equally as fast with even the slowest processor on the market as a solution that used ascii without double for loops. 13x slower on paper doesn't mean 13x slower in practice. It is simply a method used to get you to think about your program and what it is doing, rather than mathematical facts. If it LOOKS 13x slower, then you should be fixing it to run that 13x faster.
LARGE_INTEGER start, end;
const int NUMTESTS = 20000;
// For kicks and giggles to make sure timeing isn't screwed up.
for (int i = 0; i < NUMTESTS; ++i)
{
cogSol();
tweekSol();
}
QueryPerformanceCounter(&start);
for (int i = 0; i < NUMTESTS; ++i)
{
cogSol();
}
QueryPerformanceCounter(&end);
printf("Cogman's Solution took %d Ticks\n", end.QuadPart - start.QuadPart);
QueryPerformanceCounter(&start);
for (int i = 0; i < NUMTESTS; ++i)
{
tweekSol();
}
QueryPerformanceCounter(&end);
printf("Tweek's Solution took %d Ticks\n", end.QuadPart - start.QuadPart);
getc(stdin);Umm, no, it is not O(n^2). for that to happen, the number of iterations through the loop would have to be growing at a rate related to the number of elements in the string being searched. That simply does not and cannot happen.
The comparison you are talking about is that of a integer to a float, it is very well known and has to do with how floating points are implemented in a computer. It isn't the compilers fault, even if you programmed this in assembly you would get the same issue. Doubles should never be compared with the == operator.
Compilers aren't some sort of special magic. If you look into it, what they do is actually pretty easy to predict.
I think you are in denial. So, here are some test numbers.
"Cogman's Solution took 262607 Ticks"
"Tweek's Solution took 1767566 Ticks"
And here is the code that did the testing.
Code:LARGE_INTEGER start, end; const int NUMTESTS = 20000; // For kicks and giggles to make sure timeing isn't screwed up. for (int i = 0; i < NUMTESTS; ++i) { cogSol(); tweekSol(); } QueryPerformanceCounter(&start); for (int i = 0; i < NUMTESTS; ++i) { cogSol(); } QueryPerformanceCounter(&end); printf("Cogman's Solution took %d Ticks\n", end.QuadPart - start.QuadPart); QueryPerformanceCounter(&start); for (int i = 0; i < NUMTESTS; ++i) { tweekSol(); } QueryPerformanceCounter(&end); printf("Tweek's Solution took %d Ticks\n", end.QuadPart - start.QuadPart); getc(stdin);
Big O is not worst case, it only displays how an algorithm will perform generally with increasing n.Considering big O is to look at worst case scenario you should remove the fact it is to the 26 and only consider you have a loop within a loop.
Even if your loop was the following structure:
(int i = 0; i < N; i++)
(int j = i ; j < N; j++)
It is still O(n^2) even though you know it is going to be less than O(n^2). This is one of the most simple examples you get when learning this.
You're missing the point. You said earlier "That being said, this particular program would most likely run equally as fast with even the slowest processor on the market as a solution that used ascii without double for loops. 13x slower on paper doesn't mean 13x slower in practice. It is simply a method used to get you to think about your program and what it is doing, rather than mathematical facts. If it LOOKS 13x slower, then you should be fixing it to run that 13x faster." This absolutely proves that your code is significantly slower than a more optimal solution. Why the first test wasn't 13 times slower has more to do with the test set that I used. I didn't try and cherry pick something that your code would fail at.Also even according to the ticks its 6.7 times the difference and depending on what those units represent, it is still going to be considered instant most likely. We're not talking about a program that solves world hunger here.
I might say the same thing about you. You can't admit that you wrote crappy code and then start spouting off stuff that simply isn't true.You're clearly too stubborn to take this scenario for what it actually is.
At what point did I state that you stated that your code was the fastest solution? You stated that your code would be comparable to the more optimal solution. That is false, that is what I was showing. You stated that it was O(n^2), that is also false.At what point did I state my code is the fastest solution
No, when you make false statements, expect them to get refuted. This isn't being psycho analytical., or even efficient??? Not once. In fact I knew it was a bad solution the entire time I was writing it. Some people just like coding to have fun, some are psycho analytical.
LoL. I'm not the only one that would have came up with the optimal solution. In fact, SEVERAL people on this board would have done exactly what I did, I can pretty much guarantee it. The minute someone criticized your code, you took the defensive and started acting as if I had called your mother a whore. This is both counter productive and childish.OP, if you wan't to survive socially, I'd consider looking somewhere in between the lines here. Cogman, who is clearly superman, and your own take on the matter. Everyone can't be the king like Cogman here, sorry.
Big O is not worst case, it only displays how an algorithm will perform generally with increasing n.
Again, your code is O(n), which is faster than O(n^2). There is a big difference.
You're missing the point. You said earlier "That being said, this particular program would most likely run equally as fast with even the slowest processor on the market as a solution that used ascii without double for loops. 13x slower on paper doesn't mean 13x slower in practice. It is simply a method used to get you to think about your program and what it is doing, rather than mathematical facts. If it LOOKS 13x slower, then you should be fixing it to run that 13x faster." This absolutely proves that your code is significantly slower than a more optimal solution. Why the first test wasn't 13 times slower has more to do with the test set that I used. I didn't try and cherry pick something that your code would fail at.
I might say the same thing about you. You can't admit that you wrote crappy code and then start spouting off stuff that simply isn't true.
At what point did I state that you stated that your code was the fastest solution? You stated that your code would be comparable to the more optimal solution. That is false, that is what I was showing. You stated that it was O(n^2), that is also false.
No, when you make false statements, expect them to get refuted. This isn't being psycho analytical.
LoL. I'm not the only one that would have came up with the optimal solution. In fact, SEVERAL people on this board would have done exactly what I did, I can pretty much guarantee it. The minute someone criticized your code, you took the defensive and started acting as if I had called your mother a whore. This is both counter productive and childish.
If I see something wrong with code, I'll comment on it. That is sort of the point with a programming forum. I totally expect that if/when I post code with problems that people will point those problems out to me. This is how you improve.
If you say something false about programming, I'm going to call you out on it.
Considering big O is to look at worst case scenario you should remove the fact it is to the 26 and only consider you have a loop within a loop.
Even if your loop was the following structure:
(int i = 0; i < N; i++)
(int j = i ; j < N; j++)
It is still O(n^2) even though you know it is going to be less than O(n^2). This is one of the most simple examples you get when learning this.
Also even according to the ticks its 6.7 times the difference and depending on what those units represent, it is still going to be considered instant most likely. We're not talking about a program that solves world hunger here.
You're clearly too stubborn to take this scenario for what it actually is. At what point did I state my code is the fastest solution, or even efficient??? Not once. In fact I knew it was a bad solution the entire time I was writing it. Some people just like coding to have fun, some are psycho analytical.
OP, if you wan't to survive socially, I'd consider looking somewhere in between the lines here. Cogman, who is clearly superman, and your own take on the matter. Everyone can't be the king like Cogman here, sorry.
Do you even know what big-O notation means? This problem has two size parameters: alphabet size (call it M), and input (sentence) length (call it N).
The complexity of your algorithm is O(MN). You have to read each character of the sentence individually. For each character read, you at most scan over M (=26) letters of the (english) alphabet.
Since you have indirect addressing & pointer-arithmetic available, this algorithm only needs to be O(N), since you do not have to search the entire alphabet for a match. I mean this isn't a pure turing machine, lol. Rather you can imagine enumerating the alphabet in order (a=0, b=1, ... z=25) and indexing an array. I guess technically this is called hashing, but it's the most trivial kind of hashing, lol.
But really, I think the problem definition implies that M is fixed. Hence both algorithms are O(N), your constant is way worse than it should be, but both algorithms are linear. Your code as written is O(N) because 26 is a constant. No matter how long or short the input sentence is, you will always do 26 comparisons for each character in the input.
I haven't been, and am still not defensive of the code. I've stated several times it isn't optimized, and KNEW it wasn't while I was programming and specifically stated "bad". You state EVEN NOW I can't admit its bad code, wth? Are you blind? And what am I "admitting"? I never claimed it was good code, I said it would work for his problem, and it still would. Please quote where I stated this was good, optimized code. I already know you can't.
This is what proves to me and anyone else that you're overboard with this whole thing. I'm trying to point out what the situation is and the worst code on the planet would have worked in this scenario, and you still don't get it. Finding the solution to a problem and being able to look at something and assess the situation are 2 different things. This is where your social skills are lacking.
Feel free to PM me for an optimized solution to your problem.
It wasn't until you last post that you specifically said "bad solution" up until then, you were only throwing out insults and fits.
The situation is this. You write bad code. I called you out on bad code. You start the name calling and insults. I continue to offer to show you a better way. You insist that this code isn't bad and that you could optimize it if you want and throw in a few more insults. We derail into a discussion on big O notation. You come back and say that your code is going to be about the same speed and that it is O(n^2), both statements are false. I point that out. You say that I'm now going overboard and have no social skills.
Does that about sum things up properly? So, the guy that doesn't start with name calling and insults is suddenly the one with social problems? Umm, yeah....
Cogman - You can't admit that you wrote crappy code and then start spouting off stuff that simply isn't true.
Quote:
Tweak - At what point did I state my code is the fastest solution
Cogman - At what point did I state that you stated that your code was the fastest solution? You stated that your code would be comparable to the more optimal solution. That is false, that is what I was showing. You stated that it was O(n^2), that is also false.
Quote:
Tweak - , or even efficient??? Not once. In fact I knew it was a bad solution the entire time I was writing it.
Ok lets break it down, you started off with an insult, and it was in your first reply to my post. Here it is:
"Op, I would suggest not doing it this way. While it looks like it may work... it is VERY inefficient. (at a first glance).
Tweak155 was this a serious attempt at this problem?"
So take your own advice. Additionally you sent me a PM with your optimized code, telling me you aren't reading what I'm saying (or don't understand). You quoted my post that stated it was bad code and stated in that exact same post I hadn't "admitted" it yet.
I can't help you any further seeing the issue for what it really is. Sorry.
EDIT:
Quoted from your quote, just so you might see it:
But really, I think the problem definition implies that M is fixed. Hence both algorithms are O(N), your constant is way worse than it should be, but both algorithms are linear. Your code as written is O(N) because 26 is a constant. No matter how long or short the input sentence is, you will always do 26 comparisons for each character in the input.
In typical usage, the formal definition of O notation is not used directly; rather, the O notation for a function f(x) is derived by the following simplification rules:
- If f(x) is a sum of several terms, the one with the largest growth rate is kept, and all others omitted.
- If f(x) is a product of several factors, any constants (terms in the product that do not depend on x) are omitted.
Just throwing this out there, but the point of the exercise, coming near the beginning of the term as it does, is likely to see if the students understand and can use nested for loops.
In that context, Tweet's solution is probably the most appropriate since if the OP started using pointer arithmetic, when pointers have likely not been covered yet, would be a little suspect. Of course, he should have discussed the solution rather than just typing it in like that.
Equally of course, he should have used code tags...everyone knows this.