Re: String Buffer

["Randy Brukardt" <randy@rrsoftware.com>]

"Jeffrey R.Carter" <spam.jrcarter.not@spam.acm.org.not> wrote in message 
news:sobcg4$tc4$1@dont-email.me...
> On 2021-12-02 21:15, Dmitry A. Kazakov wrote:
>>
>> It is true only to a certain degree. When comparing algorithms it is 
>> valid to claim inefficiency without any context if computational 
>> complexity sufficiently differs.
>>
>> For example, an O(N) algorithm is unquestionably inefficient comparing to 
>> O(log N) one. I leave marginal cases of very small N.
>
> This is false. If you have the O(N) algorithm and it meets your 
> requirements, then using it is more efficient than implementing the O(log 
> N) algorithm. If you have both and the O(N) algorithm meets your 
> requirements, the effort to get your data into a form where you can apply 
> the O(log N) algorithm may still outweigh the time difference.
>
> As for "very small N", I have worked on systems where linear search was 
> efficient for sequences of 100,000 items.

And it isn't unusual that you *are* working mostly with small N. Case in 
point: The Janus/Ada parser table lookup routine. At one point, I tried to 
speed it up by implementing a binary search algorithm. (The table is 
logically a 2-dimensional array with the action being the element, but the 
majority of the elements are error markers [which have no information]. The 
usual storage is to omit those and store pairs of terminal/action. That's 
many times smaller for a language like Ada.) The binary search seemed to 
*slow down* parsing! I spent a week building instrumented versions, and 
determined that the average number of pairs was about 8, and the binary 
search (which necessarily was much more complex than a linear search) was 
slower until the number of pairs was about 20. So it only helped the largest 
states.

I ended up doing two other things instead: coding the lookup routine in 
assembler, which got the lookup loop down to about 5 instructions (it might 
be possible for a compiler to write that loop with fancy optimizations, but 
I've never seen one that could, and Janus/Ada certainly isn't able), and 
then I restructured the parse table to optimize lookups (terminals don't 
appear with a uniform frequency in code). The net result was that average 
lookup takes 1.6 iterations (of a 5 instruction loop); the binary version 
(which executed a lot more code) took somewhere around 3.5 on average.

The point is, simpler can often be better (especially as it is more likely 
to work the first time). And if it proves necessary to improve it, nothing 
really substitutes for instrumenting the actual application.

                                  Randy.