Lua学習ノート(6)テーブル.sort

原文のリンク:http://pkxpp.github.io/2016/07/26/lua%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0(6)テーブル.sort/
lua学習ノートシリーズ——上山老人が分かち合う
簡単に言えば、table.sortの2番目のパラメータはカスタム比較関数をサポートしています.これは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.カスタム並べ替えアルゴリズムの問題
最初の問題は、カスタム比較関数が二つのパラメータを比較すると、結果を厳密に与えられなくなり、エラーが発生します.公式的な言い方では、比較関数は非対称性と伝達性を満たす必要があります.この二つの性質については、中学校の時に習った不等式の関連性を思い出すことができます.公式文書では次のように説明しています.
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)

その結果、比較関数のエラーが発生しがちで、2番目のパラメータはnilです.

attempt to compare number with nil

’’’’と’:’の違いを理解すればいいです.後ろの’:’は関数の最初のパラメータをselfにします.ですから、次のような書き方で問題を解決できます.

--    
function tbSort.fComp(a, b)
	return a < b;
end

もちろん、できるだけクローズドの比較関数を使って、この多くの面倒を省きました.
table.sortの比較関数は対象に向かってプログラミングする時に注意します.
lua対象におけるselfは、テーブル:func(param)が、テーブル.func(self,param)と等価であることを理解する必要がある.
テーブル:func定義式は、パラメータとして伝達された後に使用されます.デフォルトはテーブル: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"invalid order function for sorting");
    lua_pop(L, 1);  /* remove a[j] */
  }
  if (j3);  /* pop pivot, a[i], a[j] */
    break;
  }
  set2(L, i, j);
}

何時か違うところがありますか?
luaのソースコードの中の急速なソートは、pivotの他の部分の代わりに大きな循環を使用して並べ替えられています.一般的に、私たちは自分で速く書くときに、pivotより小さい部分とpivotより大きい部分のを再帰的に調整します.
再帰＋iと＋jのwhileは、自分が書いている間に比較関数の結果とi、jの大きさを同時にチェックして、オフラインを防止します.