Nice one. I'm one of those non-CS background person in IT. Although, I'm not a dev, I do write a lot of code in SQL and Python for data analysis. People like me can benefit a lot from understanding algorithms. Especially because we often deal with huge amounts of data. Cheers.
14,000x Speedup (2015)
21–30 of 237 posts
Re: 14,000x Speedup (2015)
#22> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?
The sentence has a link to the wikipedia article on the halting problem, which is a fine way of handling the exceptions.
Re: 14,000x Speedup (2015)
#23> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?
Yes, this is not true. The law should be treated literally, in general case of all possible programs running with infinite amount of resources. If you take a program and you don't know anything about it and it has infinite amount of memory and you have to tell whether it executes or not, in general, it is not possible. On the other hand knowing a little bit about the program already can make this statement not apply.…
> As a simple example, restricting amount of memory makes it possible to build a very simple algorithm to tell whether the program terminates or repeats ad infinitum, in finite time and resources.
I feel like "finite" is doing a lot of work there.
Re: 14,000x Speedup (2015)
#24> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. This is technically not correct, is it? Or at least phrased a bit poorly. Maybe replace "your" with "any given"?
I think a better way to describe the halting problem would be: There isn't a program or algorithm of lower complexity which can prove that a specific program actually terminates.
Re: 14,000x Speedup (2015)
#25Computer Science for the... loss? I did not study computer science in any substantial way, and I hardly consider myself a computer scientist, but I do have a nose for algorithms despite not really thinking about it in a structured way. I think lot of people get wrapped up in the notation without realizing they can approach the problem in a completely different way. Case in point, a professor at a University in the US…
I'm biased because I studied Poli Sci, I'd like to think I'm a pretty successful software architect and senior developer, and for a long time I had a big chip on my shoulder because I didn't study Comp Sci (and barely graduated college at all if we're being honest).
But your story shows the gulf that exists between Computer Science and software development. You needed to actually use a piece of software constrained by business requirements (not spinning up 250 servers), and when it didn't do what you needed it to, you changed it. The fact that you failed a data structures class didn't prevent you from refactoring and improving the code. The fact that that professor wrote code that performs poorly on good hardware doesn't negate the fact that there was probably some novel CS implementation in there somewhere.
I know in the past I've gotten caught up on CS profs having terrible websites or programmers not understanding the intricacies of bubble sorting but I think it helps to keep in mind that they are two different disciplines that inform each other, and the gap is seeming to get wider over time.
Re: 14,000x Speedup (2015)
#26Computer Science for the... loss? I did not study computer science in any substantial way, and I hardly consider myself a computer scientist, but I do have a nose for algorithms despite not really thinking about it in a structured way. I think lot of people get wrapped up in the notation without realizing they can approach the problem in a completely different way. Case in point, a professor at a University in the US…
Data structures is a weird one, it's basically a memorization class. It's the kind of thing you just have to do, a bunch of times, then it clicks. That was my experience, anyways. It's largely only relevant when interviewing, and I always cram for that like I did in college, by implementing a whole ton of data structures the week before.
Re: 14,000x Speedup (2015)
#27Gamedev! One of the best parts of being in gamedev was that the problem space forces you to work this stuff out. People won’t wait 30 minutes for a frame to render.
A few ways to solve this pop to mind. As Aeolun mentions in a parallel comment, you can just divide coordinates if your grid is regular. But it often isn’t.
In that case, you can attack it in a few ways. One time Feynman was giving a lecture and said “This triangle looks a little cockeyed. Obtuse! That’s the word! I know about the triangles but not their names.” And I’m not Feynman, but I did forget the name of this: you build a tree of squares. First one is your whole grid; split it into four smaller squares, those are the children; repeat till your resolution is sufficient. Then you can attach whatever you want to the child nodes (in this case, grid squares). Since it bisects space into halves, you can do a search in O(log n).
But what if you want to go faster? What if it’s absolutely crucial for speed, like a physics engine, to be able to ask “which objects occupy this region of space?”
My favorite algorithm is absolutely delightful: a radix sort on floats. http://www.codercorner.com/RadixSortRevisited.htm
You end up getting O(k*N) time, just like radix sort normally gives you. But the real magic is that it works with bounding boxes. There’s an article from the same author which I can no longer find, detailing it. But the idea is, you sort all your objects in one spatial dimension first, say along the X axis, and then you don’t need to do anything to search quickly. No trees. Suppose you want to ask “does this region of the X-axis have any objects?” You just... do something, ha. I forgot the next step, so I don’t want to say a mistaken answer and tarnish poor Pierre’s idea, which is quite nice. But he’s been working on this problem for basically decades, so here’s one of his N papers on the topic (of spatial partitioning, not applying radix sort to solve it): http://www.codercorner.com/ZeroByteBVH.pdf
I could work it out if I sat down with it for a bit, but, I leave it to one of you younger devs can take up the torch. It’s a fun puzzle.
Re: 14,000x Speedup (2015)
#28Computer Science for the... loss? I did not study computer science in any substantial way, and I hardly consider myself a computer scientist, but I do have a nose for algorithms despite not really thinking about it in a structured way. I think lot of people get wrapped up in the notation without realizing they can approach the problem in a completely different way. Case in point, a professor at a University in the US…
There is nothing a computer science course teaches, or indeed, any university course really, that can't be learned by someone who didn't go through that course. Undergrad computer science is indeed one of the easiest things to self-teach because of the ready availability of the "lab materials", i.e., computers are cheap and abundant now.
But a structured program will take you through these things, ensure that you understand them, be available to answer questions in a manner other than "bang your head on the problem for weeks" or "just give up", and provide a structure progression through to more advanced topics.
I think it's important to keep both sides of this in mind; the universities do not have a monopoly on the knowledge and arguably it's easier than ever to pick up yourself, but that doesn't mean the structured experience is useless either. I've worked with some very good self-taught people, but they all have also tended to have gaping holes in their education relative to a good computer science education. (I agree with those people that they are much better than some people who end up with bad computer science educations. Unfortunately, if one optimizes one's computer science education for "the easiest 4.0s", one can end up with very similar gaping holes in one's formal education!)
Re: 14,000x Speedup (2015)
#29Sorry, but FTW will always mean "f... the world".
Re: 14,000x Speedup (2015)
#30Earlier quoted context omitted.
Yes, this is not true. The law should be treated literally, in general case of all possible programs running with infinite amount of resources. If you take a program and you don't know anything about it and it has infinite amount of memory and you have to tell whether it executes or not, in general, it is not possible. On the other hand knowing a little bit about the program already can make this statement not apply.…
> As a simple example, restricting amount of memory makes it possible to build a very simple algorithm to tell whether the program terminates or repeats ad infinitum, in finite time and resources. I feel like "finite" is doing a lot of work there.
At this point we are still talking mathematical terms.
So, read it the following way:
Mathematically, you can construct a program that, using finite amount of steps and finite amount of memory tells whether another program terminates or not IF you know this other program has finite amount of memory to use.
Obviously, we know that even with very small amount of memory this is going to take huge amount of time. Just look at Busy Beaver function to appreciate how quickly this grows with amount of available memory: https://en.wikipedia.org/wiki/Busy_beaver
Basically, Busy Beaver function tells how long a program, given an amount of memory, can execute and still terminate.
This fantastic function is my favorite function if we ever play a game of "who can think a function that grows faster".
As a corollary, since every real life program has finite memory, it is not possible to construct a non-terminating program that will not repeat its output. Knowing this you just construct a simple program that looks for cycle in the program state.