Efficient use of memory 
Author Message
 Efficient use of memory

I need to efficiently use memory to keep track of selections made by the user.
Using Bit seems the most efficient but should that be bits of longs or
whatever?
I will need many thousands of bits.  Users select ranges of bits or even or
odd or thelike.  They don't actually (usually) select one or more bits out of
thousands, but they could.
I need to quickly check or set a bit indicating something is selected based
on an Index pointing at the bit within the Long array.
At each occasion the user changes the set up the number of bits would change.
The user would make selection choices (setting bits) then my app would use
the bit sense to do or not do a task.
My first thought is to write an algorithm to create an array of longs, then
another algorithm to set and another to check the bit setting.
Does this seem the best way?
Does VB6 have any built-in operations to help with this?
Can someone help a little with the algorithms please.


Thu, 19 Jan 2012 07:05:01 GMT  
 Efficient use of memory

Quote:

> I need to efficiently use memory to keep track of selections made by the user.
> Using Bit seems the most efficient but should that be bits of longs or
> whatever?
> I will need many thousands of bits.  Users select ranges of bits or even or
> odd or thelike.  They don't actually (usually) select one or more bits out of
> thousands, but they could.
> I need to quickly check or set a bit indicating something is selected based
> on an Index pointing at the bit within the Long array.
> At each occasion the user changes the set up the number of bits would change.
> The user would make selection choices (setting bits) then my app would use
> the bit sense to do or not do a task.
> My first thought is to write an algorithm to create an array of longs, then
> another algorithm to set and another to check the bit setting.
> Does this seem the best way?
> Does VB6 have any built-in operations to help with this?
> Can someone help a little with the algorithms please.

Probably about as easy to use a long variable-length string; they can be
2^31 characters in length.

Simply use "0/1" for each and compare/set/test

In VB, the extra overhead of dealing w/ an array of Longs will likely be
roughely equivalent w/ getting the proper subarray setting/testing
individual bits.

VB does not have a set of bit intrinsics--to set a bit you either need
to OR in a constant as a mask or use something like

Function SetBit(bitno As Long) As Long
   Variable = 2^bitno Or Variable
End Function

One can encapsulate the string manipulation operations in a convenient
set of functions as well, of course.

--



Thu, 19 Jan 2012 08:50:53 GMT  
 Efficient use of memory
Are you sure that using an array of bits is the correct solution?

If it is unlikely that individual bits would be selected, the most
memory-efficient solution might be an array of data structures that reflect
the process that users went through to select their bits. If you are only
offering certain patterns within ranges (all, all odd, all even, alternate
starting with the first, etc) and if these selections cannot overlap, then
your data structure would be an array of ranges (pairs of values) together
with a pattern indicator.  I'm assuming that the user does not specify each
individual bit, so your storage scheme can use the same shortcuts that were
applied in presenting the selection options to the user.  Some small
selections may be stored very inefficiently, but overall you are likely to
come out well ahead of a bitarray.


Quote:
>I need to efficiently use memory to keep track of selections made by the
>user.
> Using Bit seems the most efficient but should that be bits of longs or
> whatever?
> I will need many thousands of bits.  Users select ranges of bits or even
> or
> odd or thelike.  They don't actually (usually) select one or more bits out
> of
> thousands, but they could.
> I need to quickly check or set a bit indicating something is selected
> based
> on an Index pointing at the bit within the Long array.
> At each occasion the user changes the set up the number of bits would
> change.
> The user would make selection choices (setting bits) then my app would use
> the bit sense to do or not do a task.
> My first thought is to write an algorithm to create an array of longs,
> then
> another algorithm to set and another to check the bit setting.
> Does this seem the best way?
> Does VB6 have any built-in operations to help with this?
> Can someone help a little with the algorithms please.



Thu, 19 Jan 2012 09:48:35 GMT  
 Efficient use of memory


Quote:
> My first thought is to write an algorithm to create an array of longs, then
> another algorithm to set and another to check the bit setting.
> Does this seem the best way?
> Does VB6 have any built-in operations to help with this?
> Can someone help a little with the algorithms please.

I would suggest you could wrap up the array in a class that simply
looks like some large array of bits.  To keep it efficient, you'll want
to dynamically dimension the array on an as needed basis.  Unless
you need to plan for more than (about) 15 billion bits, it would not
matter what the actual array's Data Type is.  I would suggest an
array of Bytes to avoid VB trying to mess you up with the sign bit
for Integers and Longs.  The class code below may help you get
started.  Its use would be similar to:

Private Sub Form_Load()
Dim Flags As Class1
Dim i As Long

   Set Flags = New Class1

   Flags.Bit(3) = True
   Flags.Bit(17) = True

   For i = 0 To Flags.Length
     Debug.Print i, Flags.Bit(i)
   Next

End Sub

