Lua 排序

wiki

所使用的算法是希尔排序（以其发明者唐纳德·希尔命名） [wikipedia]，间隙序列来自罗伯特·塞奇威克（参见 [A036569] 在 [在线整数序列百科全书] 中关于塞奇威克论文的引用）。我使用希尔排序而不是快速排序，因为它通常一样快，而且代码更简单。间隙序列应该足以处理至少 1000 万个元素。

另请参见 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 与table.sort 相比具有竞争力，尽管它是纯 Lua；在table.sort 具有优化实现（少于比较）的情况下，shellsort 慢了大约 75%，但在它具有优化实现（大于比较）的情况下，它更快，并且在比较函数主导计时结果的排序中，两者大致相同。

# (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