From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,FREEMAIL_FROM, LOTS_OF_MONEY,REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,eec376a334ad59ed X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-04-12 08:05:24 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.mathworks.com!solaris.cc.vt.edu!news.vt.edu!msunews!not-for-mail From: "Chad R. Meiners" Newsgroups: comp.lang.ada Subject: Re: hashing(HATs. A more efficient algorithm?) Date: Fri, 12 Apr 2002 11:00:10 -0400 Organization: Michigan State University Message-ID: References: Reply-To: "Chad R. Meiners" NNTP-Posting-Host: arctic.cse.msu.edu X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Xref: archiver1.google.com comp.lang.ada:22429 Date: 2002-04-12T11:00:10-04:00 List-Id: So what does it have to do with hash tables? All you have here is an efficient method of expanding the size of an array. -CRM "Wannabe h4x0r" wrote in message news:YYvt8.11521$Gl6.6265@sccrnsc01... > On Thu, 11 Apr 2002 19:29:16 -0400, chris.danx wrote: > > > > "Wannabe h4x0r" wrote in message > > news:mRot8.209679$Yv2.66927@rwcrnsc54... > >> Lately I've been using Hashed Array Trees(or Tables), which have cut > >> the execution time by about %40, and has given me a memory savings of > >> about %20-%30. Note that I'm just progressing from the beginner to the > >> intermediate stage in my "skillz". > >> > >> Basically, you start with an initial array of n number of elements. The > >> first element is a "pointer"(however one may choose to define that) to > >> the last element of the array. When the array is filled to n-2 > >> elements, automatically add x additional elements to the array, and > >> them set the pointer in the first element to point to the end of the > >> array again(which should be n+x_l). > >> One can use any number of methods to decide how many elements to add at > >> any time, it's not fixed. For an additional bit of buffer overflow > >> protection, one could set the pointer to point to n-2 (or n-1 or > >> whatever) depending on whatever makes sense at the time. > >> > >> This is about the simplest damn algorithm in the world, at least to me > >> it is. Heh. > > > > I don't really get it, but this sounds like chains to me. Can you > > explain it a bitty more? > > > > bye, > > Chris > > > > > > Alright. > > Suppose you have some numbers like 1,2,3,4(or could be > characters, or whatever). > The actual array would look like (using psuedocode) > > array := (pointer(array'range - 1),1,2,3,4,NULL); > -- The pointer points to the NULL at the end of > -- The array. Of course I'm using NULL here as > -- a placeholder for the psuedocode. The NULL > -- element could hold anything to indicate that > -- says "This is the end of the array" > > Now you want extend that array to hold four more values. > Look at where the pointer in the first element is > pointing, jump to that element in the array, add five > more elements from that point(one to hold the reference > element), then change the pointer to point at the end > of the array again. The extended array will look like > this... > > array := (pointer(array'range-1),1,2,3,4, , , , ,NULL --The pointer now > points here.--); > > Then you just fill in the elements. > > array := (pointer(array'range-1),1,2,3,4,5,6,7,8,NULL); > > > This beats making a new larger array and copying all the elements over, > plus the new ones. Plus you can determine with fair degree of certainty > how much memory you'll need at any one time. Since your only working with > the specific elements you need, it saves processor time. And because your > not duplicating data in various moves and copies, it saves > memory(especially on very large files.) > It could be said that one does not need a reference pointer, but that > becomes problematic if you have more than routine modifying data in the > array. > To make the array smaller, just do the reverse. Move the reference > character(or integer, or bit, or whatever) to a point in the array, and > free all memory above that point. > > Amy I making any better sense. Dr. Dobbs had an article on this. I'll see > if I can find it. > > Chris