[TOC]
table.sort
简单来说就是table.sort的第二个参数支持自定义比较函数,这类似于c++的容器支持自定义比较函数一样,代码如下:
local tbTest = {
{1, 3},
{3, 5},
{5, 4},
{2, 3},
}
-- 比较函数
function cmp(a, b)
return a[2] < b[2]
end
-- 通常用法
table.sort(tbTest, cmp)
深入学习
在自己工作过程中,遇到过下面两个问题
1.自定义排序算法的问题
第一个问题是:当自定义比较函数出现比较两个参数时,无法严格给出一个结果,就会出现错误。用官方的说法是比较函数需要满足非对称和传递性质。对于这两个性质,可以回忆一下中学时候学的不等式相关性质,也可以看看《c++标准程序库》中介绍的比较函数排序准则[1]。官网文档说明如下:
Note that the comp function must define a strict partial order over the elements in the list; that is, it must be asymmetric and transitive. Otherwise, no valid sort may be possible.
拿上面的代码举例,当把比较函数改为:
-- 比较函数
function cmp(a, b)
return a[2] <= b[2]
end
这个时候就会出现下面的错误:
attempt to index local 'b' (a nil value)
因为,这个时候元素a={1, 3}和b={2, 3}的a[2] == b[2],a[2] <= b[2]和b[2] <= a[2]都成立。所以这个是比较函数是symmetric的。
2.面向对象方式的问题
在工作中,写比较大的功能的时候,会经常用到lua的面向对象的方式编码。一开始无知的时候,会写下面的代码,结果后面的苦头自己吃了。
local tbSort = {25, 18, 15}
--面向对象隐藏self
function tbSort:fCompWrap(a, b)
print("fCompWrap(self, a, b)", self, a, b)
return a < b;
end
-- 比较
table.sort(tbSort, tbSort.fCompWrap)
结果,往往是比较函数报错,第二个参数为nil
attempt to compare number with nil
只要理解’.’和’:’的区别就可以了,后面的’:’会使得函数的第一个参数为self。所以下面的一种写法可以解决问题:
--面向对象
function tbSort.fComp(a, b)
return a < b;
end
当然,最好可以用闭包的比较函数,就省掉了这许多麻烦。一点点的总结:
- table.sort的比较函数在面向对象编程时候要注意了
- lua面向对象中的self要理解:table:func(param) 等价于table.func(self, param)
- table:func定义式在作为参数(table.func)传递之后使用,默认就是table:func的调用形式,也就是第一个参数为self
- 应该理解function table:func(param)的定义形式等价于function table.func(self, param),这样更容易分的清楚
源码的简单分学习
关于问题1中的报错,可以看一下源码
for (;;) { /* invariant: a[l..i] <= P <= a[j..u] */
/* repeat ++i until a[i] >= P */
while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
if (i>u) luaL_error(L, "invalid order function for sorting");
lua_pop(L, 1); /* remove a[i] */
}
/* repeat --j until a[j] <= P */
while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
if (j<l) luaL_error(L, "invalid order function for sorting");
lua_pop(L, 1); /* remove a[j] */
}
if (j<i) {
lua_pop(L, 3); /* pop pivot, a[i], a[j] */
break;
}
set2(L, i, j);
}
有几点不一样的地方
- lua源码中的快速排序,是用大循环代替了pivot的另外一部分排序。一般我们自己写快排的时候,会递归调两次,小于pivot的一部分和大于pivot的一部分
- 递归++i和++j的while,一般自己在写的时候会同时检查比较函数的结果和i、j的大小,防止越界
参考补充
- [1]《c++标准程序库》
所谓的“排序准则”,必须定义strict weak ordering,其意义如下:
- 必须是“反对称的(antisymmetric)” 对operator<而言,如果x<y为真,则y<x为假。
- 必须是“可传递的(transitive)” 对operator<而言,如果x<y为真且y<z为真,则x<z为真。
- 必须是“非自反的(irreflexive)” 对operator<而言,x<x永远为假。