「所定の場所に並べる」とはどういう意味ですか?
43948 次
5 に答える
42
インプレース アルゴリズムの考え方は並べ替えに固有のものではありませんが、並べ替えはおそらく最も重要なケースであり、少なくとも最もよく知られているケースです。アイデアは、スペース効率に関するものです。RAM、ハードディスク、またはその他のストレージの最小量を使用して、逃げることができます。これは、ハードウェアがはるかに制限されていた数十年前に特に関連していました。
アイデアは、出力が生成されるまでそのデータを連続的に変換することにより、入力を含む同じメモリ空間で出力を生成することです。これにより、ストレージを 2 倍使用する必要がなくなります。入力用に 1 つの領域を使用し、出力用に同じサイズの領域を使用します。
並べ替えは、アイテムを繰り返し交換することで実行できるため、並べ替えはかなり明白なケースです。並べ替えはアイテムを再配置するだけです。交換は唯一のアプローチではありません。たとえば、 Insertion Sortは、交換の実行と同等ですが、より高速な、わずかに異なるアプローチを使用します。
もう 1 つの例は、行列の転置です。繰り返しますが、これはアイテムを交換することで実装できます。2 つの非常に大きな数の加算は、最下位桁から始めて上に繰り上げることによって、その場で行うこともできます (入力の 1 つを置き換える結果)。
並べ替えに戻ると、「その場で」再配置することの利点は、パンチ カードのスタックを考えるとさらに明白になります。並べ替えるためだけにパンチ カードをコピーすることは避けたほうがよいでしょう。
並べ替えのアルゴリズムには、このスタイルのインプレース操作を許可するものと、許可しないものがあります。
ただし、すべてのアルゴリズムには、作業変数用に追加のストレージが必要です。入力を連続的に変更して出力を生成することが目標である場合、膨大な量のメモリを予約し、それを使用して補助データ構造を生成し、それを使用してそれらの変更をガイドするアルゴリズムを定義するのはかなり簡単です。入力を「その場で」変換することで出力を生成していますが、演習の要点全体を無効にしています-スペース効率が良くありません。
そのため、インプレース定義の通常の定義では、スペース効率の基準を達成する必要があります。入力に比例した余分なスペース (つまり、O(n) 余分なスペース) を使用して、アルゴリズムを「インプレース」と呼ぶことは絶対に受け入れられません。
インプレース アルゴリズムに関するウィキペディアのページでは、現在、インプレース アルゴリズムは一定量 (O(1)) の余分なスペースしか使用できないと主張しています。
コンピューター サイエンスでは、インプレース アルゴリズム (またはラテン語で in situ) は、少量の一定量の余分なストレージ スペースを持つデータ構造を使用して入力を変換するアルゴリズムです。
In Computational Complexityセクションで指定されたいくつかの技術的事項がありますが、結論としては、たとえば Quicksort は O(log n) スペースを必要とする (true) ため、インプレースではありません (これは false だと思います)。
O(log n) はO(n) よりもはるかに小さいです。たとえば、16,777,216 の基数 2 の対数は 24 です。
通常、クイックソートとヒープソートはどちらもインプレースと見なされ、ヒープソートは O(1) の余分なスペースで実装できます (これについては以前に誤解されていました)。Mergesort はインプレースで実装するのがより困難ですが、アウトオブプレース バージョンは非常にキャッシュ フレンドリーです。実際の実装では O(n) スペースのオーバーヘッドが許容されるのではないかと思います。RAM は安価ですが、メモリ帯域幅が大きなボトルネックです。そのため、キャッシュの効率と速度のためにメモリを交換することは、多くの場合、良い取引です。
[編集上記を書いたとき、配列のインプレースマージソートを考えていたと思います。リンクされたリストのインプレース マージ ソートは非常に簡単です。主な違いはマージアルゴリズムにあります-コピーや再割り当てなしで2つのリンクされたリストのマージを行うのは簡単で、より大きな配列の2つのサブアレイで同じことを行います（そしてO（n）補助ストレージなし）AFAIKはそうではありません.]
クイックソートは、インプレースでもキャッシュ効率が高いですが、最悪の場合の動作にアピールすることで、インプレース アルゴリズムとしての資格を失う可能性があります。ランタイムが予想される O(n log n) ではなく O(n^2) である縮退したケース (通常、入力が既にソートされている非ランダム化バージョン) があります。この場合、余分なスペース要件も O(n) に増加します。ただし、大規模なデータセットの場合、いくつかの基本的な予防策 (主にランダム化されたピボット選択) を使用すると、この最悪のケースの動作は非常に起こりにくくなります。
私の個人的な見解では、O(log n) の余分なスペースはインプレース アルゴリズムに許容されます。インプレースで作業するという本来の目的を損なわないため、ごまかしではありません。
ただし、私の意見はもちろん私の意見です。
1 つの追加の注意 - 入力と出力の両方に 1 つのパラメーターがあるという理由だけで、関数をその場で呼び出すことがあります。関数がスペース効率が良い、結果が入力を変換することによって生成された、またはパラメーターがまだ同じメモリ領域を参照しているとは限りません。この使用法は正しくありません (または、処方主義者はそう主張します)。ただし、十分に一般的であるため、注意してストレスを感じないようにするのが最善です。
于 2013-05-16T18:03:03.257 に答える
6
In-place sorting means sorting without any extra space requirement. According to wiki , it says
an in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space.
Quicksort is one example of In-Place Sorting.
于 2013-05-16T10:57:52.820 に答える
4
I don't think these terms are closely related:
Sort in place means to sort an existing list by modifying the element order directly within the list. The opposite is leaving the original list as is and create a new list with the elements in order.
Natural ordering is a term that describes how complete objects can somehow be ordered. You can for instance say that 0 is lower that 1 (natural ordering for integers) or that A is before B in alphabetical order (natural ordering for strings). You can hardly say though that Bob is greater or lower than Alice in general as it heavily depends on specific attributes (alphabetically by name, by age, by income, ...). Therefore there is no natural ordering for people.
于 2013-05-16T10:57:55.953 に答える
0
まったく新しい構造を作成する代わりに、swap 関数を使用して行うことができます。名前を知らなくてもそのアルゴリズムを実装します:D
于 2015-05-16T18:31:55.453 に答える