Thread: Fast way to check list of 0 or 1 values?

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    166

    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?
    Last edited by DrSnuggles; 08-03-2008 at 11:20 AM.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    If you want an array whose size is determined at runtime, then the most obvious choice is vector.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    166
    Quote Originally Posted by anon View Post
    If you want an array whose size is determined at runtime, then the most obvious choice is vector.
    Nevermind.
    Last edited by DrSnuggles; 08-03-2008 at 11:48 AM.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User
    Join Date
    Oct 2007
    Posts
    166
    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?
    Last edited by DrSnuggles; 08-03-2008 at 12:09 PM.

  6. #6
    Registered User
    Join Date
    May 2008
    Location
    Paris
    Posts
    248
    vector<bool> , although this is a special specialisation of vector

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Quote Originally Posted by DrSnuggles View Post
    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?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Consider a bitset.

  9. #9
    Registered User
    Join Date
    Oct 2007
    Posts
    166
    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.

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    What compiler are you using?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Registered User
    Join Date
    Oct 2007
    Posts
    166
    Quote Originally Posted by Elysia View Post
    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.
    Last edited by DrSnuggles; 08-03-2008 at 03:13 PM.

  13. #13
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    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.

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Last edited by matsp; 08-04-2008 at 02:09 AM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    Registered User
    Join Date
    May 2008
    Location
    Paris
    Posts
    248
    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...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  2. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM