Geekly Articles each Day

ABCソート


この種のビット単位のMSDソートは 、文字列に対して「シャープ」です。 ただし、字句の専門化のためにアルゴリズムの名前はそれほど付けられていません。 著者のAllen Beechickは自分の名前を選んだ。ABCsortはAllen Beechick Character sortの略である。

ビチク自身は、プログラマーであるだけでなく、神学の達人でもあるという点で注目に値します。 分類されていないデータの整理に関する懸念は、世俗的な職業の枠組み内でのみ彼に興味を持っています。 はるかに尊敬されている神学者は、真の信者の昇天と他の皆の最後の審判の前夜に、現代社会の混乱の中で秩序を回復することを懸念しています。

アルゴリズムに関しては、これは私が知っている唯一の種類であり、その使用には発明者がお金を必要とします。


スカージ



保守的なバプテスト、 禁欲の熱烈な反対者。 プロテスタントの異端は30年前にアレンによって彼の絶え間ないベストセラーの本、 大 Tri難の前のアセンションに押しつぶされた（1999年に再版された試練前の携挙）。 私たちのヒーローの長年の宗教研究の結果は、「 アセンションの解決策- パズルをまとめる 」という本です（「 ラプチャーソリューション、パズルをまとめる 」）。

メリット


著者はアルゴリズムを賞賛するのが大好きで、選別サイト（Webアーカイブ）に隠されていない喜びを持っている彼は、多くの利点をリストしています。



一般的に、上記のすべてが当てはまります。 確かに、比較、交換、およびサポート要素の代わりに、より単純に言うことができます-これは分布によるソートです。 まあ、「記憶の経済」についても議論することができます（しかし、それについては後で詳しく説明します）。

並べ替えのさらに優れた点-従来のMSD基数並べ替えとは異なり、すべての桁で並べ替えられるわけではありません。 リストがソートされるとすぐにプロセスが停止し、すべての数字が処理されるまで停止しません。 より低いランクによる年功が特別な意味を持たない場合、順序付けを実行する最初のランクの数を指定することもできます。

アルゴリズム


ソートには2つの補助配列が必要です。

それらの1つをワードトラッカー（WT-ワードトラッカー）と呼び、その助けを借りて、 i番目のカテゴリに同じ文字を持つワードをグループ化します。 最初に見つかったこのような単語については、値0がリストに入力され、 i番目の数字が同じ文字である後続の各単語について、同じ属性に対応する前の単語のインデックスがワードトラッカーでマークされます。



次の表は、単語を最初の文字でグループ化する場合の最初の並べ替え手順を示しています。 ソートプロセス中に、あるカテゴリから別のカテゴリに移行すると、この配列の値が変化し、ある文字で始まり同じ場所にある同じ文字を持つ単語の文字列を反映します。

別の配列は、 文字トラッカー （LT-文字トラッカー）です。 リスト内の最初（または最後）の単語のインデックスをマークします。特定の文字は対応するカテゴリに含まれます。 この単語に基づいて、ワードトラッカーの助けを借りて、 i番目の桁に対応する文字を持つ他のすべてのトークンのチェーンが復元されます。


これで、表には、ある文字で始まるリストの最後の単語のインデックスが表示されます。

与えられた瞬間に、これら2つのテーブルを使用して、たとえば文字「B」で始まるすべての単語を引き出すことができます。 これを行うには、セル値LT [1、b] = 9を使用します。これは、「b」で始まるリストの最後の単語のインデックスです-Beckie。 このワードは、ワードトラッカーのトラック値になりました： WT [9] = 8 。 これは、「b」に関する前の単語のインデックスです-ベリンダ。 値6はセルWT [8]に格納されます。Barbaraはこのインデックスの下にあり、これはBeatrixインデックスを示しています： WT [6] = 3 。 Beatrixのトラック値はゼロです。つまり、それに対して、リストにはBで始まる前の単語が含まれていません。

そのような単語の文字列を作成してトレースし、上位から下位に再帰的に移動することにより、新しいシーケンスが非常に迅速に形成され、アルファベット順にソートされます。 単語を「A」でソートすると、「B」、「C」、アルファベット順にソートされます。


