Alternative to a very large array?

[cbdeja]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and then
released for re-use. There may be many transactions taking place at any
time. I need to mark those labels which are in-use so that a new label
assignment does not choose one which is currently in-use.

If the number of possible labels was small (say 100) then I could
simply use an array of booleans (boolean labels[100]) and set the
corresponding element to true to denote in-use.

But the label is a 64 bit value ranging from 0 to 0xffffffff. What's
the best way of representing the in-use state of all label values
without having to waste memory on a vast array? (Perhaps just using
memory for those values which are in-use.)

I suspect that one of the STL classes might be the way to go, but I'm
not sure which to choose.

There are two possibilities. Either I just want a yes/no answer as to
whether a label exists (i.e. whether it is in-use), or I might also
want to store a string for only those labels which are in-use.

Any ideas what is the best solution for these two possibilites?

 

[Ben Pope]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and then
released for re-use. There may be many transactions taking place at any
time. I need to mark those labels which are in-use so that a new label
assignment does not choose one which is currently in-use.

If the number of possible labels was small (say 100) then I could
simply use an array of booleans (boolean labels[100]) and set the
corresponding element to true to denote in-use.

But the label is a 64 bit value ranging from 0 to 0xffffffff. What's
the best way of representing the in-use state of all label values
without having to waste memory on a vast array? (Perhaps just using
memory for those values which are in-use.)

I suspect that one of the STL classes might be the way to go, but I'm
not sure which to choose.

There are two possibilities. Either I just want a yes/no answer as to
whether a label exists (i.e. whether it is in-use), or I might also
want to store a string for only those labels which are in-use.

Any ideas what is the best solution for these two possibilites?

Sounds like you need a set or map. A set can store the label, a map can
attach the string to the label.

Ben Pope

 

[mlimber]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and then
released for re-use. There may be many transactions taking place at any
time. I need to mark those labels which are in-use so that a new label
assignment does not choose one which is currently in-use.

If the number of possible labels was small (say 100) then I could
simply use an array of booleans (boolean labels[100]) and set the
corresponding element to true to denote in-use.

But the label is a 64 bit value ranging from 0 to 0xffffffff. What's
the best way of representing the in-use state of all label values
without having to waste memory on a vast array? (Perhaps just using
memory for those values which are in-use.)

I suspect that one of the STL classes might be the way to go, but I'm
not sure which to choose.

There are two possibilities. Either I just want a yes/no answer as to
whether a label exists (i.e. whether it is in-use), or I might also
want to store a string for only those labels which are in-use.

Any ideas what is the best solution for these two possibilites?

You could use some sort of dynamically allocated list (e.g., std::list
or std::set) to hold a copy of the currently used labels. Then when you
need a new label, just have your label generator pick one (randomly?),
make sure it's not in the being-used list, and assign it. If it does
appear in the list, then just generate a new label and see if it's in
the list.

Cheers! --M

 

[peter steiner]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and then
released for re-use. There may be many transactions taking place at any
time. I need to mark those labels which are in-use so that a new label
assignment does not choose one which is currently in-use.
...

I suspect that one of the STL classes might be the way to go, but I'm
not sure which to choose.

There are two possibilities. Either I just want a yes/no answer as to
whether a label exists (i.e. whether it is in-use), or I might also
want to store a string for only those labels which are in-use.

Any ideas what is the best solution for these two possibilites?

std::set gives you the best out-of-the-box performance for this
application if you are considered about memory usage.

it stores unique keys (your label) and gives you logarithmic complexity
for insertion, deletion and lookups for the existance of keys with
linear memory requirement cost.

i am not sure what you mean with:

I might also
want to store a string for only those labels which are in-use.

but whatever your other requirements, inheriting/wrapping std::set
should give you a good start for a performant implementation.

-- peter

 

[David Resnick]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and then
released for re-use. There may be many transactions taking place at any
time. I need to mark those labels which are in-use so that a new label
assignment does not choose one which is currently in-use.

If the number of possible labels was small (say 100) then I could
simply use an array of booleans (boolean labels[100]) and set the
corresponding element to true to denote in-use.

But the label is a 64 bit value ranging from 0 to 0xffffffff. What's
the best way of representing the in-use state of all label values
without having to waste memory on a vast array? (Perhaps just using
memory for those values which are in-use.)

I suspect that one of the STL classes might be the way to go, but I'm
not sure which to choose.

There are two possibilities. Either I just want a yes/no answer as to
whether a label exists (i.e. whether it is in-use), or I might also
want to store a string for only those labels which are in-use.

Any ideas what is the best solution for these two possibilites?

I wonder if rather than keep track of whether a given label
is in use you keep note of two things

1) A std::set of labels that have been released and are available for
reuse.

2) A counter of the value of a label to be given out if there are no
available
labels in the set described in set 1.

Or you could just be a spendthrift and not reuse labels. Unless
your program generates an unspeakable number of labels, 64 bits
is likely to last you a lifetime... And if you generate an unspeakable
number of labels, unless any transaction might last the time needed
to wrap around a 64 bit counter, wrapping around would be fine...

