Aug 17, 2009 2
Aug 3, 2009 0
The bitvector is a nice little data structure that allows you to keep boolean values closely packed together.
In a nutshell, the bitvector lets you store boolean values ( 0 or 1 ) in the bits that make up an int. So, say you need 32 booleans, you just use the 32 bits from a ( 32 bit ) integer to store your 0′s and 1′s close together. This allows you to use up much less space than if you had an actual 32 index Boolean array or vector.
Now why not just use an array of booleans you ask ?
Well, first of all AS3 doesnt support Boolean arrays, but yes, it does have a vector class now, true dat!
Secondly, each index in the vector will be at least 4 bytes on most systemes ( I think ), and 4 * 32 = 128. So to store your 32 values you need 128 bits.
Hmm, wait a minute, a Boolean is nothing but a 0 or a 1, so why not just use 32 bits in the array instead of 128 ?? Well thats got to do with how computers actualy handle data. To keep it simple, the computer can’t really handle very small sets of data, whenever it handles memory it moves a higher number of bits at a time, 8 for example but I’m not sure exactly how much it is. So if the computers moves 8 bits at a time, using an array or vector, the computer would only be handling 2 values at a time, and not 8.
Using a bitvector allows you to keep all those values as close together as possible without waisting any space
Just google bitvectors if none of this made any sense.
Here is a little example using a bitvector to store the boolean values that represent the state of a cell in the game of life.
May 30, 2009 8
Say you live in weighted graph. And say you want to go from vertex A on that graph to vertex D, for instance, following the shortest path. Well it so happens that a smart man called Edsger Dijkstra already figured that one out. He came up with an algorithm to get the shortest path weight in a graph.
If you are interested in graph and data structures and all that stuff, you should read up about it. A quick google search should do the trick, and if not this might help, and this too.
This is the kind of stuff you can do with graphs. Pretty cool!
I added the source, and my data structure classes. They’re still work in progress, but they work pretty well with Dijkstra’s algorithm. If you want some pretty cool data structs check those out.
Click on a node to select it as source node, click on another one, and watch the shortest path show up.