Collections od KEYS only : BOOLEAN VS OBJECT, False Vs Null/Nothing

  • Thread starter Thread starter pamela fluente
  • Start date Start date
P

pamela fluente

In a previous question I asked if there were collections
similar to SortedList or Dictionary which would hold KEYS only, No
values.

It seems that the framework does not have such "reduced" collections,
but one can use
the standard one, adding as value a Null/Nothing value or a boolean
(of creating a collection
by inheritance).


I am wondering what is most advisable to use as type for the values:
Boolean or Object ?

For instance:
C#
SortedList<MyKey, bool> MyListB = new SortedList<MyKey, bool>();
MyListB.add(new MyKey(), false);
or
SortedList<MyKey, object> MyListO = new SortedList<MyKey, object>();
MyListO.add(new MyKey(), null);

VB
dim MyListB as new SortedList(of MyKey, Boolean)
MyListB.add(New MyKey, false)
or
dim MyListO as new SortedList(of MyKey, Object)
MyListO.add(New MyKey, Nothing)


I am wondering if using a value type (boolean) instead of a reference
type
would be more inefficient ? Your opinion ?

-P
 
pamela said:
In a previous question I asked if there were collections
similar to SortedList or Dictionary which would hold KEYS only, No
values.

It seems that the framework does not have such "reduced" collections,
but one can use
the standard one, adding as value a Null/Nothing value or a boolean
(of creating a collection
by inheritance).


I am wondering what is most advisable to use as type for the values:
Boolean or Object ?

For instance:
C#
SortedList<MyKey, bool> MyListB = new SortedList<MyKey, bool>();
MyListB.add(new MyKey(), false);
or
SortedList<MyKey, object> MyListO = new SortedList<MyKey, object>();
MyListO.add(new MyKey(), null);

VB
dim MyListB as new SortedList(of MyKey, Boolean)
MyListB.add(New MyKey, false)
or
dim MyListO as new SortedList(of MyKey, Object)
MyListO.add(New MyKey, Nothing)


I am wondering if using a value type (boolean) instead of a reference
type
would be more inefficient ? Your opinion ?

-P
Click to expand...

It doesn't really matter, as a reference itself is a value type.

The garbage collector, however, scans all references that exist when
it's doing a garbage collection. As the references will all be null, it
won't take long to ignore them, but if you don't use references the
garbage collector doesn't have to be bothered with them at all.
 
It doesn't really matter, as a reference itself is a value type.

The garbage collector, however, scans all references that exist when
it's doing a garbage collection. As the references will all be null, it
won't take long to ignore them, but if you don't use references the
garbage collector doesn't have to be bothered with them at all.

--
Göran Andersson
_____http://www.guffa.com- Nascondi testo tra virgolette -

- Mostra testo tra virgolette -
Click to expand...

Ok, so as to the GC, you are saying, if I use boolean I will save it
some little work. Right ?
Actually these list can be pretty long, so it's not a bad idea to cut
references.

But what about memory use ? In any case both collection vould have a
list
of Values. Right ? Now, is it possible that all Nothing would waste
less memory than a tons of FALSE values ?

Or do the occupy the same ? And what about the Add(Key, Value) or
other operations, would it make any difference
to deal with a Value instead of a Reference ?

-P
 
pamela said:
Ok, so as to the GC, you are saying, if I use boolean I will save it
some little work. Right ?
Right.

Actually these list can be pretty long, so it's not a bad idea to cut
references.

But what about memory use ? In any case both collection vould have a
list
of Values. Right ? Now, is it possible that all Nothing would waste
less memory than a tons of FALSE values ?
Click to expand...

On a 32 bit system it will be the same. A reference is four bytes, and a
boolean uses one byte but will require four bytes in the KeyValuePair
structure.
Or do the occupy the same ? And what about the Add(Key, Value) or
other operations, would it make any difference
to deal with a Value instead of a Reference ?
Click to expand...

No difference at all. A reference is treated just as an integer, until
the point where you actually dereference it to reach the object that
it's pointing to.
 
