Re: Shifting memory to the right

Article View: bit.listserv.asm370

Article #129

Back to bit.listserv.asm370 Previous Next

#129

From: Edward E. Jaffe
Date: Fri, 30 Sep 2005 16:48

32 lines
3247 bytes

Michael Stack wrote:

> If you're going to do a binary search, why not use a balanced binary
> search
> tree?  If a tree node is a row, your link memory overhead would be
> relatively small and your search time would be comparable.  And if you
> are
> not inserting too many rows, the overhead for balancing should be small,
> too.  A lot less virtual (and real) memory used, as well.
>
> It's usually (!) less costly to manipulate a data structure than to move
> data around.  YMMV.  See Knuth, TAoCP, Vol 3, 2nd Ed. (Sorting and
> Searching) pp 471-473 for a discussion of using a balanced tree to
> represent a linear list.

In addition, if the search keys themselves are relatively small and
represent a small percentage of the total storage for each table entry,
it might make sense to place a copy of the keys into the tree structure
rather than always using the data pointer during the search. Avoiding
access to the real data when performing the search can help keep the
working set to a minimum. If the keys are large, this approach probably
isn't worth the extra storage requirements for the tree structure.

--
.-----------------------------------------------------------------.
| Edward E. Jaffe                |                                |
| Mgr, Research & Development    | edjaffe@phoenixsoftware.com    |
| Phoenix Software International | Tel: (310) 338-0400 x318       |
| 5200 W Century Blvd, Suite 800 | Fax: (310) 338-0801            |
| Los Angeles, CA 90045          | http://www.phoenixsoftware.com |
'-----------------------------------------------------------------'

Technical Details

Message-ID: <433D6C4C.5040603@phoenixsoftware.com>

Path:

arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!newsfeed.gamma.ru!Gamma.RU!sn-xit-03!sn-xit-11!sn-xit-05!sn-xit-14!supernews.com!149.173.6.116.MISMATCH!foggy!vm.sas.com!phoenixsoftware.com!edjaffe

References: <F57FDB5201A2AA488C21CC5CC9759029848D60@cdmail.cmscms.com> <6.2.1.2.2.20050930103912.05b381f0@ux.cs.niu.edu>

Show Full Headers

Complete Article Headers

X-Google-Thread: fcdcb,3e46d196c2b56e33
X-Google-Attributes: gidfcdcb,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: arc1-ca.pugleaf.net!g2news1.google.com!news1.google.com!newsfeed.gamma.ru!Gamma.RU!sn-xit-03!sn-xit-11!sn-xit-05!sn-xit-14!supernews.com!149.173.6.116.MISMATCH!foggy!vm.sas.com!phoenixsoftware.com!edjaffe
From: "Edward E. Jaffe" <edjaffe@phoenixsoftware.com>
Newsgroups: bit.listserv.asm370
Subject: Re: Shifting memory to the right
Date: Fri, 30 Sep 2005 09:48:12 -0700
Organization: SAS Inc.
Lines: 32
Sender: IBM Mainframe Assembler List <ASSEMBLER-LIST@LISTSERV.UGA.EDU>
Message-ID: <433D6C4C.5040603@phoenixsoftware.com>
References: <F57FDB5201A2AA488C21CC5CC9759029848D60@cdmail.cmscms.com>
            <6.2.1.2.2.20050930103912.05b381f0@ux.cs.niu.edu>
NNTP-Posting-Host: mozart.unx.sas.com
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: foggy.unx.sas.com 1128099141 19045 10.19.150.41 (30 Sep 2005 16:52:21 GMT)
X-Complaints-To: usenet@unx.sas.com
NNTP-Posting-Date: Fri, 30 Sep 2005 16:52:21 +0000 (UTC)
Comments: Gated by NETNEWS@VM.SAS.COM
Return-Path: <owner-assembler-list@LISTSERV.UGA.EDU>
User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716)
X-Accept-Language: en-us, en
Approved-By: "Edward E. Jaffe" <edjaffe@PHOENIXSOFTWARE.COM>
In-Reply-To: <6.2.1.2.2.20050930103912.05b381f0@ux.cs.niu.edu>
Return-Path: owner-assembler-list@LISTSERV.UGA.EDU
X-OriginalArrivalTime: 30 Sep 2005 16:52:18.0826 (UTC)
                       FILETIME=[51A7D6A0:01C5C5DF]
Originator: daemon@mozart.unx.sas.com

Reply to Parent Message