News for hackers. Stuff that matters.
Re:Principles for C programming by userbinator on Thursday March 16, 2017 @07:39AM (#13884187)
I prefer attempting to find an O(1)-space algorithm over dynamic allocation, which I suppose means using fixed-size buffers anyway.

In my experience it is surprising how many programmers will --- regardless of language --- tend to settle for O(n)-space or higher algorithms when just a little more thought would produce a simpler O(1). Line numbering is a common example of this.

Re:Principles for C programming by renox on Sunday March 19, 2017 @10:05AM (#13907134)
Could you explain your point about line numbering?
Re:Principles for C programming by MaulingMonkey on Monday March 20, 2017 @01:50AM (#13912040)
Take, for example, displaying the context source code for an error when you know the file and lineNo of the error.

A naive approach would be to read the entire file into an array and then to output the lines [lineNo-context..lineNo+context], possibly with line numbers prefixed. This is O(N) memory with regards to the size of the file being processed. A 8GB source file will crash your program when built for 32-bit.

Another approach is to read and discard until you've discarded lineNo-context '\n' characters, then copy chunks from your source directly to the output until you've read another 2*context+1 characters. This is O(1) memory (strictly speaking, you could do it byte-by-byte with an integer counter or two - practically you might have a fixed size buffer to read/write faster) and would allow you to handle even 1TB files sanely.

To be fair, I'm often guilty of the naive approach myself :)