The Daily WTF: Curious Perversions in Information Technology

Anonymous · 2014-12-11 Reply Admin

What's with the stylesheets again?

[image]

VinDuv · 2014-12-11 Reply Admin

Anonymous:
What's with the stylesheets again?

Maybe Alex is planning to rename the site to TheDailyCSSFail.com?

VinDuv · 2014-12-11 Reply Admin

Also, this:

for(int i = 0; i < m; ++i) {
    for(int j = 0; j < n; ++i) {

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:

aliceif · 2014-12-11 Reply Admin

So TRWTF is @Remy? [image]

Filed under: [Standard infinite loop operation]()

Julia · 2014-12-11 Reply Admin

Well, he was right about the "really expensive" bit...

Gaska · 2014-12-11 Reply Admin

aliceif:
Filed under: Standard infinite loop operation

It's only infinite if m is larger than MAX_INT. And if you can read each and every byte `sizeof(typeof(**target))*MAX_INT*n` before and after the target's first element. Good luck with allocating several hundred gigs in one block.

Fellshard · 2014-12-11 Reply Admin

Gotta love how he got a name change from Rayer to Radar half-way through the article.

Kian · 2014-12-11 Reply Admin

Unless m and n are guaranteed to grow together, the loop wasn't O(n^2) in the first place.

DaveK · 2014-12-11 Reply Admin

Gaska:
It's only infinite if m is larger than MAX_INT.

No, it's infinite if n>0, because j is never incremented.

Gaska · 2014-12-11 Reply Admin

Oh, wait. Right. Too much debugging C++ without a debugger does it to you...

Gaska · 2014-12-11 Reply 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

Dragnslcr · 2014-12-11 Reply Admin

Kian:
Unless m and n are guaranteed to grow together, the loop wasn't O(n^2) in the first place.

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.

boomzilla · 2014-12-11 Reply Admin

Please give to TDWTF Writers Fund, because a typo is a terrible thing to notice.

narbat · 2014-12-11 Reply Admin

Kian:
Unless m and n are guaranteed to grow together, the loop wasn't O(n^2) in the first place.

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."

anonymous234 · 2014-12-11 Reply Admin

narbat:
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.

But what if you have n elements, and you make a matrix where each value represents a relationship between two of them?

It all depends on what you call an element.

chubertdev · 2014-12-11 Reply Admin

This is why we can't have nice CSS, people.

narbat · 2014-12-11 Reply Admin

anonymous234:
But what if you have n elements, and you make a matrix where each value represents a relationship between two of them?
It all depends on what you call an element.

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.

LB_ · 2014-12-11 Reply Admin

Is process(*((target*)(&target) + i)); correct? It does not compile for me: http://ideone.com/MPOcMG

accalia · 2014-12-11 Reply Admin

C89, don't think so.

C99... it might be... been a long time since i did C work.

tarunik · 2014-12-11 Reply 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.

Jim_Buck · 2014-12-11 Reply 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.

xaade · 2014-12-11 Reply 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.

FrostCat · 2014-12-12 Reply Admin

tarunik:
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.

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

*target + j * sizeof(array item) + i. /* i think-- was a long time ago */

CoyneTheDup · 2014-12-12 Reply Admin

Be fair: He said it looked "something like this", not that it looked "exactly like this".

("...read between the lines...")

HardwareGeek · 2014-12-12 Reply Admin

tarunik:
it tries to use the nontype name target in a context that expects a type name.

Change target* to int* and it works.

tarunik · 2014-12-12 Reply Admin

HardwareGeek:
Change target* to int* and it works.

Exactly...how that mistake got in there in the first place beats me, though.

Severity_One · 2014-12-12 Reply 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.

Scarlet_Manuka · 2014-12-12 Reply Admin

Well, don't leave us in suspense; had he?

foxyshadis · 2014-12-12 Reply Admin

Anonymous:
What's with the stylesheets again?
<img src="/uploads/default/11054/ce3c01ec76d7851f.png" width="460" height="500">

User agent stylesheets are now Remy's fault?

Bulb · 2014-12-12 Reply Admin

Jim_Buck:
You can have both a type and a variable of the same name

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.

foxyshadis:
User agent stylesheets are now Remy's fault?

The user agent stylesheet is what contains the correct definitions. And they are crossed out because overridden by the page stylesheet.

VinDuv · 2014-12-12 Reply Admin

Bulb:
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.

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 is struct target target; which is valid C/C++).

$ cat test.cpp 
struct target {
};
target target;
$ g++ -Wall -W -ansi -pedantic -c test.cpp
$

Still a Bad Idea, tough.

Bulb · 2014-12-12 Reply 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.

VinDuv · 2014-12-12 Reply Admin

Bulb:
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.

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

kupfernigk · 2014-12-12 Reply Admin

FrostCat:
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
target + j * sizeof(array item) + i. / i think-- was a long time ago */

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.

Bulb · 2014-12-12 Reply Admin

VinDuv:
even C is not immune to ambiguity

Bulb:
In C and C++

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.

FrostCat · 2014-12-12 Reply Admin

kupfernigk:
That's in principle how you actually do it in assembler. Except that it's base + (size of item)* ((size of 1st array dimension*j) + 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.

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.

eekysam · 2014-12-12 Reply 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.

boomzilla · 2014-12-12 Reply Admin

eekysam:
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.

Not in a Big-O Notation kind of way, though.

AndreiRinea · 2014-12-14 Reply Admin

You guys are mean. There is some optimization since there is less looping overhead (1 for vs 2 fors). :P

Polynomial Optimization

Leave a comment on “Polynomial Optimization”