1

これを行うためのより速い方法はありますか？

    Vector3* points = malloc(maxBufferCount*sizeof(Vector3));
    //put content into the buffer and increment bufferCount        
    ...

    // remove one point at index `removeIndex`
    bufferCount--;
    for (int j=removeIndex; j<bufferCount; j++) {
        points[j] = points[j+1];
    }

私は非常に頻繁に要素を削除する巨大なバッファを持っているので、私は尋ねています。

4

3 に答える 3

5

いいえ、申し訳ありません。配列の途中から要素を削除するには時間がかかりO(n)ます。本当に要素を頻繁に変更したい場合（つまり、特定のアイテムを削除したり、他のアイテムを追加したりする場合）は、代わりにリンクリストを使用してください。対照的に、配列のルックアップ時間は一定ですが、リンクリストは線形時間でアクセス（読み取り）できます。したがって、より頻繁に行うこと（読み取りまたは書き込み）を決定し、その決定に基づいて適切なデータ構造を選択します。

ただし、私は（親切に）あなたが時期尚早の最適化の罪を犯そうとしていないと仮定したことに注意してください。これがボトルネックであることをベンチマークしていない場合は、おそらく心配する必要はありません。

于 2013-02-26T20:56:49.670 に答える
3

ボトルネックであることがわかっていない限り、コンパイラに最適化させることができますが、試してみることができますmemmove。

ここで選択された答えはかなり包括的です：strncpyまたはmemmoveをいつ使用するのですか？

説明はここにあります：http ：//www.kernel.org/doc/man-pages/online/pages/man3/memmove.3.html

于 2013-02-26T21:01:10.353 に答える
2

言うべきいくつかのこと。memmove関数はおそらくあなたよりも速くコピーします。多くの場合、インラインアセンブラなしでC言語で利用できる特別な命令を使用するように、特定のコンパイラの作成者によって最適化されます。これらの命令はSIMD命令（単一命令複数データ）と呼ばれていると思いますか？私が間違っている場合、誰かが私を訂正します。

削除するアイテムを保存できる場合は、削除するアイテムのリストを並べ替えてから、シングルパスを実行することで最適化できます。難しいことではありませんが、面白い計算が必要です。

また、各アイテムをリンクリストに保存することもできます。アイテムを削除するのは簡単ですが、配列へのランダムなアクセスが失われます。

最後に、配列と同じサイズのポインターの追加配列を作成できます。各ポインターは要素を指します。次に、二重間接参照を介して配列にアクセスしたり、ポインターを交換して配列を並べ替えたり、ポインターをNULLにすることでアイテムを削除したりできます。

これがあなたにいくつかのアイデアを与えることを願っています。通常、物事を最適化する方法がありますが、その後、よりアプリケーション固有になります。

于 2013-02-26T21:20:51.783 に答える