-Daivd

 

[cbdeja]

Thanks everyone. Looks like a set will do fine for now.

 

[Ben Pope]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and
then released for re-use. There may be many transactions taking
place at any time. I need to mark those labels which are in-use so
that a new label assignment does not choose one which is currently
in-use.

If the number of possible labels was small (say 100) then I could
simply use an array of booleans (boolean labels[100]) and set the
corresponding element to true to denote in-use.

But the label is a 64 bit value ranging from 0 to 0xffffffff.
What's the best way of representing the in-use state of all label
values without having to waste memory on a vast array? (Perhaps
just using memory for those values which are in-use.)

<snip>

1) A std::set of labels that have been released and are available for
reuse.

Presumably a set of 2^64 elements will be at least as big as an array 2^64?

A set with the used values would likely be more appropriate. In fact, a
map of used labels and transaction pointers would likely be very useful.

Ben Pope

 

[David Resnick]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and
then released for re-use. There may be many transactions taking
place at any time. I need to mark those labels which are in-use so
that a new label assignment does not choose one which is currently
in-use.

If the number of possible labels was small (say 100) then I could
simply use an array of booleans (boolean labels[100]) and set the
corresponding element to true to denote in-use.

But the label is a 64 bit value ranging from 0 to 0xffffffff.
What's the best way of representing the in-use state of all label
values without having to waste memory on a vast array? (Perhaps
just using memory for those values which are in-use.)

<snip>

1) A std::set of labels that have been released and are available for
reuse.

Presumably a set of 2^64 elements will be at least as big as an array 2^64?

A set with the used values would likely be more appropriate. In fact, a
map of used labels and transaction pointers would likely be very useful.

I guess I wasn't clear, that was what I meant "that have been released"
and
"reuse". The set would start empty, the counter at 1. As labels are
released, they'd be added to the set and available for reuse.

-David

 

[Ben Pope]

(e-mail address removed) wrote:
I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and
then released for re-use. There may be many transactions taking
place at any time. I need to mark those labels which are in-use so
that a new label assignment does not choose one which is currently
in-use.

If the number of possible labels was small (say 100) then I could
simply use an array of booleans (boolean labels[100]) and set the
corresponding element to true to denote in-use.

But the label is a 64 bit value ranging from 0 to 0xffffffff.
What's the best way of representing the in-use state of all label
values without having to waste memory on a vast array? (Perhaps
just using memory for those values which are in-use.)
<snip>

1) A std::set of labels that have been released and are available for
reuse.

Presumably a set of 2^64 elements will be at least as big as an array 2^64?

A set with the used values would likely be more appropriate. In fact, a
map of used labels and transaction pointers would likely be very useful.

I guess I wasn't clear, that was what I meant "that have been released"
and "reuse". The set would start empty, the counter at 1. As labels are
released, they'd be added to the set and available for reuse.

So you can choose from the released labels. What about the initial
state when the set is empty? I'm also unclear as to what your counter
does, does it keep track of the greatest label value so far? OK, I
re-read your original post, I didn't understand point 2 initially.

So when finding a new label, you check the set, if not empty, grab a
value (assign it's value to the label and remove it from the set), if
set is empty, assign count++. When a transaction finishes, it's label
is added to the set.

What happens if count++ reaches it's maximum value? I guess that's not
likely unless you have 2^64 simultaneous transactions at any point in
time. OK, so as a side effect, the counter also gives you the maximum
number of simultaneous transactions to date.

Ben Pope

 

[=?ISO-8859-1?Q?Sch=FCle_Daniel?=]

[...]

But the label is a 64 bit value ranging from 0 to 0xffffffff. What's

64 bit = 8 byte
0 to 0xFFFFFFFFFFFFFFFF

regards

 

[AnonMail2005]

I am using a "unsigned long long" as a label to identify various
transactions that are taking place in my program.

The label is reserved during the lifetime of the transaction and then
released for re-use. There may be many transactions taking place at any
time. I need to mark those labels which are in-use so that a new label
assignment does not choose one which is currently in-use.

If the number of possible labels was small (say 100) then I could
simply use an array of booleans (boolean labels[100]) and set the
corresponding element to true to denote in-use.

But the label is a 64 bit value ranging from 0 to 0xffffffff. What's
the best way of representing the in-use state of all label values
without having to waste memory on a vast array? (Perhaps just using
memory for those values which are in-use.)

I suspect that one of the STL classes might be the way to go, but I'm
not sure which to choose.

There are two possibilities. Either I just want a yes/no answer as to
whether a label exists (i.e. whether it is in-use), or I might also
want to store a string for only those labels which are in-use.

Any ideas what is the best solution for these two possibilites?

Why do you need to keep track of already used numbers? Look at the
maximum number that can be stored in your 64 bit value. You could
just increment a counter and forget about ever reusing a number.

Take 2^64 and divide it by the number of seconds in a year to get an
idea of many transcation numbers are contained in that number.