Fast way to check list of 0 or 1 values?

What is the fastest way to look up a list for 0 or 1 values?

I used an Array which was very fast like:

Code:

---

int boolList[5000];

---

and each entry would either have a value of 0 or 1.

I would then check this like:

Code:

---

if (boolList[i])

---

...but that needs to be initialized to a set number of entries. I would like to be able to have the same speed but also be able to set number of entries at runtime. A linked list would be a lot slower right? The predefined lists I tested with was but I'm not sure how much bulk they had. Ideas?

If you want an array whose size is determined at runtime, then the most obvious choice is vector.

Quote:

---

Originally Posted by anon

If you want an array whose size is determined at runtime, then the most obvious choice is vector.

---

Nevermind.:)

Vector reference.

Ok I tried with vector now but it is about 30% slower than with an Array in my test case.

Could it be worth having a pointer to an Array and deleting and recreating the Array at runtime instead? Can you even do that?

vector<bool> , although this is a special specialisation of vector

Quote:

---

Originally Posted by DrSnuggles

Ok I tried with vector now but it is about 30% slower than with an Array in my test case.

Could it be worth having a pointer to an Array and deleting and recreating the Array at runtime instead? Can you even do that?

---

That is exactly what the vector does.

Would you mind posting some code that you are worrying about?

Consider a bitset.

Ok, I tried a few things and timed them, here are the results. Not very high values overall but they were consistent anyways.

Array: 0.078 sec
vector<int>: 0.094 sec
bitset: 0.156 sec
vector<bool>: 0.172 sec
Tab<int> : 0.203 sec

Array is still the fastest by quite a lot. Need to find a way to use something similar.

What compiler are you using?

Those times don't mean anything without code. Array does not seem a lot faster than a vector in those timings, and you said you won't be able to use an array anyway.

Quote:

---

Originally Posted by Elysia

What compiler are you using?

---

Visual Studio 2008 pro

Quote:

---

Originally Posted by anon

Those times don't mean anything without code. Array does not seem a lot faster than a vector in those timings, and you said you won't be able to use an array anyway.

---

What I'm doing is actually intersecting a 3d object(60000 tris) 1000 times. For each triangle I check if the value in the list is 0 or 1. Quite a lot of code involved but this is the difference in time if I use the different types to get and set the 0 or 1 values. Nothing else is different so those are real differences. Did a test now with 10000 intersections and for Array the time was 0.703 and vector<int> 0.938. That is quite a lot more intersections I could squeeze in for the time difference between those...something like 3300 more if I use Array.

I probably won't be able to use an Array no which is too bad. If I can't find another way the vector<int> will have to do.

Try using a vector<char> to make it 4 or 8 times smaller than vector<int>. Making the vector smaller could allow more of it to stay in the CPU cache.
Also, try calling vector::reserve() to reserve a large size first before you start using your vector. If you can reduce the number of reallocations the vector does, it could speed things up.

Can I just point out that there's no way that you can get faster than an array - other solutions will be SIMILAR speed, but likely never quite as fast.

If you just need to know at runtime how large your array should be, you could use dynamic memory allocation, but that [at least sometimes] adds an extra memory read to fetch the pointer to the memory block that contains your array.

Edit: As suggested, using a byte-size entry (char or bool) would increase performance of walking through the array due to less cache pollution.

--
Mats

Quote:

---

Array: 0.078 sec
vector<int>: 0.094 sec
bitset: 0.156 sec
vector<bool>: 0.172 sec
Tab<int> : 0.203 sec

---

Well, 'vector<int>' is not bad at all! This is just the price for the generic programming part. What does surprise me, however, is that the 'vector<bool>' is so much slower than the 'int' specialisation.
I think this is due to the abscence of what cpjust is suggesting: the member function "reserve(..)". The boolean specialisation should be faster than the int specialisation, as matsp says....

In general, if speed is an enourmous constraint on your design, your application is extremely critical etc etc, use an array. If not, use a container from the library. Simply because you don't have to care anymore about what's behind and because it's so much more generic...