Solved

ultra huge array of Bits (Boolean)

Posted on 2006-11-28
6
347 Views
Last Modified: 2010-04-05
i Want to create a bit array , size [1...1E6, 1...1E6] or even a little bit bigger.  .-))  
I used a TList Object and a Bool-Pointer
max. array size is only 1E5x1E5 . Any Hint thow o blow up my record size?
the function TBitplane.Init_BitArray  should run with stepx=1E6.. and function stepy=1E6...

------------------
some trial code
------------------

type
       TPointBoolZ = record
               // x  : Integer;    {  x index = 0...n, removed, changed to lin. Address }
               // y  : Integer;    {  y index = 0...m, removed, changed to lin. Address }
               Z  : Boolean;
               end;

     TPointBoolZPtr =^TPointBoolZ;



 { 2D Array of Bool to calc the area of any arbitray gemomatical layouts }
     TBitPlane = Class

           BitArray  :  TList;

           constructor  Create;

           private
           Upp   :   FPoint;
           Low   :   FPoint;

           deltax  :  Real;
           deltay  :  Real;

           stepX :  Integer;
           stepY :  Integer;


           { Function for discrete geometric (DG) problems }

           public




           function Init_BitArray : Boolean;

           function AddTRect(MyRect :  TRect) : Boolean;
           function AddTFRect(MyFRect : TFRect) : Boolean;

           function AddTCircle(MyRect :  TRect) : Boolean;
           function AddFCircle(MyFRect : TFRect) : Boolean;

           function AddTThickline(MyLine: TThickline): Boolean;

           function GetTIndex (MyPoint :FPoint): TPoint;
           function GetFPoint (MyPoint :TPoint): FPoint;

           function VirtualPoint(I: Integer): TPoint;

           function AssignSize(UpperCorner, LowerCorner :  FPoint; Sx, Sy :  Integer) :  Boolean;

           function SetBitArray (x,y : Integer; Value : Boolean) : Boolean;

           function GetBitArea: real;

           function GetFalseCount :  Integer;
           function GetBitArray(x, y: Integer): Boolean;
           end;








{ Calculate from the 1D Array of Bool to  2d Array  A[X;Y]  }
function TBitplane.VirtualPoint(I : Integer):  TPoint;
var     V   :   TPoint;
        x,y :   Word;
begin
      // procedure DivMod(Dividend: Integer; Divisor: Word; var Result, Remainder: Word);
      DivMod(i, stepx,y,x);

      V.x :=x;
      V.y :=y;

      result := v;

end;


function TBitplane.Init_BitArray : Boolean;
var    x, y    :  Integer;

       SinglePoint : TPointBoolZPtr;
begin

      BitArray.Clear;

     try
      begin
      for y:=0 to stepy do
        for x := 0 to stepx do
        begin

          new(SinglePoint);

          //  SinglePoint^.x := x;    {  version 1 only }

         //   SinglePoint^.y := y;    {  version 1 only }

          SinglePoint^.Z := false;

          BitArray.Add(SinglePoint);
        end;
       result := true;
       end;
       except
          result := false;
       end;
end;
0
Comment
Question by:BdLm
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
6 Comments
 
LVL 21

Assisted Solution

by:ziolko
ziolko earned 20 total points
ID: 18026679
if You want that huge ammount of items stored give up with arrays or TList
make Your own data structure which will be limited only by system resources... something like this

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type

  TItem = class(TObject)
  private
    FNextItem: TItem;
    FYourData: Pointer;
  public
    constructor Create(AData: Pointer);
    property NextItem: TItem read FNextItem write FNextItem;
  end;

  TForm1 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
  private
    FMyDataStructure: TItem;
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

{ TItem }

constructor TItem.Create(AData: Pointer);
begin
  inherited Create;
  FYourData := AData;
  FNextItem := nil;
end;

procedure TForm1.Button1Click(Sender: TObject);
var nIt: TItem;
begin
  nIt := TItem.Create(nil);
  nIt.NextItem := FMyDataStructure;
  FMyDataStructure := nIt;
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  FMyDataStructure := TItem.Create(nil);  
end;

