- Feature Articles
- CodeSOD
- Error'd
- Forums
-
Other Articles
- Random Article
- Other Series
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
What's with the stylesheets again?
[image]Admin
Maybe Alex is planning to rename the site to TheDailyCSSFail.com?
Admin
Also, this:
And giving the same name to a type and a variable is a Bad Idea :arrow_up_small: :rewind: :arrow_upper_right: :arrow_heading_down: :arrows_counterclockwise:
Admin
So TRWTF is @Remy? [image]
Filed under: [Standard infinite loop operation]()
Admin
Well, he was right about the "really expensive" bit...
Admin
Admin
Gotta love how he got a name change from Rayer to Radar half-way through the article.
Admin
Unless m and n are guaranteed to grow together, the loop wasn't O(n^2) in the first place.
Admin
Admin
Oh, wait. Right. Too much debugging C++ without a debugger does it to you...
Admin
Dammit, I deleted that post before I realized I was half-right - you do need hundreds-of-gigabytes-malloc to make it actually infinite loop.
Mod - PJH: UTFY
Admin
Yup, that was exactly my reaction. TRWTF is even more basic than basic arithmetic; it's not understanding that n and m are different variables.
Admin
Please give to TDWTF Writers Fund, because a typo is a terrible thing to notice.
Admin
Came here to say just this. It's already O(n) because the number of operations changes linearly with the number of elements. I don't care how many indices you have, the 'n' represents the total number of data elements. The change made in the article just demonstrates that it's already linear. The story could have been salvaged by Ra(ye|da)r pointing this out; the fact that he didn't shows that he also believed it was O(n^2).
The cow-orker should have opened with, "You know how you're always bitching that the main loop is slow because it's O(n^2)? The real WTF is you."
Admin
It all depends on what you call an element.
Admin
This is why we can't have nice CSS, people.
Admin
Well, yeah. But in the case of the example given in the article we're dealing with a 2D array of undefined "somethings". Each of those "somethings" is operated on independently of how many "somethings" are contained in the array. With respect to the "somethings" in the array, the algorithm scales linearly and is O(n). If those "somethings" are relationships between elements of another set of "different things" then you could indeed have a different complexity with respect to the set of "different things". The article doesn't provide information about that, so we can't estimate the complexity with respect to those "different things". It's also possible that the process() function contains its own internal iterations across the 2D array, in which case all bets are off. For this sort of analysis you have to just assume that a generic function only acts upon its actual arguments without hidden dependencies on the rest of the data set.
Admin
Is
process(*((target*)(&target) + i));
correct? It does not compile for me: http://ideone.com/MPOcMGAdmin
C89, don't think so.
C99... it might be... been a long time since i did C work.
Admin
It isn't -- it tries to use the nontype name
target
in a context that expects a type name. Unfortunately, the compiler error you get back is cryptic and unhelpful due to limitations of the C and C++ grammars.Admin
You can have both a type and a variable of the same name, but your code doesn't actually define a type named 'target', hence why you are getting a compile error. The larger problem is that, based on missing information of the original code, the changed co-worker's code might not even be correct. It's only correct if 'm' and 'n' are hard-coded to be the sizes of the rows/columns of the array. If they are truly variable, and can be [0-arraysize), then the updated code the co-worker came up with is totally wrong. It won't access the same array elements.
Admin
In that case, the O(n^2) would occur because the operation called on each element would iterate over the array as well.
Nested loops, unless they reiterate over the array, no matter the shape of the array, does not make the operation O(n^2).
You must have each iteration perform an iteration over the same set to get O(n^2).
The way you get O(nlogn) is if the iteration's iteration is cut short by some efficiency logic.
Admin
Now that I think of it I've seen this technique actually used in real code, but instead of that monstrosity it was something like
Admin
Be fair: He said it looked "something like this", not that it looked "exactly like this".
("...read between the lines...")
Admin
Admin
Exactly...how that mistake got in there in the first place beats me, though.
Admin
This reminds of what a friend of mine, who was graduating in Computing Science at the time, told me. Another student had, rather proudly, shown a solution/algorithm to his professor. The professor pointed out that, apparently, he'd managed to solve the Travelling Salesman problem, and that perhaps he'd want to check his results.
Admin
Well, don't leave us in suspense; had he?
Admin
User agent stylesheets are now Remy's fault?
Admin
No, you definitely can't. In C and C++ the lexer refers back to the list of types and assigns different token type to type identifiers. So once something is a type, attempt to declare it as variable or function or anything simply won't parse.
Edit: Actually it seems to parse fine. Sometimes. The grammar ambiguity is going to get you, eventually.
The user agent stylesheet is what contains the correct definitions. And they are crossed out because overridden by the page stylesheet.
Admin
In C++ you can refer to a struct type without prepending the “struct” keyword, so definitions like
target target;
are actually valid (since it really isstruct target target;
which is valid C/C++).Still a Bad Idea, tough.
Admin
Hm, it indeed seems to compile. There are many places where it would lead to ambiguous grammar though, because for some productions it is important to know whether something is a type or not.
Admin
It looks like even C is not immune to ambiguity because of typedef scoping: http://eli.thegreenplace.net/2011/05/02/the-context-sensitivity-of-cs-grammar-revisited/#complications
Admin
That's in principle how you actually do it in assembler. Except that it's base + (size of item)* ((size of 1st array dimensionj) + i). If the array is J by I, then the (j,i) element is offset by (element size) (j*J + i) and the boundary check has to establish that i LT I and j LT J. Or so I think, I'm tired.
Admin
Of course it isn't. Nor are Java and C#. That's why most new languages returned to pascal-style identifier
:
type, because that does not have these ambiguities. Or solve it like Ruby and Haskell where type identifiers (and constructors in Haskell case) must start with uppercase letter and value identifiers must start with lowercase letter or underscore.Admin
I knew what I had wasn't exactly right but I didn't think it was actually worth coming up with the exact syntax; the acknowledgement that the original syntax was totally wacky was enough.
Admin
Who saw this coming? I suppose it is technically O(n) where n is size of 'target' flattened. In a way every algorithm is O(n) where n is the number of 'O's of time required to run the algorithm for a given input.
Admin
Not in a Big-O Notation kind of way, though.
Admin
You guys are mean. There is some optimization since there is less looping overhead (1 for vs 2 fors). :P