キューのシェルスクリプトによる実装 (キューの状態遷移の履歴をファイルとして保存)
[動機]
・シェルスクリプトのコーディング能力向上。
・キューを手続き型言語 (C 言語等) で実装したことはあるが、
ファイルの入出力ベースで状態遷移の履歴込みで
実装することによるノウハウを貯めたかった。 (※)
※ あくまでも内発的な動機付けで、特にこういうノウハウの
必要性が世間にあるわけではない。
速く省メモリで動く実装を目指しているわけではなく、
時間計算量や空間計算量の議論等もここではとりあえずおいておく。
[予備知識]
・キューがどのようなものかわかっていること。
・シェルスクリプトがある程度書けること。
[主な考え方]
・キューを様々なキューの状態を表すファイルを複数もつディレクトリとみなす。
・キューの状態を一意で表すために、ミリ秒単位でファイル名を付ける。
[キューの状態の例]
1
2
3
先頭行から要素を挿入し、最終行から要素を取り出し標準出力する。
[スクリプト: 4 種類]
キュー自体の作成: ディレクトリと空ファイルの生成
(キュー自体を削除する場合は rm -f によるディレクトリ削除をする。)
$ cat create.sh
DATE=`date +"%Y%m%d%H%M%S%3N"`
mkdir queue_${DATE}
touch queue_${DATE}/queue_${DATE}
キューにおける要素の存在性チェック:
$ cat empty.sh
QUEUE_NAME=$1
QUEUE_NEWEST=`ls -1 ${1}/* | tail -n 1`
cat ${QUEUE_NEWEST} | wc -l
キューへの挿入: 第 1 引数にキューの名前を、第 2 引数に挿入する要素を指定する。
$ cat enqueue.sh
QUEUE_NAME=$1
DATE=`date +"%Y%m%d%H%M%S%3N"`
QUEUE_NEWEST=`ls -1 ${1}/* | tail -n 1`
cp ${QUEUE_NEWEST} ${1}/queue_${DATE}
if [ `sh empty.sh ${QUEUE_NAME}` -gt 0 ] ; then
sed -i "1s/^/${2}\\n/" `ls -1 ${1}/* | tail -n 1`
else
echo ${2} >> `ls -1 ${1}/* | tail -n 1`
fi
キューからの取り出し (標準出力した上で最後の行を削除) :
第1 引数にキューの名前を指定する。
$ cat dequeue.sh
QUEUE_NAME=$1
DATE=`date +"%Y%m%d%H%M%S%3N"`
QUEUE_NEWEST=`ls -1 ${1}/* | tail -n 1`
cp ${QUEUE_NEWEST} ${1}/queue_${DATE}
if [ `sh empty.sh ${QUEUE_NAME}` -gt 0 ] ; then
cat ${QUEUE_NEWEST} | tail -n 1
sed '$d' ${QUEUE_NEWEST} > ${1}/queue_${DATE}
else
echo -n > ${1}/queue_${DATE}
fi
[使い方]
キュー自体の作成
$ sh create.sh
キューへの挿入
$ sh enqueue.sh queue_20170818151740370 1
$ sh enqueue.sh queue_20170818151740370 2
$ sh enqueue.sh queue_20170818151740370 3
キューからの要素の取り出し
$ sh dequeue.sh queue_20170818151740370
1
$ sh dequeue.sh queue_20170818151740370
2
$ sh dequeue.sh queue_20170818151740370
3
$ sh dequeue.sh queue_20170818151740370
$