27

2 つの質問があります。

  1. 各要素を反復するよりも速い方法で、配列内のエントリを別の配列にコピーしrealloc()ますか? 答えが「はい」の場合、その複雑さは何だと思いますか?memcpy()O(N)

  2. 割り当てられたサイズが元のサイズよりも小さい場合、realloc()エントリを別の場所にコピーするか、配列のサイズを縮小しているためそのままにしますか?

4

8 に答える 8

21

1 - いいえ。一度にブロックをコピーします。非常に優れた分析については、http://www.embedded.com/design/configurable-systems/4024961/Optimizing-Memcpy-improves-speedを参照してください。

2 - これは実装に依存します。glibc の詳細については、http: //www.gnu.org/software/libtool/manual/libc/Changing-Block-Size.htmlを参照してください。「いくつかの割り当ての実装では、ブロックを小さくすると、コピーが必要になる場合があります」

于 2008-12-12T14:28:33.123 に答える
21

andをもう少し詳しく見てみましょうmemcpy。さらに、「ビッグ オー」またはランダウ記法を見てみましょう。

まずはビッグオー。他の場所で話したように、大きな O の定義を覚えておく価値があります。これは、g ( n ) ≤ kf(n) . 定数の機能は、重要な部分を優先して細部を無視できるようにすることです。誰もが指摘したように、ほとんどの通常のアーキテクチャではnバイトはO(n)になります。なぜなら、それらのnバイトを一度に 1 チャンクずつ移動する必要があるからです。したがって、C での最初の素朴な実装は次のように記述できます。memcpymemcpy

unsigned char *
memcpy(unsigned char * s1, unsigned char * s2, long size){
    long ix;
    for(ix=0; ix < size; ix++)
        s1[ix] = s2[ix];
    return s1;
}

これは実際にはO(n)であり、なぜライブラリ ルーチンをわざわざ使用するのか不思議に思うかもしれません。ただし、libc関数に関する問題は、それらがプラットフォーム固有のユーティリティを作成する場所であるということです。アーキテクチャを最適化したい場合は、これを実行できる場所の 1 つです。したがって、アーキテクチャによっては、より効率的な実装オプションがある場合があります。たとえば、IBM 360 アーキテクチャーには、MOVL非常に高度に最適化されたマイクロコードを使用してデータを大きなチャンクで移動する命令があります。したがって、そのループの代わりに、memcpy の 360 実装は次のようになります。

LR 3,S1      LOAD S1 ADDR in Register 3
LR 4,S2      
MOVL 3,4,SIZE

(ちなみに、それが正確に正しい 360 コードであるという保証はありませんが、説明には役立ちます。) この実装は、C コードのようにループを nステップ実行する代わりに、3 つの命令を実行するだけのように見えます。

ただし、実際には、 O(n) 個のマイクロ命令が内部で実行されています。2 つの違いは定数kです。マイクロコードははるかに高速で、命令のデコード手順が 3 つしかないため、単純なバージョンよりも劇的に高速ですが、それでもO(n)です。定数が小さいだけです。

漸近的に高速というわけではありませんが、実装はその特定のアーキテクチャでmemcpy誰かが実現できるのと同じくらい高速です。

于 2008-12-27T04:19:34.363 に答える
5
  1. N 個のアイテムを O(N) より速くコピーする方法は絶対にありません。ただし、一度に複数のアイテムをコピーしたり、特別なプロセッサ命令を使用したりできる可能性があるため、自分で行うよりも高速になる可能性があります.
  2. 確かなことはわかりませんが、メモリは完全に再割り当てされていると思います。これは最も安全な仮定であり、とにかく実装に依存する可能性があります。
于 2008-12-12T14:02:16.390 に答える
5

  1. のパフォーマンスはmemcpy実際には O(N) よりも優れているわけではありませんが、手動コピーよりも優れたパフォーマンスが得られるように最適化できます。たとえば、1 バイトをコピーするのにかかる時間で 4 バイトをコピーできる場合があります。多くのmemcpy実装は、一度に複数の要素をコピーできる最適化された命令を使用してアセンブリで記述されます。これは通常、一度に 1 バイトずつデータをコピーするよりも高速です。

  2. 私はこの質問をよく理解していません。reallocメモリのサイズを減らすために使用し、それが成功した場合 (非 NULL を返す)、新しい場所には古い場所と同じデータが新しい要求のサイズまで含まれます。呼び出しの結果としてメモリの場所が変更されたrealloc場合 (サイズを縮小する場合は通常ではありません)、内容がコピーされます。それ以外の場合は、メモリが移動していないため、コピーを行う必要はありません。

于 2008-12-12T14:04:23.733 に答える
2
  1. memcpy は、大量のビットを移動するように記述できると推測できます。たとえば、有利な場合は、SSE 命令を使用してデータをコピーすることは完全に可能です。

他の人が言ったように、O(n) よりも高速ではありませんが、メモリ システムには多くの場合、推奨されるブロック サイズがあり、キャッシュ ラインのサイズを一度に書き込むことも可能です。

于 2008-12-17T19:35:38.177 に答える
0

x86には、メモリブロック内のバイト/ワードをスキャンして一致させるための特別な命令と、メモリブロックをコピーするために使用できる特別な命令があります（結局のところCISC cpuです）。インライン アセンブリ言語と関数全体のインライン化を行うプラグマを実装する多くの C コンパイラは、長年にわたってライブラリ関数でこれを利用してきました。

mem コピーに使用するのは、rep 命令に組み合わせた movsb/movsw です。

CMPS/MOVS/SCAS/STOS
REP, REPE, REPNE, REPNZ, REPZ

src/trg アドレスと int カウントを使用してレジスタをセットアップすれば、すぐに使用できます。

于 2008-12-27T05:51:37.720 に答える
0

realloc(dev c++ で確認) に関連するいくつかの重要なポイント: void *realloc(void *ptr, size_t size);

  1. realloc() 関数は、ptr が指すメモリ オブジェクトのサイズを size で指定されたサイズに変更します。

  2. オブジェクトの内容は、新しいサイズと古いサイズの小さい方まで変更されません。

  3. 新しいサイズがより大きい場合、オブジェクトの新しく割り当てられた部分の内容は未規定です。

  4. size が 0 で、ptr がヌル ポインターでない場合、ポイントされているオブジェクトは解放されます。

  5. ptr が NULL ポインターの場合、realloc() は、指定されたサイズの malloc() と同等でなければなりません。

  6. ptr が、calloc()、malloc()、または realloc() によって以前に返されたポインターと一致しない場合、または空間が以前に free() または realloc() の呼び出しによって割り当て解除されている場合、動作は未定義です。

于 2012-02-18T03:13:00.487 に答える
0

あなたがglibcについて話していると仮定すると、あなたの質問は実装に依存しているため、ソースを確認するのがおそらく最善です:

malloc.c

memcpy.c

私がそれを読んだ方法では、答えは次のようになります。

  1. O(N) --- 線形時間以上にアイテムをコピーする方法はありません。
  2. realloc() を使用してそれらを縮小すると、時折大きなアイテムがコピーされます。
于 2008-12-27T02:21:34.960 に答える