WoWInterface

WoWInterface (https://www.wowinterface.com/forums/index.php)
-   Tutorials & Other Helpful Info. (https://www.wowinterface.com/forums/forumdisplay.php?f=12)
-   -   Sorting tables with no garbage (table.sort alternatives) (https://www.wowinterface.com/forums/showthread.php?t=40748)

Iza 07-05-11 10:41 AM
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

Torhal 07-05-11 11:50 AM
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)

Iza 07-06-11 02:28 AM
Yes, you're perfectly right, thank you...

Xinhuan 07-09-11 12:54 AM
Gooder:
Code:
local function MySortFunction(a, b)
    return a.name < b.name
end

table.sort(my_table, MySortFunction)

Torhal 07-09-11 05:30 AM
Indeed. :P


All times are GMT -6. The time now is 05:23 PM.

vBulletin © 2024, Jelsoft Enterprises Ltd
© 2004 - 2022 MMOUI