2

Cに循環型の静的に割り当てられたバッファーがあり、これを幅優先探索のキューとして使用しています。キューの上位N個の要素を並べ替えてもらいたいのですが。通常のqsort（）を使用するのは簡単ですが、循環バッファであり、上位N個の要素がラップアラウンドする可能性があります。もちろん、モジュラー演算を使用し、配列をラップする方法を知っている独自のソート実装を作成することもできますが、ソート関数を作成することは良い演習であると常に考えていましたが、ライブラリに任せたほうがよいでしょう。

私はいくつかのアプローチを考えました：

  1. 別の線形バッファーを使用します。最初に循環バッファーから要素をコピーし、次にqsortを適用してから、コピーして戻します。追加のバッファーを使用するということは、追加のO（N）スペース要件を意味します。
    • qsortを使用して「上」と「下」の半分を並べ替えてから、追加のバッファーを使用してそれらをマージします
    • 2.と同じですが、インプレースで最終的なマージを実行します（インプレースマージについてはあまりわかりませんが、私が見た実装では、スペースの複雑さを軽減する価値はないようです）

一方、25行（またはそれ以上）を追加する代わりに、自分のクイックソートをエレガントに作成しないようにする方法を1時間かけて検討することも、最も生産的ではない可能性があります...

訂正： DFSとBFSを切り替えるという愚かな間違いを犯しました（私はDFSを書くことを好みますが、この特定のケースではBFSを使用する必要があります）。混乱して申し訳ありません。

元の問題の詳細：

私は幅優先探索を実装しています（15パズルと同じように、より複雑で、各状態で4ではなく約O（n ^ 2）の拡張が可能です）。「ブルートフォース」アルゴリズムは実行されますが、「愚か」です。各ポイントで、すべての有効な状態がハードコードされた順序で展開されます。キューは循環バッファ（unsigned queue [MAXLENGTH]）として実装され、整数インデックスを状態テーブルに格納します。インデックスをキューに入れたりデキューしたりする2つの単純な関数を除けば、カプセル化はありません。これは、静的に割り当てられた符号なしの単純な配列です。

次に、ヒューリスティックをいくつか追加します。私が最初に試したいのは、拡張後に拡張された子の状態を並べ替えることです（「より良い順序で拡張する」）。これは、単純なベストファーストDFSをプログラミングする場合と同じです。このために、キュー（最新の展開された状態を表す）に参加し、ある種のヒューリスティックを使用してそれらをソートしたいと思います。状態を別の順序で展開することもできます（したがって、この場合、キューのFIFOプロパティを壊してもそれほど重要ではありません）。

私の目標は、 A *、または深さ優先探索ベースのアルゴリズムを実装することではありません（すべての状態を拡張する余裕はありませんが、実装しないと、状態空間での無限サイクルの問題が発生し始めるため、反復深化のようなものを使用する必要があります）。

4

6 に答える 6

5

問題から大きく後退して、全体として解決する必要があると思います。セミソートされた循環バッファがデータを格納するための最良の方法ではない可能性があります。もしそうなら、あなたはすでにコミットされており、要素をソートするためにバッファを書く必要があります-それが外部ライブラリで時折ソートを実行することを意味するのか、要素が挿入されたときにそれを実行するのかはわかりません。 しかし、FIFOとソートされたバッファは根本的に異なるため、結局のところ、それは醜いものになるでしょう。

以前の回答は、ソートライブラリに堅牢で機能が豊富なAPIがあることを前提としています（質問で要求されたように、これは独自のmodソートなどを記述する必要はありません-通常はコールバックを介して、任意の場所にあるデータをサポートするライブラリに依存します関数。ソートがリンクリストをサポートしていない場合、これを処理できません）：

循環バッファは、％（mod）演算を使用してこの問題をすでに解決しています。QSortなどは、メモリ内の場所を気にしません。データを線形にアドレス指定するためのスキームが必要なだけです。

これらは、「実際の」線形非循環配列の場合と同様に、リンクリスト（メモリ内で線形ではない）に対しても機能します。

したがって、100エントリの循環配列があり、上位10を並べ替える必要があり、上位10がたまたま上部で半分に折り返されている場合は、次の2ビットの情報を並べ替えにフィードします。

  • 配列アイテムを見つける関数は（x％100）です
  • ソートするアイテムは95から105の位置にあります

この関数は、並べ替えに使用するアドレスを実際の配列で使用されるインデックスに変換します。配列が境界を超えて並べ替えると奇妙に見えるかもしれませんが、配列がラップアラウンドするという事実は隠されています。限界はありません。％演算子はそれを処理します。配列の一部を1295から1305として参照することもできます。

2^n個の要素を持つ配列を持つためのボーナスポイント。

その他の考慮事項：

線形配列以外のものを並べ替えることができない並べ替えライブラリを使用しているように思われます。そのため、リンクリストや単純な順序以外の配列を並べ替えることはできません。実際には3つの選択肢しかありません。

  • ライブラリをより柔軟に書き直すことができます（つまり、ライブラリを呼び出すときに、比較操作とデータアクセス操作のための関数ポインタのセットをライブラリに与えます）
  • 配列を書き直して、既存のライブラリに何らかの形で適合するようにすることができます
  • 特定のソリューションのカスタムソートを作成できます。

さて、私の部分では、ソートコードを書き直して、より柔軟にしました（または、複製して新しいコピーを編集し、線形配列に対して高速なソートと、非線形配列に対して柔軟なソートを作成します）。

しかし、現実には、現在、ソートライブラリは非常に単純であり、線形に格納されていないデータにアクセスする方法を指示することさえできません。

