【第20回】RPGの基礎：配列

RPGの基礎：配列

2017年4月 | ジョン・パリス、スーザン・ガントナー

今月は現代のRPGの基礎に関するシリーズを開始しています。長年に渡ってRPGに多くの変更が行われていますが、私達のクラスの学生が、利用できる多くの基本ツールを知らないと気付くことが増えています。ですから、もしあなたにとってこれがすべて “陳腐なこと”なら事前にお許しを願い、配列の処理の話から始めるつもりです。この記事では、配列のロードと検索について検討しています。私達の意図は、最近OSSILeオープンソース・コレクションに追加されたArraylistのようなアドオン・ライブラリーによって提供される、ずっと多様で柔軟な配列機能ではなく、RPGの組み込み機能に注目することです。あなたがこのシリーズを完了するまでに、このようなライブラリーの能力を探求したいと強く思うことを望みます。

長年にわたり、個人用ツールボックスにRPG以外の言語を追加してきたことで、1つのことが非常に明確になりました。私達は、RPGプログラマーとして本来はそうすべきなのに、配列を頻繁には活用していません。たとえば、パフォーマンス面で配列の方が優れているのに、作業ファイルを使用している人々をしばしば見かけます。おそらく、これには多くの歴史的な理由があります。1つは、V6が登場するまで、配列の最大要素数は32,767個に制限されていたことです。もう１つは、SORTAのような配列操作は、配列内のすべての要素が使用されていると仮定していました。これは、配列の先頭に空白やゼロが残らないように、配列をハイバリュー（*HIVAL）で事前設定しなければならないことを意味していました。大事なことを言い忘れていましたが、配列ルックアップの処理は遅かったのです。ちょっと先走りし過ぎてしまいました‐これについては後で説明します。

基本的な配列検索

以下のコード例で、（F）はこれから使用するサンプル配列の初期定義です。これらのテストでは、要素数5,000のサイズを使用しました。（G）は、FillArray（）サブプロシージャの呼び出しです。我々は配列に5000個の項目をロードし、valueArrayの値として最大値10,000を使うことにしました。これにより、私達の簡単なテストでは理論的に約50％の確率で一致するデータが生成されます。使用された方法の詳細については、補足記事“テスト値の生成”を参照してください。

（I）では、%Lookupを使用して配列を検索し、searchForに格納された値を探して検索結果をテストし、適切なカウンタの値を1増やします。

(F) dcl-s  valueArray  Packed(7) Dim(5000);

     // ランダム値で配列を満たす
(G) FillArray( 5000 : 10000 ) ;  

(H) For searchFor = 1 to maxValue;
(I)   location = %LookUp( searchFor: valueArray );
      If location = 0;
        countMissing += 1;
      Else;
        countFound += 1;
      EndIf;
    EndFor;

配列を検索するこのアプローチは、私達が長年にわたって出合ってきた最も一般的なものですが、それは相対的に効率が良くありません。その理由は、このようにコーディングすると、線形検索を実行するために%Lookupが必要だからです。つまり、そのやり方では配列の各項目と検索値を順々に比較します。その結果、n個の要素を持つ配列に対して、比較の回数は平均n / 2になります。私達のケースでは、これは検索引数がその配列内に存在するかどうかを判断するために、平均2,500回の比較を行う必要があることを意味します。

この方法が非効率的であるのなら、なぜそれがいまだに一般的に使われているのでしょう？おそらく多くの理由がありますが、古いLOOKUP命令を使用しているときに、この処理方法がおそらく利用できる唯一の方法だからです。RPGプログラマーはLOOKUP命令の代わりに%Lookupを採用していますが、多くの人は%Lookupが高速検索オプションを提供していることに気付いていません。では、私達はそれをどう活用するのでしょう？

高速検索

高速検索を利用するには、プログラムに2つの基本的な変更が必要です。まず、ASCEND（またはDESCEND）キーワードを配列定義に追加する必要があります。下の（J）でそれを見ることができます。

次に、私達がコンパイラに指示した順序で配列が実際に並んでいることを保証しなければなりません。これを行うために、（K）のように検索ループを始める前にSORTA命令を追加する必要もあります。

以下は変更／追加された行です：

(J)    dcl-s  valueArray  Packed(7) Dim(10000)  Ascend;
(K)    SortA valueArray;  // 値に基づいてソート

このアプローチはどれくらい速いのでしょうか？一言でいえば、“とても速い”です。私達のテストでは、要素数5,000の配列で10,000回検索し、高速検索は基本検索の100倍以上の速さでした。これは大きな違いです。下記の2つのプログラムの結果表示から、あなた自身で確認できます。あなたは、どっちがどっちか推測できるはずです！

DSPLY  Found 3285 - Missing 6715 - Time = 1.797 sec

DSPLY  Found 3148 - Missing 6852 - Time = .017 sec

疑問に思われるといけないので念のため書き添えますが、私達は%Timestamp（）を使用してFORループの直前と直後の時間を取得し、%Diffを使用して両者の間の秒数を計算して時間計測をしました。

