Lua 排序

wiki

所使用的演算法是希爾排序 (以其發明者唐納·希爾命名)[維基百科]，而間隙遞迴來自羅伯特·塞奇威克 (請參閱 [A036569]，位在[整數遞迴線上百科全書]中，這裡可以參考 Sedgewick 的論文)。我使用希爾排序而非快速排序，因為前者通常速度差不多，而且程式碼簡單許多。這個間隙遞迴對於至少 1,000 萬個元素已經足夠了。

另請參閱 LazySort，以取得 Lua 排序的另一種觀點。

為了達到效率，有三個版本的分類器；最高層級的函式會根據環境選擇其中一個。有針對 < 運算子以及 > 運算子的特別版本，以及採用任何比較函式的通用程式，例如 table.sort。請注意，和 table.sort 一樣，如果比較函式的參數相等，則該函式應回傳 false，儘管在希爾排序的情況下並非那麼重要。

範例計時如下。

-- shellsort.lua
-- Written by Rici Lake. The author disclaims all copyright and offers no warranty.
--
-- This module returns a single function (not a table) whose interface is upwards-
-- compatible with the interface to table.sort:
--
-- array = shellsort(array, before, n)
-- array is an array of comparable elements to be sorted in place
-- before is a function of two arguments which returns true if its first argument
--    should be before the second argument in the second result. It must define
--    a total order on the elements of array.
--      Alternatively, before can be one of the strings "<" or ">", in which case
--    the comparison will be done with the indicated operator.
--    If before is omitted, the default value is "<"
-- n is the number of elements in the array. If it is omitted, #array will be used.
-- For convenience, shellsort returns its first argument.

do
  local incs = { 1391376,
                 463792, 198768, 86961, 33936,
                 13776, 4592, 1968, 861, 336, 
                 112, 48, 21, 7, 3, 1 }

  local function ssup(t, n)
    for _, h in ipairs(incs) do
      for i = h + 1, n do
        local v = t[i]
        for j = i - h, 1, -h do
          local testval = t[j]
          if not (v < testval) then break end
          t[i] = testval; i = j
        end
        t[i] = v
      end 
    end
    return t
  end

  local function ssdown(t, n)
    for _, h in ipairs(incs) do
      for i = h + 1, n do
        local v = t[i]
        for j = i - h, 1, -h do
          local testval = t[j]
          if not (v > testval) then break end
          t[i] = testval; i = j
        end
        t[i] = v
      end 
    end
    return t
  end

  local function ssgeneral(t, n, before)
    for _, h in ipairs(incs) do
      for i = h + 1, n do
        local v = t[i]
        for j = i - h, 1, -h do
          local testval = t[j]
          if not before(v, testval) then break end
          t[i] = testval; i = j
        end
        t[i] = v
      end 
    end
    return t
  end

  function shellsort(t, before, n)
    n = n or #t
    if not before or before == "<" then return ssup(t, n)
    elseif before == ">" then return ssdown(t, n)
    else return ssgeneral(t, n, before)
    end
  end
  return shellsort
end

一個簡單的測試（而且不是很好的基準）架構

local function gt(a, b) return a > b end
local function lt(a, b) return a < b end

local function builtinsort(t, before)
  if not before or before == "<" then table.sort(t)
  elseif before == ">" then table.sort(t, gt)
  else table.sort(t, before)
  end
  return t
end

local algo, sort = "Shell sort", shellsort
if not tonumber(arg[1]) then
  if arg[1] == "builtin" then
    algo, sort = "table.sort", builtinsort
  elseif arg[1] == "shell" then
    algo, sort = "Shell sort", require"shellsort"
  else error"Only shell and builtin are implemented"
  end
  table.remove(arg, 1)
end

local a = {}
local range = 100
for i = 1, tonumber(arg[1]) or 10000 do a[i] = math.random(1, range) end
local before = arg[2] and
        ( arg[2]:match"^[<>]$"
          or arg[2] and assert(loadstring("return function(a, b) return "..arg[2].." end"))()
        )
      or "<"