C ++デモコード（著者-Lynn D. Yarbro）
/* ** ABCsort  C **         **   (Allen Beechick)      , **  №5218700. **        . **    : **  .  (Lynn D. Yarbrough) **   (Palm Desert),  **====================================================================== */ #include <malloc.h> #include <stdio.h> #include <stdlib.h> long *RT; /*   */ long **LT; /*   */ void ABCsort (int keys) { /*     */ void process (int, int); long register i, j, recno; int register c; int nodup = noduplicates; long start, step, stop; /*      */ LT = lmatrix(1, keys, alphamin, alphamax); RT = lvector(1, N); /*   : */ for (j = alphamin; j <= alphamax; j++) { for (i = 1; i <= keys; i++) LT[i][j] = 0; } /*    */ if ((keys & 1) ^ nodup) { start = N; stop = 0; step = -1; } else { start = 1; stop = N + 1; step = 1; } /*  1 */ /*      */ for (recno = start; recno != stop; recno += step) { c = GetNextField(recno, 1); RT[recno] = LT[1][c]; LT[1][c] = recno; } /*       . */ process(1, keys); free_lmatrix(LT, 1, keys, alphamin, alphamax); free_lvector(RT, 1, N); } /* ======================================================== */ /*     1- : */ /*  ,       */ void process (int level, int keys) { long i, newlevel, nextrec, recno; int nodup = noduplicates; unsigned char c; /*    */ for (i = alphamin; i <= alphamax; i++) { /*   i-  */ recno = LT[level][i]; LT[level][i] = 0; /*      */ while (recno != 0) { /* i-    ,        */ if (RT[recno] == 0) { PutCurrRecord(recno); recno = 0; continue; } else { /*     i- : */ if (level == keys) { /*      : */ while (recno != 0) { /*       */ PutCurrRecord(recno); recno = RT[recno]; if (nodup) recno = 0; } } else { /*    :*/ /*     */ newlevel = level + 1; while (recno != 0) { nextrec = RT[recno]; c = GetNextField(recno, newlevel); RT[recno] = LT[newlevel][c]; LT[newlevel][c] = recno; recno = nextrec; } /*    */ process(newlevel, keys); } } } } }


アニメーションのYoutubeバージョン




時間の複雑さ


一般的に、平均時間の複雑さO（k * n）について自信を持って話すことができます。ここで、 kは処理されたビットの数です。

集積回路の開発に従事する会社「 ASIC DESIGN＆MARKETING 」は、 PPVM （ ユーザープログラマブルゲートアレイ ）を作成する際にアルゴリズムを実装しました。 同社のエンジニアによると、 ABCsortはQuickSortよりも2.5〜10倍高速です。 これは、このPDFレポートに記載されています。

記憶困難


ソートには、2つの補助配列が必要です。文字トラッカーの2次元は、複雑さを評価するときに無視できます。 また、ワードトラッカー用のn要素の配列。 つまり、追加メモリの総合評価はO（n）です。



価格


アルゴリズムが気に入った場合は、所有者に報酬を支払うことなく、急いで本番環境で実行しないでください。 この方法は特許を取得しており（ 特許のpdfへのリンク ）、その海賊版使用のために、アメリカ正義の罰剣は泥棒に落ちます。

並べ替えの価格は非常に高く、49ドルです。 この金額について、満足した顧客は以下を受け取ります：



上に39個の条件付きユニットをスローすると、C ++のコメント付きソースとともにDLLが返されます。

また、進取的な宗教プログラマーは、 ABCの並べ替えが Quick並べ替えの少なくとも2倍の速度でない場合、無条件にお金を払い戻すとすべての聖人に誓います。

特許について質問がある方のために、アレンビーチックは包括的な回答を提供します。
アルゴリズムをマイクロソフトに販売すべきでしょうか？

試した。 それは私が特許を取得する前でした。 Microsoftの関係者は、これは別の種類のビット単位の並べ替えであるため、特許を取得できないと述べました。 その上、彼女はそれらを印象づけませんでした。 しかし、特許局はアルゴリズムの一意性を認識しました。

アルゴリズムをパブリックドメインに入れてみませんか？

弁理士は理由もなく働きません。 政府機関は無料で特許を付与しません。 ですから、自分のポケットから消費したお金の少なくとも一部を返還するのは良いことです。


アルゴリズムの特徴


役職ABCソート（ABCsort、Allen Beechick Characterソート）;
ビーチックソート
著者アレン・ビーチック
発行年1993
クラス分布ソート
サブクラスビットソート
持続可能性持続可能な
比較比較なし
時間の複雑さ最悪の平均的最高
O（k * n）O（k * n）O（n）
記憶困難O（n）


参照資料


並べ替えサイト（Webアーカイブ）
Lin D. YarbroのC ++での実装（web-archive）
アルゴリズム特許（pdf）
集積回路でのハードウェア実装（pdf）

アレン・ビーチニック


Facebookで
LinkedInで
「アセンションの鍵-パズルを組み立てる」という本のサイト


投票

Source: https://habr.com/ru/post/J201534/

More articles:


All Articles