Optimization issue

[Crirus]

Hello
I have 512x512 grid of booleans
At a specific point in my application, I need to find out if a particular
point in my grid have value true of false.

Now I need a way to store the boolean value for each coordinates in my grid.

I found some methods:

1. I could have a 512x512 BitArray Class something like P(x,y) ~
myBitArray(y*512+x) = True
A simple check will tell me what value is in a particular point
Drawback: memory occupied without reason

2. Another way is to store only the true values in an array. Each value
y*512+x added to the array tells me that in p(x,y) I have value True
Drawback: Search if there is a value like y*512 +x in my array can be
long, setting a new value means Redim Preserve the array and is time
consumming, right?

3. I could use ArrayList with y*-512+x values and Add, Contains, Remove for
adding, testing, setting a value.
Drawback: have no iddea if is faster than the other ways or how much
memory require

Anyway, I need the best compromise memory allocated - search for value - set
a value

Any advices?

I know I could test each one, just hope someone have allready done it

 

[One Handed Man [ OHM# ]]

Why not

Dim BoolsGrid(511,511) As Boolean

'Access 255,255

If BoolGrid(255,255) Then

'I Found It to be True

End If


Regards - OHM

 

[Crirus]

BoolGrid(511,511) require the same memoy as myBitArray.Length(511*511)??

 

[One Handed Man [ OHM# ]]

I would think they are the same or very similar. I'm not actually sure how
to find out how much memory an individual object takes up on the heap, thats
a good question.

Regards OHM

 

[Crirus]

BitArray it may be better

Each 8 elements of a BitArray need a byte
How about Boolean?

Boolean variables are stored as 16-bit (2-byte) numbers... so I guess
BitArray fit better for big arrays of boolean values

 

[One Handed Man [ OHM# ]]

I must admit I didnt check the boolean storage, seems a bit over the top to
me.

Regards - OHM

BitArray it may be better

Each 8 elements of a BitArray need a byte
How about Boolean?

Boolean variables are stored as 16-bit (2-byte) numbers... so I guess
BitArray fit better for big arrays of boolean values

I would think they are the same or very similar. I'm not actually
sure how to find out how much memory an individual object takes up
on the heap, thats a good question.

Regards OHM

BoolGrid(511,511) require the same memoy as
myBitArray.Length(511*511)??


"One Handed Man [ OHM# ]" <O_H_M{at}BTInternet{dot}com> wrote in
message Why not

Dim BoolsGrid(511,511) As Boolean

'Access 255,255

If BoolGrid(255,255) Then

'I Found It to be True

End If


Regards - OHM



Crirus wrote:
Hello
I have 512x512 grid of booleans
At a specific point in my application, I need to find out if a
particular point in my grid have value true of false.

Now I need a way to store the boolean value for each coordinates
in my grid.

I found some methods:

1. I could have a 512x512 BitArray Class something like P(x,y) ~
myBitArray(y*512+x) = True
A simple check will tell me what value is in a particular
point Drawback: memory occupied without reason

2. Another way is to store only the true values in an array. Each
value y*512+x added to the array tells me that in p(x,y) I have
value True Drawback: Search if there is a value like y*512 +x
in my
array can be
long, setting a new value means Redim Preserve the array and is
time consumming, right?

3. I could use ArrayList with y*-512+x values and Add, Contains,
Remove for adding, testing, setting a value.
Drawback: have no iddea if is faster than the other ways or
how much memory require

Anyway, I need the best compromise memory allocated - search for
value - set a value

Any advices?

I know I could test each one, just hope someone have allready done
it

 

[Dominique Vandensteen]

totally different approach...
if you don't have a lot booleans being true (or false) you can maybe create
a collection that contains the "index" of the "small group" elements
index here would be y*512 + x

 

[Crirus]

I considered that solution either.. still not sure how may of them whould
be...
And a redim each time a value is swithched ...hmmm, may be time consumming?

 

[Dominique Vandensteen]

I was thinking about a collection not an array
so a redim is not needed...
for an ArrayList add, remove and contains methods can be used

 

[Crirus]

yah, but how much memory require an ArrayList vs. array then?

 

[lostdreamz]

yah, but how much memory require an ArrayList vs. array then?

heres a little info i found on memory management between the two...

An array is a set of numbered items maintained contiguously in memory.
An array has a fixed size. So if you want to add an additional item to
an array, a new array must be created and all the items copied from
the old array into the new one. In vb.net that is done with the redim
statement. This operation is not particularly fast.

An arraylist is similar to an array, except that memory management of
a growing list is done for you. If you allocate an arraylist of 35
items, .NET actually allocates space for 64. When you add additional
items to the list, it fills up to 64 without any additional allocation
of memory. If you add a 65th item, it automatically allocates a new
arraylist with 128 spaces and copies the 64 items from the old
arraylist into the new one, then deallocates the memory for the old
one (which gets cleaned up on the next garbage collection).

So when you have a growing list, it means that you don't have to
manage the memory management issues of efficiently maintaining the
size of the list. There is some overhead to the arraylist, so if you
know the final size that you want the list to be ahead of time, you
are better off using an array. If you don't know the size it needs to
be, the arraylist is the better option.

lostdreamz

 

[Dominique Vandensteen]

you can also define the allocated space when creating the arraylist

so if you know you will need max 200 elements, just create an arraylist of
200 elements...
if you stay under that limit a "resize" will never be done...