On a 32 bit system it will be the same. A reference is four bytes, and a
boolean uses one byte but will require four bytes in the KeyValuePair
structure.


No difference at all. A reference is treated just as an integer, until
the point where you actually dereference it to reach the object that
it's pointing to.
Click to expand...
Thank you Goran. Now It's much more clear.


I remain with a last doubt. Please, do not laugh at me :-))

I had "imagined" a key value pair like something like that:

Key , Reference ---------> Object

Now I was thinking that:

Key, EmptyReference (4 bytes, for the empty reference)
Key, Reference -----> BooleanValue (4bytes + 1 byte )

where the second would involve 1 Byte more (the boolean value).
So it would be convenient to use an empty reference !

Why is this naive representation of mine wrong and instead the 2 above
involve exactly the same memory occupation ?

Is perhaps because in the second case there is no reference to a
boolean and directly

Key, BooleanValue ? (1 byte, for the value)

But if this is so we would have a gain using boolean.

I am confused !! :-) So what is actually the correct
representation ?

-P
 
By the way, just wanted to mention: If you want a collection of "keys" only,
and not key/value pairs, why not just use the appropiate list class, such
as:

List<string> mykeys.

Thanks,
MB
 
Muj Beg said:
By the way, just wanted to mention: If you want a collection of "keys" only,
and not key/value pairs, why not just use the appropiate list class, such
as:

List<string> mykeys.
Click to expand...

Because checking whether a list contains an element or not is an O(n)
operation instead of an O(1) operation.
 
Because checking whether a list contains an element or not is an O(n)
operation instead of an O(1) operation.
Click to expand...

Yes and also because we are talking here about sorted list and
dictionaries.
 
pamela said:
Thank you Goran. Now It's much more clear.


I remain with a last doubt. Please, do not laugh at me :-))

I had "imagined" a key value pair like something like that:

Key , Reference ---------> Object

Now I was thinking that:

Key, EmptyReference (4 bytes, for the empty reference)
Key, Reference -----> BooleanValue (4bytes + 1 byte )

where the second would involve 1 Byte more (the boolean value).
So it would be convenient to use an empty reference !

Why is this naive representation of mine wrong and instead the 2 above
involve exactly the same memory occupation ?

Is perhaps because in the second case there is no reference to a
boolean and directly

Key, BooleanValue ? (1 byte, for the value)

But if this is so we would have a gain using boolean.

I am confused !! :-) So what is actually the correct
representation ?

-P
Click to expand...

The KeyValuePair structure will contain the value itself, not a
reference to the value. When the value is a reference type, the
reference is stored, but when the value is a value type, the value
itself is stored.

A boolean variable uses one byte, but in a structure the data will be
padded to an even multiple of four bytes, so the boolean still requires
four bytes in the structure.
 
The KeyValuePair structure will contain the value itself, not a
reference to the value. When the value is a reference type, the
reference is stored, but when the value is a value type, the value
itself is stored.

A boolean variable uses one byte, but in a structure the data will be
padded to an even multiple of four bytes, so the boolean still requires
four bytes in the structure.

--
Göran Andersson
_____http://www.guffa.com- Nascondi testo tra virgolette -

- Mostra testo tra virgolette -
Click to expand...

Ah, I understand now. Very clear and useful.

Thanks Göran

-P
 
Ah, I see.

Although one could do list.Sort() (once), followed by list.BinarySearch() to
gain seom of the same advantages.
 
Ah, I see.

Although one could do list.Sort() (once), followed by list.BinarySearch() to
gain seom of the same advantages.
Click to expand...

Actually, I do not think you can replace, in most cases a sorted list
with a list + Ordering
without a huge performace dropdown. I mean in the cases where a sorted
list is actually needed.

For instance, you cannot be sorting after any add...

-P
 
Muj Beg said:
Ah, I see.

Although one could do list.Sort() (once), followed by list.BinarySearch() to
gain seom of the same advantages.
Click to expand...

True. That would give O(log(N)) performance instead of O(N) performance
- but with a decently chosen hashcode, a hashtable type of structure
will be much quicker for large sets.
 
Back
Top