Author: Peter Thörnqvist
Sparse arrays are arrays that only uses memory for the cells that are actually in
use although the full size of the array is always available. A prime example is the
cells in a spreadsheet application: they can have enormous dimensions (like 99999 *
99999 cells) but still only use memory equivalent to the cells where there is any
data. This article shows how you can easily create a sparse array with any number
of dimensions and of arbitrary size.
Answer:
One solution is to create a new class (let's call it TSparseArray) that stores the
data in a TStringlists Objects array and the dimensions in the Strings array as a
compound string. Here's a two-dimensional example:
1 interface
2
3 type
4 TSparseArray = class(TObject)
5 private
6 FCells: TStringlist;
7 function GetCell(Col, Row: integer): TObject;
8 procedure SetCell(Col, Row: integer; const Value: TObject);
9 public
10 constructor Create;
11 destructor Destroy; override;
12 property Cells[Col, Row: integer]: TObject read GetCell write SetCell; default;
13 end;
14
15 implementation
16
17 const
18 cFmtDims = '%d:%d';
19
20 constructor TSparseArray.Create;
21 begin
22 inherited Create;
23 FCells := TStringlist.Create;
24 FCells.Sorted := true; // faster retrieval, slower updates, needed for dupIgnore
25 FCells.Duplicates := dupIgnore;
26 end;
27
28 destructor TSparseArray.Destroy;
29 begin
30 FCells.Free;
31 inherited Destroy;
32 end;
33
34 function TSparseArray.GetCell(Col, Row: integer): TObject;
35 var
36 i: integer;
37 begin
38 Result := nil;
39
40 i := FCells.IndexOf(Format(cFmtDims, [Col, Row]));
41 if i > -1 then
42 Result := FCells.Objects[i];
43 end;
44
45 procedure TSparseArray.SetCell(Col, Row: integer; const Value: TObject);
46 begin
47 // dupIgnore guarantees that if this cell already exists, this will overwrite it
48 FCells.AddObject(Format(cFmtDims, [Col, Row]), Value);
49 end;
50
51 end.
To create a sparse array with more dimensions, you just have to redefine the Cells property (and the read / write methods) and change the format of cFmtDims accordingly. You can even mix dimensions of different types (i.e Cells[const Row:string;Col:integer]:TObject). I think you can come up with more neat things yourself. Enjoy!
|
