Hacker News Reader

Comment by thecopy | Hacker News Reader

Do i really _must_ know 1) Big O notation, 2) common algorithms and their time and space complexity, 3) which opcodes exist for a CPU of your choice and 4) a kernels main system calls?

I dont know any of these. I know they exist, i know of the concepts, but no specifics. I would argue that these are good to know, and a must if you are working in a domain where this matters. For design, architecture and implementation in a high level language when the problem do not touch these areas this is not a MUST have.

View on HN

> Do i really _must_ know 1) Big O notation

Big O's not too hard. I would imagine that most programmers have an intuitive feeling for them. For example:

If I need to use a loop, that's going to slow things down (formally, going from O(1) to O(n)).

If I keep putting loops inside loops, it's going to get really slow (formally, going from O(n^x) to O(n^(x+1))).

Each element requires all the previous to be processed again. That's not going to work (formally, reaching O(2^n)).

Maybe some fancy datastructure would speed this up (formally, going from O(n) to O(log n)).

> 2) common algorithms and their time and space complexity

I think this just boils down to appreciating what kind of work must be going on in some algorithm. For example, sorting a list is surely going to loop through it (i.e. O(n)); actually it's O(n * log n), but that's pretty close.

I would imagine that the most effective knowledge for a complete beginner would be bad usage patterns for a bunch of common datastructures. For example, a loop which appends to the end of a linked list is a bad idea, since finding the end of the list requires looping through all the nodes. This is a loop inside a loop (AKA O(n^2)) when we intuitively know that only a single loop is required (AKA O(n)).

> For example, a loop which appends to the end of a linked list is a bad idea, since finding the end of the list requires looping through all the nodes. This is a loop inside a loop (AKA O(n^2)) when we intuitively know that only a single loop is required (AKA O(n)).

That would be indicative of a bad/naive linked-list implementation, wouldn't it? It's not that much overhead to maintain a wrapper with front and back pointers.

Well, there are some caveats. Firstly, that would technically be a double-ended queue ("dequeue") rather than a linked list. That's fine if you're using it as an abstract datatype, i.e. you're doing things like "myList.append(foo)", "myList.get(0)", etc. and hence you're able to swap out the implementation of those methods.

There are some widespread cases of these naive datastructures which don't fit that model though. For example, Lisp makes heavy use of "cons" to pair up two values. By nesting these pairs, we can get arbitrary tree structures, and this is how lists are implemented, e.g. "(list 1 2 3 4)" is equivalent to "(cons 1 (cons 2 (cons 3 (cons 4 nil))))". These structures are heavily used in Lisp (since it does so much "LISt Processing"), and since the language is so dynamic it's hard to compile it away.

Haskell's default list type works in this way too. There, the problem is compounded by immutability: changing the start of a list is easy, since we can re-use the pointer (immutability allows a lot of sharing). For example, if "list1" is "[1, 2, 3]" and "list2" is [9, 2, 3]", they can share the "[2, 3]" part:

                1
                ^
                |
    list1: cons * *----+    2           3
                       |    ^           ^
                       V    |           |
                       cons * *--->cons * *--->nil
                       ^
                       |
    list2: cons * *----+
                |
                V
                9

However, if "list3" is "[1, 2, 5]", it can't share any of the "list1" or "list2" structure: the last element is different from the other lists, which requires the second-to-last element to use a different pointer, which makes it different from the other lists (even though it uses the same element); this requires a different pointer in the third-to-last element, and so on:

                                        5
                                        ^
                                        |
    list3: cons * *--->cons * *--->cons * *----+
                |           |                  |
                V           |                  |
                1           |                  |
                ^           |                  |
                |           V                  |
    list1: cons * *----+    2           3      |
                       |    ^           ^      |
                       V    |           |      V
                       cons * *--->cons * *--->nil
                       ^
                       |
    list2: cons * *----+
                |
                V
                9

The problem's not as bad in Haskell as it is for Lisp: Haskell doesn't allow as much dynamic behaviour, so a lot more usage information is available during compile time, and allows optimisation like "list fusion". Also, Haskell makes it easy for programmers to define their own datatypes (like dequeues), and allows datatypes to be abstract (either using typeclasses or "smart constructors"). Being abstract makes pattern matching more difficult though (requiring "views").

