Reply
 
Thread Tools Display Modes
Unread 07-05-11, 10:41 AM   #1
Iza
A Cyclonian
AddOn Author - Click to view addons
Join Date: May 2009
Posts: 43
Sorting tables with no garbage (table.sort alternatives)

Hi all,
if you need to sort tables quite frequently you'll find that table.sort causes a lot of garbage memory. Here are two memory friendly in-place alternatives (parameter compatible to table.sort). Maybe some people finding this helpful:

1. Shell sort (around 1/3 slower than table.sort which is a quick sort implementation in lua):

Code:
local tIncrements = {
	1391376, 463792, 198768, 86961, 33936,
	13776, 4592, 1968, 861, 336,
	112, 48, 21, 7, 3, 1
};

--
local tInc;
local tSwap;
local tCnt0, tCnt, tCnt2;
local tSize;
local tVal;
local tVal2;
function shellSort(aTable, aValidator)
  for tCnt0 = 1, #tIncrements do
    tInc = tIncrements[tCnt0];
    for tCnt = tInc + 1, #aTable do
      tVal = aTable[tCnt];

      for tCnt2 = tCnt - tInc, 1, -tInc do
        tVal2 = aTable[tCnt2];
        if (not aValidator(tVal, tVal2)) then
          break;
        end

        aTable[tCnt] = tVal2;
        tCnt = tCnt2;
      end
      aTable[tCnt] = tVal;
    end
  end
end
For tables which most likely are sorted already (or close to being sorted) even good old bubble sort can be very fast:

Code:
local tCnt, tCnt2, tSize;
local tVal1, tVal2;
local tIsSwapped;
function bubbleSort(aTable, aValidator)
	tSize = #aTable - 1;
	for tCnt = 1, tSize do

		tIsSwapped = false;
		for tCnt2 = tCnt, tSize do
			tVal1 = aTable[tCnt2];
			tVal2 = aTable[tCnt2 + 1];
			if (not aValidator(tVal1, tVal2)) then
				aTable[tCnt2] = tVal2;
				aTable[tCnt2 + 1] = tVal1;
				tIsSwapped = true;
			end
		end

		if (not tIsSwapped) then
			return;
		end
	end
end
Iza is offline   Reply With Quote
Unread 07-05-11, 11:50 AM   #2
Torhal
A Pyroguard Emberseer
 
Torhal's Avatar
AddOn Author - Click to view addons
Join Date: Aug 2008
Posts: 1,051
The only time table.sort() should be causing "garbage memory" is if you are creating a new sort function every time you call it instead of re-using a single function.

Bad:

Code:
table.sort(my_table, function(a, b)
                                if a.name < b.name then
                                    return true
                                else
                                    return false
                                end
                             end)
Good:

Code:
local function MySortFunction(a, b)
    if a.name < b.name then
        return true
    else
        return false
    end
end

table.sort(my_table, MySortFunction)
__________________
Whenever someone says "pls" because it's shorter than "please", I say "no" because it's shorter than "yes".

Author of Revelation, Spamalyzer, TravelAgent, Volumizer, and many other AddOns.
Torhal is offline   Reply With Quote
Unread 07-06-11, 02:28 AM   #3
Iza
A Cyclonian
AddOn Author - Click to view addons
Join Date: May 2009
Posts: 43
Yes, you're perfectly right, thank you...

Last edited by Iza : 07-06-11 at 04:50 AM.
Iza is offline   Reply With Quote
Unread 07-09-11, 12:54 AM   #4
Xinhuan
A Chromatic Dragonspawn
 
Xinhuan's Avatar
AddOn Author - Click to view addons
Join Date: Feb 2007
Posts: 171
Gooder:
Code:
local function MySortFunction(a, b)
    return a.name < b.name
end

table.sort(my_table, MySortFunction)
__________________
Author of Postal, Omen3, GemHelper, BankItems, WoWEquip, GatherMate, GatherMate2, Routes and Cartographer_Routes
Xinhuan is offline   Reply With Quote
Unread 07-09-11, 05:30 AM   #5
Torhal
A Pyroguard Emberseer
 
Torhal's Avatar
AddOn Author - Click to view addons
Join Date: Aug 2008
Posts: 1,051
Indeed. :P
__________________
Whenever someone says "pls" because it's shorter than "please", I say "no" because it's shorter than "yes".

Author of Revelation, Spamalyzer, TravelAgent, Volumizer, and many other AddOns.
Torhal is offline   Reply With Quote
Reply

Go BackWoWInterface » Developer Discussions » Tutorials & Other Helpful Info. » Sorting tables with no garbage (table.sort alternatives)

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off