As you see, you just create an instance of the class and start using it.
Code within the class handles the creation and use of the array.  If you
need to clear it (to recover memory), just create a new instance of the
class.  (You could add a method to erase the array if you want....)

Add the code below to a new class (Class1) and try it out:

HTH
LFS

Option Explicit

Private Flag() As Byte
Private Mask(0 To 7) As Byte

' Public Properties
Public Property Get Bit(ByVal Index As Long) As Boolean
Dim byt As Long
  ' Get bit at Index
  byt = Index \ 8
  If byt <= UBound(Flag) Then
    Bit = Flag(byt) And Mask(Index And 7)
  End If
End Property

Public Property Let Bit(ByVal Index As Long, ByVal Value As Boolean)
Dim byt As Long
  ' Set bit at Index
  byt = Index \ 8
  If UBound(Flag) < byt Then
    ReDim Preserve Flag(0 To byt)
  End If
  If Value Then
    Flag(byt) = Flag(byt) Or Mask(Index And 7)
  Else
    Flag(byt) = Flag(byt) And Not Mask(Index And 7)
  End If
End Property

Public Property Get Length() As Long
  Length = UBound(Flag) * 8 + 8
End Property

' Private routines
Private Sub Class_Initialize()
Dim idx As Long, vlu As Long
  ' Init for 8 bits
  ReDim Flag(0 To 0)
  ' Create bit mask
  vlu = 1
  For idx = 7 To 0 Step -1
    Mask(idx) = vlu
    vlu = vlu + vlu
  Next
End Sub



Thu, 19 Jan 2012 10:33:12 GMT  
 Efficient use of memory


Quote:
> Are you sure that using an array of bits is the correct solution?

> If it is unlikely that individual bits would be selected, the most
> memory-efficient solution might be an array of data structures that reflect
> the process that users went through to select their bits. If you are only
> offering certain patterns within ranges (all, all odd, all even, alternate
> starting with the first, etc) and if these selections cannot overlap, then
> your data structure would be an array of ranges (pairs of values) together
> with a pattern indicator.  I'm assuming that the user does not specify each
> individual bit, so your storage scheme can use the same shortcuts that were
> applied in presenting the selection options to the user.  Some small
> selections may be stored very inefficiently, but overall you are likely to
> come out well ahead of a bitarray.

If the selection included 2000 hits in the range of 0 to 5,000,000 I would
agree, taken a sparse (like) approach should be considered.  But if the
selection is more like 2000 out of 10,000 I's suggest the simplicity of
the array would win out.

With the range pair idea, there'd be all sorts of edge cases, for example,
the user selects all odd values between 50 and 150, but also hits 62 and
122.  Logic would have to be included to break that one range up into
five different ranges.

Then there is the selection process itself.  How do you give the user
the option to select bunches and bunches of switches?  There is only
so much screen space available....

Here's an example that helped someone out a while ago....
http://vbnet.mvps.org/code/intrinsic/matrixcheck.htm

Good luck!
LFS



Thu, 19 Jan 2012 10:57:54 GMT  
 Efficient use of memory

Quote:

> > My first thought is to write an algorithm to create an array of longs, then
> > another algorithm to set and another to check the bit setting.
> > Does this seem the best way?
> > Does VB6 have any built-in operations to help with this?
> > Can someone help a little with the algorithms please.

> I would suggest you could wrap up the array in a class that simply
> looks like some large array of bits. ?To keep it efficient, you'll want
> to dynamically dimension the array on an as needed basis. ?Unless
> you need to plan for more than (about) 15 billion bits, it would not
> matter what the actual array's Data Type is. ?I would suggest an
> array of Bytes to avoid VB trying to mess you up with the sign bit
> for Integers and Longs. ?The class code below may help you get
> started. ?Its use would be similar to:

> Private Sub Form_Load()
> Dim Flags As Class1
> Dim i As Long

> ? ?Set Flags = New Class1

> ? ?Flags.Bit(3) = True
> ? ?Flags.Bit(17) = True

> ? ?For i = 0 To Flags.Length
> ? ? ?Debug.Print i, Flags.Bit(i)
> ? ?Next

> End Sub

> As you see, you just create an instance of the class and start using it.
> Code within the class handles the creation and use of the array. ?If you
> need to clear it (to recover memory), just create a new instance of the
> class. ?(You could add a method to erase the array if you want....)

> Add the code below to a new class (Class1) and try it out:

> HTH
> LFS

> Option Explicit

> Private Flag() As Byte
> Private Mask(0 To 7) As Byte

> ' Public Properties
> Public Property Get Bit(ByVal Index As Long) As Boolean
> Dim byt As Long
> ? ' Get bit at Index
> ? byt = Index \ 8
> ? If byt <= UBound(Flag) Then
> ? ? Bit = Flag(byt) And Mask(Index And 7)
> ? End If
> End Property

