On Friday, 4 December 2015 at 09:50:15 UTC, Ola Fosheim Grøstad
wrote:
On Friday, 4 December 2015 at 09:33:42 UTC, ZombineDev wrote:
Well, I agree, but I didn't say hard real-time, only
performance requirements that are hard to achieve because the
system is large, and becuase it would cost even more if the
system was larger (slower).
Yes, if you are writing for large scalable systems then it is
interesting to know what the ceiling is, but then you probably
also want something that is no worse than O(log N). Say for a
chat service you'd know that the more expensive to develop
solution can scale to 10 million users (O(1)), and the less
expensive do develop solution will become very expensive to run
when you hit 1 million (O(log N)).
So Big-Oh can be useful when you work with very large sizes and
large variations, but in most cases I think it can be
misleading without a good description of the actual
implementation.
Another very useful measure in real time is the amount of
variation between repeated calls. Say if there is a guarantee
of <50% variation, you can measure actual running time and add
50% headroom on the hardware requirements. Some algorithms have
some fixed size tables they need to clear out every once in a
while and that can be very bad.
I strongly agree with what you said earlier that typical
complexity analysis is a too naive model for real-world systems.
Very often (e.g. due to the nature of real hardware) your time
may be dominated by constants. Or a function which looks like
O(1) is sometimes O(n), due to hidden complexity. This (the fact
that constants matter) is especially true when you aim for O(1).
And yes, variation of execution time is also very important.
However, here we're talking about API for containers and
algorithms and I think that putting the complexity in the
function signature is better than only using abstract data
structures, because it makes you more aware of the consequences
of your choice of data structures and algorithms that you make.
If we can figure out a way to put even more information it may be
even better.
