On 11/2/11 10:12 AM, Steven Schveighoffer wrote:
On Wed, 02 Nov 2011 08:40:19 -0400, Ary Manzana <a...@esperanto.org.ar>
wrote:
On 11/2/11 8:48 AM, Steven Schveighoffer wrote:
The basic response to this is, when dealing with containers generically
(that is, you know you have a container, but you don't know what type),
the "remove this element" operation is not necessarily a good primitive
to have.
Simply because from the myriad of containers, only some can implement
this operation efficiently. Java embeds this operation in the interface,
which means any interface you have to a container could potentially use
O(n) time to remove that element. Such an innocuous piece of syntax
*should* have a cost if it's not efficient IMO.
BTW, the original question doesn't provide enough information to say
"remove this element." Even in Java, if you aren't using the default
comparison, you must use a comparator method to determine which one to
remove. If cell.x == x && cell.y == y *is* the comparison operator for
the type, then the syntax gets much simpler, because you don't need to
pass a specialized comparison function.
In dcollections, removing a specific element (using the default
comparison operator for that element) on a *fast lookup* container is as
simple as:
container.remove(container.find(x));
Which removes the element x if it's found. However, this is not defined
for containers which use O(n) time to search (such as linked list), you
must use std.algorithm.find for that:
container.remove(find(container[], x).begin);
Should work, and takes O(n) time.
-Steve
I don't really understand what's wrong with inefficient methods. You
can have inefficient methods that are convenient, like removing an
element by the default comparison, or giving it a delegate to match
the element(s) to remove.
You profile your application. Is that method the bottle-neck? If so,
you change it to a more efficient one. If not, you are happy you had
that method there, performing in an inefficient way, but which doesn't
matter that much compared to, say, opening an SQL connection.
Programmers want to program, fast. They have schedules, they need to
deliver. They don't need to always find the best solution. They can
find a compromise between "working" and "fast", move on, and later
profile and worry about what matters most.
Programmers don't want to fight with the language or think "Oh, so to
remove an element I need to use this operation and combine it with
that one and with that other one"...
Or use the right container for the job?
Where it really comes into play is generic programming.
Let's say I write some algorithm that removes certain elements from a
container:
removeElements(C, T)(C c, T t[]...)
{
foreach(x; t)
c.remove(t);
}
What's the complexity of this algorithm? For a HashSet, for instance, it
will be O(n) where n is the number of elements to remove.
But for an ArrayList, it will be O(n*m) where m is the number of
elements in c.
But I'm sure in this algorithm I have for this app I'm making, my
collection won't have more than 50 elements. So everything will be O(1).
I need to remove an element from the collection. I really don't care
about the complexity of the operation, because if n is 50, everything is
O(1).
Why can't I have an inefficient (for you) remove operation that, for me,
will be ok? I don't want to spend 2 hours browsing the ranges algorithms
to figure out how to combine them to remove an element...
My point is, as someone else said it in another post: add inefficient
operations and tell the programmer so. Then he can decide what to do. If
he's sure that that performance penalty is not a big issue for him,
he'll be happy to have that method available.
