On Saturday 09 October 2010 06:54:31 Stewart Gordon wrote: > On 07/10/2010 15:22, Steven Schveighoffer wrote: > <snip> > > > The problem is with generic code. Generic code that accepts some type > > that defines the "in" operator. What can that generic code expect for > > performance when using "in"? As a general rule, generic programming must > > always assume the worst case, and if we have no rules for 'in', the > > worst case is linear. Which means generic code may not use 'in' when it > > would be a fast operation. Same thing with indexing. Try sorting a > > 'random access' range which uses a linear search on opIndex, and see > > what the performance is. > > <snip> > > Surely, what matters most for generic code is that in has consistent > _semantics_, rather than the computational complexity? > > Stewart.
_Both_ matter. 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). 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. 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. - Jonathan M Davis
