Title : Algorithm::Networksort
|
Location : Home > Languages > Perl > Package Title : Algorithm::Networksort |
|
Algorithm::Networksort - ソートのためのインライン比較
use Algorithm::Networksort qw(:all); my $inputs = 4; # # ネットワークを生成（比較子のリスト） # my @network = nw_comparators($inputs); # # リストを出力。リストのグラフを出力 # print nw_format(\@network, $inputs), "\n"; print nw_graph(\@network, $inputs), "\n";
Perl 5.6 以降。これは本モジュール開発時のバージョン。
優先度の比較の結果に基づかない比較の列であるソーティングネットワークを生成する。
配列と順序を入れ替えないので、ハードウェアに組み込む、ソフトウェアで並列処理をする際に非常に有用である。残念なことに、比較の配置がソートされるべき要素の数で固定されているためネットワークはクイックソートのような一般的な実行時ソートのために使うことができない。
本モジュールの主要な目的は、ユーザが自分のソースコードに組み込む比較・交換マクロ（関数・テンプレート）を生成することである。EPS や SVG 、アスキーアートでのネットワーク図生成にも利用できる。
デフォルトでは何もエクスポートしない。ソーティングネットワークの生成及び利用のために関数をエクスポートするにはタグ ':all' のみが利用可能である。関数には nw_comparator(), nw_format(), nw_graph(), nw_group(), nw_sort() がある。
nw_comparator()
@network = nw_comparator($inputs); @network1 = nw_comparator($inputs, algorithm => $alg);
$inputs 項目をソートする比較子のリストを返す。リストを生成するアルゴリズムを選択することができるが、デフォルトでは Bose-Nelson アルゴリズムとなる。一般に異なるメソッドを使えば異なるネットワークを生成し、場合によっては比較子の順序も数も異なることがある。
選択可能なアルゴリズムは以下の通り。
nw_format()
$string = nw_format(\@network, $format1, $format2, \@index_base);
比較子のリストを表すフォーマットされた文字列を返す。比較と変換の比率を分離する２つの sprintf スタイルのフォーマットがある。２つめのフォーマット文字列はオプションである。
１つめのフォーマット文字列はデフォルトのフォーマットである Perl で表現される配列の配列の場合は無視される。ネットワークソート対はゼロベースである。0, 1, 2, ... 以外で列を書き出したい場合には配列参照で提供すればよい。
print nw_format(\@network);
print nw_format(\@network,
undef,
undef,
[1..$inputs]);
print nw_format(\@network, "SWAP(%d, %d);\n");
print nw_format(\@network,
"SWAP(%d, %d);\n",
undef,
[1..$inputs]);
print nw_format(\@network,
"if (v[%d] < v[%d]) then\n",
" exchange(v, %d, %d)\nend if\n");
my @alphabase = ('a'..'z')[0..$inputs];
my $string = '[' .
nw_format(\@network,
"[%s,%s],", # 文字列フラグを使用
undef,
\@alphabase);
substr($string, -1, 1) = ']'; # コンマを上書き
print $string;
nw_graph()
ネットワークにおいて比較子をグラフ化する文字列を返す。フォーマットはEPS (graph=>'eps')・SVG (graph=>'svg') またはデフォルトのテキスト (graph=>'text' または指定なし）である。'text' 及び'eps' オプションは内蔵して出力するが、'svg' オプションの場合、表示させるために XML とコードと連携して <svg> と E</svg> タグの間に書かれる必要がある。
my $inputs = 4; my @network = nw_comparators($inputs); $netgraph = nw_graph(\@network, $inputs, graph=>'svg'); print "\n", "\n", $netgraph;
'graph' オプションは単独では用いられない。以下の指定によって調整される。
namespace
デフォルト値：undef
同一のタグに対する異なる XML ボキャブラリとの間で区別するためのタグプレフィクス。指定されなければタグは使われない。
hz_margin
デフォルト値：18
グラフィックの端とネットワークの間の水平の空白。
hz_sep
デフォルト値：12
水平線を分割する空白（入力行）
indent
デフォルト値：9
入力行の開始場所と最初の比較子の場所の間のインデント。同じ値だけ最後の比較子と入力行の最後との間を空ける。
stroke_width
デフォルト値：2
比較子を定義するために用いた線と入力行の幅。終点円の半径でもある。
title
デフォルト値："N = $inputs Sorting Network."
グラフのタイトル。短い１行の記述であること。
vt_margin
デフォルト値：21
グラフィックの端とネットワークの間の垂直の空白。
vt_sep
デフォルト値：12
垂直線を分離する空白。（比較子）
inputbegin
デフォルト値："o-"
入力行の開始文字。
inputline
デフォルト値："---"
入力行を示す文字。
inputcompline
デフォルト値："-|-"
比較子が交差する入力行を示す文字。
inputend
デフォルト値："-o\n"
入力行の終端を示す文字。
fromcomp
デフォルト値："-^-"
比較子の開始点と入力行を示す文字。
tocomp
デフォルト値："-v-"
比較子の終点と入力行を示す文字。
gapbegin
デフォルト値：" "（空白２つ）
入力行の間のギャップを開始する文字。
gapcompline
デフォルト値：" | " （空白＋｜＋空白）
渡す比較子とのギャップを生成する文字。
gapnone
デフォルト値：" "（空白３つ）
入力行の間の空白を生成する。
gapend
デフォルト値：" \n"（空白２つ＋改行）
入力文字の間のギャップを終了させる文字。
nw_group()
この関数は nw_graph() により呼び出される。関数は比較子のリストを取り、比較子のグループを表すサブリストのリストを一列に出力して返す。
オプションが１つあり（ 'grouping' ）、比較子の平行演算子を示すグルーピングを生成する。
これを使う機会はあまりないだろうが、以下のように使えばよい。
my $inputs = 8;
my @network = nw_comparators($inputs);
my @grouped_network = nw_group(\@network, $inputs, grouping=>'parallel');
print "There are ", scalar @network,
" comparators in this network, grouped into\n",
scalar @grouped_network, " parallel operations.\n\n";
foreach my $group (@grouped_network)
{
print nw_format($group), "\n";
}
@grouped_network = nw_group(\@network, $inputs);
print "\nThis will be graphed in ", scalar @grouped_network,
" columns.\n";
この出力は以下のようになる。
There are 19 comparators in this network, grouped into 6 parallel operations. [[0,4],[1,5],[2,6],[3,7]] [[0,2],[1,3],[4,6],[5,7]] [[2,4],[3,5],[0,1],[6,7]] [[2,3],[4,5]] [[1,4],[3,6]] [[1,2],[3,4],[5,6]]
１１列のグラフとなる。
nw_sort()
ネットワークを用いて配列をソートする。これはテストのためだけに使う。翻訳された言語における配列をソートするために比較子の配列をループにまわすことがソーティングネットワークをもちいても有効でないことを示すときなど。
この関数は比較のために <=> 演算子を使う。
my @digits = (1, 8, 3, 0, 4, 7, 2, 5, 9, 6);
my @network = nw_comparators(scalar @digits, algorithm => 'best');
nw_sort(\@network, \@digits);
print join(", ", @digits);
Batcher's Merge Exchange algorithm
John M. Gamble, <jgamble@ripco.com>
|
|
Updated : 2008/02/19 |