Ah, I was thinking more in terms of C/C++/Java/C# style linked lists, which tend to look something like this:

  class List<T> {
    ListNode<T> head;
    ListNode<T> end;
    int size;
  }
  class ListNode<T> {
    T data;
    ListNode<T> next;
    // possibly, if it is doubly-linked
    ListNode<T> prev;
  }

3 and 4 are only needed in specific domains.

1 and 2 you won't need every day. You can probably even make a career out of software not knowing them. But every software related domain will have times where knowing them will help you, and where not knowing them risks an inefficient and slow implementation and no way for you, individually, to fix it in any sort of reasonable time; you'll either have to learn it then, or you'll be reliant on someone who does know it fixing it for you.

I've had to address performance issues where knowledge of common data structures and algorithms' time and space complexity (and/or being able to look at an algorithm and realize "...this is O(n^2). It only needs to be O(n). WTF", and fixing it) was the key in Javascript, Erlang, Python, and Java. Exactly what 'high level language' do you feel you won't eventually need this stuff in?

1) and 2) are a MUST across the stack I believe. A lot of those crazy snippets from thedailywtf etc. come from the lack of this knowledge and suddenly performace suffers a lot when someone tries some O(n!) for simple stuff. Also, not to put anyone down but... it is kinda embarassing imho to not know how fast can you sort.

Probably a controversial topic, as this touches on holy grails. My personal take on this, given my own experience so far:

1) You don't strictly need to know Big O notation in order to not introduce performance bottlenecks, or mitigate them when they arise; but you should be able to use common sense resource wise, when developing things in any problem area. In other words: you should conceptually understand how computer systems work (which often implies you'll sooner or later run into Big O notation). Knowing Big O notation can also help you communicate with your peers about problems, if they know it too. 2) For a large number of problem areas, this is knowledge that is near useless I think. Know that they exist, and that they might ever help you. But for your average problem domain, you don't really need concrete knowledge there. It bothers me how much emphasis is put on this in so many job interviews, while it's hardly ever relevant in many of those cases. 3) I'm not sure how that knowledge will really help you. 4) I think this is actually the most important thing of all four. Knowledge of the kernel's main system calls will help you tremendously when your process (or any process in your stack) "just hangs" sometimes and you need to resort to systems such as strace, dtrace, sysdig and what not. That time will come, sooner or later.

> 4) I think this is actually the most important thing of all four.

I was surprised to see this so far down. I, on a somewhat regular basis, go back to system calls. Usually it's related to needing to strace a process, but it is also helpful when thinking about what's going on when I'm writing some high-level code and how that will be translated into calls to the kernel versus user-space execution.

Oh, but I really like watching the algorithm sorting gifs. They're neat.

When you find your self asking this question think..."Am I naive about the subject" Naive = Not knowing you don't know. Ignorant = Knowing your don't know. Many years in IT (40) has taught me a little base knowledge like this goes a LONG way.

Code written by people who don't know 1 and 2 tends to make the mistakes that you learn to avoid by learning 1 and 2. And these are mistakes that you can make anywhere in your code and that can be very costly in performance and correctness.

1 and 2 are critical for anything which you want to scale at all.

3 is mostly irrelevant unless you're doing embedded devices or fast maths. If you're writing Java it might be more useful to know JVM bytecode opcodes and underlying CPU opcodes are completely irrelvant to you.

4 I think you need to understand the existence of the system call mechanism; then learning the API you realise how much of it is just syscalls (e.g. open/read/write/close).

I can write Windows code quite happily without understanding its syscall mechanism.

1 and 2 were answered by others. In my opinion, 3 and 4 make you better understand the reality which makes you a better programmer. Chances are that you will not use this knowledge. On the other hand it could give you some useful ideas.

I think you definitely need an awareness of 1 and 2 but you don't need to know all details. Just be prepared that things that work great at your current scale may not work once you scale up 100x.

Reply on news.ycombinator.com