近接マップソート

近接マップソート

proxmap 中のバケットへの挿入ソート。 乱数のリストをソートする挿入ソートの例。
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(n^{2})}$
最高の パフォーマンス	${\displaystyle O(n)}$
平均的な パフォーマンス	${\displaystyle O(n)}$
最悪の場合の 空間複雑度	${\displaystyle O(n)}$

要素はビンに分配される

全てのバケットが満たされた後にソートするバケットソートとは異なり、要素は挿入されるときに挿入ソートされる。

ProxmapSort（またはProxmap sort ）は、データ項目（キー）の配列を複数の「サブ配列」（同様のソートではバケットと呼ばれる）に分割するソートアルゴリズムです。この名前は、「近接マップ」を計算することの略で、各キー K について、最終的なソート順序で K が配置されるサブ配列の先頭を示します。キーは、挿入ソートを使用して各サブ配列に配置されます。キーがサブ配列間で「適切に分散」されている場合、ソートは線形時間で実行されます。計算の複雑さの見積もりには、サブ配列の数と、使用される近接マッピング関数（「マップキー」）が含まれます。これは、バケットソートと基数ソートの一種です。

ProxmapSort が完了すると、ソート中にキーが適切に分散されていた場合、 ProxmapSearch を使用して、ソートされた配列内のキーを時間内に見つけることができます。${\displaystyle O(1)}$

どちらのアルゴリズムも、1980 年代後半にカリフォルニア大学アーバイン校のトーマス A. スタンディッシュ教授によって発明されました。

概要

基本戦略

一般的には、 n個のキー を持つ配列Aがあるとします。

• マップキー関数を各配列項目に適用して、目的の配列A2のサブ配列にキーをマップします。
• 「ヒット数」の配列Hを使用して、同じサブ配列にマップされるキーの数を決定します。
• 各バケットが、それにマッピングされるすべてのキーを保持するのにちょうどよいサイズになるように、各サブ配列が宛先配列のどこから始まるかを決定する。これには「プロキシマップ」の配列Pを使用する。
• 各キーについて、「場所」の配列Lを使用して、マップされるサブ配列を計算します。
• 各キーについて、その位置を調べ、A2の該当セルに配置します。その位置にあるキーと既に衝突する場合は、挿入ソートを行い、このキーよりも大きいキーを1つ右に移動して、このキーのためのスペースを確保します。サブ配列は、マッピングされているすべてのキーを格納できるほどの大きさであるため、このような移動によってキーが次のサブ配列にオーバーフローすることはありません。

簡略版: n個のキー を持つ配列Aが与えられた場合

1. 初期化: nサイズの 2 つの配列( hitCount、proxMap )と、 A .lengthの 2 つの配列( location、A2 )を作成して初期化します。
2. パーティション: 慎重に選択されたmapKey関数を使用して、A2をAのキーを使用してサブ配列に分割します。
3. 分散: Aを読み取り、各キーをA2のバケットにドロップします。必要に応じて挿入ソートを行います。
4. Collect : サブ配列を順番に参照し、すべての要素を元の配列に戻すか、単にA2 を使用します。

注: 「キー」には他のデータも含まれる場合があります。例えば、キーに加えて学生IDと名前を含むStudentオブジェクトの配列などです。これにより、ProxMapSortはキー自体だけでなく、オブジェクトのグループを整理するのに適しています。

例

n個のキーを持つ完全な配列A [ 0からn-1 ]を考えます。iをAのインデックスとします。Aのキーを同じサイズの 配列A2にソートします。

マップ キー関数は、mapKey(key) = floor(K) として定義されます。

配列テーブル

あ	6.7	5.9	8.4	1.2	7.3	3.7	11.5	1.1	4.8	0.4	10.5	6.1	1.8
H	1	3	0	1	1	1	2	1	1	0	1	1
P	0	1	-9	4	5	6	7	9	10	-9	11	12
L	7	6	10	1	9	4	12	1	5	0	11	7	1
A2	0.4	1.1	1.2	1.8	3.7	4.8	5.9	6.1	6.7	7.3	8.4	10.5	11.5

擬似コード

// ヒット数を計算します。
for i = 0から11 // ここで 11 は n { H [ i ] = 0 ; } for i = 0から12 // ここで 12 は A.length { pos = MapKey ( A [ i ] ); H [ pos ] = H [ pos ] + 1 ; }      

      

      

      
        


runningTotal = 0 ; // 近接マップを計算します – i = 0から11までの各サブ配列の開始位置if H [ i ] = 0 P [ i ] = - 9 ; else P [ i ] = runningTotal ; runningTotal = runningTotal + H [ i ] ;   
     
       
          
    
          
            

i = 0 ～12 の場合// A 内の各項目を配置する A2 内の位置 (サブ配列) を計算しますL [ i ] = P [ MapKey ( A [ i ] ) ] ;      
      

