ソート処理の処理時間を早く、メモリ消費を抑えたい - sort プロシジャ noequals オプション (非安定ソート)

ソート処理の処理時間を早く、メモリ消費を抑えたい - sort プロシジャ noequals オプション (非安定ソート) - SAS

- 7月 16, 2015

mergeステートメントの前処理としてお馴染みの sort プロシジャについて、noequals オプションのご紹介です。

noequals オプションを付けることで、非安定ソートを行うことができます。デフォルトの設定では equals で、安定ソートが設定されています。noequals の最大のメリットは、デフォルトの equals と比べて、CPU時間が短く、メモリが少なくすむことです！

さて、そもそも、安定ソートとはなんでしょう。安定ソートとは、Wikipedia先生から引用しますと、

安定ソート（あんていソート、stable sort）とは、ソート（並び替え）のアルゴリズムのうち、同等なデータのソート前の順序が、ソート後も保存されるものをいう。つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。たとえば、学生番号順に整列済みの学生データを、テストの点数順で安定ソートを用いて並べ替えたとき、ソート後のデータにおいて、同じ点数の学生は学生番号順で並ぶようになっている。安定ソート | Wikipedia

という感じです。ソートする前の並び順が維持されるのが安定ソート。ソートする前の並び順が無視されるのが非安定ソートです。

Wikipedia の例を元にサンプルデータを作ってみます。データは学籍番号順に並んでいます。

学籍番号	点数
001	80
002	90
003	80
004	100
005	90
006	80

上記のサンプルデータを点数で安定ソートしてみます。学籍番号の順番は維持されています。

学籍番号	点数
001	80
003	80
006	80
002	90
005	90
004	100

非安定ソートしてみると、点数の順に並んでいますが、安定ソートと並び順が異なります。(例のために並び順が異なるようにしていますが、一致することもあります。)

学籍番号	点数
001	80
006	80
003	80
005	90
002	90
004	100

proc sort noequals テストコード

SASプログラムで、安定ソートと非安定ソートを試してみましょう。

options lognumberformat msglevel=i fullstimer ;

/* テストデータ */
data TEST ;
  do I=1 to 10000000 ;
    GROUP = int(10 * ranuni(1)) ;
    R = ranuni(1) ;
    output ;
  end ;
run ;

proc sort data=TEST out=TEST_EQUALS equals ;
  by GROUP ;
run ;

proc sort data=TEST out=TEST_NOEQUALS noequals ;
  by GROUP ;
run ;


proc compare data=TEST_EQUALS comp=TEST_NOEQUALS warning ;
run ;

proc compare のログ

元のデータセットが同じで、by ステートメントに指定している変数は同じですが、proc compareから一致していないことがわかります。

 77         proc compare data=TEST_EQUALS comp=TEST_NOEQUALS warning ;
 78         run ;
 
 NOTE: PROCEDURE COMPARE処理(合計処理時間):
 WARNING: 次の2変数の値は不等です: I R 
 WARNING: データセットWORK.TEST_EQUALSとWORK.TEST_NOEQUALSには不等な値があります。
 NOTE: データセットWORK.TEST_EQUALSから10,000,000オブザベーションを読み込みました。 
 NOTE: データセットWORK.TEST_NOEQUALSから10,000,000オブザベーションを読み込みました。

proc sort のログ

proc sort のログを見てみましょう。options fullstimer により、処理の詳細情報がログに出力されています。

 68         proc sort data=TEST out=TEST_EQUALS equals ;
 69           by GROUP ;
 70         run ;
 NOTE: データセットWORK.TESTから10,000,000オブザベーションを読み込みました。 
 NOTE: SASスレッドソートを使用します。
 NOTE: データセットWORK.TEST_EQUALSは10,000,000オブザベーション、3変数です。
 
 NOTE: PROCEDURE SORT処理(合計処理時間):
       処理時間           13.47 秒
       ユーザーCPU時間    6.93 秒
       システムCPU時間    3.86 秒
       メモリ             629791.54k
       OSメモリ           655748.00k
       タイムスタンプ     2015/07/16 午後01:14:01
       ステップ数                        164  スイッチ数  78
       ページフォルト回数                242
       ページリクレーム回数              144621
       ページスワップ回数                0
       自発的コンテキストスイッチ回数    4394
       非自発的コンテキストスイッチ回数  3959
       ブロック入力操作回数              328960
       ブロック出力操作回数              486976
       
 
 71         
 72         proc sort data=TEST out=TEST_NOEQUALS noequals ;
 73           by GROUP ;
 74         run ;
 
 NOTE: SASスレッドソートを使用します。
 NOTE: データセットWORK.TEST_NOEQUALSは10,000,000オブザベーション、3変数です。
 NOTE: PROCEDURE SORT処理(合計処理時間):
       処理時間           9.43 秒
       ユーザーCPU時間    3.85 秒
       システムCPU時間    1.62 秒
       メモリ             474819.42k
       OSメモリ           500756.00k
       タイムスタンプ     2015/07/16 午後01:14:11
       ステップ数                        165  スイッチ数  43
       ページフォルト回数                213
       ページリクレーム回数              96376
       ページスワップ回数                0
       自発的コンテキストスイッチ回数    5416
       非自発的コンテキストスイッチ回数  2263
       ブロック入力操作回数              509080
       ブロック出力操作回数              471848

noequals の方が処理時間が早く、メモリが少ないのが分かるかと思います。

デフォルトの equals よりも処理が早く、消費メモリも少ない noequals ですが、重複行を削除する nodupkey オプションを使用する際には望んだオブザベーションが残るかどうか分かりません。もし nodupkey オプションを利用する場合には注意してください。

参考サイト

COMPAREプロシジャでデータセット間に不一致があった事をログに表示するオプション | SAS忘備録

このブログを検索

data Memorandum ; set Memory ; run ;