Please grow your buffers exponentially

Re:Please grow your buffers exponentially by sysk on Tuesday November 04, 2014 @04:39AM (#8555742)

I studied algorithmic complexity and software enfineering. I don't think there was ever a mention of buffers or how to allocate them. I do remember there was a brief mention of dynamically allocated arrays and that the usual way to do those was to double up their space when needed. Anyways, there are tons of programmers working in high level languages and I wouldn't call them rookies for not being C programmers.

[ Parent | on HN ]

Re:Please grow your buffers exponentially by chronial on Tuesday November 04, 2014 @04:59AM (#8555783)

You should have learned that the exponential growth is the precise reason why appending to dynamic growth arrays is O(1) – a very surprising and unintuitive result in my opinion. Not knowing about exponential growth, I would have sworn that that must be impossible. If this didn’t leave a strong impression on you, I would say that whoever taught you algorithmic complexity simply failed in this point.

[ Parent | on HN ]

Re:Please grow your buffers exponentially by metaphorm on Tuesday November 04, 2014 @01:21PM (#8558107)

the O(1) complexity is achieved as an amortized result, when taking the average time to append. which is exactly what we are allowed to assume for asymptotic analysis. however, i think we should be sensitive that real computers are machines in the real world can run into circumstances that differ greatly from the mathematical result.

for example, if you allocated a slightly too small array and then append to it just slightly too many items, you will trigger reallocation every time. ideally nobody ever writes code that bad and we get to assume that the O(1) behavior is always true. in practice we need to know how the actual algorithm works and make sure we don't accidentally code perverse cases.

[ Parent | on HN ]

Re:Please grow your buffers exponentially by chronial on Wednesday November 05, 2014 @08:09AM (#8561582)

Nope, that is not correct. Insert is always (amortized) O(1). This is worst time. There is no “bad case”. You only need to be aware that a single insert might take longer. But that is not relevant in an absolute majority of cases.

“Append to it just slightly too many items” – this “too many” makes sure that you appended enough items so that the expansion amortizes to O(1).

That’s the nice thing about a complete mathematical proof – it doesn’t leave any dodgy edge-cases.

[ Parent | on HN ]

Re:Please grow your buffers exponentially by marcosdumay on Tuesday November 04, 2014 @05:37AM (#8555902)

Yes, sure.

You should know that in the real world basing everything on asymptotic behavior does not work very well. That's why we profile things, because reality is way more complex than CS classes.

[ Parent | on HN ]

Re:Please grow your buffers exponentially by barrkel on Tuesday November 04, 2014 @06:03AM (#8555972)

Assuming with asymptotic behaviour, provided the constant factor is acceptable, ought to be your default. This is because software tends to need to work with greater volumes of data over time, on machines with more memory, and more and faster CPUs. If your algorithms grow with greater than linear complexity as a function of input, your software will tend to get worse over time.

[ Parent | on HN ]

Re:Please grow your buffers exponentially by hvidgaard on Tuesday November 04, 2014 @04:50AM (#8555761)

If you studied algorithmic complexity, you also know that doubling (or larger) the size of a fixed array when you need more space, is about the only way to ensure amotized constant inserts using continuous finite arrays (ignoring the cost of allocating the memory). From there you ought to deduce that allocating any fixed amount is going to blow up, in terms of big-O.

[ Parent | on HN ]

Re:Please grow your buffers exponentially by nitrogen on Tuesday November 04, 2014 @09:33AM (#8556622)

A buffer is a dynamically allocated array. The next step in CS+SE education should be teaching students how widely the lessons learned from theory can be applied in practice.

[ Parent | on HN ]