On Wed, 02 Nov 2011 19:24:03 -0400, Max Wolter <awishform...@gmail.com>
wrote:
On 11/2/2011 2:41 PM, Steven Schveighoffer wrote:
I never said you couldn't (and I've even given examples of such
implementations). It's just not neatly packaged into a method.
But again, if the method is exactly the same as the efficient version
for other containers, it becomes *impossible* to design an algorithm
that guarantees any sort of complexity. As I said before, quadratic sort
is epic fail, and needs to always be avoided.
I'll give you a scenario:
People often complain that Linked List does not have an opIndex on it.
Yes it's inefficient, but so what? "I know it's inefficient, let me
decide whether it's worth it or not."
So let's say I add it to LinkList. Those people are happy.
But now, LinkList becomes defined as a *random-access-range* according
to std.ranges. Therefore, std.algorithm.sort(linklist) compiles! And is
now something like O(n^3).
Whereas LinkList already defines a sort method, which uses mergesort
(O(nlgn)). So are you going to realize this when reading someones code
and you see:
sort(somelist);
That it's going to be horribly inefficient? Why shouldn't we strive for
a library where such things just don't compile?
Hello.
You generally arguing this is all nice and good, but this is a very
specific case.
I am using a LinkList because in my code, the elements are iterated over
a million times and during this, I add stuff in-between elements all the
time. However, I will be removing stuff *very* rarely. I am thus using
the appropriate container and it doesn't matter whether the remove will
be inefficient.
A linked list (any list really) is important if you want to maintain
insertion order. If that's not important, don't use a list, a hash or
tree is about as efficient. There exist (not in D) hybrid container types
that allow O(1) removal using value, and maintain insertion order.
In fact, the actual remove is not inefficient if you have a reference to
an element (not just the value). Unfortunately, for SList, this is not
the case, but it should be fixed at some point.
But I still maintain, anything in std.container is not just a container
for your code, it's a container that tries to cater to the most common
needs. If you want a remove(value) function, it is trivial to write.
To put it another way: if removing elements was of crucial importance to
the performance of my code in the first place, I wouldn't (and
shouldn't) be using a LinkList.
As long as you don't need to search for the element to remove using its
value, removal in a linked list should be O(1). A linked list that does
not allow O(1) removal and O(1) insertion given a topological reference is
a failure (yes, that includes the current version of SList).
Therefore, implementing an inefficient method which does this won't be
of consequence. Finally, the fundamental statement I'm trying to make
here is: adding and removing *single* elements should be a
straightforward method call for *any* container.
Adding, yes. Removing a container-selected element, yes. Removing a
*specific* element, no. Inserting an element in a *specific location*,
no. std.container has taken the stance that primitives should reflect the
efficiency of the operation.
This is not the only valid position to have. It's just std.container's
position. For example, Java allows this.
As a side note, your example about generic programming is really neat
and makes sense; personally, I would never want a linked list with
indexes and it's also a horrible analogy to the complaint at hand.
People have asked for it and argued vigorously for it on this newsgroup,
just as you are arguing for this.
-Steve
