104

When you see a good move, look for a better one. —Emanuel Lasker, 27-year world chess champion In my experience, the biggest driver of accidental complexity is programmers sticking with the first draft, just because it happens to work. This is something we can learn from our English composition classes. They build in time to go through several ...


91

As Mikey mentioned, writing bugless code is not the goal. If that is what you are aiming for, then I have some very bad news for you. The key point is that you are vastly underestimating the complexity of software. First things first--You're ignoring the bigger picture of how your program runs. It does not run in isolation on a perfect system. Even the ...


76

The very first words of TC++PL4: All problems in computer science can be solved by another level of indirection, except for the problem of too many layers of indirection. – David J. Wheeler (David Wheeler was my thesis advisor. The quote without the important last line is sometimes called "The first law of Computer Science.")


60

Because it's extra effort to create and maintain such a document, and too many people don't understand the associated benefits. Many programmers aren't good technical writers (although many are); they rarely write documents strictly for human consumption, therefore they don't have practice and don't like doing it. Writing a code overview takes time that you ...


46

"Software architecture skill cannot be taught" is a widespread fallacy. It is easy to understand why many people believe it (those who are good at it want to believe they're mystically special, and those who aren't want to believe that it's not their fault that they're aren't.) It is nevertheless wrong; the skill is just somewhat more practice-intensive ...


44

It is typically called "performance optimization", but I would not call it "refactoring", since this term typically refers to changes in code which don't change its visible behaviour. And a change in Big-O is definitely something which I would call a visible change. in doing so I will change the fundamental way the operation runs In this case, your ...


36

You're basically correct about P and NP, but not about NP-hard and NP-complete. For starters, here are the super-concise definitions of the four complexity classes in question: P is the class of decision problems which can be solved in polynomial time by a deterministic Turing machine. NP is the class of decision problems which can be solved in polynomial ...


34

You've overlooked the key characteristic of the logarithm base. Because i is divided by 2 in each iteration, the running time is logarithmic with base 2. And log2(500) ~ 8.9 What you are looking at is log10(500) ~ 2.7 (logarithm with base 10) By the way, the reason why the base is often omitted in runtime discussions (and your calculator probably ...


31

Well, my guess would be order, which coincides with wikipedia. Edit: (my own (any improvements appreciated)) translation from the German wikipedia article The capital letter O (actually a capital omicron at the time) as a symbol for the order of (German: "Ordnung von") was first used by the German number theorist Paul Bachman in the second issue of ...


31

I know with O(n), you usually have a single loop; O(n^2) is a double loop; O(n^3) is a triple loop, etc. How about O (log n)? You're really going about it the wrong way here. You're trying to memorize which big-O expression goes with a given algorithmic structure, but you should really just count up the number of operations that the algorithm requires and ...


30

In a way, you answered your own question with that remark in the last paragraph: I am starting to think the DRY principle does not apply as much in this kind of situation, but that sounds like blasphemy. Whenever you find some practice not really practical for solving your problem, don't try to use that practice religiously (word blasphemy is kind of a ...


30

Yes, definitely. The thing is, no abstraction is perfect. All of the details of the layer that abstractions sit atop are there for a reason, and it can simplify a lot of things, but if that complexity wasn't necessary at some point, it probably wouldn't be there in the first place. And that means that at some point, every abstraction is going to leak in ...


28

The most frequent term I heard to describe such designs is overengineering. The original meaning of that word, however, is not related to software development, and outside of software development it has probably not such a bad tone. On a more general level, Joel Spolsky gave designers who overcomplicate architectural designs the name "architecture ...


27

Mathematically it MIGHT be possible to write 'bugless' software of such complexity, depending on how you define 'bug'. Proving it MIGHT also be mathematically possible, by designing a test system that would exercise every line of code in every possible way - every possible use case. But I am not sure - if you are dealing with a system that does complex ...


27

In my view, the explicit else block is preferable. When I see this: if (sky.Color != Blue) { ... } else { ... } I know that I'm dealing with mutually exclusive options. I don't need to read whats inside the if blocks to be able to tell. When I see this: if (sky.Color != Blue) { ... } return false; It looks, on first glance, that it returns ...


26

According to this article, the on-board software for the Space Shuttle came very close -- the last three versions of the 420,000 line program had just one error each. The software was maintained by a group of 260 men and women. A large number of these people were verifiers, whose sole purpose was to find errors. The upgrade of the software to permit the ...


25

Your questions has the answer in it. Adding man-power to a project that is running late, only makes it worse because the communication overhead increases in a non-linear way. It's already been studied. Read "The Mythical Man-Month".


24

The idea is that an algorithm is O(log n) if instead of scrolling through a structure 1 by 1, you divide the structure in half over and over again and do a constant number of operations for each split. Search algorithms where the answer space keeps getting split are O(log n). An example of this is binary search, where you keep splitting an ordered array in ...


23

The principal reason for removing the else block that I have found is excess indenting. The short-circuiting of else blocks enables a much flatter code structure. Many if statements are essentially guards. They're preventing the dereferencing of null pointers and other "don't do this!" errors. And they lead to a quick termination of the current function. ...


22

The O(...) refers to Big-O notation, which is a simple way of describing how many operations an algorithm takes to do something. This is known as time complexity. In Big-O notation, the cost of an algorithm is represented by its most costly operation at large numbers. If an algorithm took n3 + n2 + n steps, it would be represented O(n3). An algorithm that ...


22

First thing that comes to mind is that the security of public-key cryptography currently depends on being unable to brute-force math problems that are in the NP difficulty class. If P = NP, everything that depends on PKC (including HTTPS, which means the entire modern, worldwide ecommerce infrastructure) would have to be reworked!


22

Pragmatic thinking by Andy Hunt addresses this issue. It refers to the Dreyfus model, according to which there are 5 stages of proficiency in various skills. The novices (stage 1) need precise instructions to be able to do something correctly. Experts (stage 5), on the contrary, can apply general patterns to a given problem. Citing the book, It’s often ...


21

This is a question I am interested in and I have been doing some research on. For other viewpoints, see this blog post by Noel Walsh or this question on Stack Overflow. I have some opinions I would like to offer: I think Akka, because it works with messages, encourages a "push mindset". Often, for concurrency, I would argue this is not what you want. Pull ...


20

It's worth considering what the actor model is used for: the actor model is a concurrency model that avoids concurrent access to mutable state using asynchronous communications mechanisms to provide concurrency. This is valuable because using shared state from multiple threads gets really hard, especially when there are relationships among different ...


18

Your mistake is with the inner loop. It does something constant n times, so it is O(n). The outer loop does the inner loop n times, so it is O(n × n), or O(n2 ). In general, if the number of iterations a loop makes is dependant on the size of the input, it is O(n). And if k such loops are nested, it is O(nk ).


18

This is covered in The Status of the P Versus NP Problem. Definitely worth a read. A few salient points from the article (quoted from the What If P = NP? section): Public-key cryptography becomes impossible. Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled ...


17

child classes use different types, the calculation varies a tiny bit from class to class. First and foremost thing is: First clearly identify what part is changing and what part is NOT changing between the classes. Once you've identified that, your problem is solved. Do that as the first exercise before starting the re-factoring. Everything else will fall ...


16

"Big" means "capital", and "O" means order, as in "order of complexity". So named because of the convention of writing "order of complexity" as O(f(x)), e.g., with a capital letter 'O', or a 'Big O'. Nobody talks about it much because 'everyone' understands what it means, and understanding it doesn't really help you understand complexity analysis. For ...


Only top voted, non community-wiki answers of a minimum length are eligible