Fractal Softworks Forum

Please login or register.

Login with username, password and session length
Advanced search  

News:

Starsector 0.97a is out! (02/02/24); New blog post: Simulator Enhancements (03/13/24)

Author Topic: O(1) memory sort  (Read 3136 times)

Ishman

  • Captain
  • ****
  • Posts: 269
    • View Profile
O(1) memory sort
« 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
Logged

xenoargh

  • Admiral
  • *****
  • Posts: 5078
  • naively breaking things!
    • View Profile
Re: O(1) memory sort
« Reply #1 on: March 19, 2014, 03:38:30 PM »

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 :)
Logged
Please check out my SS projects :)
Xeno's Mod Pack

Thaago

  • Global Moderator
  • Admiral
  • *****
  • Posts: 7174
  • Harpoon Affectionado
    • View Profile
Re: O(1) memory sort
« Reply #2 on: March 19, 2014, 06:27:43 PM »

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
Logged

Dark.Revenant

  • Admiral
  • *****
  • Posts: 2806
    • View Profile
    • Sc2Mafia
Re: O(1) memory sort
« Reply #3 on: March 19, 2014, 08:39:02 PM »

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.
Logged