Re: setIndexFromMemberLoc: I finally go it!

[donalson]

I actually spent some time on this a while ago.  In fact if I remember Glen
and I had a discussion on the O(n) vs. O(1) matter.  I was complaining that
swarm was not O(1) on delete.  Here is Roger B's description which is better
than I can do (and also alreaady done.)  The discussion is continued
afterward.


The Basic Idea
--------------

The idea is the following. In a normal linked-list you will have
some kind of list-node containing pointers to the previous node
the next node and the data item stored in that node:

------------- ------------- -------------
| | | next | ---> | |
------------- ------------- -------------
| | <--- | prev | | |
------------- ------------- -------------
| | | element | | |
------------- ------------- -------------
|
|
V

-----------
| MyAgent |
-----------

Now, this works really well for insertion, traversal etc. etc. but if
you want to remove objects from lists (and you want to do it a lot, and
you have bazillions of objects in your list, you run into a problem
because object removal takes linear time in the number of elements
on the list (you basically have to go over every node and see if its
'element' pointer is equal to the agent you intend to remove and if so
the list node is removed).

Here is a really good fix for the problem. If we allocate some memory
within the object being stored for 'prev' and 'next' then you can do
away with the list-node data-structure and you get:

My Agent
------------- ------------- -------------
| | | | | |
------------- ------------- -------------
| | | | | |
------------- ------------- -------------
| | | next | ---> | |
------------- ------------- -------------
| | <--- | prev | | |
------------- ------------- -------------

Now, if you ask the list to remove an object:

[list remove: agent]

then the list will simply poke into the agent and 'tie' the previous
agent to the next agent, and there is no need for a linear time search.
In other words you go from O(N) to O(1), which is always a good thing :)

Now, the Swarm implementation of "remove: aMember", for Swarm 1.4.1 and I
think quite a few releases prior to 1.4.1 was this:
// In Collection.m
- remove: aMember
{
  id  index, member;

  index = [(id) self begin: scratchZone];
  while ((member = [index next]) && member != aMember);
  if (member)
      [index remove];
  [index drop];
  return member;
}

This seemed to me to be an O(n) procedure.

I just looked up the 2.0 version as well:

- remove: aMember
{
  id index, member;

  index = [(id) self begin: scratchZone];
  for (member = [index next]; [index getLoc] = = Member; member = [index
next])
    if (member = = aMember)
    {
        [index remove];
        break;
    }
  [index drop];
  return member;
}


I have to admit that I don't understand the "[index getLoc] = = Member" part
of the "for" loop.  I wasn't able to figure out where "Member" is defined.

I guess that this doesn't answer anything, especially setIndexFrom, but it is
more info...

Cheers,

   D3

BTW:  I tried to make a "generic" list object in C++ using a templete (which
is similar to dynamic binding, I think) and I am not sure that it is possible
to combine an O(1) delete and a true generic List object.  Go ahead guys,
prove me wrong!


*********************************************************************
* Doug Donalson                 Office: (805) 893-2962
* Ecology, Evolution,           Home:   (805) 961-4447
* and Marine Biology            email address@hidden
* UC Santa Barbara
* Santa Barbara Ca. 93106
*********************************************************************
*
*   The most exciting phrase to hear in science, the one that
*   heralds new discoveries, is not "EUREKA" (I have found it) but
*   "That's funny ...?"
*
*       Isaac Asimov
*
*********************************************************************



                  ==================================
   Swarm-Support is for discussion of the technical details of the day
   to day usage of Swarm.  For list administration needs (esp.
   [un]subscribing), please send a message to <address@hidden>
   with "help" in the body of the message.