> Public Property Let Bit(ByVal Index As Long, ByVal Value As Boolean)
> Dim byt As Long
> ? ' Set bit at Index
> ? byt = Index \ 8
> ? If UBound(Flag) < byt Then
> ? ? ReDim Preserve Flag(0 To byt)
> ? End If
> ? If Value Then
> ? ? Flag(byt) = Flag(byt) Or Mask(Index And 7)
> ? Else
> ? ? Flag(byt) = Flag(byt) And Not Mask(Index And 7)
> ? End If
> End Property

> Public Property Get Length() As Long
> ? Length = UBound(Flag) * 8 + 8
> End Property

> ' Private routines
> Private Sub Class_Initialize()
> Dim idx As Long, vlu As Long
> ? ' Init for 8 bits
> ? ReDim Flag(0 To 0)
> ? ' Create bit mask
> ? vlu = 1
> ? For idx = 7 To 0 Step -1
> ? ? Mask(idx) = vlu
> ? ? vlu = vlu + vlu
> ? Next
> End Sub

Larry
I am coing in through Google Groups because I cannot come in through
the normal MS webpage.
Community Message Not Available for this post only.

Anyway, let's see if this goes.

I understand the sign problem with Integers and Longs but I am not
sure about t\wo things.
Since a Long is "native" then would it not be much faster than working
with bytes and that would overcome the loss due to handling the sign?
How are bytes represented in memory.  i.e do 4 Bytes take up the same
space a one Long?

I have a terrible time reading the Google Validation characters and
the wheechair pronunciation by a foreigner is lousy.  Google is not
very smart about this.  Other Validations are much easier for me and
are just as good or better.



Thu, 19 Jan 2012 12:01:40 GMT  
 Efficient use of memory


I understand the sign problem with Integers and Longs but I am not
sure about t\wo things.
Since a Long is "native" then would it not be much faster than working
with bytes and that would overcome the loss due to handling the sign?
How are bytes represented in memory.  i.e do 4 Bytes take up the same
space a one Long?
------------

I'd have to run some timed tests to be sure (no time for that now) but
I would speculate there would not be much of a difference in this case.
The Index parameter passed is a Long as well as the indexing used to
access the array.  The only time Byte values are needed is when reading
or writing to the array.  As you know, the computer's memory can be
considered as one large array of Bytes, in that it takes 4 Bytes to make
a Long.  That means everytime the array is accessed, memory has to
supply or accept 4 bytes to make a long, vs the 1 byte for a Byte array.

So does the Byte array win out due to fewer bytes needed per memory
access, or does the Long array win out due to the native size variables
used to calculate the array values?

Its an interesting question, and one I might persue sometime.

I did the conversion, and a few quick tests show it seems to work as
well with an array of Longs.  Be sure to test it for your own use....
Here is the class code using an array of Longs:

HTH
LFS

Option Explicit

Private Flag() As Long
Private Mask(0 To 31) As Long

' Public Properties
Public Property Get Bit(ByVal Index As Long) As Boolean
Dim byt As Long
  ' Get bit at Index
  byt = Index \ 32
  If byt <= UBound(Flag) Then
    Bit = Flag(byt) And Mask(Index And 31)
  End If
End Property

Public Property Let Bit(ByVal Index As Long, ByVal Value As Boolean)
Dim byt As Long
  ' Set bit at Index
  byt = Index \ 32
  If UBound(Flag) < byt Then
    ReDim Preserve Flag(0 To byt)
  End If
  If Value Then
    Flag(byt) = Flag(byt) Or Mask(Index And 31)
  Else
    Flag(byt) = Flag(byt) And Not Mask(Index And 31)
  End If
End Property

Public Property Get Length() As Long
  Length = UBound(Flag) * 32 + 32
End Property

' Private routines
Private Sub Class_Initialize()
Dim idx As Long, vlu As Long
  ' Init for 32 bits
  ReDim Flag(0 To 0)
  ' Create bit mask
  vlu = 1
  For idx = 31 To 2 Step -1
    Mask(idx) = vlu
    vlu = vlu + vlu
  Next
  Mask(1) = &H40000000
  Mask(0) = &H80000000
End Sub



Thu, 19 Jan 2012 14:11:09 GMT  
 
 [ 7 post ] 

 Relevant Pages 

1. Efficient Memory Usage

2. How i can get the Used Memory and Available Memory

3. Memory, Memory and more Memory

4. Is my search algorithm efficient

5. An efficient multiple scale calculation ?

6. Most Efficient Code To Get Data From Query

7. Need advice for efficient development (Access95)

8. Is this Search algorithm efficient?

9. Most efficient way of returning quite a few variables

10. How to run queries more efficient?

11. more efficient way?

12. Advice please on most efficient event creator to check for presence of new file

 

 
Powered by phpBB® Forum Software