SMAS：ソートされたマルチ配列構造-バイナリ検索ツリーの代替

エントリー

こんにちは、habravchane。 これは、SMASデータ構造を共有したい最初の投稿です。 記事の最後に、提案されたデータ構造のクラスであるC ++が提供されます。 実装は再帰的ですが、私の目標はアイデアを伝えることです。 2番目は、非再帰バージョンの実装です。 意見を「聞く」ことが重要です。

ツリーの何が問題になっていますか？

はい、 それで記事を完成させることができます。ありがとうございます。 左右のサブツリーへのリンクという形で補助データのメモリオーバーヘッドが大幅に増加し、バランス調整のフラグが使用されます（使用される手法-赤黒、AVLなどのツリーによって異なります）。 別の、マイナスではないのは、バランシングのために挿入するときのツリーの絶え間ない変更です（ここでは初心者向けのメソッドの複雑さと複雑さが特に重要です）。 短所はここで終わります。より良く、より普遍的なものを想像するのは困難です（ハッシュテーブル、私見、さらに涼しいが、OH OHこれらの衝突）。

なぜ配列をソートしないのですか？

ソートされた配列のバイナリ検索は、バイナリ検索ツリーと同じ対数複雑度で実装されますが、バイナリ検索ツリーのように、リンクをより小さなサブツリーにドラッグする必要はありません。



しかし、ソートされた配列の何が問題になっていますか？



はい、すべてがそうです、新しい要素を追加する（古い要素を削除する）場合、配列は次のように言うので、そのような配列に要素を追加または削除する必要がない場合にのみ、記事を終了し、バイナリ検索ツリーの代わりにソートされた配列を使用してリソースを節約できます完全に。」 しかし、ソートの問題は、特に最初に他の要素の間に新しい要素を挿入する必要がある場合、時間がかかることです。



しかし、理想的なケースがあります-新しい要素が他の要素よりも大きく、単に最後に追加するだけで十分な場合。 これは理想的です-たった1つの操作ですが、そのような理想的なケースの確率論的評価により、バイナリツリーやハッシュテーブル、または他の非常に美しく独創的なメカニズムを使用せざるを得ません。 確率理論に基づいて、この状況はまれです-すべての要素が昇順で配列に追加される場合のみです（ソートされた入力データが線形複雑性を持つリンクリストに縮退する最悪のケースである場合、バイナリ検索ツリーでの皮肉アナロジー）。

特別な場合、パターンはどうですか？

しかし、1つの要素のみの配列を見てみましょう。 どの値を入力してもかまいません。常にその前の空の配列の先頭に収まり、1要素配列はもちろん常にソートされます。 また、2番目の要素をデータ構造に合わせたい場合はどうでしょうか？ 別の1要素配列を作成し、2つのソートされた1要素配列を取得してみましょう。 2つの並べ替えられた配列から新しい並べ替えられた配列を取得するのは非常に高速ではありませんが、単純なタスクです...しかし、この場合、挿入するたびにではなく、2番目の挿入ごとに配列を並べ替える必要があります。 遅延ソートを使用します。



そして、3つ以上の要素を追加したい場合は？ 欲しいのは有害ではありません -新しい2要素配列をどこかに書き込み、単一要素配列に要素を追加し続けます。また、4番目の要素には2つの2要素ソート配列があります。 死のブルースクリーンがポップアップし、プロセッサーが爆発し、関連するすべての時空 （何かが私を退屈させた） を引き込むブラックホールの形成で爆発するまで、メモリがこれを行うことができるようになるまで。

負荷分散

このアルゴリズムは、通常の配列のソートに比べて、ソートの数をすでに大幅に削減していることは明らかです。なぜなら、配列の最初のレベルは1回、2番目のレベル-4番目の挿入ごと、3番目のレベル-8番目の挿入ごとにソートする必要があるからです。対数の複雑さ。



これを鎮めることはできますが、弱点については、各挿入で負荷を均等に分散させ、「遅延並べ替え」を段階的に補完し、すべてのレベルで次の要素を挿入するときに各ステップを実行します-これにより、すべての挿入で負荷が均等に分散されます。

検索する

検索は、ソートされた配列に対する古典的なバイナリ検索です。唯一の違いは、配列が多数あり、それらすべてを順番に検索する必要があることです。 そのため、検索の対数計算の複雑さが議論されています（間違えなければ、これは対数計算の2倍になります）。 しかし、手元のタスクでは、メモリが節約されていることを考えると、これはまったく問題ありません。

実装

やかんが沸騰している間、私はまだ書きたいと思っていましたが、やかんが沸騰し始め、そのwhiが私が再び書きたいことを忘れさせました...



私の頭にはこの車全体がどのように行くのかという表面的なアイデアしかなかったので、実装は非常に混乱していました-コードはほぼランダムに書かれていたので、悲しみで寝ますが 、同時に、クラスアルゴリズムのプログラム構造には3つのメソッドしか含まれていません（コンストラクタとデストラクタをカウントします）。 コードには、配列、ループ、およびOOPイデオロギーを扱うこと以外には何も含まれていません-狂気の天才へのすべては単純であり、私は理解できると思います。

