4 ms·

Um, what? This is like someone challenging me to implement merge-sort, and then I give him the solution to bubble-sort saying that there's "no reason to optimi

by codexon 16y ago

Um, what? This is like someone challenging me to implement merge-sort, and then I give him the solution to bubble-sort saying that there's "no reason to optimize" until necessary. Granted the cases where Chazelle's linear time algorithm is necessary is less than merge-sort. But that is true of any field, including mathematics.

palish 16y ago
Yes, yes. But the original challenge is invalid. I asserted that I could implement 99% of algorithms I came across for practical real-world problems, not 99% of all algorithms. I gave a solution that solves the problem. The problem is, convert an arbitrary concave closed polygon into a set of triangles. I maintain that it is completely valid for me to present that solution --- there are plenty of tricks you can do to optimize it in C/C++. And not just runtime optimization either... For example why not triangulate the polygon, then save the results to disk? That way O(N log N) vs O(N) becomes completely irrelevant... you only have to do it once, ever. I suppose what I am saying is this: I can solve 99% of real-world problems I am likely to encounter in my career as a software engineer. The challenge "implement THIS scientific paper!" is completely invalid because it's a solution to a problem which very likely will never exist. My solution is valid as long as it does not greatly impact the performance of the app. Which is "always", once you throw in a layer of caching. P.S. The paper has the restriction "for every polygon vertex XY, no two vertices may have the same Y coordinate", which means it's likely to not be applicable to any real-world problem.
- codexon 16y ago
  Why is it invalid? Your original comment made no mention of "practical real-world problems". Who gets to decide that? Is implementing a video codec not a "real-world" problem since only a handful of people have experience with this? What about symbolic algebra software? A handful of find those useful compared to the masses that require mundane enterprise crud. Memoization is not panacea. This is like telling someone to sort every possible group of numbers and saving it to disk so you don't have to implement something faster than bubble-sort. My point is that in any field, "99% of real-world problems" are easy enough for the average college graduate to comprehend. Think about the kind of math that is useful for "real-world" problems. When you start bragging that you can learn any CS topic/algorithm in less than a day, you just didn't look hard enough. P.S. You missed the sentence right after where it says "we can easily get around this assumption by applying the symbolic perturbation techniques of [10] and [31]"
  - palish 16y ago
    It's invalid because the paper was presented to solve a problem which does not exist. Maybe it can be applied to some other problem using similar theory, but the problem it presents would basically never have to be solved in linear time. Try to think of an application where realtime triangulation of dynamic (changes every frame, negates the possibility of caching) concave polygons is an such a bottleneck that it not only requires hand-optimizing your triangulation routine, but also requires you re-architect it to run in linear time. In Google's words, it is a "solution in search of a problem". Memoization is not panacea. This is like telling someone to sort every possible group of numbers and saving it to disk so you don't have to implement something faster than bubble-sort. I really am not trying to be mean, I'm just stating the facts -- your statement is so full of ignorance that it's kind of disturbing that you believe it. Programming is generally an exercise in caching. There was a good article posted a long time ago called It's caches, all the way down. If you think about it, memoization (a.k.a. 'caching') has been the primary solution to a large percentage of past problems. The examples off the top of my head: - GPU memory is a cache of system memory - system memory is a cache of the hard drive - the operating system presents a file I/O interface which heavily utilizes caching - John Carmack developed Quake which revolutionized the realtime graphics industry primarily because of his innovative "potential visibility set" algorithm, which is just a cache of computing visibility on-the-fly So for all intents and purposes, memoization (caching) IS the magical panacea that you deny it to be.
    - codexon 16y ago
      How do you know the problem doesn't exist? Even if you are pre-computing it, wouldn't you like it to go faster, like encoding a video or rendering a ray-traced scene? There are an infinite number of polygons. Of course caches are important. But it isn't the only thing. That's why programs aren't all giant databases. Memoization != better caching either. That is simply naive. If your algorithm can fit in L1-L2 cache, it can be better than loading a giant hash table or tree from disk. I'm not trying to be mean either, but you have all the signs of a junior developer who thinks there is nothing left in CS to challenge him as he churns out enterprise crud where caching is the only thing he can think of that matters.

