Bashを使うなら理解しておきたいアルゴリズム - 抽出・ソート・結合・集計

Bash

Bashでのアルゴリズムの書き方の覚書です。

目次

説明に使用するデータ構造

アルゴリズムの説明のために、以下のようなパイプ区切り文字列の配列を使います。

COUNTRIES=("${COUNTRIES[@]}" "日本|JPY|127156000")
COUNTRIES=("${COUNTRIES[@]}" "フランス|EUR|65073482")
COUNTRIES=("${COUNTRIES[@]}" "スペイン|EUR|44904000")
COUNTRIES=("${COUNTRIES[@]}" "ロシア|RUB|141903979")
COUNTRIES=("${COUNTRIES[@]}" "ベトナム|VND|84238000")
COUNTRIES=("${COUNTRIES[@]}" "カンボジア|KHR|14805000")
COUNTRIES=("${COUNTRIES[@]}" "コートジボワール|XOF|44904000")

この文字列の配列は、以下のようなコードでHTMLテーブルとして出力できます。

# テーブルヘッダを出力する。
echo "<table border='1'>"
echo "<tr>"
echo "<th>国名</th>"
echo "<th>通貨</th>"
echo "<th>人口</th>"
echo "</tr>"

# 配列中の文字列毎に以下を繰り返す。
for (( I=0; I < ${#COUNTRIES[@]}; ++I ))
do
	COUNTRY=${COUNTRIES[$I]}
	NAME=`echo $COUNTRY | awk -F'|' '{print $1}'`
	CURRENCY=`echo $COUNTRY | awk -F'|' '{print $2}'`
	POPULATION=`echo $COUNTRY | awk -F'|' '{print $3}'`
	
	echo "<tr>"
	echo "<td>$NAME</td>"
	echo "<td>$CURRENCY</td>"
	echo "<td>$POPULATION</td>"
	echo "</tr>"
done
echo "</table>"

このコードの実行結果は以下の通りです。

国名 通貨 人口
日本 JPY 127156000
フランス EUR 65073482
スペイン EUR 44904000
ロシア RUB 141903979
ベトナム VND 84238000
カンボジア KHR 14805000
コートジボワール XOF 44904000

■抽出

複数のデータの中から、特定の条件を満たすデータを抽出するアルゴリズムです。

例として、商品データPRODUCTSから特定の条件を満たすデータを抽出します。

PRODUCTS=("${PRODUCTS[@]}" "1010|えんぴつ|80")
PRODUCTS=("${PRODUCTS[@]}" "1020|ボールペン|100")
PRODUCTS=("${PRODUCTS[@]}" "1030|消しゴム|100")
PRODUCTS=("${PRODUCTS[@]}" "2010|定規|140")
PRODUCTS=("${PRODUCTS[@]}" "2020|コンパス|300")
PRODUCTS=("${PRODUCTS[@]}" "3010|のり|200")

商品データPRODUCTSをHTMLテーブルとして出力すると、以下のようになります。

商品ID 商品名 価格
1010 えんぴつ 80
1020 ボールペン 100
1030 消しゴム 100
2010 定規 140
2020 コンパス 300
3010 のり 200


以下のコードは、商品データPRODUCTSから「価格 > 100」を満たすデータを抽出します。

# すべての商品データについて繰り返す。
for (( I=0; I < ${#PRODUCTS[@]}; ++I ))
do
	PRODUCT=${PRODUCTS[$I]}
        PRICE=`echo $PRODUCT | awk -F'|' '{print $3}'`

	# 商品データの価格が100より大きいことを確認する。
        if [ $PRICE -gt 100 ]; then
		# 商品データを抽出結果に追加する。
                RESULTS=("${RESULTS[@]}" "$PRODUCT")
        fi
done

抽出結果は、配列RESULTSに格納されます。抽出結果RESULTSをHTMLテーブルとして出力すると、以下のようになります。

商品ID 商品名 価格
2010 定規 140
2020 コンパス 300
3010 のり 200

■ソート

複数のデータを、特定の条件でソートするアルゴリズムです。

Bashでの配列のソート

ソートの例の前に、Bashでの配列のソートについて説明します。
配列をソートするには、一旦配列の内容をファイルに書き込み、ファイルをsortコマンドでソートします。その後、ファイルの内容を読み込み、再度配列に格納します。

#!/bin/bash

ARRAY=("${ARRAY[@]}" 13)
ARRAY=("${ARRAY[@]}" 43)
ARRAY=("${ARRAY[@]}" 22)
ARRAY=("${ARRAY[@]}" 234)

# 配列の内容をファイル/tmp/sort.inに書き込み
cat /dev/null > /tmp/sort.in
for (( I=0; I < ${#ARRAY[@]}; ++I ))
do
	A=${ARRAY[$I]}
        echo $A >> /tmp/sort.in
done

# ファイル/tmp/sort.inを数値の降順ソートし、ソート結果をファイル/tmp/sort.outに出力
sort -n -r /tmp/sort.in > /tmp/sort.out

# ファイル/tmp/sort.outの内容を読み込み、配列に格納
while read LINE
do
        RESULTS=("${RESULTS[@]}" $LINE)
done < /tmp/sort.out

ソートの並び順は、sortコマンドのオプションで決めます。例えば、以下のオプションが役立ちます。

オプション 説明
-t区切り文字 ファイルを列に区切るための区切り文字を指定します。
-kキー列の番号 ソートのキーに使用する列の番号を指定します。
-d キーの五十音順に並べ替えます。
-n キーの数値順に並べ替えます。
-r キーの降順に並べ替えます。

なお、上記のコードは配列の要素を「数値の降順」にソートします。

ソートの例(五十音順)

それでは、ソートの例を挙げます。
例として、売上データSALESを特定の項目の「五十音順」にソートします。

SALES=("${SALES[@]}" "20090702|00001|1020|10")
SALES=("${SALES[@]}" "20090702|00002|1010|5")
SALES=("${SALES[@]}" "20090702|00003|3010|20")
SALES=("${SALES[@]}" "20090703|00001|1030|10")
SALES=("${SALES[@]}" "20090703|00002|1020|15")
SALES=("${SALES[@]}" "20090704|00001|2020|30")
SALES=("${SALES[@]}" "20090704|00002|3010|20")

売上データSALESをHTMLテーブルとして出力すると、以下のようになります。

売上日 売上番号 商品ID 数量
20090702 00001 1020 10
20090702 00002 1010 5
20090702 00003 3010 20
20090703 00001 1030 10
20090703 00002 1020 15
20090704 00001 2020 30
20090704 00002 3010 20


以下のコードは、売上データSALESを「五十音順で売上番号の昇順」にソートします。

# 売上データSALESをファイル/tmp/sort.inに書き込み
cat /dev/null > /tmp/sort.in
for (( I=0; I < ${#SALES[@]}; ++I ))
do
	SALE=${SALES[$I]}
        echo $SALE >> /tmp/sort.in
done

# ファイル/tmp/sort.in中の売上データを五十音順で売上番号の昇順にソートし、ファイル/tmp/sort.outに出力
sort -t'|' -k2 -d  /tmp/sort.in > /tmp/sort.out

# ファイル/tmp/sort.outからソート後の売上データを読み込み、配列RESULTSに格納
while read LINE
do
        RESULTS=("${RESULTS[@]}" "$LINE")
done < /tmp/sort.out

ソート後の売上データRESULTSをHTMLテーブルとして出力すると、以下のようになります。

売上日 売上番号 商品ID 数量
20090702 00001 1020 10
20090703 00001 1030 10
20090704 00001 2020 30
20090702 00002 1010 5
20090703 00002 1020 15
20090704 00002 3010 20
20090702 00003 3010 20

ソートの例(数値順)

例をもう一つ挙げます。商品データPRODUCTSを特定の項目の「数値順」にソートします。

PRODUCTS=("${PRODUCTS[@]}" "2010|定規|140")
PRODUCTS=("${PRODUCTS[@]}" "2020|コンパス|300")
PRODUCTS=("${PRODUCTS[@]}" "3010|のり|200")
PRODUCTS=("${PRODUCTS[@]}" "1030|消しゴム|100")
PRODUCTS=("${PRODUCTS[@]}" "1020|ボールペン|100")
PRODUCTS=("${PRODUCTS[@]}" "1010|えんぴつ|80")

商品データPRODUCTSをHTMLテーブルとして出力すると、以下のようになります。







商品ID 商品名 価格
2010 定規 140
2020 コンパス 300
3010 のり 200
1030 消しゴム 100
1020 ボールペン 100
1010 えんぴつ 80


以下のコードは、商品データPRODUCTSを「数値順で商品IDの降順」にソートします。

# 商品データPRODUCTSをファイル/tmp/sort.inに書き込み
cat /dev/null > /tmp/sort.in
for (( I=0; I < ${#PRODUCTS[@]}; ++I ))
do
	PRODUCT=${PRODUCTS[$I]}
        echo $PRODUCT >> /tmp/sort.in
done

# ファイル/tmp/sort.in中の商品データを数値順で商品IDの昇順にソートし、ファイル/tmp/sort.outに出力
sort -t'|' -k1 -n -r /tmp/sort.in > /tmp/sort.out

# ファイル/tmp/sort.outからソート後の商品データを読み込み、配列RESULTSに格納
while read LINE
do
        RESULTS=("${RESULTS[@]}" "$LINE")
done < /tmp/sort.out

ソート後の商品データRESULTSをHTMLテーブルとして出力すると、以下のようになります。







商品ID 商品名 価格
3010 のり 200
2020 コンパス 300
2010 定規 140
1030 消しゴム 100
1020 ボールペン 100
1010 えんぴつ 80

■結合

２種類のデータを、特定の条件で結合するアルゴリズムです。

例として、商品データPRODUCTSと売上データSALESを結合します。

PRODUCTS=("${PRODUCTS[@]}" "1010|えんぴつ|80")
PRODUCTS=("${PRODUCTS[@]}" "1020|ボールペン|100")
PRODUCTS=("${PRODUCTS[@]}" "1030|消しゴム|100")
PRODUCTS=("${PRODUCTS[@]}" "2010|定規|140")
PRODUCTS=("${PRODUCTS[@]}" "2020|コンパス|300")
PRODUCTS=("${PRODUCTS[@]}" "3010|のり|200")

SALES=("${SALES[@]}" "20090702|00001|1020|10")
SALES=("${SALES[@]}" "20090702|00002|1010|5")
SALES=("${SALES[@]}" "20090702|00003|3010|20")
SALES=("${SALES[@]}" "20090703|00001|1030|10")
SALES=("${SALES[@]}" "20090703|00002|1020|15")
SALES=("${SALES[@]}" "20090704|00001|2020|30")
SALES=("${SALES[@]}" "20090704|00002|3010|20")

商品データPRODUCTSをHTMLテーブルとして出力すると以下のようになります。

商品ID 商品名 価格
1010 えんぴつ 80
1020 ボールペン 100
1030 消しゴム 100
2010 定規 140
2020 コンパス 300
3010 のり 200
また、売上データSALESをHTMLテーブルとして出力すると以下のようになります。
売上日 売上番号 商品ID 数量
20090702 00001 1020 10
20090702 00002 1010 5
20090702 00003 3010 20
20090703 00001 1030 10
20090703 00002 1020 15
20090704 00001 2020 30
20090704 00002 3010 20


以下のコードは、商品データと売上データを商品IDをキーとして結合します。

# すべての売上データについて繰り返す。
for (( I=0; I < ${#SALES[@]}; ++I ))
do
	SALE=${SALES[$I]}
        S_SALES_DATE=`echo $SALE | awk -F'|' '{print $1}'`
        S_SALES_NO=`echo $SALE | awk -F'|' '{print $2}'`
        S_PRODUCT_ID=`echo $SALE | awk -F'|' '{print $3}'`
        S_AMOUNT=`echo $SALE | awk -F'|' '{print $4}'`

	# すべての商品データについて繰り返す。
	for (( J=0; J < ${#PRODUCTS[@]}; ++J ))
        do
		PRODUCT=${PRODUCTS[$J]}
                P_PRODUCT_ID=`echo $PRODUCT | awk -F'|' '{print $1}'`
                P_PRODUCT_NAME=`echo $PRODUCT | awk -F'|' '{print $2}'`
                P_PRICE=`echo $PRODUCT | awk -F'|' '{print $3}'`

		# 売上データと商品データの商品IDが一致することを確認する。
                if [ $S_PRODUCT_ID = $P_PRODUCT_ID ]; then

			# 商品データと売上データの項目を結合した結果を配列RESULTSに格納する。
			RESULT="$S_SALES_DATE|$S_SALES_NO|$S_PRODUCT_ID|$P_PRODUCT_NAME|$S_AMOUNT|$P_PRICE"
                        RESULTS=("${RESULTS[@]}" "$RESULT")
                fi
        done
done

結合結果RESULTSをHTMLテーブルとして出力すると、以下のようになります。

売上日 売上番号 商品ID 商品名 数量 価格
20090702 00001 1020 ボールペン 10 100
20090702 00002 1010 えんぴつ 5 80
20090702 00003 3010 のり 20 200
20090703 00001 1030 消しゴム 10 100
20090703 00002 1020 ボールペン 15 100
20090704 00001 2020 コンパス 30 300
20090704 00002 3010 のり 20 200

■集計

複数のデータを特定の条件で集計するアルゴリズムです。

例として、売上データSALESを集計します。

SALES=("${SALES[@]}" "20090702|00001|ボールペン|100|10")
SALES=("${SALES[@]}" "20090702|00002|えんぴつ|80|5")
SALES=("${SALES[@]}" "20090702|00003|のり|200|20")
SALES=("${SALES[@]}" "20090703|00001|消しゴム|100|10")
SALES=("${SALES[@]}" "20090703|00002|ボールペン|100|15")
SALES=("${SALES[@]}" "20090704|00001|コンパス|300|30")
SALES=("${SALES[@]}" "20090704|00002|のり|200|20")

売上データSALESをHTMLテーブルとして出力すると以下のようになります。

売上日 商品ID 商品名 価格 数量
20090702 00001 ボールペン 100 10
20090702 00002 えんぴつ 80 5
20090702 00003 のり 200 20
20090703 00001 消しゴム 100 10
20090703 00002 ボールペン 100 15
20090704 00001 コンパス 300 30
20090704 00002 のり 200 20


以下のコードは、売上データSALESを集計して売上日毎の合計数量と合計売上高を求めます。

#######################################################
## 集計結果の初期化
#######################################################

# すべての売上データについて繰り返す。
for (( I=0; I < ${#SALES[@]}; ++I ))
do
	# 売上データの売上日を取得する。
	SALE=${SALES[$I]}
        S_SALES_DATE=`echo $SALE | awk -F'|' '{print $1}'`

	# 集計結果の配列RESULTSに売上日S_SALES_DATEが含まれていないことを確認する。
        FOUND=0
	for (( J=0; J < ${#RESULTS[@]}; ++J ))
        do
		RESULT=${RESULTS[$J]}
                R_SALES_DATE=`echo $RESULT | awk -F'|' '{print $1}'`

                if [ $S_SALES_DATE = $R_SALES_DATE ]; then
                        FOUND=1
			break
                fi
        done

        if [ $FOUND = 0 ]; then
		# 集計結果の配列RESULTSに売上日S_SALES_DATEが含まれていない:

		# 集計結果の初期値を生成する。
		RESULT="$S_SALES_DATE|0|0"
		# 生成した初期値を集計結果の配列RESULTSに格納する。
                RESULTS=("${RESULTS[@]}" "$RESULT")
        fi
done

#######################################################
## 売上データを集計
#######################################################

# すべての売上データについて繰り返す。
for (( I=0; I < ${#SALES[@]}; ++I ))
do
	SALE=${SALES[$I]}
        S_SALES_DATE=`echo $SALE | awk -F'|' '{print $1}'`
        S_PRICE=`echo $SALE | awk -F'|' '{print $4}'`
        S_AMOUNT=`echo $SALE | awk -F'|' '{print $5}'`

	# すべての集計結果について繰り返す。
	for (( J=0; J < ${#RESULTS[@]}; ++J ))
        do
                RESULT=${RESULTS[$J]}
                R_SALES_DATE=`echo $RESULT | awk -F'|' '{print $1}'`
                R_AMOUNT=`echo $RESULT | awk -F'|' '{print $2}'`
                R_TOTAL=`echo $RESULT | awk -F'|' '{print $3}'`

		# 売上日付が一致する集計結果に対し、売上データを計上する。
                if [ $S_SALES_DATE = $R_SALES_DATE ]; then
			# 売上データの数量を集計結果に足し合わせる。
                        R_AMOUNT=$(( $R_AMOUNT + $S_AMOUNT ))
			# 売上データの価格と数量を掛けた値を集計結果に足し合わせる。
                        R_TOTAL=$(( $R_TOTAL + $S_PRICE * $S_AMOUNT ))

                        RESULTS[$J]="$R_SALES_DATE|$R_AMOUNT|$R_TOTAL"
			break
                fi
        done
done

集計結果は配列RESULTSに格納されます。集計結果RESULTSをHTMLテーブルとして出力すると以下のようになります。

売上日 合計数量 合計売上高
20090702 35 5400
20090703 25 2500
20090704 50 13000

関連記事

データ構造

アルゴリズム