On Tue, 12 Oct 2010 10:48:26 -0400, Stewart Gordon <smjg_1...@yahoo.com>
wrote:
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....
No, what is suggested is that we build the complexity guarantees into the
interface. For example, if you had a List interface, and it could only
guarantee O(n) performance for get, you'd call it e.g. slowGet(), to
signify it's a slow operation, and define get to signify a fast
operation. Similarly, 'in' is defined to be fast, so it has no business
being a function on an array.
So you can still have the List interface, but you don't hijack the "fast
operation" of 'in' with a slow operation. This allows it to still provide
the slow operation, just not in a way that makes generic code use it
assuming it is fast.
-Steve
