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=-1.9 required=5.0 tests=BAYES_00,LOTS_OF_MONEY autolearn=ham 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 00:24:40 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!feed2.news.rcn.net!rcn!wn14eed!worldnet.att.net!204.127.198.203!attbi_feed3!attbi.com!sccrnsc01.POSTED!not-for-mail From: Wannabe h4x0r Subject: Re: hashing(HATs. A more efficient algorithm?) Newsgroups: comp.lang.ada References: User-Agent: Pan/0.11.1 (Unix) Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Comment-To: "chris.danx" Message-ID: NNTP-Posting-Host: 12.245.48.122 X-Complaints-To: abuse@attbi.com X-Trace: sccrnsc01 1018596280 12.245.48.122 (Fri, 12 Apr 2002 07:24:40 GMT) NNTP-Posting-Date: Fri, 12 Apr 2002 07:24:40 GMT Organization: AT&T Broadband Date: Fri, 12 Apr 2002 07:24:40 GMT Xref: archiver1.google.com comp.lang.ada:22409 Date: 2002-04-12T07:24:40+00:00 List-Id: 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