探索
探索
探索（英: search）とは、特定の制約条件を満たす物を見つけ出す行動のことである。
探索アルゴリズム
探索アルゴリズムとは、大まかに言えば、問題を入力として、考えられるいくつもの解を評価した後、解を返すアルゴリズムである。
まず解くべき問題を状態（英: state）と状態変化（行動、英: action）に分ける。 最初に与えられる状態を初期状態（英: initial state）といい、目的とする状態は最終状態（ゴール、英: final state, goal）と呼ばれる。 初期状態から最終状態に至る、状態及び状態変化の並びが解である。 将棋ならば、盤面の駒の配置と指し手の持ち駒が状態であり、交互に駒を動かすことが状態変化に当たる。
問題を解く類として研究されているアルゴリズムの多くは探索アルゴリズムである。ある問題の考えられるあらゆる解の集合を探索空間と呼ぶ。力まかせ探索や素朴な（知識を用いない）探索アルゴリズムは、探索空間を探索する手法としては最も単純で直観的である。一方、知識を用いた探索アルゴリズムはヒューリスティクスを使って探索空間の構造に関する知識を利用し、探索にかかる時間を削減しようとする。
知識を用いない探索
知識を用いない探索（英: uninformed search）アルゴリズムは、その問題の性質を考慮しない手法である。そのため汎用的に実装可能であり、抽象化のおかげで幅広い問題に同じ実装を適用可能である。問題は、探索空間が一般に非常に大きいため、問題が小さいものでもそれなりの時間がかかる点である。処理を高速化するため、知識を用いた探索だけを行う場合がある。
線形探索
線形探索は、配列の先頭から各要素が目的の値と等しいかどうかを順番に調べる。等しいものが見つかった時点でその位置を返し探索を終了する。末尾まで調べて目的の値が存在しなかった場合はそのことを示す特別な値を返す。アルゴリズムの効率は悪いが、線形探索はデータの並び方に関係なく適用することができる。
二分探索
二分探索やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つである。コンピュータで扱うデータは、多くの場合ある項目によって整列され管理されており、そのような場合はより効率的なアルゴリズムを適用することができる。二分探索は、データの大小関係を利用した高速な探索アルゴリズムである。
ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
ラウンドロビンスケジューリングのアルゴリズムをPerlで実装してみた
概要
ラウンドロビン・スケジューリングは、オペレーティングシステムなどにおけるプロセスなどに関するスケジューリング規則のひとつで、単純な部類に分類される一種である。実行可能状態にあるプロセスに、順番にプロセッサを割り当てる。順番に交代する、という意の「ラウンドロビン」が名前の由来である。
原始的なラウンドロビン・スケジューリングは単純で実装が容易であり、優先度をつけたり、他のアルゴリズムと併用しなければ、リソーススタベーションも発生しない。
アルゴリズム
各タスク(またはジョブ)にはタイムスロットあるいは「クォンタム; quantum」が割り当てられる(CPU時間の割り当てであり、例えば100ミリ秒といった長さ)。job1が完了までに250msかかるとき、ラウンドロビンスケジューラは job1 が 100ms 間実行された後で中断し、他のジョブにCPU時間を割り当てる。
他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、job1 にはさらに100msのCPU時間が割り当てられ、ラウンドロビンスケジューラがその実行を中断して別のジョブにCPU時間を割り当てる。再度、他のジョブがそれぞれ同じ時間(100ms)ずつ実行された後、job1 が再度実行され、最後まで実行されることになる。
具体例
use strict; use warnings; use utf8; binmode(STDOUT, ":utf8"); &main; sub main { print "プロセス数を表す整数nとクオンタムを表す整数qを入力してください。\n"; my $input_nq = <STDIN>; chomp($input_nq); my @input_nq_arr = split(/ /, $input_nq); my $p_num = $input_nq_arr[0]; my $quantum = $input_nq_arr[1]; print "文字列name^iと整数time^iを改行区切りで入力してください。入力完了後、endと入力してください。\n"; my @input_times_arr; while (my $input_name_time = <STDIN>) { last if $input_name_time eq "end\n"; chomp($input_name_time); my $input_time = substr($input_name_time, 3); push (@input_times_arr, $input_time); } my $result_times = &queue_algorithm($p_num, $quantum, \@input_times_arr); for (my $i = 0; $i < $p_num * 2; $i = $i + 2) { my @time_name_tmp; push (@time_name_tmp, "p".$result_times->[$i], $result_times->[$i + 1]); my $result_name_time = join(' ', @time_name_tmp); print $result_name_time; } } sub queue_algorithm { my ($p_num, $quantum, $input_times_arr) = @_; $\="\n"; my @input_times_arr = @{$input_times_arr}; my @result_times; my $time = 0; for (my $i = 0; $i < $p_num; $i++) { if ($input_times_arr[0] > 0 ) { my $head_time = shift @input_times_arr; my $sub_time = $head_time - $quantum; push (@input_times_arr, $sub_time); if ($sub_time <= 0) { $time = $time + $head_time; push (@result_times, $i + 1, $time); } else { $time = $time + $quantum; } } else { my $head_time = shift @input_times_arr; push (@input_times_arr, $head_time); } if ($i == 4 && ($#result_times + 1 != $p_num * 2)) { $i = -1; } } return \@result_times; }
マークアップ言語/JavaScript系概要
マークアップ言語
概要
マークアップ言語とは、文字の並びであるテキストに適当な指示を挿入して文字の形や大きさ、段落、見出しなど文章の構造と体裁を指定するためのコンピュータ用言語である。
目印をつける（Markup）というのは、文書の各部分が、どのような役割を持っているのかを示すということである。 例えば、見出し・段落・表・リストなど、文書の中で各部分が果たしている役割が分かるように目印をつける。 こうした見出し・段落・表・リストなどの文書内の各部分を要素（element）と呼ぶ。
HTML
HTML（HyperText Markup Language）は、ウェブページを作成するために開発された言語である。 現在、インターネット上で公開されてるウェブページのほとんどは、HTMLで作成されている。Hypertextでは、ウェブページから別のウェブページにリンクをはったり、 ウェブページ内に画像・動画・音声などのデータファイルをリンクで埋め込むことができる。HTMLには、このハイパーリンク機能で関連する情報同士を結びつけて、情報を整理するという特徴がある。
HTMLで書かれたWebページはHTMLで使用するタグは世界レベルで統一されているので、どのような種類のWebブラウザであっても、文字の強調などの文字装飾や段落など、同じように表示され、Webブラウザによって、表示内容やレイアウトが変わることは基本的にない。
Hypertext
文章や画像、音声など、複数のオブジェクトをリンクさせた文書の表現形式のこと。印刷物のように、文章や画像が単に表示されているだけでなく、文章中の特定のキーワードから、ほかの文章や画像などを即座に表示できる構造になっている。たとえば、目次のページで項目をクリックすると、目的のページに移動する。
ハイパーテキストを作成するための代表的な言語としてHTMLがあり、Webページは、ハイパーテキストの概念をインターネット上で実現している。
JavaScript
概要
JavaScriptとは、動的なWebページを作成する事のできるプログラミング言語である。通常はブラウザー上で実行される。JavaScriptを使うと、ユーザーのアクションに応じたコンテンツの表示の他、ブラウザー上で表示される地図やグラフィックアニメーションなども表示する事ができる。
フレームワーク
フレームワークとは、全体の処理の流れが実装されておりその中の一部の具体的な処理を自分で実装して、はめ込めるようになっているシステムのことである。はめ込めるようになっている箇所はホットスポットと呼ばれたりする。
ライブラリ
ライブラリは、汎用性の高い複数のプログラムを再利用可能な形でひとまとまりにしたものである。 ライブラリと呼ぶ時は、それ単体ではプログラムとして作動させることはできない実行ファイルではない場合がある。 ライブラリは他のプログラムに何らかの機能を提供するコードの集まりと言うことができる。ライブラリは、フレームワークのような全体を動かすためのロジックはなく、部品の集まりであると言える。
代表的なフレームワーク
・AngularJS
AngularJS、または Angular は、Googleと個人や企業のコミュニティによって開発されている、完全にJavaScriptで書かれたオープンソースのフロントエンドWebアプリケーションフレームワークである。
・Vue.js
Vue.jsはGoogleにおいてAngularJSを使用した開発に携わったエヴァン・ヨーによって開発され、2014年2月にリリースされた。Webアプリケーションにおけるユーザーインターフェイスを構築するための、オープンソースのJavaScriptフレームワークである。ヨーは「Angularの本当に好きだった部分を抽出して、余分な概念なしに本当に軽いものを作る」ことをコンセプトとした。
・Ember.js
Ember.jsは、Vue.jsと同じく「MVVM」モデルを採用したフロントエンド フレームワークである。Ember.jsでは、Ruby on RailsやLaravelと同じように サーバーサイドの処理ができる。また、 URL駆動型で、 JavaScript上の変数とコントローラやモデルクラス変数を直接結び付けることも可能である。
代表的なライブラリ
・React.js
Reactは、 Facebookが開発を行っている JavaScriptライブラリである。 Facebookのフィード画面やYahoo!、Airbnb、Atomなど、大手のサービスでも採用されている。
・jQuery
jQueryは、ウェブブラウザ用のJavaScriptコードをより容易に記述できるようにするために設計されたJavaScriptライブラリである。ジョン・レシグが、2006年1月に開催された BarCamp NYC でリリースした。
代表的なサーバサイド用プラットフォーム
・Node.js
Node.js は、2009年にリリースされたオープンソースなサーバー・サイド用のプラットフォームである。リアルタイムな Web アプリ環境を可能とするノンブロッキング I/O や Google Chrome にも搭載されている Google V8 JavaScript エンジンを採用している特徴がある。要はJSでサーバサイドの開発ができるようになるということ。
AltJS
概要
AltJS（代替JavaScript言語）とは、コンパイルすることでJavaScriptが生成されるプログラミング言語である。JavaScriptはとても便利な反面、幾つかの弱点もあり、苦手とする人が多い言語でもあります。そんな弱点をカバーするためにAltJSが考案された。
TypeScript
TypeScriptは2012年に登場した、Microsoft製のAltJSである。フリーかつオープンソースで提供されており、中規模〜大規模な開発を想定した仕様を持つ。クラスを使うことが可能である点、静的型付け言語である点が通常のJSと異なる点である。JavaScirptとの互換性を保ち、既存のコードを資産として生かすことにも対応しつつ、静的型付けを導入することで、より堅牢なアプリケーションの開発の実現が可能となった。
CoffeeScript
CoffeeScriptは、動的型付け言語である。TypeScriptに比べると、少ないコード量で快適なコーディングを行うことにより主眼を置いたAltJSであると言える。RubyのほかPythonなどに影響を受けたすっきりとした文法を持ち、素のJavaScriptに比べると、coffeescriptはコード量が少なく済む傾向にある。またコンパイルによって生成されるJavaScriptのコードの綺麗さも長所である。
sudoの設定ファイルsudoersについて
概要
Linuxでは例えばユーザーの追加や削除やプロセスの管理など、管理者以外が操作するとシステム運用にリスクを伴う。そのため、Linuxシステムにとって重要なコマンドは、rootのような管理者だけが実行できるようにするのが一般的だ。一般ユーザでrootユーザしかできないような各種作業を使いたいときはsudoを使う。
sudoersとはsudoに関する設定の定義ファイルである。suコマンドでユーザ切り替えを実施せずsudoコマンドを使用する環境を構築すれば、危険な操作のみ確認を求めたり、初級エンジニアに一部権限のみを譲渡したりする事ができる。
sudoersの編集
sudoに関する設定は/etc/sudoersに記録される。この設定ファイルは直接編集する事は非推奨とされており、設定ファイルを編集する時はvisudoというコマンドを使用する事が推奨されている。
# 推奨されない $ sudo vi /etc/sudoers # 推奨される $ sudo visudo
sudoersファイルは、2 つのタイプのエントリから構成される。 (基本的には変数である) エイリアスと (誰が何を実行できるかを指定する) ユーザ 指定である。 sudoers の文法は、 Extended Backus-Naur Form (EBNF) (拡張バッカス・ナウア記法) を用いて記述する。
alias
Linuxなどでよく利用するシェル（bash）上では，長いコマンド名を短い名前に置き換えたり、常に指定するオプションをあらかじめ設定したりできる。これを実現するのが，エイリアス（alias＝別名）である。
バッカス・ナウア記法
バッカス・ナウア記法（Backus-Naur form）とは、文脈自由文法を定義するのに用いられるメタ言語のことで、一般にBNFやBN記法と略される。現在はこのBNFを拡張したEBNF (拡張バッカス・ナウア記法) が一般的に使われている。EBNFでは正規表現を用いてより簡単に記述でき、プロトコル規定言語であるASN.1や、XMLの構文定義にも利用されている。
ASN.1
Abstract Syntax Notation One（ASN.1）とは、電気通信やコンピュータネットワークでのデータ構造の表現・エンコード・転送・デコードを記述する標準的かつ柔軟な記法である。
バイト列の形式が定義されているため、マシン固有の技法などに依存せず、曖昧さのない記述を可能とする形式規則を提供できる。形式を明確に定義できるため処理の自動化やコードの共用化なども行いやすい。ASN.1で記述されたデータ構造は、プレゼンテーション層においてBERなどにより転送オクテット列に変換されネットワーク上で転送される。
参考
sudoersの設定方法
ジョブ管理システム
ジョブ管理システム
概要
ジョブ管理システムとは、複数のジョブ（プログラム、バッチ処理）の起動や終了を制御したり、ジョブの実行・終了状態の監視・報告などを行うソフトウェアである。「ジョブスケジューラ」、「タスクスケジューラ」とも呼ばれる。
なお、設定した時間にプログラムを起動するような単純なものを「タスクスケジューラ」と呼び、高度なもの（営業日や稼働日などの複数のカレンダーを持ち、複数のコンピュータ間の複雑なジョブ間の先行関係や例外処理を定義できるものなど）を「ジョブスケジューラ」と呼び分ける場合もある。比較的単純なものはオペレーティングシステムに標準装備されている場合も多い。
ジョブのスケジューリング
複数あるジョブそれぞれの起動契機をスケジュールする。たとえば、毎日何時何分にジョブ A を起動するとか、ジョブ B が正常終了したらジョブ C を起動する等とかいったことである。WindowsやUNIXなどのOS標準機能でも簡単な曜日・時刻指定の起動ができるが、ジョブ管理ソフトウェアでは複数のカレンダー、複雑な先行関係、ファイルトリガー、外部トリガーなどが組み合わせられるものが多い。
ジョブの異常の報告
ジョブが実行時あるいは終了時に異常が発生した場合、メールやメッセージ等でオペレータに異常を報告する。
ジョブの実行状態のログを保存
ジョブが出力したメッセージやジョブの終了ステータス等をログに保存する。
crontab
crontabコマンドはUnix系オペレーティングシステム (OS) において、コマンドの定時実行のスケジュール管理を行うために用いられるコマンドである。標準入力からコマンド列を読み取り、crontabと呼ばれるファイルにそれを記録する。この記録を元に定時になると、その命令内容を読み取り、実行が行われる。
一般にcrontabコマンドで編集されたスケジュール内容は、crondデーモンにより実行される。crondはバックグラウンドで稼動し、毎分ごとに実行すべきスケジュールがないか確認し、もし実行すべきジョブがあれば、それを実行する。
デーモン
デーモン (Daemon) は、UNIX, Linux, MacOSXなどUnix系のマルチタスクオペレーティングシステム (OS) において動作するプロセス（プログラム）で、主にバックグラウンドで動作するプロセス。ユーザが直接対話的に制御するプログラムもデーモンとして作ることができる。典型的なデーモンは名前の最後尾に "d" が付く。例えば、syslogd はシステムログを扱うデーモン、sshd は内外のSSH接続要求を受け付けるデーモンである。
Unix系の環境では、常にではないが、デーモンの親プロセスはinitプロセスとなっていることが多い。デーモンは起動処理内でforkで子プロセスを作成し、親プロセスの方が即座に終了するため、init が里親となる。さらにデーモンまたはOSは制御端末 (tty) からの切り離しなどの処理も行う必要がある。こういったデーモンを生成するための手続きをUnix系では daemonなどの便利なルーチンにまとめて実装していることが多い。
システムは、ブート処理の延長上でデーモンを多く起動する。ネットワークからの要求を処理するもの、ハードウェアの何らかの活動を処理するものなどがある。他にも、一部のLinuxシステムの udevd のようにハードウェアの設定を行うもの、cronのようにスケジュールされたタスクを実行するものなど、様々な処理を担っている。cronはデーモンプロセスの1種である。
init
initは、UNIXおよびUnix系システムのプログラムのひとつであり、他の全てのプロセスを起動する役目を持つ。デーモンとして動作し、一般にPID 1 を付与される。ブートローダがカーネルを起動し、カーネルがinitを起動する。代替手段を用意せずにinitを削除すると、次回のリブート時にシステムはカーネルパニックに陥る可能性がある。
init の機能はBSD系とSystem V系では大きく異なるため、ユーザーは自分のシステムがどちらのバージョンを使っているかをマニュアルで調べる必要がある。多くのLinuxディストリビューションで使われていたinitはSystem Vと互換性がある。
ジョブキュー
ジョブキューとはジョブをキューで管理するものである。キューとはFIFO(First In First Out)を実現するデータ構造である。キューに登録されたモノは、キューに登録した順に処理される。ジョブキューにおいては、キューに登録するモノはジョブなので、キューに登録した順にジョブが処理されることになる。
ユーザから重たいジョブを処理するようにリクエストされたときに、ジョブを逐次的に処理せず、ジョブキューに登録することで「ジョブの受付をしました」とユーザにレスポンスを返すことができる。「リクエストを受け付ける=>リクエストを処理する=>レスポンスを返す」という従来の流れから「リクエストを受け付ける=>(とりあえず)レスポンスを返す=>リクエストを処理する」という流れを実現することができる。
ジョブキューでは、キューからジョブを取り出し順次処理を行うワーカーと呼ばれるプロセスが常駐することで、プロセス起動のコストを削減することができる。cronが起動するプロセスがライブラリなどを大量に読み込む必要がある場合、プロセス起動のコストは高い。そのような場合は、cronで都度プロセスを立ち上げるより、ジョブキューの常駐プロセス(ワーカー)を使う方が適切である。
同期処理と非同期処理
非同期処理は、あるタスクが実行をしている際に、他のタスクが別の処理を実行できる方式である。「ある関数が呼び出されたとき、戻り値として本来渡したい結果を返すのではなく、一度関数としては終了し（＝呼び出し元に戻る）、後で『本来渡したかった値』を返せる状態になったときに、呼び出し元にその値を通知する」という処理を実現することができる。
同期処理では、あるタスクが実行している間、他のタスクの処理は中断される方式である。同期処理の場合は、時間がかかるタスクが存在する場合、そのプロセスが完了するまで他のプロセスも完了しません。これにより全体の効率(スループット)が低下する場合がある。
コールバック関数
非同期処理において、「ある特定の処理が終わったら、引数に渡した関数の処理を実行する」といったように処理のフローを制御する必要があるが、その際引数に渡される関数のことを「コールバック関数」という。
参考
ジョブ管理システム - Wikipedia
crontab - Wikipedia
デーモン (ソフトウェア) - Wikipedia
VOYAGE GROUP エンジニアブログ : 重たい処理を華麗にスルーして、アプリケーションの体感速度をぐっと向上させる方法
逆ポーランド記法で与えられた数式の計算結果を出力するアルゴリズムの実装
逆ポーランド記法
逆ポーランド記法（Reverse Polish Notation, RPN）とは、数式の記述方法で、演算子を被演算子の後に記述する表記法である。日本語では、後置記法とも呼ばれたりする。この記法は、演算の優先順位を指定する括弧が不要な点が特徴のひとつである。
たとえば、(1＋5) * (2+3)は、次のように記述する。
1 5 + 2 3 + *
オペランド
オペランドとは、数式を構成する要素のうち、演算の対象となる値や変数、定数などのこと。プログラミングの分野ではこれに加えて、プログラム中の個々の命令・処理の対象となるデータや、データの所在情報などのこともオペランドという。
具体例
■入力
１つの数式が１行に与えられます。連続するシンボル（オペランドあるいは演算子）は１つの空白で区切られて与えられます。
■出力
計算結果を１行に出力してください。
■制約
2 ≤ 式に含まれるオペランドの数 ≤ 100
1 ≤ 式に含まれる演算子の数 ≤ 99
演算子は +、-、* のみを含み、１つのオペランドは106 以下の正の整数
-1 × 109 ≤ 計算途中の値 ≤ 109
use strict; use warnings; use utf8; binmode(STDOUT, ":utf8"); &main; sub main { print "逆ポーランド記法で数式を入力してください。\n"; # reverse polish notation, rpn my $input_rpn = <STDIN>; chomp($input_rpn); my @input_rpn_arr = split(/ /, $input_rpn); my $calc_end_result = &stack_algorithm(@input_rpn_arr); print $calc_end_result; } sub stack_algorithm { my @input_rpn_arr = @_; $\="\n"; my $cnt_rpn_arr = $#input_rpn_arr + 1; my @int_tmp; for (my $i = 0; $i < $cnt_rpn_arr; $i++) { push (@int_tmp, $input_rpn_arr[$i]); if ($input_rpn_arr[$i] eq '+' || $input_rpn_arr[$i] eq '-' || $input_rpn_arr[$i] eq '*') { my $operator = pop (@int_tmp); my $operand_1 = pop (@int_tmp); my $operand_2 = pop (@int_tmp); my $calc_result = &calculate($operator, $operand_2, $operand_1); push (@int_tmp, $calc_result); } } my $calc_end_result = $int_tmp[0]; return $calc_end_result; } sub calculate { my ($operator, $operand_2, $operand_1) = @_; my $calc_result; if ($operator eq '+') { $calc_result = $operand_2 + $operand_1; } if ($operator eq '-') { $calc_result = $operand_2 - $operand_1; } if ($operator eq '*') { $calc_result = $operand_2 * $operand_1; } return $calc_result; }
[hogefuga@data_structure]$ perl stack.pl 逆ポーランド記法で数式を入力してください。 1 2 + 3 [hogefuga@data_structure]$ perl stack.pl 逆ポーランド記法で数式を入力してください。 1 2 + -6 3 * * -54
シェルソートをPerlで実装してみた
シェルソート
シェルソート（Shellsort）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、バブルソートあるいは挿入ソートの一般化と見なすことができる。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。
アルゴリズム
基本的な部分は、挿入ソートと同じである。挿入ソートは「ほとんど整列されたデータに対しては高速」という特長があるものの、「隣り合った要素同士しか交換しない」ため、あまり整列されていないデータに対しては低速であった。そのため、適当な間隔をあけた飛び飛びのデータ列に対してあらかじめソートしておき、挿入ソートを適用すれば高速になると考えられる。この考え方を適用したのがシェルソートである。
１.適当な間隔 h を決める
２.間隔 h をあけて取り出したデータ列に挿入ソートを適用する
３.間隔 h を狭めて、2.を適用する操作を繰り返す
４.h=1 になったら、最後に挿入ソートを適用して終了
適切な間隔
シェルソートでは、間隔 h の決め方が重要になってくる。同じ位置の要素ばかりが選択される状況を避け、数値がよく混ざり合うような間隔 h を設定する。「h^(n+1) = 3h^(n) + 1」という条件で選び出した数列を選択すると高速化できる。
具体例
■入力
1 行目に整数 n が与えられます。続く n 行目に n 個の整数 Ai(i=0,1,...,n−1) が与えられます。
■出力
3 行目に、sub insertion_sort を用いた場合のプログラムが終了した直後の cnt の値を出力してください。
続く n 行に整列した Ai(i=0,1,...,n−1) を出力してください。
■制約
1 ≤ n ≤ 1,000,000
0 ≤ Ai ≤ 109
■入力例
5 5 1 4 3 2
■出力例
2 4 1 3 1 2 3 4 5
use strict; use warnings; use utf8; binmode(STDOUT, ":utf8"); use Time::HiRes qw( usleep gettimeofday tv_interval ); &main; sub main { print "数列の長さを表す整数を入力してください。\n"; my $input_num_length = <STDIN>; print "整数を改行区切りで1つずつ入力してください。入力完了後、endと入力してください\n"; my @input_lines_arr; while (my $input_int = <STDIN>) { last if $input_int eq "end\n"; chomp($input_int); push(@input_lines_arr, $input_int); } my ($m, $output_g, $cnt, $input_lines_arr) = &shell_sort($input_num_length, @input_lines_arr); print $m; foreach (@{$output_g}) { print $_; } print $cnt; foreach (@{$input_lines_arr}) { print $_; } } sub shell_sort { my ($input_num_length, @input_lines_arr) = @_; $\="\n"; my $cnt = 0; my $m = 2; my @g = (4, 1); my $input_lines_arr; for (my $i = 0; $i < $m; $i++) { ($cnt, $input_lines_arr) = &insertion_sort($input_num_length, \@input_lines_arr, $g[$i], $cnt); @input_lines_arr = @{$input_lines_arr}; } my @output_g = join(' ', @g); return ($m, \@output_g, $cnt, $input_lines_arr); } sub insertion_sort { my ($input_num_length, $input_lines_arr, $g, $cnt) = @_; my @input_lines_arr = @{$input_lines_arr}; for (my $i = $g; $i < $input_num_length; $i++) { my $v = $input_lines_arr[$i]; my $j = $i - $g; while ($j >= 0 && $input_lines_arr[$j] > $v) { $input_lines_arr[$j + $g] = $input_lines_arr[$j]; $j = $j - $g; $cnt++; } $input_lines_arr[$j + $g] = $v; } return ($cnt, \@input_lines_arr); }
[hogefuga@localhost:sort_algorithm]$ perl shell_sort.pl 数列の長さを表す整数を入力してください。 5 整数を改行区切りで1つずつ入力してください。入力完了後、endと入力してください。 5 1 4 3 2 end 2 4 1 3 1 2 3 4 5
