Gammon Forum : Programming : General : String based flag list VS. Bit based flag list

Log on

Gammon Forum

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 (22,975 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 (22,975 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.

17,695 views.

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

Go to topic: Search the forum

top

Quick links: MUSHclient. MUSHclient help. Forum shortcuts. Posting templates. Lua modules. Lua documentation.

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