for I = 0 to 12 ; // 項目をソートしますA2 [ I ] = <空> ; for i = 0 to 12 // 順序を維持しながら、各項目を start からサブ配列に挿入します{ start = L [ i ] ; //この項目のサブ配列はこの位置から始まります挿入済み= false ; for j = start to ( < A2の末尾が見つかり、挿入は行われていません> ) { if A2 [ j ] == <空> // サブ配列が空の場合は、項目をサブ配列の最初の位置に配置しますA2 [ j ] = A [ i ] ;挿入済み= true ; else if A [ i ] < A2 [ j ] // キーは A2[j] に属しますint end = j + 1 ; // サブ配列の使用済み部分の末尾を検索します – 最初の <空> はwhile ( A2 [ end ] != <空> ) end ++ ; for k = end - 1 to j // 大きいキーを1つ右のセルへ移動A2 [ k + 1 ] = A2 [ k ] ; A2 [ j ] = A [ i ] ;挿入済み= true ; // 新しいキーを追加} }      
      
      

       
       
                  
    
            
              
               
             
                  
               
                
                   
                  
                  
                
    

ここでAはソート対象の配列であり、 mapKey 関数は使用するサブ配列の数を決定します。例えば、 floor(K) はAのデータから整数と同じ数のサブ配列を単純に割り当てます。キーを定数で割るとサブ配列の数は減ります。A の要素の範囲をサブ配列に変換するには、A～Zの文字を0～25に変換したり、文字列をソートするために最初の文字（0～255）を返したりするなど、様々な関数を使用できます。サブ配列は、バケットソートで一般的に行われるように、すべてのデータがサブ配列に格納された後ではなく、データが入力された順にソートされます。

Proxmap検索

ProxmapSearch は、以前に実行された ProxmapSort によって生成されたproxMap配列を使用して、ソートされた配列A2内のキーを定数時間で検索します。

基本戦略

• ProxmapSortを使用してキーをソートし、MapKey関数とP配列とA2配列を保持します。
• キーを検索するには、そのキーがデータセット内にある場合、キーを含むサブ配列の先頭であるP[MapKey(k)]に移動します。
• サブ配列を順番に検索します。キーが見つかった場合は、それ（および関連情報）を返します。キーよりも大きい値が見つかった場合は、キーはデータセットに存在しません。
• P[MapKey(k)] の計算には時間がかかります。ソート中にキーの分布が良好なマップキーが使用された場合、各サブ配列は定数cで上方に制限されるため、キーを見つけるか、キーが存在しないことを確認するのに必要な比較回数は最大でc回です。したがって、ProxmapSearch は です。最悪のマップキーが使用された場合、すべてのキーが同じサブ配列に存在するため、この最悪のケースでは ProxmapSearch は比較を必要とします。${\displaystyle O(1)}$ ${\displaystyle O(1)}$ ${\displaystyle O(n)}$

擬似コード

関数mapKey(key)は
    floor(key)
を返します。

    proxMap ← 以前に生成されたサイズ n の proxmap 配列
    A2 ← 以前にソートされたサイズnの配列
関数proxmap-search(key)は
    i = proxMap[mapKey(key)]に対してlength (array) − 1を実行し
        、 sortedArray[i].key == keyの場合は
            sortedArray[i]
を返す。

分析

パフォーマンス

H、P、Lの計算にはいずれも時間がかかります。それぞれ配列を1回ずつ処理することで計算され、配列の各位置で一定の時間がかかります。 ${\displaystyle O(n)}$

• 最悪の場合: MapKey はすべての項目を 1 つのサブ配列に配置するため、標準の挿入ソートとなり、時間は になります。${\displaystyle O(n^{2})}$
• 最良のケース：MapKeyは、挿入ソートの最良のケースが発生する順序で、各サブ配列に同じ数のアイテムを配布します。各挿入ソートは、cはサブ配列のサイズです。サブ配列はp個あるため、 p * c = nとなり、挿入フェーズはO(n)かかります。したがって、ProxmapSortは です。${\displaystyle O(c)}$ ${\displaystyle O(n)}$
• 平均的なケース：各サブ配列のサイズは最大でc（定数）です。各サブ配列の挿入ソートは、最悪でも O(c^2) （定数）です。（c 個の項目は最後の項目がバケットに配置されるまでソートされないため、実際の時間ははるかに短くなる可能性があります。）合計時間はバケットの数（n/c） × = です。${\displaystyle O(c^{2})}$ ${\displaystyle O(n)}$

最悪の事態を回避するには、適切なMapKey関数が不可欠です。適切なキーを生成するには、データの分布についてある程度の知識が必要です。

最適化

1. 時間を節約: MapKey(i) の値を保存して、再計算する必要がないようにする (上記のコードのように)
2. スペースを節約: proxmap が計算されるとヒット カウントは必要なくなるため、proxMap は hitCount 配列に格納できます。どの A 値がこれまでにソートされ、どの値がソートされていないかを注意深く記録しておけば、A2 を使用する代わりに、データを A にソートし直すことができます。

JavaScript コードの実装:

