どうも、みーくんです。
本日は2月22日ということで、私の中では「猫の日」か「にこにーの日」で壮大な陣営争いが繰り広げられています。まぁ、自分を可愛いと錯覚している女性の、猫耳をつけ自撮りした写真がTwitterのTLに回ってくることはなかったので、それだけでも良しとします。
さて、今日は日常生活を裏で支えるアルゴリズム第2弾として、レジシステムのアルゴリズムについてご紹介します。
アルゴリズムを解剖
皆さん、日頃お買い物でスーパーやコンビニ等を利用していると思います。その際、店員がレジにて商品のバーコードを読み込み、レジ画面に対象商品が反映されますよね。そこで例えば、「対象商品3個お買い上げで100円引き！」のようなお買い得セールが開催されていたとします。お客さんが対象商品を3つ以上買った場合には、当然レジ側でも値引き処理が行われます。その処理がどのようなアルゴリズムで動いているか興味が湧いてこないでしょうか。今回はそんなレジシステムについてアルゴリズムを解剖していきたいと思います。
【検索処理】
まずは上の図を見てください。
商品をスキャンすると「購入」の表に商品が上から順に並びます。Kは購入行数を表しています。ここで、ptrはポインタのことで、参照している行の商品番号より1段階大きい商品番号がある添字を指しています。例えば上の図の場合、最も小さい商品番号は111番のA社牛乳1000mlですが、ポインタは1を指しており、添字1を持つ商品番号は222番です。
「対象」の表ですが、こちらは特売商品対象の商品番号が格納されています。今回は222番と224番が該当するので、その数を「対象」のAmountに格納します。Tは対象行数を表しています。
「特売」のレコードは商品番号とは別の固有番号が割り当てられています。上の図の場合はお買い上げ3本ごとなので、指定数量には3が入っています。また、100円引きなのでUnitPriceに-100が格納されています。
「購入」にある対象商品の数を「対象」に格納するためには、商品番号が一致している商品はあるか精査しなくてはなりません。これが検索処理です。
【計算処理】
ここでは、値引き対象商品の合計数を求め、指定数量で割った値を「特売」レコードのAmountに格納します。
【更新処理】
ここでは「特売」レコードを「購入」表に格納します。格納する際は、当然ポインタの部分を変更しなくてはなりません。商品番号が最も小さな商品からポインタ検索していきます。そして、「特売」レコードの商品番号よりも大きな商品番号を見つけたら、その前の商品番号の商品との間に格納します。
【値引き金額反映処理】
ここでは、特売レコードのAmountが1以上であるとき、「特売」レコードのUnitPriceとAmountを掛け合わせた金額を「購入」表のTotalCostに格納します。
【特売レコードの削除処理】
ここでは、「特売」レコードが「購入」表に存在しているものの、1本か2本のみの購入となってしまい指定数量に届かずAmountが0になったとき、削除を行う処理です。「特売」レコードを削除する際は、当然ポインタの部分を変更しなくてはなりません。
このようなアルゴリズムを応用し、レジシステムは稼働しています。
疑似言語で表現
では、このアルゴリズムを疑似言語で表現するとどうなるのでしょうか。実際に基本情報技術者試験で出題された疑似言語を以下掲載します。(一部、改変してあります。)
人間では暗算で値引き結果を算出できるかもしれませんが、コンピュータはそこまで賢くないので、繰り返し処理や分岐処理を用いて疑似言語で表現し、反映させてあげる必要があります。しかし、一度これをプログラム言語で実装すれば、店員は商品のバーコードをスキャンするだけで済み、その都度計算する手間が省けるのです。