Others have done things like it. Noone has done it as well. This is a complete O(log n) priority queue to replace GM's O(n) queue. Every function for Game Maker's priority queue is implemented, and a function to merge two queues has been added.
Please note that the FDS queues begin beating the DS queues only when they contain sufficiently many elements. Here is experimental data on what "sufficiently many elements" means for various GM versions and extensions.
- GM:8.1, DLL extension, direct-access functions: 23 elements
- GM:8.1, DLL extension, generalized functions: 93 elements
- GM:8.1, GML extension: 1024 elements
- GM:Studio, DLL extension, direct-access functions: 64 elements
- GM:Studio, DLL extension, generalized functions: 296 elements
- GM:Studio, GML extension: 8200 elements
Version 2.2 and the GML implementation use a binary min-max heap.
The DLL and dylib in Versions 2.3 and 2.4 use a double-heap, which reduces the average number of comparisons during removals.
Version 2.5 uses an interval heap, which improves on the concept of a double-heap by reducing paged memory access.
Replacements for all of Game Maker's ds_priority functions:
Additions for greater ease of use:
Additions for greater efficiency (Call these directly to avoid GM's script overhead):
- 2.5 - Improved C++ performance and reduced memory consumption, created GML extension using interval heap, removed deprecated functions and dylib, and moved to different licence.
- 2.4 - Rare bug fixed, improved C++ source, updated unregistered GML version, created more sensible naming scheme for exported DLL functions, created more sensible naming scheme for GM functions, and deprecated (but not removed) old naming scheme.
- 2.3 - HAS ERROR Reworked DLL back-end. Now has better average performance for large queues. Small-queue performance not noticeably changed. Additionally adds an untested dylib. Error Description: Removing minimum element from queue of 2 elements removes incorrect element.
2.2 - Reduced memory use for numbers. Performance is unchanged.
- 2.1 - OBSOLETE Slight tweaks, source code released.
- 2.0 - OBSOLETE Reworked entire back end. Now is much more useful. Also doubled maximum size of unregistered queues and fixed bugs.
- 1.1 - OBSOLETE Updated to work with both 8.1 and 7.0. fds_priority_read reads strings from both, and fds_priority_write writes for 7.0 (which 8.1 can read)
- 1.0 - OBSOLETE Release
Edited by Gamer3D, 21 November 2013 - 05:51 AM.