2012/12/01 〜 2012/12/25TeX & LaTeX Advent Calendar
こちらは(ry
* * *
例の「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}