The Problem
If you have a big array, and you want to find something in it, you can do something like this:
PHP Code:
temp.bigArray = {1,45,6,2,34,843,1236,7456,234,1237,345,12367,345123,34575,1311,63467,3482,34572,355}; // even bigger if you want
if (1311 in temp.bigArray) {
echo("Found it!");
} else {
echo("Couldn't find it.");
}
This works fine. But say this is in a 0.05 timeout... this means it may slow down you code even if it is a tiny bit slow.
The main problem is that if
temp.bigArray gets even bigger,
someNumber in temp.bigArray will take even longer.
The way
in works is that the GS engine does a loop until it finds what you are looking for, then it stops. So if what you are looking for happens to be at the end of a really big list (or not in the list at all), you could be in trouble, because it'd need to go through the whole list to find it.
Oh no, I'm doomed now! Or am I?
Thankfully, there is a way to make this faster in GS2, because Stefan has implemented a "hash map". What this means is that, no matter how big your data is, it will always take the same amount of time to find something.
The way we can harness this power is with a
TStaticVar.
Here is some code:
PHP Code:
temp.bigHash = new TStaticVar();
temp.bigHash.x1 = true;
temp.bigHash.x45 = true;
temp.bigHash.x6 = true;
temp.bigHash.x2 = true;
temp.bigHash.x34 = true;
temp.bigHash.x843 = true;
temp.bigHash.x1236 = true;
temp.bigHash.x7456 = true;
temp.bigHash.x234 = true;
// keep going etc....
temp.bigHash.x1311 = true;
// more! ...
// until you are done
if (temp.bigHash.x1311) {
echo("Found it!");
} else {
echo("Couldn't find it.");
Note: The reason for the "x" is because you can't start a variable name with a number. If you were looking for strings then you wouldn't need that.
No matter how big your
temp.bigHash is, you will always be able to find your number in the same amount of time!
If you are wondering how to do
PHP Code:
if (temp.v in temp.bigArray) {
in a hash, this is how:
PHP Code:
if (temp.bigHash.(@"x"@temp.v)) {
The only downside to this approach is that a TStaticVar will take slightly longer for the engine to make than an array would.
This means that a good place to use a TStaticVar is when you need to look up a couple things at once or infrequently update the hash.
The Evidence
Without this, I'd just be some crazy guy blabbing on about stuff. Here are the facts!
I'll be using my GBench script to take get these statistics since its makes everything really easy.
This is the code to run (and change the number based on how many we are trying).
PHP Code:
this.num = 3;
this.testStatic = new TStaticVar();
this.testArray = new[0];
for (temp.i = 1; temp.i <= this.num; temp.i++) {
this.testStatic.(@"x"@temp.i) = true;
this.testArray.add(temp.i);
}
temp.a = function () {
return this.num in this.testArray;
};
temp.h = function () {
return this.testStatic.(@"x"@this.num);
};
temp.cfg = new TStaticVar();
temp.cfg.samples = 50;
this.defaultMainWith(temp.cfg, {
this.bench("BigArray", temp.a),
this.bench("BigHash", temp.h)
});
Starting small, let's fill up an array with 10 things, and a hash with 10 things. Then we'll try to find the last (tenth) item each and see which takes longer.
And the results...
NPC Code:
BigArray: 0.001807276 ms
BigHash: 0.001884771 ms
Oh no, looks like the array was a bit faster for this one...
If you are thinking now that it's going to require thousands of elements to see a speed increase from the hash, you are wrong.
Let's try 30:
NPC Code:
BigArray: 0.00200592 ms
BigHash: 0.00194334 ms
It's a small increase, but this proves that the
TStaticVar is already working at a list size of only 30!
Let's crank it up a notch to 100...
NPC Code:
BigArray: 0.003129381 ms
BigHash: 0.001909805 ms
It's getting really clear now that the hash is a lot faster when your list is bigger.
1000:
NPC Code:
BigArray: 0.016829137 ms
BigHash: 0.002007371 ms
This means at 1000 elements, the hash is almost 10x as fast as the array.
It gets even better if you go higher, but I'm not sure how many people work with arrays that big.
Final Thoughts
In general, this would be pointless if you are already looping through the list to say, add up all the numbers or something.
But, if you are just trying to see if something exists in a set of data, using the
TStaticVar approach will be a sure way to guarantee that your system will not slow down once you get more data.
06-15-2010, 06:10 AM
Linear Mode