実際にコード

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <windows.h> #define undefined 2147483648 class ARRAY { private: ARRAY*nextLevel; unsigned int *keyResult, //          - keyLeft, keyRight *keyLeft, //     *keyRight, //     *keyTemp, //     *valResult, //   , *valLeft, //   *valRight, //  *valTemp, //  countResult,countLeft,countRight, //        1  2   0 . len;//  ( 0-  2  ) void upd() //       { if(keyResult) { if(countLeft<len) { if(countRight<len) { if(keyLeft[countLeft]<keyRight[countRight])//   1-   2- -   { keyResult[countResult]=keyLeft[countLeft]; valResult[countResult]=valLeft[countLeft]; countResult++; countLeft++; } else//   2-   1- -      { keyResult[countResult]=keyRight[countRight]; valResult[countResult]=valRight[countRight]; countResult++; countRight++; } } else // 2-        .     { keyResult[countResult]=keyLeft[countLeft]; valResult[countResult]=valLeft[countLeft]; countResult++; countLeft++; } } else { if(countRight<len) // 1-     -  .     { keyResult[countResult]=keyRight[countRight]; valResult[countResult]=valRight[countRight]; countResult++; countRight++; } //           -    } if(countResult==len*2) //      { if(!nextLevel)nextLevel=new ARRAY; // . ,      nextLevel->set(keyResult,valResult,len*2); keyResult=NULL; keyLeft=NULL; keyRight=NULL; keyTemp=NULL; valResult=NULL; valLeft=NULL; valRight=NULL; valTemp=NULL; } } if(nextLevel)nextLevel->upd(); } void set(unsigned int*Key,unsigned int*Val,unsigned int Len) { len=Len; if(!keyTemp){keyTemp=Key;valTemp=Val;} else { keyLeft=Key; valLeft=Val; keyRight=keyTemp; valRight=valTemp; keyTemp=NULL; valTemp=NULL; countResult=0; countLeft=0; countRight=0; keyResult=new unsigned int[len*2]; valResult=new unsigned int[len*2]; } upd(); } public: ~ARRAY() { if(keyResult)delete[]keyResult; if(keyLeft)delete[]keyLeft; if(keyRight)delete[]keyRight; if(keyTemp)delete[]keyTemp; if(valResult)delete[]valResult; if(valLeft)delete[]valLeft; if(valRight)delete[]valRight; if(valTemp)delete[]valTemp; if(nextLevel)delete nextLevel; } ARRAY() { keyResult=NULL; keyLeft=NULL; keyRight=NULL; keyTemp=NULL; valResult=NULL; valLeft=NULL; valRight=NULL; valTemp=NULL; countResult=0; countLeft=0; countRight=0; len=0; nextLevel=NULL; } void set(unsigned int Key,unsigned int Val) { unsigned int*k=new unsigned int[1];k[0]=Key; unsigned int*v=new unsigned int[1];v[0]=Val; set(k,v,1); } unsigned int get(unsigned int Key) { unsigned int l,r,i; if(keyTemp) { l=0;r=len; while(l!=r-1) { i=(l+r)/2; if(keyTemp[i]<Key)l=i; else if(keyTemp[i]>Key)r=i; else return valTemp[i]; } if(keyTemp[l]==Key)return valTemp[l]; } if(keyLeft) { l=0;r=len; while(l!=r-1) { i=(l+r)/2; if(keyLeft[i]<Key)l=i; else if(keyLeft[i]>Key)r=i; else return valLeft[i]; } if(keyLeft[l]==Key)return valLeft[l]; } if(keyRight) { l=0;r=len; while(l!=r-1) { i=(l+r)/2; if(keyRight[i]<Key)l=i; else if(keyRight[i]>Key)r=i; else return valRight[i]; } if(keyRight[l]==Key)return valRight[l]; } if(nextLevel)return nextLevel->get(Key); else return undefined; } }; void main() { ARRAY*arr=new ARRAY; char inp[256]; unsigned int Key,Val; while(gets(inp)&&inp[0]) { if(inp[0]=='+'){Key=atoi(&inp[1]);gets(inp);Val=atoi(inp);arr->set(Key,Val);} else if(inp[0]=='='){Key=atoi(&inp[1]);Val=arr->get(Key);if(Val!=undefined)printf("%d\n",Val);else printf("undefined\n");} else system("cls"); } delete arr; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

PS：

いくつかのエロティックな空想がありますが、アルゴリズムは削除を実装しません。 しかし、これは別の記事です。 ここで、私はアイデアを広めることを賢くしようとしましたが 、誰かが削除の実装について自分の考えを持っているなら、それは良いアイデアです。 実際、この構造は、削除を必要とせず、クイック挿入とクイック検索以外には何も必要としない特定のタスクのために開発されましたが、日常生活でよく必要とされる他の方法を実装することでクラスを洗練したいという要望がありました。いつか。