Fractal Softworks Forum
Other => Discussions => Topic started by: Ishman on March 19, 2014, 03:23:58 PM
-
Ho snap, new sort algorithm. Thought some of you fine folks might be interested in it.
Note, this isn't O(1) operations, but memory.
https://github.com/BonzaiThePenguin/WikiSort (https://github.com/BonzaiThePenguin/WikiSort)
-
Neat! And licensed so that everybody can use it, too, which was very nice of them :)
I must admit that I don't follow all of this paper (this kind of low-level hackery not being my thing, generally) but the documentation is really quite nicely written and clean. It really looks cool, especially for certain types of big number-crunching :)
-
Cool stuff! I'm looking at their explanation pages and they are really nice. I was up to my eyeballs in pointers and custom data structures about a year back, so this brings back painful memories. :P
-
Neat! And licensed so that everybody can use it, too, which was very nice of them :)
I must admit that I don't follow all of this paper (this kind of low-level hackery not being my thing, generally) but the documentation is really quite nicely written and clean. It really looks cool, especially for certain types of big number-crunching :)
Not even close to low-level hackery. As far as I can tell, they have not optimized this at the assembler level, which is usually what is needed in order for a sorting algorithm to compete in terms of speed. However, it does increase speed significantly over the standard similarly-featured sorting methods, which is obviously a good sign.
This seems to be a nice advance in sorting methodology. It's not a lifechanger or anything, for the most part, but it's worth using if you need it.
As far as modding goes, this is almost completely irrelevant. In most games, we're bounded by computational time, not memory usage, so this type of algorithm is usually pointless in the first place. However, on memory-limited devices such as severs with enormous databases (if your database is over 64GB you can't use an O(n) memory sort; only O(lgn) and O(1) are viable, and for truly gigantic databases -- especially over multiple devices -- only O(1) can be used), this can have a tremendous benefit because it speeds things up by a significant amount. If you have a server that handles massive databases, you should look into this algorithm.