Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to "verify" your details, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.
 Entire forum ➜ Programming ➜ General ➜ String based flag list VS. Bit based flag list

String based flag list VS. Bit based flag list

It is now over 60 days since the last post. This thread is closed.     Refresh page


Posted by Nick Cash   USA  (626 posts)  Bio
Date Thu 04 May 2006 05:33 PM (UTC)
Message
I was pondering about this the other night. A string based flag list (that is, something like "dark inside safe") fairly easy to parse and has no max limit of flags. A bit based flag list (using ints) is very fast and relatively easy to manipulate, but it has a maximum capacity (though it can be extended like SMAUG).

My question is thus: which is better? Is the flexibility of the string based list better despite the greater overhead? Do you think the lag would even be noticable for a relatively large world doing string lookups for flags? Or is it worth just running with bitvectors and having an extended system from the start?

~Nick Cash
http://www.nick-cash.com
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #1 on Thu 04 May 2006 07:16 PM (UTC)
Message
String comparison really isn't that slow. So, to answer your question, the time spent comparing strings will be very low, especially if you store them in a fast lookup format (e.g. a tree, or binary search over a sorted list of strings) -- but frankly, even a linked list will be quite fast.

A hybrid solution is to create a runtime correspondence between the flag names and integers, and use those integers to create the numerical bit vectors. If bitvectors are implemented correctly, that is, with no limit on the number of flags you could put in, then you get the speed of numerical comparison with the flexibility you were describing with strings.

But seriously, the string comparisons really aren't that slow... you'd have to be doing a LOT of them to really feel the difference.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Nick Gammon   Australia  (23,057 posts)  Bio   Forum Administrator
Date Reply #2 on Thu 04 May 2006 10:41 PM (UTC)
Message
If you are doing a lot of them, scanning a long string for names seems to me to be a bit of a slow way. Especially if you have flags with similar names (like "dark" and "darkness") so a simple search for "dark" won't work.

If you are using C++ why not just use the STL and use a set? That gives an unlimited number of flags, and is quick as it has a fast lookup.

Here is an example:


#include <set>
#include <string>
#include <iostream>

using namespace std;

int main ()
  {
  set<string> flags;

  flags.insert ("dark");

  if (flags.find ("dark") != flags.end ())
    cout << "dark found" << endl;
  else
    cout << "dark not found" << endl;

  }


The set here (flags) can have an unlimited number of unique elements, keyed by name. You use "find" to see if a flag is set.

Of course, this is an internal structure, you would need to serialise it (eg. to a comma-delimited string) for saving to disk.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Samson   USA  (683 posts)  Bio
Date Reply #3 on Fri 05 May 2006 12:56 AM (UTC)
Message
Nice. These would be even more useful than std::bitset flags as far as the ease with which you can check them in code. I might play around a bit with std::set

I know this is something I should probably know, but when you mention serialization, how would one go about that?
Top

Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #4 on Fri 05 May 2006 01:29 AM (UTC)
Message
You'd have to serialize by hand. You would write a function that took a set of strings and outputted its elements as, for instance, CSV. Then you'd write a function that took a CSV string and created a set of strings.

It's not clear how much more general you can make this without implementing a whole bucketload of Java into C++, by giving all your objects toString() methods -- but if you had those, you could make this rather generic by serializing any set by writing CSV of the elements' toString() results. Of course, you'd have to be clever and escape commas, etc.

David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top

Posted by Nick Gammon   Australia  (23,057 posts)  Bio   Forum Administrator
Date Reply #5 on Sat 06 May 2006 06:00 AM (UTC)
Message
On this page:

http://www.gammon.com.au/forum/bbshowpost.php?bbsubject_id=2896

I describe various utilities including VectorToString and StringToVector which are basically what you would need to serialize. This was for vectors but the nice thing about STL is that sets would be virtually identical.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

Posted by Nick Cash   USA  (626 posts)  Bio
Date Reply #6 on Sat 06 May 2006 07:20 AM (UTC)
Message
Ah, very nifty. Thanks.

~Nick Cash
http://www.nick-cash.com
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


19,378 views.

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum


[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.