procedure TForm1.FormDestroy(Sender: TObject);
var it: TItem;
begin
  repeat
    it := FMyDataStructure;
    FMyDataStructure := FMyDataStructure.NextItem;
    FreeAndNil(it);
  until FMyDataStructure = nil;
end;

end.

ziolko
0
 
LVL 26

Accepted Solution

by:
Russell Libby earned 20 total points
ID: 18028217

Lol... you do realize what you are asking, right?

1E6 (1 million) squared is 1E12, or 1 trillion bits. Even given the fact that you could compress this by 8 (8 bits / byte) and use 64 bit integer math to locate the desired byte at X,Y (and mod to determine the bit), eg:

1M rows / Each row at 125K (1M / 8) / Each byte of the row comprises 8 values

and you would still be faced with storing 125 GB of data to make up your array. Now also consider that the max address space of any user mode windows process is technically 2GB (possible to achieve up to 4gb), and you quickly see that you can only address 1.6% of the actual array in memory. This would mean using a 125 GB disk file as the actual storage backing for the array. So while theortically achievable, its not going to be fast, and you need a pretty beefy system with plenty of storage to handle this. And even on a fast disk, you would probably be looking @ roughly 1-2 hours to perform an Init(...) on your virtual array.

As far as what ziolko is recommending, it just does not apply here, as your process would hit the 2GB address limit before it even finished 0.2% of the array.

---

Russell
0
 
LVL 19

Expert Comment

by:MerijnB
ID: 18028557
I agree with rlibby.

So the big question is what you need it for, maybe there is a better solution for your problem.
0
[Live Webinar] The Cloud Skills Gap

As Cloud technologies come of age, business leaders grapple with the impact it has on their team's skills and the gap associated with the use of a cloud platform.

Join experts from 451 Research and Concerto Cloud Services on July 27th where we will examine fact and fiction.

 
LVL 26

Expert Comment

by:Russell Libby
ID: 18029122
**IF** you are dealing with a very sparse array/matrix, then there may be some hope. For the education of those not familiar with what a sparse array/matrix is:

http://www.answers.com/topic/sparse-matrix

An example data structure for the handling might look like:

type
  PSparseCol     =  ^TSparseCol;
  TSparseCol     =  packed record
     Col:        Integer;
     Next:       PSparseCol;
  end;

var
  RowArray:      Array [1..1000000] of PSparseCol;

The row array is 4MB in size, and contains a singly linked list to each "column" that is in an "on" state (on/set/true/whatever you want to call it). This would allow for a theoretical maximum of 267 million bits being on at once. And by very sparse, I mean VERY sparse, as you would still only be able to address less than 1 percent of the virtual array size.

Russell
0
 
LVL 4

Assisted Solution

by:tobjectpascal
tobjectpascal earned 20 total points
ID: 18034757
What i find interesting about Boolean is, it's not a Bit, it's actually a Byte / 8 bit register.


Var
 B: Boolean;
begin
 Asm
  mov al,10;
  mov b,al;
 End;
  If Al=True Then
    ShowMessage('True');


>0 true...

0
 
LVL 8

Author Comment

by:BdLm
ID: 18035262
many thanks to all of you for the good inputs.

1)  the background of the question:  I got tons of images (~  xx  GByte) building up a map, I have to sum up cerain araes with in  these images. Step and repeat with my algo through the whole image would be one idea, but to keep the whole image in one array makes the code quite easy.


2)  a sparse matrix approach won't help completly, Im thinking about something like a compressed array , as 0 and 1 's are balanced and once I got a '1'  the will always be a certain sequence of '1'. This would also speed my area sum algorithm.


0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small print…
Introduction Raise your hands if you were as upset with FireMonkey as I was when I discovered that there was no TListview.  I use TListView in almost all of my applications I've written, and I was not going to compromise by resorting to TStringGrid…
Monitoring a network: why having a policy is the best policy? Michael Kulchisky, MCSE, MCSA, MCP, VTSP, VSP, CCSP outlines the enormous benefits of having a policy-based approach when monitoring medium and large networks. Software utilized in this v…
Do you want to know how to make a graph with Microsoft Access? First, create a query with the data for the chart. Then make a blank form and add a chart control. This video also shows how to change what data is displayed on the graph as well as form…
Suggested Courses
Course of the Month9 days, 9 hours left to enroll

624 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question