• (disco)

    What's with the stylesheets again?

    [image]
  • (disco) in reply to Anonymous
    Anonymous:
    What's with the stylesheets again?

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

  • (disco)

    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:

  • (disco) in reply to VinDuv

    So TRWTF is @Remy? [image]


    Filed under: [Standard infinite loop operation]()
  • (disco)

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

  • (disco) in reply to aliceif
    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.
  • (disco)

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

  • (disco)

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

  • (disco) in reply to Gaska
    Gaska:
    It's only infinite if m is larger than MAX_INT.
    No, it's infinite if n>0, because j is never incremented.
  • (disco) in reply to DaveK

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

  • (disco) in reply to DaveK

    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

  • (disco) in reply to Kian
    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.

  • (disco) in reply to Dragnslcr

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

  • (disco) in reply to Kian
    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."

  • (disco) in reply to narbat
    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.

  • (disco)

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

  • (disco) in reply to anonymous234
    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.

  • (disco)

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

  • (disco) in reply to LB_

    C89, don't think so.

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

  • (disco) in reply to LB_

    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.

  • (disco) in reply to LB_

    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.

  • (disco) in reply to anonymous234

    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.

  • (disco) in reply to tarunik
    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 */
    
  • (disco) in reply to aliceif

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

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

  • (disco) in reply to tarunik
    tarunik:
    it tries to use the nontype name target in a context that expects a type name.
    Change target* to int* and it works.
  • (disco) in reply to HardwareGeek
    HardwareGeek:
    Change target* to int* and it works.

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

  • (disco)

    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.

  • (disco) in reply to Severity_One

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

  • (disco) in reply to Anonymous
    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?

  • (disco) in reply to Jim_Buck
    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.

  • (disco) in reply to Bulb
    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.

  • (disco) in reply to VinDuv

    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.

  • (disco) in reply to Bulb
    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

  • (disco) in reply to FrostCat
    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.

  • (disco) in reply to VinDuv
    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.

  • (disco) in reply to kupfernigk
    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.

  • (disco) in reply to HardwareGeek

    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.

  • (disco) in reply to eekysam
    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.

  • (disco)

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

Leave a comment on “Polynomial Optimization”

Log In or post as a guest

Replying to comment #:

« Return to Article