32 replies to this topic

[Gamer3D]

I'd jsut like to point out that the priority queue functions are implemented incorrectly. Specifically, the find_max/find_min functions should return the VALUE, not the priority.

Also, various functions don't access local variables.

As of now, I've edited your functions to use a minmax heap. More specifically, the priority queue. Not done optimizing though.

Edited by Gamer3D, 08 March 2011 - 07:02 AM.

[Davve]

Why do you use instances for this, why not arrays? What if somebody does instance_deactivate_all()?

And imagine if the only reason a person buys Game Maker is to use the ds_ functions. But with these scripts, he no longer have to buy it. In these cases, you are basically stealing money from yyg, and they can decide to take legal action against this.

Edited by Davve, 08 March 2011 - 10:41 AM.

[creativebunch]

And imagine if the only reason a person buys Game Maker is to use the ds_ functions. But with these scripts, he no longer have to buy it. In these cases, you are basically stealing money from yyg, and they can decide to take legal action against this.

As you should be able to tell from previous posts, these don't work anywhere near as well as the actual data structures. If Yoyo Games wants this taken down I will glady comply, however I don't believe someone will not buy game maker because he/she can get a crappy buggy version of the actual functions for free.

[Gamer3D]

And imagine if the only reason a person buys Game Maker is to use the ds_ functions. But with these scripts, he no longer have to buy it. In these cases, you are basically stealing money from yyg, and they can decide to take legal action against this.

As you should be able to tell from previous posts, these don't work anywhere near as well as the actual data structures. If Yoyo Games wants this taken down I will glady comply, however I don't believe someone will not buy game maker because he/she can get a crappy buggy version of the actual functions for free.

How did this even come up? The iOS "compiler" people got a cease-and-decist order because YoYo wants to be the ONLY provider of a method for putting GM games on non-windows platforms. I think the ONLY legal reasons they could have would be (maybe) copyrights on the iOS runner (and with how GM does things, "compiling" a game is nothing more than copying file A into specific places in file B, making it equivalent to modding). Personally, I think the "compiler" people could win in court.

Also, this is not stealing from YoYo. By that logic, if someone is selling a $1000 game engine, and I make a cheaper one that does the same thing, I am stealing from the previous person. This is clearly false. It is not stealing, as I haven't used what the other person did.

I don't condone trying to profit from other people's work. I LOVE when people make competing products; it forces people to either lower their prices or make better products. It's simple economics.

EDIT: The guy below me understands. I love sarcasm.

Edited by Gamer3D, 09 March 2011 - 06:48 PM.

[LSnK]

Guys, someone didn't give me a million euros today.

That's right, someone stole a million euros from me. I'm pretty broken up about it...

[paul23]

Why do you use instances for this, why not arrays? What if somebody does instance_deactivate_all()?

And imagine if the only reason a person buys Game Maker is to use the ds_ functions. But with these scripts, he no longer have to buy it. In these cases, you are basically stealing money from yyg, and they can decide to take legal action against this.

uhm no they can't take "legal action".. This is silly to even consider!

[FoxInABox]

Some fixes:

// uds_priority_add(id,val,prio)

argument0.Value[argument0.PriorMax]=argument1;
argument0.Prior[argument0.PriorMax]=argument2;
argument0.PriorMax+=1;

added argument0. in front of each PriorMax, since it tried to access PriorMax outside the priority object

// uds_priority_delete_min(id)
if argument0.PriorMax = 0 return noone;
var i,n;
n=0;
for (i=0; i<argument0.PriorMax; i+=1) {
    if argument0.Prior[n]>argument0.Prior[i] n=i;
}
i=n;
n=argument0.Value[n];
argument0.PriorMax-=1;
for (i=i; i<argument0.PriorMax; i+=1) {
    argument0.Value[i]=argument0.Value[i+1];
    argument0.Prior[i]=argument0.Prior[i+1];
}
return n;

This one was returning the priority, not the value, so I made n find the row with the smallest priority, then tell the row number to i, then overwrite the n Value, before pushing all rows below that row, 1 row up .. so I just returned n

[Gamer3D]

Here's an unregistered implementation of priority queues using a minmax heap. It doesn't use the same function names as your implementation, but on a sample size of 15999 (max size), it performs 17.59 times as fast as GM's priority queues.

I've put it here so people here can:

• Copy its functions into this script library.
• Improve its maximum size (Just use separate arrays for priority and value. I don't know why I didn't do that in the first place, but...)
• Add string reading/writing functions for the other GM data structures, using mine as an example.

Edited by Gamer3D, 02 June 2012 - 02:19 AM.

[sabriath]

Wait...a GML version of priority queues that is 17x faster than the built-in versions? There has to be something wrong with the bench-marking of it, I just don't see how in the world interpretive beats hardcode. Scanning through quickly revealed that your first set of scripts are commented out anyway, so I'm not sure what that's all about...I'll have to take a look at it more thoroughly to find the fault (and yes, there will be one somewhere).

[Gamer3D]

Wait...a GML version of priority queues that is 17x faster than the built-in versions? There has to be something wrong with the bench-marking of it, I just don't see how in the world interpretive beats hardcode. Scanning through quickly revealed that your first set of scripts are commented out anyway, so I'm not sure what that's all about...I'll have to take a look at it more thoroughly to find the fault (and yes, there will be one somewhere).

