On 10/10/2010 02:05, Jonathan M Davis wrote:
On Saturday 09 October 2010 06:54:31 Stewart Gordon wrote:
<snip>
Surely, what matters most for generic code is that in has consistent
_semantics_, rather than the computational complexity?
Stewart.
_Both_ matter.
True, yet you don't address semantic differences at all in what follows,
so it doesn't really follow on from what I said. But anyway....
Imagine, for instance, if we were to make Java's mistake of having List be an
interface which ArrayList and LinkedList implement and that List has a get()
function. Using ArrayList, get() has a complexity of O(1). Using LinkedList, it
has a complexity of O(n).
Are you suggesting we just don't have a List interface, just to prevent
people from writing algorithms that work well in some list
implementations but poorly in others? I'm not sure if that risk
outweighs any benefits....
Now, imagine code written with List rather than
ArrayList or LinkedList directly. If you use get(), then your code will vary
considerably in how efficient is. In small cases, this won't matter, but with
large lists, it could matter a lot. Your generic code which uses List _has_ to
worry about the computational complexity of get() or it could become very
inefficient. In this case, for most situations, that would mean using a foreach
loop or iterators directly, but using get() is likely a _bad_ idea. You need to
know the computational complexity of get() in order to use List efficiently.
Indeed. But what is an efficient algorithm depends on how the data
structure works in the first place, not just the computational
complexity of particular operations. It is perhaps for this reason that
it is foolish to try to write such generic algorithms.
An example of this is Collections.sort(List) in Java, which gets around
it by dumping the list into an array, an operation which itself adds
overhead. Better would be to have sort as a method of List, so that for
each list class an efficient implementation of sort can be provided.
To write efficient algorithms, you _must_ be able to rely on certain complexity
guarantees for the operations that you use. So, regardless of what those
complexity gurantees actually _are_, they need to be there.
Setting the complexity guarantee of everything to O(n!) would achieve
_that_ aim in most everyday cases.... :)
Stewart.
