Patrick Dughi wrote:
> > search routines(BST's etc; i realize you can implement a bst with an
> > array but its really really nasty)
>
> Actually, its much easier to make arrays rather then linked lists,
> for just about anything. The only real downside to arrays is that
yes, its MUCH easier to make them. but its harder to manipulate them.(ie
add and remove records) in an array if you want to add an element you
can only do it if you reallocate the memory for the array(unless you
make the array big enough to hold new stuff, which circle doesnt do,
except for the stock implementation of spells, skills, etc.
if you want to delete a record from the array you must also reallocate
the array, or have some sort of sentinal value to mark the record
deleted.
both require copying the old info to the new info.
with a linked list, its a cinch to add a new record anywhere. all you do
is make the new structure and move 4 pointers around(if you use a doubly
linked list)
> normally, they're statically allocated, so usually you make them bigger
> than you could ever want, because otherwise, you could overrun them.
>
> Linked lists are usually dynamic - you can keep adding, and
by definition, a linked list is always dynamic.
> adding. As far as beginners are concerned, I'd say its rather easy to
> create memory leaks with linked lists. Of course, if you build up some
> control functions like 'remove from list' or 'add to list', a linked list
> is as simple (at the programming level) as the array. It just takes a bit
exactly, but its much easier to write abstract routines for a linked
list than it is for an array/table(well...perhaps not).
> more work to make it work as easily.
>
> Both of the types above can be put into any sorting algorithm
> rather easily. BST's are simple with arrays.. Incredibly easy as a matter
> of fact. Once you've written your control functions, they're just as
I hope you arent confusing doing a binary search on an array with
implementing a BST with an array. they are quite different. at least if
i remember correctly. its been awhile. yes, the routine to search an
array by a binary search is quite simple (about 30 lines or so). So is
the function so search a BST array(recursive, about 6 lines). but the
BST array is nasty nasty to setup(not to be confused with hard, just
ugly)in an array.
>easy with linked lists...
> The only advantage in this situation is lookup time - arrays have
> a lookup time less than or equal to linked lists... Think about it this
> way, if you have all the mobs in the game, and you want to load up a mob
> with a rnum of 700, you would have to go through a linked list structure
> 700 times before you reach your mob. With an array, it would be
> mob=mob_list[700]; (well, sorta). Of course, searching would take the
actually, with a BST implementation it would be significantly less than
that.
the average lookup time for a BST is lgN where the average lookup
time(operations) in an ordered array is N/2. Thats significant with an
array/list of 20 or 30 thousand elements.(15000 operations vs a little
under 5 operations). The worst case for both implementations is N
operations. so the BST is to be far superior for doing a search,
especially in large lists. also, if you are searching for a string(ie
player name) it doesnt affect the search times in a BST. if you have an
array of strings, you cant just say goto array[string] and get the
element so the example of saying mob=mob_list[700] only applyies a small
portion of the time. that is one good thing about an ordered array of
integers tho.
> same time, but I'd think incrementing an integer would be easier to
> understand than using control functions - to a new programmer..
>
my main concern tho is adding and removing items from the world files,
mob files, player files, etc while the mud is running. the code to do
this with a linked list implementation would be so much more simple than
it currently is would almost make it worth it to convert all the storage
schemes to the linked
list structure.
one thing i'm thinking about tho, with a BST, you can only search on the
KEY that the BST was sorted by. if you search for any other item in the
structure you are basically getting the same thing as an ordered array,
because you will have to search (on average) N/2 elements before you
find the one you want. right off the top of my head, i cant recall just
how many searches are done on members of the structres other than the
key. drat. dagnabbit.
i suppose it would be beneficial to implement the linked list scheme and
make a file called search.c or sort.c which implements all your basic
functions. then it would be just like a library.(unless you wanted to
use existing libraries which are out there). But, combined with
abstraction, i would think BST's would significantly increase the
efficiency. but no more ram or cp than Circle takes up, compared to
today's machines, its probably not worth it to mess with it other than
if you are a typical obsessive coder who has to have the fastest and
most efficient code there is :)
bill
--
reply to bill<@>longboys.net(remove the<>)
...spam avoidance policy in effect.
check out www.giftsgalore.com, lots 'o neat stuff there.
Happy New Year
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://qsilver.queensu.ca/~fletchra/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/15/00 PST