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 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,13ab88b30e0f779d
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-12-26 16:35:38 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed.icl.net!newsfeed.fjserv.net!colt.net!kibo.news.demon.net!news.demon.co.uk!demon!grazebrook.demon.co.uk!nospam
From: Alvery Grazebrook <nospam@grazebrook.demon.co.uk>
Newsgroups: comp.lang.ada
Subject: Re: Efficient Matrix?
Date: Fri, 27 Dec 2002 00:23:18 +0000
Message-ID: <Vg9FFjG215C+Ewh5@grazebrook.demon.co.uk>
References: <3e0b2a66_4@news.bluewin.ch>
 <slrnb0mvgq.j0i.adi@drcomp.erfurt.thur.de>
NNTP-Posting-Host: grazebrook.demon.co.uk
Mime-Version: 1.0
Content-Type: text/plain;charset=us-ascii
X-Trace: news.demon.co.uk 1040949338 4480 212.228.3.39 (27 Dec 2002 00:35:38
 GMT)
X-Complaints-To: abuse@demon.net
NNTP-Posting-Date: Fri, 27 Dec 2002 00:35:38 +0000 (UTC)
User-Agent: Turnpike/6.02-S (<pKJPL7qH9Ucx5yYBxeodw6oVQz>)
Xref: archiver1.google.com comp.lang.ada:32325
Date: 2002-12-27T00:23:18+00:00
List-Id: <comp.lang.ada>

In message <slrnb0mvgq.j0i.adi@drcomp.erfurt.thur.de>, Adrian Knoth
<adi@drcomp.erfurt.thur.de> writes
>Jonas Gasser <jonas.gasser@dataflow.ch> wrote:
>
>> type MATRIX is array (POSITIVE range <>, POSITIVE range <>) of BOOLEAN;
>> type POINTER_MATRIX is access all MATRIX;
>> A : POINTER_MATRIX := new MATRIX(1..10000,1..5000);
>
>> ideas to optimize this.
>
>   pragma Pack (MATRIX);
>

There is another issue / option for efficiency - nothing particular to
Ada, just an alternative way to do a Matrix. This option works if you
have a very large array, and the array only has a fairly small number of
significant values in it. I would be guessing, and it depends on the
application, but if your array of booleans has most values False, and
only a few hundred or thousand True, then it would be more space
efficient to store a list of the elements which are actually set to
true.

As you are probably aware, your matrix will take up 5e7 bits, or just
under 10 Mbytes of storage, assuming the compiler is efficient in the
way it packs the data. This may not matter much if you are writing for a
workstation environment, but probably will matter for some types of
system.

To present this, you would probably want a structure something like
this:

generic
   First_Size, Second_Size : Positive;
package Sparse_Boolean_Array is

subtype First_Range is Positive range 1..First_Size;
subtype Second_Range is Positive range 1..Second_Size;

type List_Entry is
   record
      first : First_Range;
      second : Second_Range;
   end record;

-- you need to insert some structure to hold List_Entries in a
searchable
-- form in here. Perhaps a binary tree or hash-table.
-- The subprograms Value and Set will access the structure to handle
-- the data structure you choose.

function Value
      (pFirst : First_Range;
       pSecond : Second_Range)
return Boolean;

procedure Set
      (pFirst : First_Range;
       pSecond : Second_Range;
       pValue : Boolean);

end Sparse_Boolean_Array ;

-- 
Alvery Grazebrook