一次元の若いテーブル
Youngテーブルの次元を無限に移動する前に、背後に残っているものを見てみましょう。 2未満は1つだけです（ゼロはカウントしませんが、ゼロ次元のヤングテーブルはゼロスペースのようなものです-誰もそれが何であるかを知りませんが、美しく聞こえます）。
だから、一次元のヤングテーブル-それは何ですか？ 前のトピックで与えられた定義に従って、それは降順でソートされた単なる1次元配列であり、そのすべての空でないセルはその先頭にあります。
この場合の要素の上昇と下降（若いテーブルの基本操作）は、右から左（上昇）または左から右（下降）のテーブルの線形表示に縮小されます。
def MoveUp(X, i): while i>0 and X[i]>X[i-1]: X[i], X[i-1] = X[i-1], X[i] i -= 1 def MoveDown(X, n): i = 0 while i+1<n and X[i]a>X[i+1]: X[i], X[i-1] = X[i-1], X[i] i += 1
ソートアルゴリズム自体は実際にここで説明されたものと違いはありません。
def YoungSort(X, n): for i in range(1,n): MoveUp(X,i) for i in range(1,n): X[0], X[ni] = X[ni], X[0] MoveDown(X,ni)
注意深い読者は、このソートの最初のサイクルが標準の挿入ソートに過ぎないことに気付くでしょう。 確かに、結果は降順のシーケンスです。 したがって、2番目のサイクルは、このシーケンスのcな逆処理を実行します。 この処理をより効率的に実行できることは明らかですが、現在の目標は、Youngテーブルの概念を任意の次元のケースに一般化しようとすることです。したがって、特定の1つのケース（およびそのような単純なケースでも）の最適化は意味がありません。
一般化された若いテーブル
一般化されたYoungテーブルの定義については、次のようになります。Youngテーブルは、次元dの部分的に順序付けられたほぼ満たされた数値配列です。
半順序性とほぼ完全性のプロパティを決定するために、配列のセル（要素）の最上位の概念を導入します。 いくつかの配列セルをインデックスi 1 、i 2 、...、i dで特徴付けます。 次に、指定されたセルの一番上の隣接セルは、1を除くすべてのインデックスがこのセルのインデックスに等しく、残りのインデックスが指定されたセルの対応するインデックスよりも1だけ小さい任意のセルです。 たとえば、インデックス[1,0,5,3]のセルには、[0,0,5,3]、[1,0,4,3]、および[1,0,5,2]の3つの上位近傍があります。 したがって、セルのすべてのインデックスがゼロ以外の場合、正確にd個の上部近傍があり、すべてのインデックスがゼロの場合、上からの近傍はありません。そのような要素をYoungテーブルの上部と呼びます。
次に、半順序とは、Youngテーブルの任意の要素の値が、このテーブルのすべての上位近傍の値より大きくないことを意味します。
ほとんど塗りつぶされているということは、Youngテーブルのセルが塗りつぶされている（つまり、値が含まれている）場合、その上位のすべてのセルも塗りつぶされることを意味します。
各ディメンションに沿って（1つを除くすべてのインデックスが固定されている場合）、Youngテーブルのセルの値が増加しないシーケンスを形成することを示すのは簡単です。 その結果、テーブルの最大要素は常に最上部に配置されます。
残念なことに、すでに3次元のYoungテーブルの視覚化にはかなりの困難が伴うため、読者は、必要に応じて通常の2次元Youngテーブルの写真で彼（想像力）を助ける多次元の想像力を含めるように求められます。
上昇および下降操作は、明白な方法で一般化されます。 特定の要素が上昇すると、そのすべての隣接要素が上から上に移動し、低い値の隣接要素が見つかった場合、最小のものが選択され、現在の要素で場所が変更され、新しい現在の要素に対してプロセスが続行されます。 すべての上位近傍の値が現在の値より大きい場合、上昇は終了しています。 3次元のYoungテーブルの要素を持ち上げる例が図に示されています（テーブルのフラグメントのみが示されています）。
降下も同様に実行されますが、下からのすべての隣接セル（現在のセルが上部隣接セルであるセル）がソートされ、最大のセルが選択されます。
これらの2つの操作を使用して、テーブルへの新しい要素の挿入とテーブルからの最大要素の削除を実装できます。 そして、挿入と削除の助けを借りて、ソートが簡単に実装されます。 原則として、アセントとディセントの実装は、d次元のテーブルに対しても特別な問題を引き起こすことはありませんが、それにもかかわらず、最初にこれら2つの操作の複雑さを評価しようとします。
d次元のYoungテーブルの各インデックスは0からm-1まで変化すると仮定します。 最悪の場合を考えてみましょう-テーブルは最後まで満たされ（要素数n = m d ）、最後の要素を上げる必要があります（それが（起こった）最大です）。 つまり 上昇の終わりに、この要素はテーブルの最上部になければなりません。 なぜなら 各反復のリフティングプロセス中に、要素インデックスが1つだけ減少し、dm反復の順序を完了する必要があります。 各反復で、1回の交換が実行され、d回以下の比較が行われます（近隣を表示する場合）。 合計で1回のリフティング操作（最悪の場合）では、O（d 2 m）アクションかかります。 これは、このような操作がn回実行されると、すでにO（d 2 mn）アクションかかることを意味します。 n = m dの場合、d次元のYoungテーブルを使用してソートの複雑さの次の推定値を取得します：O（d 2 n 1 + 1 / d ）。
良いニュースは、dの増加に伴い、指数1 + 1 / dが減少することです：2（1次元のヤング表）、1.5（標準のヤング表）、1.33、1.25、1.2など、このすべてのコストの限界で1-本当に超えることができますかクイックソート？！ 悪いニュースは、dが増加すると、所定の次数の前の係数も増加することです。 （微分を使用して）最適な選択はlog 2 nにほぼ等しいパラメーターdであることを示すのは簡単です。 この値を式O（d 2 n 1 + 1 / d ）に代入し、単純な変換後、最終的な推定値O（nlog 2 n）を取得します。つまり、回転はキャンセルされます。 結果の推定値は漸近的に少しですが、最適な線形ロゴよりも悪いです...
若いバイナリテーブル
最良の場合でも、Youngテーブルを使用した並べ替えは漸近的な最適性に達しないことを示しましたが、そのようなテーブルのベストを実装しようとします。 次元d = log 2 nのテーブル。これをバイナリヤングテーブルと呼びます。 このようなテーブルを使用して効果的な並べ替えを整理することはできませんが、それでも、誰かが便利なアプリケーションを見つけることができる可能性があります。 そして何よりも、バイナリYoungテーブルを実装することは、優れたプログラミング演習です。
最初に、バイナリYoungテーブルの概念を形式化します。 各インデックスが0と1の2つの値のみを取ることができる次元dのバイナリYoungテーブルを呼び出します。このようなテーブルの容量をnで表すと、n = 2 dまたはd = log 2 nになります。 d値が小さい場合のこのようなテーブルの例を次の図に示します。 そう、目の肥えた読者は言うだろうが、これらは次元dの超立方体だ！ そして彼は絶対に正しいでしょう。
次に、メモリ内の多次元配列の標準レイアウトを使用して、このようなハイパーキューブを線形配列に拡張します。最も低いインデックスが最もすばやく変更されます。 たとえば、前の図の次元d = 3のテーブルを考えます。
私たちが見ているもの-インデックスは、2進数システムで数値として解釈され、0、1、2、3などのシーケンスを形成します。 つまり、バイナリヤングテーブルのセルの座標を線形化テーブルの同じセルの座標に変換するための簡単なアルゴリズムを得ました。 まあ、私たちはビットを扱う方法を知っています！ できるようです...
Youngテーブルの重要な概念は、上位セルと下位セルの隣接です。 バイナリYoungテーブルに関して、これらの概念は次のように定義されます：インデックスi（線形化されたテーブル）のセルは、iのビット表現がjのビット表現と一致する場合、インデックスjのセルの上位隣接セルと呼ばれます。単位、およびi-ゼロ。 したがって、この定義のセルjはセルiの下位になります。 たとえば、セル番号6 = 110 2はセル番号7 = 111 2の上位隣接であり、セル番号2 = 010 2の下位隣接です。
要素の高度と下降
上昇および下降操作は、一般化されたテーブルに対して上記で定義されたのとまったく同じ方法で定義されます。 バイナリテーブルにこれらの操作を実装するには、上隣と下隣の決定が行われたため、特定の整数のすべてのユニット（上）またはゼロ（下）ビットを列挙するための効果的なアルゴリズムが必要です。 特に、この方向で考えるのが面倒な人のために、ヘンリー・ウォーレンによる素晴らしい本「プログラマーのためのアルゴリズムのトリック」があります。 したがって、数値xの右端のビットをゼロにするために、操作x＆（x-1）が使用されます。 右のゼロから最後の1つを置き換えるには、同様の操作x |（x + 1）が使用されます。 これらの操作（およびタンバリンとのいくつかのダンス）は、指定された整数のすべてのユニット（ゼロ）の列挙を整理するのに十分です。
実装
以下は、ベクトルXで表されるバイナリYoungテーブルの要素を上げ下げする操作の実装です。
def MoveUp(X, i): while True: t = i j = i while j: # i k = j-1 l = k&i if X[t]>X[l]: t = l # j = k&j if i==t: return # X[i], X[t] = X[t], X[i] # i = t
降下中、隣接ノードは番号の昇順で並べ替えられるため、最初の空の隣接ノード（テーブルサイズより大きい番号を持つ）が検出されると、検索は終了します。
def MoveDown(X, n): i = 0 while True: t = i j = i while True: # k = j+1 l = k|i if l>=n: break # - if X[t]<X[l]: t = l # j = k|j if i==t: return # X[i], X[t] = X[t], X[i] i = t
ソート自体は、すでに標準的なスキームに従って実行されます。
def YoungTableauSort(X, n): for i in range(1,n): # MoveUp(X,i) for i in range(1,n): # X[0], X[ni] = X[ni], X[0] MoveDown(X,ni)
結論の代わりに
それで、私たちは何を達成しましたか？ 特別なものは何もないと誰かが言うだろうし、彼自身のやり方で正しいだろう。 ソートは明らかに最適には達しません。たとえば、同様の原理に基づいて配置されたピラミッド型ソートは失われます。 同じ理由で、バイナリヤングテーブルに基づく優先度を持つADTキューの実装は、ピラミッドを使用した同様の実装よりも劣ります。 さらに、標準テーブルからバイナリテーブルへの移行が停止しました。おそらく、ピラミッドに対するヤングテーブルの唯一の利点は、任意の要素の検索です。 2次元テーブルでは、このような検索はO（n 1/2 ）時間で実行されますが、バイナリテーブルでは、任意の値の検索にはテーブル全体のほぼ完全な列挙が必要になります。 n時間で線形。 一方、彼らが言うように、リスクを冒さない人は、彼はシャンパンを飲みません。 私たちは新しいソートアルゴリズムを考案しようとしましたが、成功しました。 はい、そのようなまれなパフォーマンスO（nlog 2 n）で！ それでも、このような美しいデータ構造には、読者の一部がおそらく発見できる興味深い有用なプロパティを単に持たなければならないという希望があります。 ご清聴ありがとうございました！
参照：
- Kormen T. et al。-アルゴリズム。 建設と分析、2009
- フルトン・W-ヤングテーブル、2006
- Warren G.-プログラマ向けアルゴリズムトリック、2004
PS：ところで、私は上記のすべてが誰かによってかつて公然と開かれたという考えを完全に認めています。 誰かがこの種の情報を持っていて、彼がそれを共有する準備ができているなら、私は非常に感謝します！