それがそれほど単純な場合は、ライブラリ自体を特定のニーズに適合させたり、バッファをライブラリに適合させたりすることに躊躇しないでください。

どういうわけかバッファを線形配列に変換し、並べ替えてから元に戻すなど、醜い恨みを試してみるのはまさにそれです。醜い恨みは後で理解して維持する必要があります。FIFOに「侵入」し、内部をいじります。

-アダム

于 2008-11-11T17:11:37.283 に答える
3

あなたがcで求めた解決策を正確に見ていません。次のいずれかのアイデアを検討してください。

  • libcのソースにアクセスできる場合はqsort()、それをコピーして、すべての配列アクセスおよびインデックス コードを適切に一般化された同等のものに置き換えることができます。これにより、下層のソートが効率的でバグがほとんどないというある程度の保証が得られます。もちろん、独自のバグを導入するリスクはありません。Big O は systemqsortに似ていますが、乗数が悪い可能性があります。

  • ソートする領域がバッファのサイズに比べて小さい場合は、ストレート アヘッド リニア ソートを使用して、テスト フォー ラップで呼び出しを保護し、copy-to-linear-buffer-sort-then- を実行できます。必要な場合にのみコピーバック ルーチンを実行します。O(n)(ソートされる領域のサイズに対して) ガードをトリップする場合に追加の操作を導入しn、平均をO(n^2/N) < O(n).

C++ はあなたの選択肢ではないようです。::はぁ:: 他の誰かが使用できる場合に備えて、ここに残しておきます。

  • C++ がオプションの場合は、(必要に応じてバッファーをサブクラス化し、)[]演算子をオーバーロードして、標準の並べ替えアルゴリズムを機能させることができます。繰り返しますが、乗数ペナルティを伴う標準的な並べ替えのように機能するはずです。
于 2008-11-11T18:24:01.070 に答える
2

問題のサブセットがラップアラウンドしなくなるまで、循環キューをローテーションできます。次に、そのサブセットをqsort通常のように渡します。頻繁に並べ替える必要がある場合、または配列要素のサイズが非常に大きい場合、これはコストがかかる可能性があります。ただし、配列要素が他のオブジェクトへの単なるポインターである場合、キューの回転は十分に高速である可能性があります。実際、それらが単なるポインターである場合、最初のアプローチも十分に高速である可能性があります。サブセットの個別の線形コピーを作成し、それを並べ替えて、結果を書き戻します。

于 2008-11-11T18:20:39.627 に答える
2

あなたの問題を解決するために優先キューを適応させることができるかもしれません。

于 2008-11-11T17:22:59.837 に答える
1

最適化に関するルールを知っていますか? それらをグーグルで検索できます（いくつかのバージョンが見つかりますが、ほとんど同じことを言っているので、やめてください）。

テストせずに最適化しているようです。それは大したことではありません。一方、ストレート C を使用しているため、速度にある程度の注意を払う必要がある制限されたプラットフォームを使用している可能性が高いため、最初の 2 つのルールをスキップする必要があると思われます。

最適化のルール:

  1. 最適化しないでください。

  2. 自分が何をしているかわかっている場合は、ルール 1 を参照してください

より高度なルールに移動できます。

最適化のルール (続き):

  1. 特定のレベルのパフォーマンスが必要な仕様がある場合は、最適化されていないコードを記述し、その仕様を満たしているかどうかを確認するテストを記述します。それを満たせば完了です。この時点に到達するまでは、パフォーマンスを考慮してコードを記述しないでください。

  2. ステップ 3 を完了してもコードが仕様を満たしていない場合は、元の「最も明白な」コードをコメントとしてそこに残して再コーディングし、再テストしてください。要件を満たしていない場合は、破棄して最適化されていないコードを使用してください。

  3. 改善によってテストに合格した場合は、テストがコードベースに残って再実行され、元のコードがコメントとしてそこに残っていることを確認してください。

注: それは 3. 4. 5. である必要があります。

さて、最後に--どこかで読んだので、これを言っているのではありません。私は DAYS を費やして、他の人が「最適化」されたためにコード化した恐ろしい混乱を解決しようとしました。

最適化が必要な場合があることは理解しています。私が言っているのは、最適化されていない状態で記述し、テストして再コーディングすることだけです。それほど長くはかからず、最適化されたコードの作成がより簡単になるかもしれません。

私がこれを投稿している唯一の理由は、あなたが書いたほとんどすべての行がパフォーマンスに関係しているためです。次にあなたのコードを見る人が私のような貧弱な人になるのではないかと心配しています.

于 2008-11-11T19:09:01.027 に答える
0

こちらの例のようなものはいかがでしょうか。この例では、多くの余分なメモリを再定義する必要なく、部品または必要なものを簡単に並べ替えることができます。forループには、ステータスビットとカウンターの2つのポインターが必要です。

#define _PRINT_PROGRESS
#define N 10
BYTE buff[N]={4,5,2,1,3,5,8,6,4,3};
BYTE *a = buff;
BYTE *b = buff;
BYTE changed = 0;
int main(void)
{
    BYTE n=0;
    do
    {
        b++;
        changed = 0;
        for(n=0;n<(N-1);n++)
        {
            if(*a > *b)
            {
                *a ^= *b;
                *b ^= *a;
                *a ^= *b;
                changed = 1;
            }
            a++;
            b++;
        }
        a = buff;
        b = buff;
#ifdef _PRINT_PROGRESS
        for(n=0;n<N;n++)
            printf("%d",buff[n]);
        printf("\n");
    }
#endif
    while(changed);
    system( "pause" );
}
于 2008-11-13T22:32:31.590 に答える