local now = os.clock()
sort(a, before)
local took = os.clock() - now
io.write(("%-12s with %i values: %7.3f seconds, comparison: %s"):format(algo, #a, took, arg[2] or "<"))

-- Validate
before = ({["<"] = lt, [">"] = gt})[before] or before
for i = 1, #a-1 do
  if before(a[i+1], a[i]) then print(("\t****Failed at %i\n"):format(i)); return end
end
print"\tOrder checked"

結果顯示，shellsort 儘管是純 Lua，但與 table.sort 相比具有競爭力；如果 table.sort 有最佳化的程式碼（小於比較），則 shellsort 會慢約 75%，但在 table.sort 有最佳化程式碼（大於比較）時，shellsort 比較快，而在比較函式主導計時的排序中，速度則大約相同。

# (luafast is compiled with aligned doubles):

rlake@freeb:~/lualib$ for count in 1e5 2e5 5e5 1e6; do
>  for comp in "<" ">" "(a-50)^2<(b-50)^2"; do echo
>    for algo in shell builtin; do
>      luafast testsort.lua $algo $count $comp
>    done           
>  done     
>done

Shell sort   with 100000 values:   0.352 seconds, comparison: < Order checked
table.sort   with 100000 values:   0.195 seconds, comparison: < Order checked

Shell sort   with 100000 values:   0.352 seconds, comparison: > Order checked
table.sort   with 100000 values:   0.430 seconds, comparison: > Order checked

Shell sort   with 100000 values:   0.914 seconds, comparison: (a-50)^2<(b-50)^2 Order checked
table.sort   with 100000 values:   0.805 seconds, comparison: (a-50)^2<(b-50)^2 Order checked

Shell sort   with 200000 values:   0.734 seconds, comparison: < Order checked
table.sort   with 200000 values:   0.414 seconds, comparison: < Order checked

Shell sort   with 200000 values:   0.758 seconds, comparison: > Order checked
table.sort   with 200000 values:   0.906 seconds, comparison: > Order checked

Shell sort   with 200000 values:   1.891 seconds, comparison: (a-50)^2<(b-50)^2 Order checked
table.sort   with 200000 values:   1.758 seconds, comparison: (a-50)^2<(b-50)^2 Order checked

Shell sort   with 500000 values:   1.961 seconds, comparison: < Order checked
table.sort   with 500000 values:   1.062 seconds, comparison: < Order checked

Shell sort   with 500000 values:   1.938 seconds, comparison: > Order checked
table.sort   with 500000 values:   2.352 seconds, comparison: > Order checked

Shell sort   with 500000 values:   5.031 seconds, comparison: (a-50)^2<(b-50)^2 Order checked
table.sort   with 500000 values:   5.000 seconds, comparison: (a-50)^2<(b-50)^2 Order checked

Shell sort   with 1000000 values:   4.320 seconds, comparison: <        Order checked
table.sort   with 1000000 values:   2.391 seconds, comparison: <        Order checked

Shell sort   with 1000000 values:   4.500 seconds, comparison: >        Order checked
table.sort   with 1000000 values:   6.062 seconds, comparison: >        Order checked

Shell sort   with 1000000 values:  12.305 seconds, comparison: (a-50)^2<(b-50)^2        Order checked
table.sort   with 1000000 values:  12.359 seconds, comparison: (a-50)^2<(b-50)^2        Order checked

留言

以下是元編程的程式碼：--DavidManura

do
  local incs = { 1391376,
                 463792, 198768, 86961, 33936,
                 13776, 4592, 1968, 861, 336, 
                 112, 48, 21, 7, 3, 1 }

  local function make_sorter(compare)
    local src = [[
      local incs = ...
        return function(t, n, before)
        for _, h in ipairs(incs) do
          for i = h + 1, n do
            local a = t[i]
            for j = i - h, 1, -h do
              local b = t[j]
              if not (]] .. compare .. [[) then break end
              t[i] = b; i = j
            end
            t[i] = a
          end 
        end
        return t
      end
    ]]
    return assert(loadstring(src))(incs)
  end

  local sorters = {}
  local aliases = {["<"] = "a<b", [">"] = "a>b"}

  function shellsort(t, before, n)
    before = aliases[before] or before or "a<b"
    n = n or #t
    local beforesrc = type(before) == "function" and "before(a,b)" or before
    local sorter = sorters[beforesrc]
    if not sorter then
      sorter = make_sorter(beforesrc)
      sorters[beforesrc] = sorter
    end
    return sorter(t, n, before)
  end

  return shellsort
end