Use bit arrays?

Question

Imagine there's a fixed and constant set of 'options' (e.g. skills). Every object (e.g. human) can either have or not have any of the options.

Should I maintain a member list-of-options for every object and fill it with options?

OR:

Is it more efficient (faster) to use a bitarray where each bit represents the respective option's taken (or not taken) status?

-edited:-

To be more specific, the list of skills is a vector of strings (option names), definitely shorter than 256. The target is for the program to be AS FAST as possible (no memory concerns).

I really think your question needs to be more targeted. The answers depend greatly on the technology you are using and what you are hoping to achieve (performance? efficient use of space/ memory? flexibility?) to give a definitive statement. — user610217
– user610217, Commented Aug 15, 2011 at 18:12

Fred Foo · Accepted Answer · 2011-08-15 18:23:02Z

2

That rather depends. If the number of options is small, then use several bool members to represent them. If the list grows large, then both your options become viable:

a bitset (which an appropriate enum to symbolically represent the options) takes a constant, and very small, amount of space, and getting a certain option takes O(1) time;
a list of options, or rather an std::set or unordered_set of them, might be more space-efficient, but only if the number of options is huge, and it is expected that a very small number of them will be set per object.

When in doubt, use either a bunch of bool members, or a bitset. Only if profiling shows that storing options becomes a burden, consider a dynamic list or set representation (and even then, you might want to reconsider your design).

Edit: with less than 256 options, a bitset would take at most 64 bytes, which will definitely beat any list or set representation in terms of memory and likely speed. A bunch of bools, or even an array of unsigned char, might still be faster because accessing a byte is commonly faster than accessing a bit. But copying the structure will be slower, so try several options and measure the result. YMMV.

edited Aug 15, 2011 at 18:23

answered Aug 15, 2011 at 18:16

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

vedran Over a year ago

Very helpful answer! Since I'll not be copying much, rather, accessing a lot, I might go for array of unsigned char. Incidentally, when you mentioned the enum to symbolically represent the options in the bitarray, I'm unsure as to how to define the not-so-small amount of enum elements. Surely not typing their identifiers by hand? The option list is populated from a resource.

Fred Foo Over a year ago

@vedran: that depends on where the properties are coming from, but I do suggest giving them symbolic names. If typing them in by hand is too much of a burden, but you have them available digitally and the rest of your program structure admits it, you might want to write a quick 'n' dirty code generator (e.g. a shell script) to get them into the program.

Pepe · Accepted Answer · 2011-08-15 18:11:44Z

1

Using a bit array is faster when testing for the presence of multiple skills in a person in a single operation.

If you use a list of options then you'll have to go over the list one item at a time to find if a skill set exits which would obviously take more time and require many comparison operations.

answered Aug 15, 2011 at 18:11

Pepe

6,4805 gold badges29 silver badges29 bronze badges

Comments

Qwertie · Accepted Answer · 2011-08-15 18:12:00Z

0

The bitarray will be generally faster to edit and faster to search. As for space required, just do the math. A list of options requires a dynamically sized array (which suffers some overhead over the set of options itself); but if there are a large number of options, it may be smaller if (typically) only a small number of options are set.

answered Aug 15, 2011 at 18:12

Qwertie

17.4k22 gold badges115 silver badges155 bronze badges

4 Comments

user610217 Over a year ago

Keep in mind many languages (.NET for certain, prolly others) create bitarrays out of 8-byte booleans... not a huge space saver. Also, I'm curious about why you think bitarrays are faster to search? It seems that doing bitwise comparisons would be an expensive operation.

David Hammen Over a year ago

I disagree with the speed comments. Bit arrays are typically slower to edit and slower to search than a structure of bools. Accessing an element of a bit array requires accessing the bit vector itself and a bitwise and. The structure of bools omits the bitwise and. Updating an element of a bit array requires accessing that element, applying boolean arithmetic to set or clear the bit in question, and then saving the modified element. Updating an element of a structure of bools omits the initial access and the boolean arithmetic.

vedran Over a year ago

@David, exactly what kind of bool "structure" did you have in mind?

Mooing Duck Over a year ago

@vedran probably bool options[256]; (which is fast, if it fits in caches well.

Collectives™ on Stack Overflow

Use bit arrays?

3 Answers 3

2 Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related