Re: Efficient Matrix?

[Alvery Grazebrook <nospam@grazebrook.demon.co.uk>]

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