Re: your mail

From: Sean Butler (sbutler@DEVEAST.COM)
Date: 11/08/97


On Sat, 8 Nov 1997, Sean Butler wrote:

-->Actually, with a sorted list of idnumbers:

Daniel wrote:
>Sorted?  Someone say sorted?

Yes, I said sorted is that so hard to understand.
When you add a number to the list, you make sure to
insert the number it the right place.  Probably using
a binary insertion sort since the list should already
be sorted.

* Joe introduces himself to you.
* Joe's ID number is 42.
* Find where 42 should go in your list of acquaintences.
* Insert 42 in the list.

Since it will only be called when you are introduced to
someone, the sort can't possibly lag the mud.

If the list is sorted, you reduce the time it takes to
check to see if someone has been introduced to you by at least
1 order of magnitude.


-->is the worst case.  And its not searches, it's comparisons.

>Sorry for the terminology, but I have no formal training in this.

Whatever man, I just didn't want someone to get the idea
that it would take 47000 searches (which are many comparisons
each.)



     +------------------------------------------------------------+
     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
     +------------------------------------------------------------+



This archive was generated by hypermail 2b30 : 12/08/00 PST