January 01, 1993
Hypercard Database TuningHYPERCARD DATABASE TUNING
Linked lists for greater performance
Jeff Elliott
Jeff, an engineer and freelance writer whose work has appeared in EIR magazine and the San Francisco Chronicle, can be contacted at 6945 Hutchins Ave., Sebastopol, CA 95472. Everybody knows that large HyperCard stacks are supposed to be slow. It's common knowledge, part of the same musty storehouse of wisdom that reminds you never to swim after a full meal, run while holding scissors, or believe a politician during an election year. If everybody knows it, it must be true, right? Common knowledge isn't always true, of course, except perhaps the bit about politicians. It certainly isn't true that large HyperCard stacks have to be sluggish. HyperCard may not match the speed of a true database engine like FoxBase, but HyperCard's find is no slouch either, taking only 20 seconds to search my database of over 3600 cards and find 190 matches--that's an impressive speed of about 180 cards per second. Not bad, but faster is always better, and searches can be up to 20 times faster if you use linked lists.
What are Linked Lists?Linked lists (as in links of a chain) tie together information scattered through a database. This information can be text in a particular field, the highlight of a button, or anything el e important enough to need frequently. A recipe database might have a "main ingredient" field that specifies whether a recipe uses chicken, broccoli, or other meats or vegetables. Each unique entry in this field would be linked together: fried chicken linked to General Tso's chicken, and so on. Another set of links may connect a popup that indicates the cuisine type: Chinese, Italian, or Mexican. As the different links thread their way through the stack they will sometimes overlap, as Chinese and chicken do in the recipe for General Tso's chicken. In addition to reducing search time because fewer cards have to be examined, linked lists can also be a powerful navigational tool. Each item linked provides an opportunity for the user to branch off in a new direction following a link trail. And, to give the browser as much control as possible (after all, this is a Macintosh), there can be a second link for each item, providing the freedom to move backward through the chain as well as forward. The benefits of linked lists--faster searches and easier browsing--can be lost if it is hard to find one of the cards with the link you need. A good solution is to maintain an index of all the linked strings. This index can be kept in a scrolling field from which the user may select a linked topic. The recipe stack, for example, would benefit from both a cuisine index and main-ingredient index, allowing simple and quick access to linked lists covering different topics.
HyperLinksUnfortunately, the only linking capability built into HyperCard is the linkTo option found in the button dialog, and it's unusable for linked lists. For starters, linkTo is one of the few things that cannot be used in a HyperTalk script. To link, therefore, the user must change to the button tool, double-click on a card-level button to invoke the dialog, click on linkTo, find the card to link with, click OK, and finally choose the browse tool again. Together, the link function and insert-Link subroutine (Listing One , page 41) provide a better solution. These routines make the linking process invisible to the user and create links for each topic on-the-fly. The link function also builds and maintains an index of all linked topics. The linking is fast, requiring only about 15 ticks to insert a new card into the chain, quick enough that it's probably not necessary to change the cursor or otherwise notify the user. The links are stored in one or more hidden fields on each card. The card ID is used for the links because it is guaranteed not to change if cards are added or sorted. All of the links can be stored on different lines of a single field, but there are some performance trade-offs when HyperCard has to work harder to find the link. Figure 1 compares the speed of fetching a link when it is alone in a field, when it is one of several items on a line, and when it is on a separate line. When speed is important, it's best just to have a single link in the field. Figure 1 also compares the performance of HyperCard's find when there are only two characters in a search string vs. three or more characters. It's well known that triplet searches are quicker, but I was surprised to discover that they're over 20 times faster. This is another advantage to using linked lists: Because we're using card IDs instead of find, there's no performance difference if there are fewer than three characters in the search string.
Linking Your StackTo build your own linked lists, drop the link and insertLink functions into the stack script of your HyperCard stack. As mentioned previously, there are advantages to using the linked lists with an index. They provide fast search access to a card with the desired link, and also a simple way for the user to select a linked topic. These routines expect you to have a card named index with both a back ground field hiddenIndex and a card field index. Field index only has the selectable text strings, and hiddenIndex (which obviously should be a hidden field) has three items on each line: the string that the user sees, the ID of the first card in the link, and the count of how many cards share the link. The index field is not technically necessary, but it keeps things neat. Both fields must have the "don't wrap" and "lock text" options turned on. When the user clicks on a line in the index field, the script looks up the string in hiddenIndex and takes the user to the first card in the linked list. Listing Two (page 41) is the script for field index. The link handler has four parameters: name, linkf, n, and i. The name parameter is a string to search for in field hiddenIndex on the index card. If this name is not found, it is added to the index. Otherwise, this card is linked into the chain of other cards that share the name string in this field. The next three parameters, linkf, n, and i, all refer to the same background field on the card being linked. linkf is the name of the field that holds the links, n is the line number, and i the item number for the forward link. The backward link follows as item i + 1. If you're only linking a single field, you may want to simply have an Add Link button that prompts for a string (new or existing) and creates a new linked card for the user. Listing Three (page 41) shows what the script for this button might look like. If you have more than one object to link, you should call link whenever data has been entered; you don't want to clutter the cards with a multitude of special buttons. When you are linking text fields, the closeField handler is an ideal time to call link because this message is sent only when something has been entered or changed in the field. Once the links are in place, you can use them for navigation. In my HyperCard stacks, each field and group of buttons that is linked has an adjoining pair of arrows that allow the user to branch off and follow a particular link. The scripts for these navigational arrows should read something like:
go card ID item 1 of line 3 of field links where the item 1 of line 3 is the next link in that particular chain.
[LISTING ONE] [LISTING TWO] [LISTING THREE]
Copyright © 1993, Dr. Dobb's Journal 
Previous Page |
1
|
2
|
3
|
 |
|||||||||||||||||
|
|
|
more