The fault is that GM's priority queues are naively implemented, at O(n), while mine are implemented properly, at O(log n). The more elements in the queue, the better mine will perform than GM's (I haven't checked how many there have to be to tip in my favor yet, but I'm still winning with just 2000 elements)

FYI, I just put up my extension benchmark, so the first folder of scripts is just for the extension. Use the second folder of scripts.

[sabriath]

The fault is that GM's priority queues are naively implemented, at O(n), while mine are implemented properly, at O(log n). The more elements in the queue, the better mine will perform than GM's (I haven't checked how many there have to be to tip in my favor yet, but I'm still winning with just 2000 elements)

FYI, I just put up my extension benchmark, so the first folder of scripts is just for the extension. Use the second folder of scripts.

orly? Last time I created a benchmarking program, I actually used separate variables at each phase....this:

time = current_time;
repeat 15999
    fds_priority_add(pq1, 1, random(1));
time2 = current_time;

time = current_time;
repeat 10000
    fds_priority_delete_min(pq1);
time2 = current_time;

room_caption = 'Time for deleting 10000 time using: Scripts: ' + string((time2 - time) / 1000);

time = current_time;
repeat 15999
    ds_priority_add(pq1, 1, random(1));
time2 = current_time;

time = current_time;
repeat 10000
    ds_priority_delete_min(pq1);
time2 = current_time;

room_caption += ', Built-in: ' + string((time2 - time) / 1000);

Looks like you used the same variables...the only thing you are measuring is the time of "delete_min" for both sets. Unless you purposely just left the code fully uncommented for your own purposes (testing each phase separately), but "add" and "delete_min" are hardly enough testing for the scripts as a whole.

Plus, it looks like you are using a ONE array for ALL priority queues. This may seem trivial considering not a lot of people are going to be using PQs, but since you are stating that "with enough elements" your scripts will work better, but I'm seeing it more of the fact that "with enough elements," your scripts will not work at all (face it, if someone is using PQs to the extent that you say, then they will easily be needing much much more at some point).

I commend you for making a minmax heap for PQs...it's a great self-exercise and possibly a kick in the butt for YYG to possibly go that way with them.

[Gamer3D]

orly? Last time I created a benchmarking program, I actually used separate variables at each phase....this:

Spoiler

time = current_time;
repeat 15999
    fds_priority_add(pq1, 1, random(1));
time2 = current_time;

time = current_time;
repeat 10000
    fds_priority_delete_min(pq1);
time2 = current_time;

room_caption = 'Time for deleting 10000 time using: Scripts: ' + string((time2 - time) / 1000);

time = current_time;
repeat 15999
    ds_priority_add(pq1, 1, random(1));
time2 = current_time;

time = current_time;
repeat 10000
    ds_priority_delete_min(pq1);
time2 = current_time;

room_caption += ', Built-in: ' + string((time2 - time) / 1000);

Looks like you used the same variables...the only thing you are measuring is the time of "delete_min" for both sets. Unless you purposely just left the code fully uncommented for your own purposes (testing each phase separately), but "add" and "delete_min" are hardly enough testing for the scripts as a whole.

Yes, I was just testing delete_min. My reasons:

• delete_min is almost exactly the same as delete_max, code-wise.
• Addition was extremely fast in both, although because of the simpler implementation, GM's was faster (Mine: 0.33s, GM: 0.03s for 15999)
• Addition, finding, and deletion of min/max are just about the ONLY operations that a priority queue should be used for.
• Also, this was made as a test-bed for my own extension. It creates a queue with n elements, then benchmarks m operations on it.

Also, comparing speed of finding maximum elements (minimum will be slightly faster than maximum in mine): (Mine: 0.03s, GM: 16.63s for 10000 operations on a queue of size 15999)

Plus, it looks like you are using a ONE array for ALL priority queues. This may seem trivial considering not a lot of people are going to be using PQs, but since you are stating that "with enough elements" your scripts will work better, but I'm seeing it more of the fact that "with enough elements," your scripts will not work at all (face it, if someone is using PQs to the extent that you say, then they will easily be needing much much more at some point).

Yes, yes, this was on the list of things people could do to improve it. I don't remember why I did one array, but by editing it to use three (For size, values, and priorities), you can double the maximum elements. This'll be a back-burner project for me.

I commend you for making a minmax heap for PQs...it's a great self-exercise and possibly a kick in the butt for YYG to possibly go that way with them.

Yeah, you'd think that, but when I recommended this exact same thing (And pointed to my extension as a "Oh hey, you're really, really slow" proof) they ignored it.


EDIT: After a quick edit of the scripts, I found occasional errors. They could be from either the original scripts (unlikely) or the edit, but I'm writing a diagnostic script to be sure. I'll post the results.

EDIT #2: Looks like it was probably in both. I guess that's what I get for copy-pasting from my (working, tested) C++ code.

EDIT #3: Fixed.

Edited by Gamer3D, 02 June 2012 - 02:19 AM.

[creativebunch]

I have updated the topic to my latest scripts. I made them a few months ago but I guess never got around to uploading them.

I have almost no memory making the scripts, I only remember that I made them. I hope there aren't any problems, I can't remember if there are The grid scripts still use an object like last time, but this time it's created in a script so you don't have to import the object.

Edited by creativebunch, 06 July 2012 - 02:13 PM.