by codexon 16y ago

palish 16y ago

Yes, yes. But the original challenge is invalid. I asserted that I could implement 99% of algorithms I came across for practical real-world problems, not 99% of all algorithms. I gave a solution that solves the problem. The problem is, convert an arbitrary concave closed polygon into a set of triangles. I maintain that it is completely valid for me to present that solution --- there are plenty of tricks you can do to optimize it in C/C++. And not just runtime optimization either... For example why not triangulate the polygon, then save the results to disk? That way O(N log N) vs O(N) becomes completely irrelevant... you only have to do it once, ever. I suppose what I am saying is this: I can solve 99% of real-world problems I am likely to encounter in my career as a software engineer. The challenge "implement THIS scientific paper!" is completely invalid because it's a solution to a problem which very likely will never exist. My solution is valid as long as it does not greatly impact the performance of the app. Which is "always", once you throw in a layer of caching. P.S. The paper has the restriction "for every polygon vertex XY, no two vertices may have the same Y coordinate", which means it's likely to not be applicable to any real-world problem.

codexon 16y ago
Why is it invalid? Your original comment made no mention of "practical real-world problems". Who gets to decide that? Is implementing a video codec not a "real-world" problem since only a handful of people have experience with this? What about symbolic algebra software? A handful of find those useful compared to the masses that require mundane enterprise crud. Memoization is not panacea. This is like telling someone to sort every possible group of numbers and saving it to disk so you don't have to implement something faster than bubble-sort. My point is that in any field, "99% of real-world problems" are easy enough for the average college graduate to comprehend. Think about the kind of math that is useful for "real-world" problems. When you start bragging that you can learn any CS topic/algorithm in less than a day, you just didn't look hard enough. P.S. You missed the sentence right after where it says "we can easily get around this assumption by applying the symbolic perturbation techniques of [10] and [31]"
- palish 16y ago
  It's invalid because the paper was presented to solve a problem which does not exist. Maybe it can be applied to some other problem using similar theory, but the problem it presents would basically never have to be solved in linear time. Try to think of an application where realtime triangulation of dynamic (changes every frame, negates the possibility of caching) concave polygons is an such a bottleneck that it not only requires hand-optimizing your triangulation routine, but also requires you re-architect it to run in linear time. In Google's words, it is a "solution in search of a problem". Memoization is not panacea. This is like telling someone to sort every possible group of numbers and saving it to disk so you don't have to implement something faster than bubble-sort. I really am not trying to be mean, I'm just stating the facts -- your statement is so full of ignorance that it's kind of disturbing that you believe it. Programming is generally an exercise in caching. There was a good article posted a long time ago called It's caches, all the way down. If you think about it, memoization (a.k.a. 'caching') has been the primary solution to a large percentage of past problems. The examples off the top of my head: - GPU memory is a cache of system memory - system memory is a cache of the hard drive - the operating system presents a file I/O interface which heavily utilizes caching - John Carmack developed Quake which revolutionized the realtime graphics industry primarily because of his innovative "potential visibility set" algorithm, which is just a cache of computing visibility on-the-fly So for all intents and purposes, memoization (caching) IS the magical panacea that you deny it to be.
  - codexon 16y ago
    How do you know the problem doesn't exist? Even if you are pre-computing it, wouldn't you like it to go faster, like encoding a video or rendering a ray-traced scene? There are an infinite number of polygons. Of course caches are important. But it isn't the only thing. That's why programs aren't all giant databases. Memoization != better caching either. That is simply naive. If your algorithm can fit in L1-L2 cache, it can be better than loading a giant hash table or tree from disk. I'm not trying to be mean either, but you have all the signs of a junior developer who thinks there is nothing left in CS to challenge him as he churns out enterprise crud where caching is the only thing he can think of that matters.