Array . prototype . ProxmapSort = function () { //-- 編集日: 2019/11/13 台湾 --// var start = 0 ; var end = this . length ; var A2 = new Array ( end ); var MapKey = new Array ( end ); var hitCount = new Array ( end ); for ( var i = start ; i < end ; i ++ ) { hitCount [ i ] = 0 ; } var min = this [ start ]; var max = this [ start ]; for ( var i = start + 1 ; i < end ; i ++ ) { if ( this [ i ] < min ) { min = this [ i ]; } else { if ( this [ i ] > max ) { max = this [ i ]; }} } //最適化 1.MapKey[i]を保存します。for ( var i = start ; i < end ; i ++ ) { MapKey [ i ] = Math . floor ((( this [ i ] - min ) / ( max - min )) * ( end - 1 )); hitCount [ MapKey [ i ]] ++ ; }  

     
     
      
      
      
  
               
     
     
           
            
             
  
  
           
                  
    
  
  //最適化 2.ProxMaps を hitCount に格納します。
hitCount [ end - 1 ] = end - hitCount [ end - 1 ]; for ( var i = end - 1 ; i > start ; i -- ){ hitCount [ i - 1 ] = hitCount [ i ] - hitCount [ i - 1 ]; } //A[i]=this[i] を A2 の正しい位置に挿入します。var insertIndex = 0 ; var insertStart = 0 ; for ( var i = start ; i < end ; i ++ ) { insertIndex = hitCount [ MapKey [ i ]]; insertStart = insertIndex ; while ( A2 [ insertIndex ] != null ) { insertIndex ++ ; } while ( insertIndex > insertStart && this [ i ] < A2 [ insertIndex - 1 ]) { A2 [ insertIndex ] = A2 [ insertIndex - 1 ]; insertIndex -- ; } A2 [ insertIndex ] = this [ i ]; } for ( var i = start ; i < end ; i ++ ) { this [ i ] = A2 [ i ]; } };      
          
        
  
  
     
     
           
      
      
          
            
        
      
    
      
  
               

他のソートアルゴリズムとの比較

ProxmapSort は比較ソートではないため、Ω( n log n ) の下限は適用できません。^{[引用が必要]その速度は、比較ベースではなく、}バイナリ検索ツリーを使用する場合のように、動的に割り当てられたオブジェクトとポインターの代わりに配列を使用することに起因します。

ProxmapSortはProxmapSearchの使用を可能にします。O(n)の構築時間にもかかわらず、ProxMapSearchは平均アクセス時間でそれを補うため、大規模データベースに非常に魅力的です。データが頻繁に更新される必要がない場合、アクセス時間の観点から、他の非比較ソートベースのソートよりもProxMapSearchの方が有利になる可能性があります。 ${\displaystyle O(1)}$

ProxmapSortに関連する一般的なバケットソート

ProxmapSort と同様に、バケット ソートは一般に、 0 から最大キーまたは値Mまでのn 個の数値入力のリストに対して動作し、値の範囲をサイズM / nのn個のバケットに分割します。各バケットが挿入ソートを使用してソートされる場合、ProxmapSort とバケット ソートは予測どおりの線形時間で実行できることが示されています。^{[1] [独自の研究? ]}ただし、このソートのパフォーマンスはクラスタリング (またはキーが多すぎるのにバケットが少なすぎる) によって低下します。つまり、多くの値が接近して発生する場合、それらはすべて 1 つのバケットに分類され、パフォーマンスが大幅に低下します。この動作は ProxmapSort でも当てはまり、バケットが大きすぎるとパフォーマンスが大幅に低下します。

参考文献

1. Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、2001年、ISBN 0-262-03293-7セクション8.4: バケットソート、pp.174–177。

• Thomas A. Standish著『Javaにおけるデータ構造』 Addison Wesley Longman、1998年、ISBN 0-201-30564-Xセクション10.6、394～405ページ。
• Standish, TA; Jacobson, N. (2005). 「O ( n ) Proxmap SortとO (1) Proxmap Searchを用いたCS2生徒の学習意欲向上（パートI）」. ACM SIGCSE Bulletin . 37 (4). doi :10.1145/1113847.1113874.
• Standish, TA; Jacobson, N. (2006). 「O ( n ) Proxmap SortとO (1) Proxmap Searchを用いたCS2生徒の学習意欲向上（パートII）」ACM SIGCSE Bulletin . 38 (2). doi :10.1145/1138403.1138427.
• Norman Jacobson 著「ProxmapSort と ProxmapSearch の概要」、カリフォルニア大学アーバイン校ドナルド ブレン 情報・コンピュータ サイエンス学部コンピュータサイエンス学科より。

外部リンク

• http://www.cs.uah.edu/~rcoleman/CS221/ソート/ProxMapSort.html
• https://web.archive.org/web/20120712094020/http://www.valdosta.edu/~sfares/cs330/cs3410.a.sorting.1998.fa.html
• https://web.archive.org/web/20120314220616/http://www.cs.uml.edu/~giam/91.102/Demos/ProxMapSort/ProxMapSort.c