配列サイズが大きければ大きいほど、速度差はより劇的になります。たとえば、配列のサイズを10,000要素に倍増すると、従来の線形方式の経過時間は約2倍になります。しかし、高速検索の時間は大きな変化は見られません。どうやってこれが可能になるのでしょうか？

答えは実に簡単です。Ascend／Descendキーワードで有効にされている高速検索は、“二分割”技法を使用して実装されています。このアプローチでは、最初の比較は配列の中間の要素に対して行われます。一致しない場合、配列は2つの部分に“分割”され、次に、要求された値が配列の下側または上側の部分に（潜在的に）あるかどうかを判断するためにテストが行われます。どちらの部分が選択されても、続けて同じプロセスが適用されます。つまり、配列の選択された部分の中間点が次の比較位置になります。この例で配列のサイズを2倍にしても、時間にほとんど影響がないと皆さんが理解できることを望みます。最初の“分割”は、配列のスコープを元のサイズに戻します。ですから、必要な追加操作の数は線形検索への影響に比べて極めて小さくなります。

もちろん、この性能にはコストがかかりますが幸いにもそれは僅かです。“二分割”技法が機能するためには、配列は格納している値の順番に並んでいなければならないので、検索の開始前にソートされなければなりません。その要件が速度差を帳消しにするのではと思われるといけないので、SORTAを時間計測ループに組み込んだときでも高速ソートはまだ60〜70倍速いことを指摘しておきます。

ならば、スピードの利点を考慮して、順番に並べられた配列だけを検索するよう常に努力するべきでしょうか？答えは、いつものように“場合によりけり”ということです。ほとんどの場合、少なくとも大規模な配列や非常に多くの検索反復では、答えは“はい”になります。たとえば、夜間バッチ処理時間を大幅に削減する必要があるお客様と一度仕事をしたケースでは、すべての顧客および製品コードを配列にロードするアプローチを使いました。データをロードした後の検証は、従来のCHAIN / SETLLアプローチではなく、それらの配列上で検索を実行しました。それはSETOBJACCまたはSQLを使用した場合のパフォーマンスを大幅に上回りました。

しかし、それを試さずに選択肢を評価することがもっと難しい状況があります。たとえば、一連のトランザクションの処理中に、さらに処理が必要な顧客のリストを作成し、重複項目を避ける必要があるとします。 1つのアプローチは、検索を行って顧客が配列に既に存在するかどうかを調べ、存在しなければそれを後ろに追加することです。順番に並んでいないにもかかわらず、もしその顧客が後で現れても線形検索はやはりその項目を見つけるだろうという理由で、古い線形検索アプローチを使用するのが唯一の方法です。このアプローチの問題は、新しい項目が追加される度に検索が遅くなることです。多数の顧客が処理されている場合、これは問題を引き起こす可能性があります。

しかし、高速アプローチをとると、新たに追加する度に配列を再ソートする必要が潜在的にあります。私達が有意義に適用できる唯一の短絡ロジックは、新規顧客の値が現在の最大の顧客の値より大きいかどうかをチェックし、そうであればソートを省略することです。まあ、こんなところです。このような状況では、追加のソート要件によって速度の利点の多くのが使い尽くされてしまう可能性があります。それはすべてどれくらいの数の顧客が処理されているか、そしてどれくらいの頻度で重複が生じるかに掛かっています。

このように動的に配列を構築する場合、あるいは単に配列にデータを格納して使用する場合でさえも、配列が完全にはデータで満たされていない状況に対処する必要があります。前述のように、1つの方法は、未使用の要素が常に最後までソートされるように、配列にハイバリューを事前に設定しておくことです。しかし、それは旧式のRPGの考え方であり、最近ではもっと良い選択肢があります。

部分的にデータの詰まった配列の処理

ここで使用している例題の文脈内では、部分的にデータが格納された配列の処理を支援するRPGに2つの機能があります。

まず1つ目として、組み込み関数%SubArrがあります。これは、以下に示す（L）のコード例のように配列名の代りに指定することができ、ここではSORTAの動作を配列の有効な要素に限定する効果があります。最初のパラメーター（valueArry）は配列名を指定し、2番目のパラメーター（1）は使用する範囲の最初の要素を指定し、3番目のパラメーター（count）は範囲に含める要素の数を指定します。これは、処理中に配列が動的にロードされる場合に特に便利です。

が動的にロードされる場合に特に便利です。
    // valueArray内のアクティブな要素をソート  
(L) SortA %SubArr( valueArray: 1: count ); 

(M)   location = 
       %LookUp( searchFor: valueArray: 1: count );

2つ目の有用な機能は、%LookUpによって検索される要素の範囲を制限するオプションです。これは、オプションの第3および第4のパラメーターを指定することで行われます。（M）の例では、第3のパラメーター（1）は検索される最初の要素の番号を指定し、第4パラメーターの（count）は検索される要素の数を指定します。

私達のWebサイトからこの記事に付随するコードをダウンロードすると、プログラムARRAYS3の中にこの例があります。上記のコード行はここから採られたものです。また、私達はロードされる要素の数を指定する機能も追加しました。

まとめ

このシリーズの次の記事では、グループフィールドを使用して配列を定義する方法、検索時のデータ構造配列の使い方と制限事項、代替ソートと検索ストラテジーについて説明するつもりです。