commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael Smith" <mich...@iammichael.org>
Subject RE: [collections][PATCH] SequencedHashMap violates Map contract, has poor performance
Date Fri, 01 Feb 2002 14:24:43 GMT
> -----Original Message-----
>
> I just took a look at the code.
>
> There were a couple of details that are still not clear to me (as
> around the "sentinel" use) but it looks much better than what we have
> and it is e very complete implementation of the Map interface.

The sentinel style linked list is based on the algorithm described in
"Introduction to Algorithms" by Cormen Leiserson and Rivest, a book that
I highly recommend.  It allows you to pretty much ignore the boundary
conditions.

There are references to using sentinels on the web as well:
http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Dllists/
http://www.cs.utk.edu/~plank/plank/classes/cs360/360/notes/Dlists/lectur
e.html
http://www.cs.sunysb.edu/~algorith/lectures-good/node7.html
http://dept-info.labri.u-bordeaux.fr/~strandh/Teaching/MTP/Common/Strand
h-Tutorial/sentinel.html

> However (playing Jon) there is a code style issue there.

In using a sentinel?  I can update the code to describe the algorithm
used.  I'll do that as soon as I have time -- either this evening or
tomorrow.

> Michael, you sure save on lines of code but is is not so easy to read
> that way.

If you're still referring to the sentinel thing, it's not about lines of
code.  It's about efficiency of the algorithm.

Compare:

void remove(Entry e) {
  if(e == head) {
      // entry is at head of list, update head rather than previous's
next
	head = e.next;
  } else {
      e.prev.next = e.next;
  }
  if(e == tail) {
      // entry is at tail of list, update tail rather than next's
previous
      tail = e.prev;
  } else {
      e.next.prev = e.prev;
  }
}

To:

void remove(Entry e) {
  e.next.prev = e.prev
  e.prev.next = e.next
}


> Have fun,

always!

> Paulo Gaspar

regards,
michael

>
> > -----Original Message-----
> > From: James Strachan [mailto:james_strachan@yahoo.co.uk]
> > Sent: Friday, February 01, 2002 2:01 PM
> > To: Jakarta Commons Developers List
> > Subject: Re: [collections][PATCH] SequencedHashMap violates Map
> > contract, has poor performance
> >
> >
> > +1
> >
> > Sounds good to me.
> >
> > James
> > ----- Original Message -----
> > From: "Remy Maucherat" <remm@apache.org>
> > > > I've submitted this patch twice now (once back in
> mid-November, once a
> > > > week ago), but it still has yet to be committed.
> > >
> > > If nobody has time to apply or look at Michael's patches, how
> > about giving
> > > him karma on jakarta-commons ?
> > >
> > > Remy
> > >
> > >
> > > --
> > > To unsubscribe, e-mail:
> > <mailto:commons-dev-unsubscribe@jakarta.apache.org>
> > > For additional commands, e-mail:
> > <mailto:commons-dev-help@jakarta.apache.org>
> >
> >
> > _________________________________________________________
> > Do You Yahoo!?
> > Get your free @yahoo.com address at http://mail.yahoo.com
> >
> >
> > --
> > To unsubscribe, e-mail:
> <mailto:commons-dev-unsubscribe@jakarta.apache.org>
> For additional commands, e-mail:
> <mailto:commons-dev-help@jakarta.apache.org>
>
>
> --
> To unsubscribe, e-mail:
<mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail:
<mailto:commons-dev-help@jakarta.apache.org>



--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message