2012/12/01 〜 2012/12/25TeX & LaTeX Advent Calendar
こちらは（ｒｙ
* * *
例の「TeXsort」では満足しない人のために、「変換して TeX プログラミング」でビンソートを取り扱う。配列を含むプログラムの変換の例。
Lua で「ビンソート」してみた
bin_sort(ary) で整数値の要素をもつ配列 ary を昇順に整列する（上書きする）。((なお、Lua では配列の添字は 1 から始まる。ary の長さ（＝要素数＝最大添字）を #ary と記述する。))ここでの処理では、まず配列を一度スキャンして最小値と最大値を求めた上で、その範囲の添字をもつ係数の「配列」ct((ary 中の最小値を 10、最大値を 20 とすると、ct[10]〜ct[20] の範囲だけが非 nil の値をもつ、ということ。「長さ」の概念がないので厳密には配列でなく連想配列である。))を用意する、という手順をとっている。それ以外は通常のビンソートの手順（Wikipedia「バケットソート」を参照*1）と同じである。
なお、bin_sort() だけ TeX で実装しても LaTeX で実行を確認できるコードが書けないので、ここでは動作確認のデモとして demo_bin_sort(x,...) という関数を用意している。引数の整数列からなる配列について bin_sort() を実行しその結果を表示している。
-- 整数型: j, k, m, min, max -- 配列型: ct (ary は引数) --(公開) bin_sort(配列ary) -- 整数配列 ary を昇順に整列する. (結果で上書きする.) function bin_sort (ary) -- 入力データの最小値, 最大値を求める min = ary[1]; max = min for k = 1, #ary do if min > ary[k] then min = ary[k] end if max < ary[k] then max = ary[k] end end -- 計数の配列を初期化 ct = {} for m = min, max do ct[m] = 0 end -- 計数を行う for k = 1, #ary do m = ary[k]; ct[m] = ct[m] + 1 end -- 計数結果に基づき値を並べる k = 0 for m = min, max do for j = 1, ct[m] do k = k + 1; ary[k] = m end end end ---- 以下はデモ用コード --(公開) demo_bin_sort(整数,...) -- デモ用に以下の処理を行う. -- * 引数(可変個数)の整数からなる配列を作成する. -- * その内容を表示する. -- * 配列を bin_sort() で整列する. -- * 再び内容を表示する. function demo_bin_sort(...) ary = { ... } print_array(ary) bin_sort(ary) print_array(ary) end --(公開) print_array(配列ary) -- 配列 ary の内容を出力する. function print_array(ary) for k = 1, #ary do io.write(""..ary[k].." ") end io.write("\n") end -- メイン demo_bin_sort(3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 9)
実行結果。
3 1 4 1 5 9 2 6 3 5 8 9 1 1 2 3 3 4 5 5 6 8 9 9
さて、例によって、配列変数は「名前参照」の形に書き換えることになるが、その際に「配列変数の引数」というのが問題になる。*2「名前参照」で配列 ary を表現した場合、「ary 自体に相当するオブジェクト（モノ）」は存在しない。従って、配列自体は "ary" という名前（文字列）で指示することになる。
もう一つの問題は「配列の長さ」である。Lua では配列 ary の長さを #ary で得ることができるが、「名前参照」ではそのような機能は備わっていないし、また配列の長さを求める手段も存在しない。*3そこで、ここでは、「ary という名前の『配列』の長さは『ary/*』という名前の変数に入っている」という規則を採用することにする。もちろん ary の要素を書き換えたときに ary/* が自動更新されるわけではないので、必要な時に正しい値を入れておく必要がある。
書き換え後のコードは以下のようになった。
-- 整数型: j, k, l, m, min, max -- 配列型: ct --(公開) bin_sort(配列名) function bin_sort (_1) min = _G[_1.."/1"]; max = min l = _G[_1.."/*"] -- 配列の長さ k = 0 while k < l do k = k + 1 m = _G[_1.."/"..k] if min > m then min = m end if max < m then max = m end end m = min; m = m - 1 while m < max do m = m + 1 _G["ct/"..m] = 0 end k = 0 while k < l do k = k + 1 m = _G[_1.."/"..k] _G["ct/"..m] = _G["ct/"..m] + 1 end k = 0 m = min; m = m - 1 while m < max do m = m + 1 l = _G["ct/"..m] j = 0 while j < l do j = j + 1 k = k + 1; _G[_1.."/"..k] = m end end end ---- 以下はデモ用コード --(公開) demo_bin_sort(整数,...) function demo_bin_sort(...) k = 0 for _, m in pairs({...}) do -- 可変個数引数部分の for-each k = k + 1 _G["ary/"..k] = m end _G["ary/*"] = k -- 長さを設定する print_array("ary") bin_sort("ary") print_array("ary") end -- print_array(配列名) function print_array(_1) l = _G[_1.."/*"] k = 0 while k < l do k = k + 1 io.write("".._G[_1.."/"..k].." ") end io.write("\n") end -- メイン demo_bin_sort(3, 1, 4, 1, 5, 9, 2, 6, 3, 5, 8, 9)
demo_bin_sort() 冒頭の「引数列を配列 ary に読み込む」部分は、「えるたそ」（eltaso4.lua）と同じように @for マクロで実装する予定なので、それに合わせた処理になっている。前述のように、ここで「ary/*」という変数に配列の長さを設定する必要がある。
TeX で「ビンソート」してみた
パッケージ名は tcbinsort、名前空間は tcbs。公開命令は \binsort{<名前>} およびデモ用の \demobinsort{<整数>,...}（コンマ区切りで複数値指定）である。
% tcbinsort.sty
\NeedsTeXFormat{LaTeX2e}
\ProvidesPackage{tcbinsort}
%% 変数定義
%(整数値)
\newcount\tcbs@j
\newcount\tcbs@k
\newcount\tcbs@l
\newcount\tcbs@m
\newcount\tcbs@min
\newcount\tcbs@max
%(配列型)
%\tcbs@ct/*
\def\tcbs@nameedef#1{%
\expandafter\edef\csname#1\endcsname
}
%%(公開) \binsort{配列名}
\newcommand*{\binsort}[1]{%
\tcbs@min=\@nameuse{tcbs@#1/1}\relax \tcbs@max=\tcbs@min
\tcbs@l=\@nameuse{tcbs@#1/*}\relax
\tcbs@k=0
\@whilenum \tcbs@k<\tcbs@l \do{%
\advance\tcbs@k 1
\tcbs@m=\@nameuse{tcbs@#1/\the\tcbs@k}\relax
\ifnum \tcbs@min>\tcbs@m \tcbs@min=\tcbs@m \fi
\ifnum \tcbs@max<\tcbs@m \tcbs@max=\tcbs@m \fi
}%
\tcbs@m=\tcbs@min \advance\tcbs@m -1
\@whilenum \tcbs@m<\tcbs@max \do{%
\advance\tcbs@m 1
\tcbs@nameedef{tcbs@ct/\the\tcbs@m}{0}%
}%
\tcbs@k=0
\@whilenum \tcbs@k<\tcbs@l \do{%
\advance\tcbs@k 1
\tcbs@m=\@nameuse{tcbs@#1/\the\tcbs@k}\relax
\tcbs@j=\@nameuse{tcbs@ct/\the\tcbs@m}\relax \advance\tcbs@j 1
\tcbs@nameedef{tcbs@ct/\the\tcbs@m}{\the\tcbs@j}%
}%
\tcbs@k=0
\tcbs@m=\tcbs@min \advance\tcbs@m -1
\@whilenum \tcbs@m<\tcbs@max \do{%
\advance\tcbs@m 1 \tcbs@j=0
\tcbs@l=\@nameuse{tcbs@ct/\the\tcbs@m}\relax
\@whilenum \tcbs@j<\tcbs@l \do{%
\advance\tcbs@j 1 \advance\tcbs@k 1
\tcbs@nameedef{tcbs@#1/\the\tcbs@k}{\the\tcbs@m}%
}%
}%
}%
%%%% 以下はデモ用コード
%%(公開) \demobinsort{値,...}
\newcommand*{\demobinsort}[1]{%
\tcbs@k=0
% \@for のループ「変数」はマクロ(=文字列変数)であることに注意
\@for\tcbs@x:=#1\do{% \@for\tcbs@m:=... はダメ
\advance\tcbs@k 1
\tcbs@nameedef{tcbs@ary/\the\tcbs@k}{\tcbs@x}%
}%
\tcbs@nameedef{tcbs@ary/*}{\the\tcbs@k}%
% ↑ここまで読込部
\tcbs@print@array{ary}%
\binsort{ary}%
\tcbs@print@array{ary}%
}
%% \tcbs@print@array{配列名}
\def\tcbs@print@array#1{%
\tcbs@l=\@nameuse{tcbs@#1/*}\relax
\tcbs@k=0
\@whilenum \tcbs@k<\tcbs@l \do{%
\advance\tcbs@k 1
\@nameuse{tcbs@#1/\the\tcbs@k}\space
}%
\par
}
\endinputテスト用文書は以下の通り。
\documentclass[a4paper]{article} \usepackage{tcbinsort} \begin{document} \demobinsort{3,1,4,1,5,9,2,6,5,3,5,8,9} \end{document}
