Also you might be able to easily separate your data management from your other code through an interface which makes it easy to switch between the different implementations (database, even different database systems, and what are going to use at first).
The Big Programming Thread - Page 341
Forum Index > General Forum |
Thread Rules 1. This is not a "do my homework for me" thread. If you have specific questions, ask, but don't post an assignment or homework problem and expect an exact solution. 2. No recruiting for your cockamamie projects (you won't replace facebook with 3 dudes you found on the internet and $20) 3. If you can't articulate why a language is bad, don't start slinging shit about it. Just remember that nothing is worse than making CSS IE6 compatible. 4. Use [code] tags to format code blocks. | ||
spinesheath
Germany8679 Posts
Also you might be able to easily separate your data management from your other code through an interface which makes it easy to switch between the different implementations (database, even different database systems, and what are going to use at first). | ||
Shield
Bulgaria4824 Posts
On August 11 2013 20:24 one-one-one wrote: Yeah. It is also important to not bring up asymptotic complexity when uncalled for. This is a programming thread. In most cases you care about raw performance. To express yourself in more fine grained terms you might use execution time, number of instructions, etc. which might be depend on one or more variable quantities. When saying that something is O(n) or O(n log n), or whatever, you have most certainly made a number of idealizations that don't reflect how a modern computer actually works. So instead of worrying about theoretical complexity you should focus on writing simple, reasonable code with good cache access patterns. Or in the words of Linus Torvalds: https://lkml.org/lkml/2008/5/7/456 Honestly, I wouldn't rely on any of Torvalds' sayings about programming. He has already proven to be quite radical in this field by declaring C++ as bs. You can't teach an old dog new tricks. ^^ The guy may be well recognised and all for his Linux, but that doesn't make him an always-right hero. Edit: I'd like to practise and enhance my programming skills, so I'm thinking what program to do. However, I can't think of anything that would be at least a little bit useful. Could you give me ideas? I'm not looking for something super time-consuming, but I want it to be challenging and fun. I'm going to use Java as a programming language. It would be nice if I use data structure that isn't array. It'd be nice if I try generics (C++ templates) as well. I'm still thinking what to do, but I hope for some ideas. ![]() Edit #2: OnlineJudge seems like a silly useless thing imho, so I'd rather avoid practising on that. | ||
FunkyLich
United States107 Posts
For those of you who are in college and just learning this big O notation stuff, don't go away thinking this is all useless BS theory. Order notation refers to asymptotic time complexity. It answers the question: "For varying input size N, what is the end behavior of the graph T(N), where T(N) is how long the algorithm takes to execute". End behavior is the key word. That means it is most useful for reasoning about large values of N. Most of the time, when doing performance computing, we can make assumptions about the maximum size of N, which may forgo the need for heavier duty algorithms. For example, insertion sort (O(n^2) worst case) is faster than quick sort for very small N, so if you need to sort a thousand arrays of size 10, you should use that instead of quicksort (O(nlogn)). The point is that order notation is a useful performance consideration, but it is far from the being the only. Remember, order complexity ignores differences that can be expressed as a constant factor. So, when an algorithm that is ""only"" at most 100 times faster than another, they are treated with the same big O notation. An algorithm with bad asymptotic complexity is the kind of performance problem that will make the difference between coming back from lunch and the program having finished, and the program tying up your computer for 2 weeks. People who do performance computing generally take this stuff for granted, and are thinking about much more fine-tuned optimizations. Having said that, I want to share a few good model cases I've experienced where order notation is utterly useless. Caching and matrix multiplication: + Show Spoiler + Matrix multiplication is probably one of the best ways to demonstrate the penalties imposed by a cache miss. Just to keep it simple, the result of multiplying an NxN matrix A with an NxN matrix B will produce an NxN matrix C by finding the dot product with the corresponding rows of A and columns of B. For a better explanation: Matrix Multiplication This means that in our program, we will need to pull data by traversing A by row, and B by column. What does that look like in memory? This is what a traversal by row looks like in memory, each "v" marks a step in the traversal: v-------v-------v------v------v------v-------v------v------v--... [0,0] [1,0] [2,0] [3,0] [4,0] [5,0] [6,0] [7,0] [0,1] and traversal by column: v-------------------------------------------------------------v-----... [0,0] [1,0] [2,0] [3,0] [4,0] [5,0] [6,0] [7,0] [0,1] [1,1] [2,1] [3,1] [4,1] [5,1] [6,1] [7,1] Doesn't make sense? See row-major order If you are familiar with one of the fundamental rules of processor caching, principle of locality, you know this column traversal is going to be the source of lots of systematic cache misses, which are bad. The processor generally caches contiguous memory, memory that's close together. How can it possibly know to cache something that may be a thousand addresses ahead? The remedy for this is to store the inverse of B instead. This way we can traverse B by row and treat the rows as columns. When I did this experiment, it was for a parallel and distributed computing course. The goal of the assignment was to implement a parallel matrix multiplier on SRAM (shared memory), in such a way that the processors would not be competing for resources. So we did this complex stuff to make sure they were staggered and everything, and did some performance tests (with timers), to find very minimal, almost nonexistent gains. Then we tried with an inverted B matrix, and the difference was hilarious (I think it was something like 2x speed up). It was a huge performance boost just for paying a little bit of attention to caching, and stupidly easy to code too. Slow O(n) Radix sort: + Show Spoiler + For those not familiar with radix sort, it is a theoretically interesting sorting algorithm because it has linear O(n) time complexity (sort of), and space complexity isn't terrible. Here is a simple example of a radix sort. The gist is that you impose an arbitrary base on the integer elements, say 10 (it's usually much higher). And you sort the numbers one digit at a time, starting from left to right: 123 900 900 900 223 536 536 537 537 537 537 536 536 223 256 256 256 256 223 256 900 123 123 123 This is a gross simplification because I am obviously using some auxillary sort on each step (and we're using the MSD(most significant digit) variant cause it's easiest to understand). But since each step only sorts on one digit we can use a bucket sort or counting sort with linear complexity. Radix sort looks really good on paper, and it is fast. But in spite of being linear, it's not as fast as you'd think. A large constant is imposed on its time complexity mostly from the heavy use of division and modulus. So even for large N it doesn't fair a whole lot better than plain old quicksort. When implementing it, I used the LSD variant, and compared it to quicksort, which is asymptotically inferior. If I remember correctly, the radix sort only barely edged out the quicksort even with very large N and picking an optimum base (our example used base 10, the fastest base for me was in the 200s). So for those of you still learning the ropes--I know I am--try to expose yourself to some good experimental computer science. Personally, I consider myself a theory guy, and my first experience with real hard core performance computing didn't happen till the last semester of my senior year, and it changed the way I think about computing. After you get your fill of basic theory, start getting your feet wet with experiments. Try implementing an algorithm and use clever caching to get some quantifiable speed up. It will open up your world just a little bit. | ||
obesechicken13
United States10467 Posts
On August 12 2013 01:03 Morfildur wrote: How many items are in the config file? The correct answer is most likely: It does not matter, just pick the easy solution. I usually go with a Dictionary/Associative array of arrays, e.g. (C#) "Dictionary<String, List<String>>" or something similar. I looked into dictionaries. I don't think they'll work, but thanks for the suggestions. I think I'll try out a list of objects. Linked lists are hard to get my head around. | ||
one-one-one
Sweden551 Posts
On August 12 2013 06:03 FunkyLich wrote: Why would you take that one statement from Linus and just automatically assume that he thinks order complexity is a bunch of BS? I think the takeaway should be that if you are coding for performance you need to be cognizant of how the hardware works, and that CODE is not automatically faster because it implements an algorithm with superior asymptotic time complexity i.e. O(n) vs O(1). There are many other factors to take into account when considering what the true performance will be, namely caching, as others have mentioned. For those of you who are in college and just learning this big O notation stuff, don't go away thinking this is all useless BS theory. Order notation refers to asymptotic time complexity. It answers the question: "For varying input size N, what is the end behavior of the graph T(N), where T(N) is how long the algorithm takes to execute". End behavior is the key word. That means it is most useful for reasoning about large values of N. Most of the time, when doing performance computing, we can make assumptions about the maximum size of N, which may forgo the need for heavier duty algorithms. For example, insertion sort (O(n^2) worst case) is faster than quick sort for very small N, so if you need to sort a thousand arrays of size 10, you should use that instead of quicksort (O(nlogn)). The point is that order notation is a useful performance consideration, but it is far from the being the only. Remember, order complexity ignores differences that can be expressed as a constant factor. So, when an algorithm that is ""only"" at most 100 times faster than another, they are treated with the same big O notation. An algorithm with bad asymptotic complexity is the kind of performance problem that will make the difference between coming back from lunch and the program having finished, and the program tying up your computer for 2 weeks. People who do performance computing generally take this stuff for granted, and are thinking about much more fine-tuned optimizations. Having said that, I want to share a few good model cases I've experienced where order notation is utterly useless. Caching and matrix multiplication: + Show Spoiler + Matrix multiplication is probably one of the best ways to demonstrate the penalties imposed by a cache miss. Just to keep it simple, the result of multiplying an NxN matrix A with an NxN matrix B will produce an NxN matrix C by finding the dot product with the corresponding rows of A and columns of B. For a better explanation: Matrix Multiplication This means that in our program, we will need to pull data by traversing A by row, and B by column. What does that look like in memory? This is what a traversal by row looks like in memory, each "v" marks a step in the traversal: v-------v-------v------v------v------v-------v------v------v--... [0,0] [1,0] [2,0] [3,0] [4,0] [5,0] [6,0] [7,0] [0,1] and traversal by column: v-------------------------------------------------------------v-----... [0,0] [1,0] [2,0] [3,0] [4,0] [5,0] [6,0] [7,0] [0,1] [1,1] [2,1] [3,1] [4,1] [5,1] [6,1] [7,1] Doesn't make sense? See row-major order If you are familiar with one of the fundamental rules of processor caching, principle of locality, you know this column traversal is going to be the source of lots of systematic cache misses, which are bad. The processor generally caches contiguous memory, memory that's close together. How can it possibly know to cache something that may be a thousand addresses ahead? The remedy for this is to store the inverse of B instead. This way we can traverse B by row and treat the rows as columns. When I did this experiment, it was for a parallel and distributed computing course. The goal of the assignment was to implement a parallel matrix multiplier on SRAM (shared memory), in such a way that the processors would not be competing for resources. So we did this complex stuff to make sure they were staggered and everything, and did some performance tests (with timers), to find very minimal, almost nonexistent gains. Then we tried with an inverted B matrix, and the difference was hilarious (I think it was something like 2x speed up). It was a huge performance boost just for paying a little bit of attention to caching, and stupidly easy to code too. Slow O(n) Radix sort: + Show Spoiler + For those not familiar with radix sort, it is a theoretically interesting sorting algorithm because it has linear O(n) time complexity (sort of), and space complexity isn't terrible. Here is a simple example of a radix sort. The gist is that you impose an arbitrary base on the integer elements, say 10 (it's usually much higher). And you sort the numbers one digit at a time, starting from left to right: 123 900 900 900 223 536 536 537 537 537 537 536 536 223 256 256 256 256 223 256 900 123 123 123 This is a gross simplification because I am obviously using some auxillary sort on each step (and we're using the MSD(most significant digit) variant cause it's easiest to understand). But since each step only sorts on one digit we can use a bucket sort or counting sort with linear complexity. Radix sort looks really good on paper, and it is fast. But in spite of being linear, it's not as fast as you'd think. A large constant is imposed on its time complexity mostly from the heavy use of division and modulus. So even for large N it doesn't fair a whole lot better than plain old quicksort. When implementing it, I used the LSD variant, and compared it to quicksort, which is asymptotically inferior. If I remember correctly, the radix sort only barely edged out the quicksort even with very large N and picking an optimum base (our example used base 10, the fastest base for me was in the 200s). So for those of you still learning the ropes--I know I am--try to expose yourself to some good experimental computer science. Personally, I consider myself a theory guy, and my first experience with real hard core performance computing didn't happen till the last semester of my senior year, and it changed the way I think about computing. After you get your fill of basic theory, start getting your feet wet with experiments. Try implementing an algorithm and use clever caching to get some quantifiable speed up. It will open up your world just a little bit. Interesting. Your entire post is just reiterating stuff I already said in a much more verbose format. You are mostly correct, but did you actually make an effort to understand what I wrote? I already mentioned the aspects about asymptotic behavior and cache locality. The point about the quote from Linus was that it is overly simplistic to think about O(1) functions as cheap to execute on a real computer. As we have already concluded, something could be considered O(n^2) or O(1) depending on what is variable, albeit while causing some confusion to some people here. In the Linux kernel example a developer said: "The sort time on an 8k array runs in constant time". This is true in the sense that the sorting algorithm is invoked on a bounded size array which requires a bounded amount of time to execute with any sane sorting algorithm. Linus point is that 8k might still be a freaking large array to sort. What matters here is not the actual complexity, but total time required to execute. So the point about including that quote was to show that this misuse of big O notation is quite common due to programmers not having a solid enough grasp of what the concept actually means. Hell, even Linux kernel developers get it wrong. So yes, if used in the wrong way, complexity notation is just a bunch of BS in actual programming. I'm NOT saying complexity notation is a bunch of BS in general. Why would I do that when I explicitly wrote that I studied computer science at university? | ||
Shield
Bulgaria4824 Posts
There is no confusion about Big O. Just because some guy writes crappy code with no variables doesn't mean we don't know Big O. If his code was better written, then it would have been O(n^2). Magic numbers are bad. | ||
FunkyLich
United States107 Posts
On August 12 2013 07:13 one-one-one wrote: Interesting. Your entire post is just reiterating stuff I already said in a much more verbose format. I guess this is one way of saying you agree with me, albeit stripping my post of all novelty. I'll take what I can get. On August 12 2013 07:13 one-one-one wrote: You are mostly correct, but did you actually make an effort to understand what I wrote? Candidly, no. Sorry. I tend to just read things at face value out of context. And no I didn't read anything else you said because I'm lazy and pig-headed. [/not being sarcastic] On August 12 2013 07:13 one-one-one wrote: I already mentioned the aspects about asymptotic behavior and cache locality. My impression was that this thread was mostly supposed to be a place for aspiring programmers to learn programming from those who've been doing it for a while, and a place for programmers to discuss programming. My post was taking the former approach. The point was not to argue really, it was just to give me a reason to drop a knowledge bomb... and show off, cause that's just how I get my fix. edit: On an entirely different note: Is anyone here a prolog user, or interested in prolog/declaritive programming/deductive databases? | ||
Deleted User 101379
4849 Posts
On August 12 2013 07:50 darkness wrote: Most of us here have studied Computer Science or a branch of it, so you don't have to show off. You may also better your behaviour as one of the guys here has pointed out. There is no confusion about Big O. Just because some guy writes crappy code with no variables doesn't mean we don't know Big O. If his code was better written, then it would have been O(n^2). Magic numbers are bad. The confusion is: void foo() Why should foo() be O(N) and bar() O(1) eventhough calling them always uses a constant amount of time since they do not change depending on their input? | ||
waxypants
United States479 Posts
On August 12 2013 07:50 darkness wrote: Most of us here have studied Computer Science or a branch of it, so you don't have to show off. You may also better your behaviour as one of the guys here has pointed out. There is no confusion about Big O. Just because some guy writes crappy code with no variables doesn't mean we don't know Big O. If his code was better written, then it would have been O(n^2). Magic numbers are bad. How can you speak for everybody? Not everybody is wrong, but there has been some pretty obvious confusion using Big O going on here. | ||
Shield
Bulgaria4824 Posts
On August 12 2013 11:26 Morfildur wrote: The confusion is: void foo() Why should foo() be O(N) and bar() O(1) eventhough calling them always uses a constant amount of time since they do not change depending on their input? This is a tricky question, but I guess because '2' is (sort of) considered as a variable. You change it to "10", you have do_stuff() 10 times. On the other hand, you can't change just 1 variable/number/thing in bar() to have do_stuff() executed more than twice. The confusion may be about if you agree to imagine "2" as a variable instead of a number. I may be wrong, but this is just my thinking. Edit: If you really think about semantics of "constant", you really shouldn't be able to change the value. However, you can change it in the for loop case, so it's not really constant imho. It's what O(1) stands for: wikipedia Edit #2: On the other hand, constant time's definition says if you don't rely on input, then it's constant time. O(N) http://en.wikipedia.org/wiki/Time_complexity#Constant_time | ||
spinesheath
Germany8679 Posts
On August 12 2013 11:57 darkness wrote: This is a tricky question, but I guess because '2' is (sort of) considered as a variable. You change it to "10", you have do_stuff() 10 times. On the other hand, you can't change just 1 variable/number/thing in bar() to have do_stuff() executed more than twice. The confusion may be about if you agree to imagine "2" as a variable instead of a number. No, this is not how it works. Algorithmically, foo() and bar() are exactly the same thing which means they have the same complexity. You don't randomly consider hardcoded things as variables. There would be infinitely many possible interpretations (2 = f(2) aka O(N), 2 = f(4) aka O(sqrt(N)) and so on). And code isn't considered changeable in the first place. | ||
gedatsu
1286 Posts
| ||
Tobberoth
Sweden6375 Posts
On August 12 2013 11:26 Morfildur wrote: The confusion is: void foo() Why should foo() be O(N) and bar() O(1) eventhough calling them always uses a constant amount of time since they do not change depending on their input? Why would foo() be O(N)? I mean, if you simplify, you could say it's O(N) because it's one loop, but since the loop size is not dependent on input, it's just constant. | ||
obesechicken13
United States10467 Posts
O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set. bool IsFirstElementNull(String[] strings) Source: http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ Pretty sure some schools teach this differently. Can we put this to rest now? | ||
HardlyNever
United States1258 Posts
+ Show Spoiler + /******************************************************************************* I can't just remove the event helper, as this particular form needs it to do what it needs to do right. I may be able to come up with a simpler solution for getting the form to work if I can't figure it out. I don't 100% need recaptcha on this form, but it would be nice as we've had a few spam bots hit it. | ||
heroyi
United States1064 Posts
| ||
Encdalf
Germany66 Posts
On August 13 2013 01:34 HardlyNever wrote: Anyone with a lot of experience with recaptcha? I got it to work on one of the forms I made, but I can't get it to work (it always fails, no matter what) on another form someone else made but I need to add it to. I've isolated the problem to an event handler javascript piece that for some reason always causes a fail. I'm not super familiar with javascript, especially if someone else wrote it (and this is kinda big), and was wondering if anyone has a similar problem in the past. Somewhere in here is the part that is causing the recaptcha to always fail (I'm thinking it is one of the set global variables, but I'm not sure). I believe it is some premade piece of script that a lot of people use. Warning, it is pretty big: [...] I can't just remove the event helper, as this particular form needs it to do what it needs to do right. I may be able to come up with a simpler solution for getting the form to work if I can't figure it out. I don't 100% need recaptcha on this form, but it would be nice as we've had a few spam bots hit it. I'm sorry, but without any further context, I doubt anyone will be able to help you. This is a problem caused by the combination of scripts on your page, and without a live example these things are pretty hard to track down. Or to put it into a metaphor.. You get a combustion engine to a mechanic, and tell him "I think this eingine is broken.". "Why?" the mechanic asks. "Well, I checked everything and I believe it's the engine which is broken.". The mechanic checks the engine, but unfortunately the engine is brand new and working perfectly. The real problem was somewhere else: The car was electric. | ||
Shield
Bulgaria4824 Posts
Is it also a good idea to just use already implemented algorithms in the language you use? I've read that std::sort, Java's Collections.sort(), Linked List, etc are much more optimised than you would possibly implement them. | ||
Tobberoth
Sweden6375 Posts
On August 13 2013 17:19 darkness wrote: Where do you guys read/learn which algorithm is best for your problem? For example, I've read today that MergeSort is best for linked lists, while QuickSort is best for general use and that it is more memory efficient than MergeSort. Well, I guess that's logical when you know MergeSort uses additional array. Is it also a good idea to just use already implemented algorithms in the language you use? I've read that std::sort, Java's Collections.sort(), Linked List, etc are much more optimised than you would possibly implement them. You pretty much just have to learn various algorithms to know in what cases they are strong/weak. If you're sorting a huge list of heavy objects, you probably want something memory efficient, while if it's several smaller lists you might want something faster. I think best practice is to use library functions almost always nowadays, unless you specifically know that the language implementation is suboptimal for your problem at hand. It makes you far more productive and the designers of the language know what they are doing and specifically implement their algorithms to be good for the most common situations. It's also worth noting that optimization on the level of which algorithm to use often has a very small impact unless you're talking heavy calculations. Which sort you use for a few hundred string entries will probably not impact your performance noticeably. | ||
spinesheath
Germany8679 Posts
On August 13 2013 17:19 darkness wrote: Where do you guys read/learn which algorithm is best for your problem? For example, I've read today that MergeSort is best for linked lists, while QuickSort is best for general use and that it is more memory efficient than MergeSort. Well, I guess that's logical when you know MergeSort uses additional array. Is it also a good idea to just use already implemented algorithms in the language you use? I've read that std::sort, Java's Collections.sort(), Linked List, etc are much more optimised than you would possibly implement them. Yes, you always should use existing implementations by default. Especially if they come with the language or standard librariers. Only if you have very special requirements that existing algorithms can't fulfill you should look for a specialized implementation. You should almost never have to implement a sorting algorithm by hand. The fact that the existing implementations usually are more robust and faster than your own implementations doesn't even matter. It's mostly about saving coding and debugging time. Your code will be buggy at first no matter what, while existing code has been tested thoroughly. | ||
| ||